# 1.7 解析算术表达式 - 左递归和其消除法

## 算术表达式语法

到目前为止，我们的 hi 语言还是显得有些单薄了。接下来我们将给它添加计算数学表达式的功能。

未来我们在像 hi 语言中增加新的语法功能的时候，都将按照这样的步骤：

1. 增加相应的语法规则，也就是在我们的 EBNF 中增加需要新增的语法规则
2. 根据新增的语法规则，向词法解析器中增加适应新规则的内容
3. 根据新增的语法规则，向语法解析器中增加适应新规则的内容

按照上面的步骤来看，首先我们需要在向语法中增加数学表达式的新规则。我们来看看数学表达式的语法来如何书写：

```
expr ::= expr "*" expr
       | expr "/" expr
       | expr "+" expr
       | expr "-" expr
       | num
```

## 左递归「Left Recursion」

我们先来回顾下，我们对已有的 hi 语言规则是如何进行解析的：

```
prog ::= say_hi*
say_hi ::= HI STRING
HI ::= "hi"
STRING ::= '"' [^"]* '"'
```

我们分别在 Parser 中写了 `parseProg` 和 `parseSayHi` 两个方法，它们分别对应语法中的 `prog` 和 `say_hi` 这两个规则。然后我们根据 `prog` 的语法规则，在 `parseProg` 内部调用了 `parseSayHi`，方法之间的协作方式，完全的参照了语法规则的定义。

再来看一看我们目前得到的数学表达式语法规则，我们立刻按部就班地往 Parser 中添加一个新的 `parseExpr` 方法。

但是问题很快就出现了，我们先看第一个分支：

```
expr ::= expr "*" expr
```

按照规则的定义，我们在 `parseExpr` 内部，需要首先调用 `parseExpr` 方法。很显然，由于这个方法直接调用了自身的同时、内部并没有对需要处理的字符串进行任何步进操作，因此会导致程序陷入无限循环。

对于一个规则而言，如果它右边的规则内容部分、最左边出现的又是自身的规则，我们就称该规则是左递归「Left Recursion」的；并且该规则所属的语法，又被称为是左递归的语法。相似的，如果它右边的规则内容部分、最右边出现的又是自身的规则，我们就称之为右递归的规则。

## 消除左递归「Elimination of Left Recursion」

我们目前手写的语法解析器，是属于自上而下「Top-Down」的类型，我们还发现，自上而下的语法解析器，是无法处理左递归语法的。

所以我们要考虑，如何消除左递归「Elimination of Left Recursion」。

为了将问题简化，我们来看一个简单的左递归的语法规则：

```
A ::= Aα | β
```

这个语法规则中包含这样几个内容：

1. 非终结符 A
2. 不以 A 开头的(非)终结符 α
3. 不以 A 开头的(非)终结符 β

有一点需要注意的是，上面的语法规则属于直接左递归，因为它的右边的规则内容立刻出现了自身。为了做为对比，我们看一下间接左递归：

```
A ::= Sα | β
S ::= Aβ
```

我们来看一下这个规则的匹配过程：

1. 选取 `A ::= Sα` 这个分支
2. 因为 `S ::= Aβ`，所以将其右边带入到上一步、替换其中的 `S`，得到：`A ::= Aβα`

这又符合了我们之前对左递归的定义。我们的自上而下的解析器同样无法处理间接左递归的语法。

我们先看一下对于直接左递归 `A ::= Aα | β` 而言，它如何匹配输入的字符串：

1. `A ::= Aα`
2. `A ::= Aαα`
3. `A ::= Aααα`
4. 以此类推...
5. 直到某一时刻，输入的内容匹配到了 `β`，最终我们匹配的结果为
6. `A ::= βααα...`

当然，我们也可能在第一步的时候就直接匹配到了 `β`。因此，上面的语法匹配的字符为：以 `β` 开头的，后面紧接着任意数量的 `α`。

现在我们知道对于上面的规则来说，形如 `βααα...` 的输入，将会符合规则。并且上面的语法规则实际上是从右往左来匹配输入的。

为了使得我们的自上而下的解析器得以工作，我们重写后的规则需要满足：

1. 规则 A 需要从左往右来匹配输入
2. 规则 A 最左边的第一个(非)终结符不能为 A 自身

根据这两个原则，我们首先将 A 写成：

```
A ::= βA'
```

这样的目的就是先匹配 `βααα...` 中的第一个 `β`，这就满足了我们上面的两点重写需求。但是还没结束，我们接着 `A'` 要做的就是能够匹配重复出现的 `α`，因此我们可以将 `A'` 写成：

```
A' ::= αA' | ε
```

`ε` 表示匹配输入的结尾，作为匹配的终止条件。

我们将它们放到一起：

```
A  ::= βA'
A' ::= αA' | ε
```

我们来试着使用重写后的规则，看看它将如何匹配输入：

1. `A ::= βA'` 匹配开头第一个 `βA'`
2. 因为 `A' ::= αA'`，将其右边带入上一步的右边、替换 `A'`，可以匹配到 `βαA'`
3. 继续上一步，可以继续匹配到 `βααA'`
4. 继续上一步，可以继续匹配到 `βαααA'`
5. 以此类推...
6. 直到匹配到输入的结尾部分，满足 `A' ::= ε` 
7. 最终得以匹配的结果为 `βααα...αααε`

现在我们得出结论，对于直接左递归：

```
A ::= Aα | β
```

我们可以通过左递归消除，将其变换为：

```
A  ::= βA'
A' ::= αA' | ε
```

现在我们着手看一下我们的算术表达式语法，针对它如何进行左递归消除：

```
expr ::= expr "*" expr
       | num
```

我们直接套用公式，令:

* `A = expr`，因为 `A` 的定义为需要进行消除的项
* `α = "*" expr`，因为 `α` 的定义为，以不是待消除项开头的(非)终结符
* `β = num`，因为 `β` 的定义为，以不是待消除项开头的(非)终结符

经过变换得到：

```
expr  ::= num expr'
expr' ::= "*" expr expr' | ε
```

我们已经可以将乘法表达式进行左递归消除了，接下来我们看看如何处理整个算术表达式：

```
expr ::= expr "*" expr
       | expr "/" expr
       | expr "+" expr
       | expr "-" expr
       | num
```

面对一下变得这么复杂的表达式，大家估计会感到无从下手。我们可以利用已经掌握的知识，将每个分支先拆开来进行消除：

```
expr  ::= num expr'
expr' ::= "*" expr expr' | ε

expr  ::= num expr'
expr' ::= "/" expr expr' | ε

expr  ::= num expr'
expr' ::= "+" expr expr' | ε

expr  ::= num expr'
expr' ::= "-" expr expr' | ε
```

我们将上面的结果两行一组、相互对照起来观察，不难发现，第一行都是相同的，第二行也只是操作符不同，将所有第二行综合起来看，它们其实都是表示 `expr'` 的不同分支。我们可以将上面的结果进行合并：

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

于是我们发现一个新的结论，对于形如：

```
A ::= Aα | Aβ | γ
```

的规则，我们可以将其转换成：

```
A  ::= γA'
A' ::= αA' | βA' | ε

/* A' 根据 EBNF 语法功能，上面的 A' 又可进一步简化为 */
A' ::= α*
    |  β*
    |  ε

/* 将 A' 进一步简化  */
A' ::= ( α | β )*
    |  ε
```

来消除左递归。

我们最终处理完成后的表达式语法为：

```
expr  ::= num expr'

/* 对照上面简化 A' 中间形式 */
expr' ::= ( "*" expr )*
        | ( "/" expr )* 
        | ( "+" expr )*
        | ( "-" expr )*
        | ε

/* 对照 A’ 的最终形式 */
expr' ::= ( "*" expr )*
        | ( "/" expr )* 
        | ( "+" expr )*
        | ( "-" expr )*
        | ε

/* 根据我们的表达式内容进一步简化 */
expr' ::= ( ( "*" | "/" | "+" | "-" ) expr )*
        | ε

/* 最终我们得到 */
expr  ::= num expr'
expr' ::= ( ( "*" | "/" | "+" | "-" ) expr )*
        | ε
```

## 完善解析器

现在我们来补全我们的解析器，以解析算术表达式。

### 完善词法解析器

我们先来完善词法解析器，首先我们先增加几个 Token 类型：

```javascript
TokenType.NUMBER = "number";
TokenType.MUL = "*";
TokenType.DIV = "/";
TokenType.ADD = "+";
TokenType.SUB = "-";
```

这些新增的类型即为我们接下来将要解析的 Token 类型，我们来修改一下 `Lexer::next` 方法：

```javascript
next() {
  this.skipWhitespace();
  const ch = this.src.peek();
  if (ch === '"') return this.readString();
  if (ch === "h") return this.readHi();
  // 解析数字
  if (Lexer.isDigit(ch)) return this.readNumber();
  // 解析运算符
  if (Lexer.isOp(ch)) return this.readOp();
  if (ch === EOF) return new Token(TokenType.EOF);
  throw new Error(this.makeErrMsg());
}
```

没有什么特别新的东西，只是增加了两个预测分支，分别预测接下来选择解析数字还是解析运算符。接着我们看一下 `readNumber` 和 `readOp` 的实现：

```javascript
readNumber() {
  const tok = new Token(TokenType.NUMBER);
  tok.loc.start = this.getPos();
  const v = [this.src.read()];
  while (true) {
    let ch = this.src.peek();
    if (Lexer.isDigit(ch)) {
      v.push(this.src.read());
      continue;
    }
    break;
  }
  tok.loc.end = this.getPos();
  tok.value = v.join("");
  return tok;
}

readOp() {
  const tok = new Token();
  tok.loc.start = this.getPos();
  tok.type = this.src.read();
  tok.loc.end = this.getPos();
  return tok;
}
```

如果输入的是数字的话，我们就不断的尝试读取接下来的数字，直到接下来的字符不是数字为止，这里我们只处理了整型数，并且没有特别考虑前导零和正负整数的情况。所以符合我们条件的数字面量的类型为：以可选前导零开头的任意整数。

处理操作符(运算符)的过程就很简单了，由于我们目前的操作符都是单个字符的，直接读取它们就行了。

### 完善语法解析器

我们继续看一下如何完善语法解析器。

首先，我们添加几个新的节点类型的定义：

```javascript
class ExprStmt extends Node {
  constructor(loc, value) {
    super(NodeType.EXPR_STMT, loc);
    this.value = value;
  }
}

class BinaryExpr extends Node {
  constructor(loc, op, left, right) {
    super(NodeType.BINARY_EXPR, loc);
    this.op = op;
    this.left = left;
    this.right = right;
  }
}

class NumLiteral extends Node {
  constructor(loc, value) {
    super(NodeType.NUMBER, loc);
    this.value = value;
  }
}
```

这里我们开始区分表达式「Expression」和语句「Statement」这两种不同的节点类型了。

运算符 `* / + -` 被称为双目运算符，所谓「目」就是操作数的意思。因为这些运算符都需要两个操作数，所以称之为双目运算符，它们所表示的运算就称为双目运算。

我们通过类「BinaryExpr」来表示这样的程序结构。

对于数值字面量而言，我们使用类「NumLiteral」来表示它。字面量也是表达式，表达式「Expression」是语句「Statement」的组成部分。

为了表示程序中出现的表达式语句，我们还定义了类「ExprStmt」，该类的属性 `value` 表示的就是作为其唯一子节点的表达式节点。

为了对应新增的节点定义，我们也需要添加几个新的节点类型：

```javascript
NodeType.EXPR_STMT = "exprStmt";
NodeType.BINARY_EXPR = "binaryExpr";
NodeType.NUMBER = "number";
```

和完善词法解析器的步骤相似，我们也从语法解析的入口方法开始完善：

```javascript
parseProg() {
  const node = new Prog();
  node.loc.start = this.lexer.getPos();
  while (true) {
    const tok = this.lexer.peek();
    let stmt;
    if (tok.type === TokenType.EOF) break;
    if (tok.type === TokenType.HI) stmt = this.parseSayHi();
    // 预测解下来是否需要进行表达式的解析
    if (tok.type === TokenType.NUMBER) stmt = this.parseExprStmt();
    node.body.push(stmt);
  }
  node.loc.end = this.lexer.getPos();
  return node;
}
```

上一节我们已经将算术表达式的左递归进行了消除，通过消除后的表达式我们发现，算术表达式总是以数值字面量作为开头的，因此我们可以使用上面代码中的预测条件。

由于 ExprStmt 只有唯一的表达式节点，所以对它的解析也很接单：

```javascript
parseExprStmt() {
  const node = new ExprStmt();
  const expr = this.parseExpr();
  node.loc = expr.loc;
  node.value = expr;
  return node;
}
```

`parseExprStmt` 只是简单地调用 `parseExpr` 方法，那么 `parseExpr` 实现为：

```javascript
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;
}
```

上面的代码对照消除左递归后的表达式语法：

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

我们只是使用方法来替代语法规则中的展开操作。`parseNum` 就是解析数值字面量，就不过多解释了。

`parseExpr1` 方法就对应了消除后的 `expr'` 的内容。`parseExpr1` 中我们先预读接下来的 Token 是否为操作符，如果不是，就表示处理已经完成了，直接返回传入的 `left`。如果接下来为操作符，我们就先将已经处理的操作符跳过，然后接续调用 `parseExpr`。我们没有陷入无限循环的原因就是，我们在方法内部总是可以消化掉一部分输入。

对于表达式 `1 + 2 * 3` 来说，调用的过程如下：

![](/files/-LgNHYoXNi4PTUxR4lTU)

我们可以以一个 U 型的方式来看这个图，从左边开始往下，到了最底部时，转到右边往上。左边和中间左半边部分，表示我们的递归调用链、期间发生的参数传递、以及表达式字符串被不断读取的消减过程。右边和中间的右半部分表示了递归调用结束，不断返回并构造节点的过程。

上图中我们不仅分析了整个表达式解析的过程；还根据这个过程，演示了我们消除左递归后的右递归的执行过程。

在我们着手试一试完善的成果之前，我们先添加一个新的 Visitor - 「YamlVisitor」，它可以将我们的 AST 输出为 [YAML](https://yaml.org/) 的格式，这个格式的好处就是既能体现我们树形结构的层级关系，格式上也显得更加清晰。

我们先往类「Visitor」中增加一些内容：

```javascript
visitExprStmt(node) {}

visitStmt(node) {
  switch (node.type) {
    case NodeType.EXPR_STMT:
      return this.visitExprStmt(node);
    case NodeType.SAY_HI:
      return this.visitSayHi(node);
  }
}

visitStmtList(list) {}

visitNumLiteral(node) {}

visitBinaryExpr(node) {}

visitExpr(node) {
  switch (node.type) {
    case NodeType.NUMBER:
      return this.visitNumLiteral(node);
    case NodeType.BINARY_EXPR:
      return this.visitBinaryExpr(node);
  }
}
```

空着的方法留给子类去实现。`visitStmt` 和 `visitExpr` 做一个简单的任务派发，根据不同节点的类型，将它们派发到各自的处理方法中。

下面是「YamlVisitor」的实现：

```javascript
const { Visitor } = require("./visitor");
const yaml = require("js-yaml");

class YamlVisitor extends Visitor {
  visitProg(node) {
    return yaml.dump({
      type: node.type,
      body: this.visitStmtList(node.body)
    });
  }

  visitStmtList(list) {
    return list.map(stmt => this.visitStmt(stmt));
  }

  visitExprStmt(node) {
    return {
      type: node.type,
      value: this.visitExpr(node.value)
    };
  }

  visitBinaryExpr(node) {
    return {
      type: node.type,
      op: node.op.type,
      left: this.visitExpr(node.left),
      right: this.visitExpr(node.right)
    };
  }

  visitNumLiteral(node) {
    return node.value;
  }
}
```

在对不同节点的处理中，我仅输出扼要的内容，比如跳过了行列号。在起始点的处理方法 `visitProg` 中，我们将返回根据 YAML 语法序列化后的字符串。

我们尚未考虑如何消除间接左递归，因为消除直接左递归已经可以应对大部分情况了，我们不妨等遇到间接左递归的时候再考虑如何消除它。

最后通过一小段程序来检验这次的完成结果：

```javascript
const { Source } = require("./source");
const { Lexer, TokenType } = require("./lexer");
const { Parser } = require("./parser");
const { InterpretVisitor } = require("./interpret-visitor");
const { YamlVisitor } = require("./yaml-visitor");
const util = require("util");

const code = `1 + 2 + 3
4 + 5 * 6
`;
const src = new Source(code);
const lexer = new Lexer(src);
const parser = new Parser(lexer);

const ast = parser.parseProg();
const visitor = new YamlVisitor();
console.log(visitor.visitProg(ast));
```

幸运的话，将看到类似下面的输出：

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hsiaosiyuan0.gitbook.io/icj/part1/1-7-arith-left-recursion.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.