1.8 解析算术表达式 - 优先级与结合性

优先级「Precedence」

上一节我们已经得到了消除左递归后的算术表达式语法，并根据语法完善了我们的解析程序。现在让我们来试着用我们上一节完成的内容，来解析算术表达式 2 * 3 + 4，我们会得到类似下面的输出：

type: prog
body:
  - type: exprStmt
    value:
      type: binaryExpr
      op: '*'
      left: '2'
      right:
        type: binaryExpr
        op: +
        left: '3'
        right: '4'

我们解析的结果，从现实的数学表达式的角度来看，是存在问题的，因为我们将表达式解析成了：

 node
 / | \
2  * node
    / | \
   3  +  4

上面的结构表示的是 2 * (3 + 4)，而表达式 2 * 3 + 4 的结构应为：

    node
    / | \
 node +  4
 / | \
2  *  3

为了解决这个问题，我们引入和数学上解决该问题类似的概念 - 优先级「Precedence」。优先级表示的是，在一个表达式中，如果同时出现多个运算符，那么具有较高优先级的运算符将先进行预算。

我们通过观察上面 2 * 3 + 4 对应的结构图发现，具有较高优先级的表达式(*)，将作为较低优先级的表达式(+)的操作数，即子节点。而是什么造就了图中的层次结构呢？就是我们的语法，语法规则和其待展开项，经过我们的 Top-Down 解析器的解析，就会体现为父子节点的关系。

依照这个思路，我们可以将具有较高优先级的表达式独立出来、作为新的语法规则，然后将其作为具有较低优先级的语法规则的待展开项。对于四则运算而言，其中的操作符优先级由高到低为：num > "*/" > "+-"，因此我们可以得到：

/* rule1 */
expr ::= expr "+" term
       | expr "-" term
       | term

/* rule2 */
term ::= term "*" factor
       | term "/" factor
       | factor

/* rule3 */
factor ::= num

我们通过三个规则来区分运算符的优先级。rule1 和 rule2 为我们之前所提到的左递归规则。我们拿 rule1 来再次实践如何消除左递归。

回顾我们的左递归消除公式：

A ::= Aα | β
// 消除左递归后
A  ::= βA'
A' ::= αA' | ε
// 将消除后的内容利用 EBNF 语法进一步合并为
A  ::= βα*

根据上面的式子，我们令：

• A = expr

• α = "+" term

• β = term

将得到消除后的结果：

expr ::= term ( ("+" | "-") term )*

rule2 的消除就留给大家来尝试了。上面的算术表达式语法最终为：

expr ::= term ( ( "+" | "-" ) term )*
term ::= factor ( ( "*" | "/" ) factor )*
factor ::= num

根据最终的语法，我们来完善我们的解析器。得益于我们之前的完善工作，现在我们这里只需要向语法解析器中增加3个方法，来对应上面的规则：

parseExpr() {
  let left = this.parseTerm();
  while (true) {
    const op = this.lexer.peek();
    if (op.type !== "+" && op.type !== "-") break;
    this.lexer.next();
    const node = new BinaryExpr();
    node.left = left;
    node.op = op;
    node.right = this.parseTerm();
    left = node;
  }
  return left;
}

parseTerm() {
  let left = this.parseFactor();
  while (true) {
    const op = this.lexer.peek();
    if (op.type !== "*" && op.type !== "/") break;
    this.lexer.next();
    const node = new BinaryExpr();
    node.left = left;
    node.op = op;
    node.right = this.parseFactor();
    left = node;
  }
  return left;
}

parseFactor() {
  return this.parseNum();
}

parseExpr 和 parseTerm 的内容差不多，所以我们理解一下 parseExpr 的实现内容：

1. 首先 let left = this.parseTerm() 对应 expr 规则的最左边第一个非终结符的解析

2. 随后我们进入了 while 循环

3. 在循环中，我们预读下一个 Token 是否为 + 或 -

4. 如果不是，我们就跳出循环，返回 left

5. 如果是 + 或 -，我们就调用 parseTerm 来解析运算符右边的子节点

6. 这样我们就已经得到了一个 BinaryExpr 节点，此时我们将它替换之前的 left 值

7. 跳到第3步继续执行

在循环中，我们将中间每一步得到的节点，都作为下一个即将处理的 BinaryExpr 节点的左边子节点。因此对于表达式 1 + 2 - 3，解析后的结构为：

    node
    / | \
 node -  3
 / | \
1  +  2

也就是说，对于优先级相同的情况，我们采用了和数学中类似的从左往右处理的方式。

我们可以试再着解析问题表达式 2 * 3 + 4，我们会得到下面的输出：

type: prog
body:
  - type: exprStmt
    value:
      type: binaryExpr
      op: +
      left:
        type: binaryExpr
        op: '*'
        left: '2'
        right: '3'
      right: '4'

上面的结果对应下图：

    node
    / | \
 node +  4
 / | \
2  *  3

可见我们的工作已经达到目的了。

结合性「Associativity」

接下来我们来解析一个新的运算符 **，这个运算符就是 JS 中的指数运算符。该运算符含有两个字符，而我们目前的运算符还只是单个字符，除了这点不同之外，它还具有比 */ 运算符更高的优先级。

我们可以打开这个页面 Operator precedence ，这个页面中列出了 JS 中所有的运算符，以及它们的优先级。

在这上述页面中，我们可以发现 ** 运算符的优先级为 15，而 */ 的优先级为 14。因此为了在语法中包含这个运算规则，我们需要将现有的规则修改成如下的形式：

expr ::= term ( ( "+" | "-" ) term )*
term ::= expo ( ( "*" | "/" ) expo )*
expo ::= factor ( "**" factor )*
factor ::= num

只要将现有的实现，修改下面几处，就可以实现对该运算规则的解析。

首先在 Lexer 中修改：

// 增加 Token 类型
TokenType.EXPO = "**";

// 修改 Lexer::isOp 方法，增加 `*`
static isOp(ch) {
  return ["*", "/", "+", "-", "*"].indexOf(ch) !== -1;
}

// 修改 Lexer::readOp 方法，使之可以读取 `**`
readOp() {
  const tok = new Token();
  tok.loc.start = this.getPos();
  tok.type = this.src.read();
  if (tok.type === "*") {
    // 如果当前的字符为 `*`，我们就预读下一个，如果也是 `*` 就读取它
    if (this.src.peek() === "*") {
      this.src.read();
      tok.type = "**";
    }
  }
  tok.loc.end = this.getPos();
  return tok;
}

接着修改 Parser：

parseTerm() {
  let left = this.parseExpo();
  while (true) {
    const op = this.lexer.peek();
    if (op.type !== "*" && op.type !== "/") break;
    this.lexer.next();
    const node = new BinaryExpr();
    node.left = left;
    node.op = op;
    node.right = this.parseExpo();
    left = node;
  }
  return left;
}

parseExpo() {
  let left = this.parseFactor();
  while (true) {
    const op = this.lexer.peek();
    if (op.type !== "**") break;
    this.lexer.next();
    const node = new BinaryExpr();
    node.left = left;
    node.op = op;
    node.right = this.parseFactor();
    left = node;
  }
  return left;
}

我们增加了 parseExpo 方法，并将 parseTerm 中原本调用 parseFactor 的地方替换为 parseExpo，而在 parseExpo 中，我们调用 parseFactor。这些修改都是一一对应了我们的语法规则的变动。

修改完成后，我们试着解析表达式 2 ** 3 ** 4，我们会得到下面的输出：

type: prog
body:
  - type: exprStmt
    value:
      type: binaryExpr
      op: '**'
      left:
        type: binaryExpr
        op: '**'
        left: '2'
        right: '3'
      right: '4'

该输出的结构即为：

    node
    / | \
 node **  4
 / | \
2  **  3

该结构表示的计算等于表达式 (2 ** 3) ** 4。但是我们知道，在 JS 中，表达式 2 ** 3 ** 4 实际上等于 2 ** (3 ** 4)，大家动手试一试。

造成这个结果的原因，就是我们没有正确处理运算符的结合性。当表达式中的运算符具有相同的优先级时，就需要通过结合性来指定计算的先后顺序。

更为具体地来说，对于表达式 a OP b OP c 而言：

• 因为两个 OP 相同，即具有相同的优先级，此时我们需要考虑 OP 的结合性

• 如果 OP 为左结合的，那么 b 将先和左边的 a 一起，执行 OP 运算，运算的结果再和 c 一起，做右边的 OP 运算。

• 如果 OP 为右结合的，那么 b 将先和右边的 c 一起，执行 OP 运算，运算的结果再和 a 一起，做左边的 OP 运算。

比如 a ** b ** c ** d，对应的结构应为：

 node
 / | \
a  ** node
     / | \
    b  **  node
          / | \
         c  ** d

在了解了结合性之后，我们来看如何将 parseExpo 进行修改，以解析具有右结合性的操作符 **。

我们来回顾一下在 1.7 解析算术表达式 - 左递归和其消除法 末尾的测试用例，对于表达式 1 + 2 + 3，我们输出的结果为

type: prog
body:
  - type: exprStmt
    value:
      type: binaryExpr
      op: +
      left: '1'
      right:
        type: binaryExpr
        op: '+'
        left: '2'
        right: '3'

对应的结构就是：

 node
 / | \
1  + node
     / | \
    2  +  3

这个结果其实可以看成是将 + 当做右结合性来解析的结果。为什么能有这样的效果，我们来看当时的语法：

expr  ::= num expr'
expr' ::= ( ( "*" | "/" | "+" | "-" ) expr )*
        | ε

为了解析这样的语法，我们的代码为：

parseExpr() {
  const num = this.parseNum();
  return this.parseExpr1(num);
}

parseNum() {
  const node = new NumLiteral();
  let tok = this.lexer.next();
  assert.ok(tok.type === TokenType.NUMBER, this.makeErrMsg(tok));
  node.loc = tok.loc;
  node.value = tok.value;
  return node;
}

parseExpr1(left) {
  const node = new BinaryExpr();
  node.left = left;
  node.op = this.lexer.peek();
  if (!Lexer.isOp(node.op.type)) return left;
  this.lexer.next();
  assert.ok(Lexer.isOp(node.op.type), this.makeErrMsg(node.op));
  node.right = this.parseExpr();
  return node;
}

我们还一起看了这段代码执行的流程示意图，大家可以结合起来看。这段代码将操作符都处理成右结合性的原因就在于，parseExpr1 方法中，对于右边节点的处理，总是调用 parseExpr：

parseExpr1(left) {
  // ...
  node.right = this.parseExpr();
  return node;
}

而在 parseExpr 内部，它先读取一个操作数，然后将其作为参数继续调用 parseExpr1，在未来某一时刻 parseExpr1 返回时，此前被传入的操作数，成为了返回的节点的左边子节点；这样的间接递归形式，使得所有的操作数都和它右边的操作符结合到了一起，刚好符合了我们需要对右结合性的处理需求。

所以我们可以将我们的 ** 处理方法修改成：

parseExpo() {
  let left = this.parseFactor();
  while (true) {
    const op = this.lexer.peek();
    if (op.type !== "**") break;
    this.lexer.next();
    const node = new BinaryExpr();
    node.left = left;
    node.op = op;
    node.right = this.parseExpo();
    left = node;
  }
  return left;
}

非常简单的修改，只有一行 node.right = this.parseExpo();，我们将原本 parseFactor 换成了 parseExpo。虽然我们这里使用的是直接递归，但是不必担心，我们在 parseExpo 中总是会先读取 factor，从而消耗掉一部分输入，因此不会陷入无限循环。

我们通过一个测试来试一试我们修改后的内容，解析表达式 2 ** 3 ** 4 ** 5。我们可以得到下面的输出：

type: prog
body:
  - type: exprStmt
    value:
      type: binaryExpr
      op: '**'
      left: '2'
      right:
        type: binaryExpr
        op: '**'
        left: '3'
        right:
          type: binaryExpr
          op: '**'
          left: '4'
          right: '5'

再来一个综合型的测试，解析表达式 1 + 2 ** 3 * 5。我们可以得到下面的输出：

type: prog
body:
  - type: exprStmt
    value:
      type: binaryExpr
      op: +
      left: '1'
      right:
        type: binaryExpr
        op: '*'
        left:
          type: binaryExpr
          op: '**'
          left: '2'
          right: '3'
        right: '5'