Press "Enter" to skip to content

【第2405期】你所见过的最简单的AST入门

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

前言

 

:congratulations:各位读者中秋快乐。今日前端早读课文章由快手@Leo投稿分享。

 

@Leo,来自快手音视频中台,非典型程序员,爱代码,爱生活,欢迎交流,更欢迎一起做同事~

 

正文从这开始~~

 

写在前面

 

很多铁子可能一直都在谈AST,但是实际开发过程中对它又不怎幺在乎。就像空气一样,看不见的东西不代表不重要,AST其实隐藏在各种环节中:比如JavaScript引擎的编译,Vue/React的编译,CSS的预处理器,Babel的编译等等,都在使用着AST。

 

AST全称Abstract Syntax Tree,即抽象语法树。但是好像「抽象」这个词也太「抽象」了,说人话就是把代码变成JSON,用这段JSON去描述这段代码干了啥。

 

一段代码的编译过程分为三个重要的步骤:分词、解析、生成可执行代码。下面会通过制作一个简单的计算器去一步一步走完这三个步骤。

 

开始!

 

如果我们要写一个计算器去执行 1 + 2 / 2 * 3 + 2 该怎幺做呢?

 

第一步,我们要把所有的数字和运算符给摘出来,这就是「分词」,也叫「词法分析」;

 

第二步,我们要按照数学规则去把分词的结果变成一段JSON,这就是「编译」,也叫「语法分析」;

 

第三步,我们要把语法树变成可执行的代码去执行;

 

第四步,这就完事了,没有第四步。

 

分词

 

这一步比较简单,先做一下空值检查和去掉空白字符这种前期处理,然后遍历字符串即可,处理逻辑如下:

 

function genTokens (str) {
  if (!/^(\d|\s|\+|\-|\*|\/)+$/.test(str)) { // 空值检查
    throw new Error('请检查输入,只支持数字与四则运算符"+-*/" ')
  }
  const s = str.replace(/\s/g, '') // 去掉所有的空白字符
  let arr = []
  for (let char of s) {
    const len = arr.length
    if (len && !isOperator(arr[len - 1]) && !isOperator(char)) { // 处理两位及以上位数数字,比如10,100
      arr[len - 1] = `${arr[len - 1]}${char}`
      continue
    }
    arr.push(char)
  }
  return arr  // 得到结果 ['1', '+', '2', '/', '2', '*', '3', '+', '2']
}
function isOperator (str) {
  return /[\+\-\*\/]/.test(str)
}

 

通过这一步,我们把1 + 2 / 2 * 3 + 2这个字符串变成了数组[‘1’, ‘+’, ‘2’, ‘/’, ‘2’, ‘*’, ‘3’, ‘+’, ‘2’]

 

编译

 

编译过程也叫语法分析,因为涉及到了语法,这个过程也是相对比较复杂的过程。

 

我们思考下这个1 + 2 / 2 * 3 + 2这个计算公式的语法核心是什幺?其实就是运算符的优先级,乘除的优先级最高,加减的优先级最低。我们需要把分词阶段得到的数组按照运算优先级变成对应的语法树。

 

手画了一下我们期望的语法树:evergreen_tree:如下,这个语法树越往下,优先级越高。

 

 

我们需要遍历分词阶段得到的数组,遇到运算符后比较优先级:

 

优先级更高:在上一个运算符节点下沉一级;

 

优先级相同:在上一个运算符节点上浮一级;

 

优先级更低:要找到最近的,比当前运算符优先级低一级的运算符节点,再上浮一级;

 

备注:为什幺优先级低的运算符要上浮呢?需要结合下文的第三步来看,第三步我们用了深度优先的方式去递归这棵树:evergreen_tree:

 

代码如下,核心函数中用的工具函数放在了下方:

 

function genTree (tokens) {
  let lastOpr = null
  return tokens.reduce((acc, cur, index) => {
    if (index === 0) {
      return {
        value: cur
      }
    }
    if (isOperator(cur)) {
      if (!lastOpr) { // 首个运算符
        acc = {
          operator: cur,
          left: acc
        }
        lastOpr = acc
        return acc
      }
      switch (priorityComparison(cur, lastOpr.operator)) {
        case 1: { // 优先级更高
          const old = lastOpr.right
          lastOpr.right = {
            operator: cur,
            left: old,
            parent: lastOpr
          }
          lastOpr = lastOpr.right
          break
        }
        case -1: { // 优先级更低
          acc = {
            operator: cur,
            left: acc
          }
          lastOpr = acc
          break
        }
        case 0: { // 优先级相同
          if (!lastOpr.parent) { // 在顶部节点
            acc = {
              operator: cur,
              left: acc
            }
            lastOpr = acc
          } else {
            lastOpr.parent.right = {
              operator: cur,
              left: lastOpr,
              parent: lastOpr.parent
            }
            lastOpr = lastOpr.parent.right
          }
        }
      }
    } else {
      if (cur == 0 && lastOpr.operator === '/') { // 兼容0做分母的情况
        throw new Error ('分母不能为0')
      }
      lastOpr.right = {
        value: cur
      }
    }
    return acc
  }, {})
}
function isOperator (str) {
  return /[\+\-\*\/]/.test(str)
}
function priorityComparison (x, y) {
  return weightMap[x] - weightMap[y]
}
const weightMap = {
  '+': 0,
  '-': 0,
  '*': 1,
  '/': 1
}

 

通过这一步,我们得到了我们期望的JSON结构。

 

生成可执行代码

 

这一步就是把编译阶段得到的JSON结构通过递归的方式变成可执行的代码,代码如下:

 

function visitor (node) {
  if (node.operator) {
    return calcValue(visitor(node.left), visitor(node.right), node.operator)
  } else {
    return node.value
  }
}
function calcValue (px, py, rule) {
  const [x, y] = [Number(px), Number(py)]
  switch(rule) {
    case '+': {
      return x + y
    }
    case '-': {
      return x - y
    }
    case '*': {
      return x * y
    }
    case '/': {
      return x / y
    }
  }
}

 

执行完这一步,我们终于得到了1 + 2 / 2 * 3 + 2的运算结果6!

 

写在后面

 

这篇文章是通过一个基础的计算器去模拟AST的过程,让大家有一个入门级的具像的认识。当然上面涉及的算法比较简单,计算器还没有考虑有括号的情况,如果要支持括号,我们第二步的编辑阶段的语法分析的算法要进一步升级,感兴趣的铁子可以自行尝试。

 

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注