二元表达式*与/优先级处理：如何将词法Token转换为对应AST语法树

核心逻辑是通过不同层级的解析函数对应不同优先级的运算符，优先级越高的运算符对应的解析函数调用层级越深，天然保证高优先级运算先被绑定为AST子节点。

前置准备 #

首先定义两个基础配置：

• 运算符优先级表：+/-优先级为1，*//优先级为2，数字越大优先级越高
• 全局指针：用来记录当前遍历到Token序列的位置，初始值为0

核心解析函数设计 #

我们只需要3个函数就能完成需求：

1. parsePrimary() 解析基础单元 #

负责处理优先级最高的语法单元，当前场景下就是直接读取字面量Token，返回Literal节点，指针后移一位。如果后续要支持括号表达式，也可以在这个函数里处理括号嵌套的逻辑。

2. parseTerm() 解析高优先级运算 #

负责处理*、/这一类高优先级的二元运算：

• 首先调用parsePrimary()拿到左节点
• 循环判断当前指针指向的Token是不是*或者/：
  • 如果是，记录当前运算符，指针后移一位
  • 再调用parsePrimary()拿到右节点
  • 把左节点、运算符、右节点拼接为BinaryExpression节点，作为新的左节点
  • 继续循环判断下一个运算符是不是高优先级运算符
• 循环结束后返回最终的左节点

3. parseExpression() 解析低优先级运算 #

负责处理+、-这一类低优先级的二元运算，逻辑和parseTerm完全一致，只是判断的运算符类型换成低优先级的+、-，且获取左右节点时调用的是parseTerm()而不是parsePrimary()：

• 首先调用parseTerm()拿到左节点
• 循环判断当前指针指向的Token是不是+或者-：
  • 如果是，记录当前运算符，指针后移一位
  • 再调用parseTerm()拿到右节点
  • 把左节点、运算符、右节点拼接为BinaryExpression节点，作为新的左节点
  • 继续循环判断下一个运算符是不是低优先级运算符
• 循环结束后返回最终的左节点，就是完整的AST根节点

针对示例Token序列的执行过程 #

Token序列顺序为：1 -> + -> 2 -> * -> 3 -> + -> 4

1. 调用parseExpression()，先调用parseTerm()：
   • parseTerm()调用parsePrimary()拿到{type: "Literal", value: 1}，指针到1，当前Token是+不属于*//，直接返回1作为左节点
2. parseExpression判断当前Token是+，记录运算符，指针到2，调用parseTerm()拿右节点：
   • parseTerm()调用parsePrimary()拿到{type: "Literal", value: 2}，指针到3，当前Token是*属于高优先级运算符
   • 记录运算符*，指针到4，调用parsePrimary()拿到{type: "Literal", value: 3}，指针到5
   • 拼接为BinaryExpression(2 * 3)作为返回值，传给parseExpression作为右节点
3. parseExpression拼接为BinaryExpression(1 + (2*3))作为新的左节点，当前Token是+，属于低优先级运算符
4. 记录运算符+，指针到6，调用parseTerm()拿到{type: "Literal", value: 4}，指针到7，超出Token长度
5. 拼接为最终的BinaryExpression((1+2*3) + 4)，就是要求的AST结构

极简JS实现示例 #

const tokens = [
  { type: "Literal", value: 1 },
  { type: "Operator", value: "+" },
  { type: "Literal", value: 2 },
  { type: "Operator", value: "*" },
  { type: "Literal", value: 3 },
  { type: "Operator", value: "+" },
  { type: "Literal", value: 4 }
];
let index = 0;

function parsePrimary() {
  const token = tokens[index];
  index++;
  return token;
}

function parseTerm() {
  let node = parsePrimary();
  while (index < tokens.length && tokens[index].value.match(/[\*\/]/)) {
    const operator = tokens[index];
    index++;
    const right = parsePrimary();
    node = {
      type: "BinaryExpression",
      left: node,
      operator: operator,
      right: right
    };
  }
  return node;
}

function parseExpression() {
  let node = parseTerm();
  while (index < tokens.length && tokens[index].value.match(/[\+\-]/)) {
    const operator = tokens[index];
    index++;
    const right = parseTerm();
    node = {
      type: "BinaryExpression",
      left: node,
      operator: operator,
      right: right
    };
  }
  return node;
}

const ast = parseExpression();
console.log(JSON.stringify(ast, null, 2));

运行上述代码输出的AST结构和要求的完全一致。

内容的提问来源于stack exchange，提问作者Mora Hutabarat