算术表达式语法
到目前为止，我们的 hi 语言还是显得有些单薄了。接下来我们将给它添加计算数学表达式的功能。
未来我们在像 hi 语言中增加新的语法功能的时候，都将按照这样的步骤：
增加相应的语法规则，也就是在我们的 EBNF 中增加需要新增的语法规则
根据新增的语法规则，向词法解析器中增加适应新规则的内容
根据新增的语法规则，向语法解析器中增加适应新规则的内容
按照上面的步骤来看，首先我们需要在向语法中增加数学表达式的新规则。我们来看看数学表达式的语法来如何书写：
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 ::= Sα | β
S ::= Aβ
我们来看一下这个规则的匹配过程：
因为 S ::= Aβ，所以将其右边带入到上一步、替换其中的 S，得到：A ::= Aβα
这又符合了我们之前对左递归的定义。我们的自上而下的解析器同样无法处理间接左递归的语法。
我们先看一下对于直接左递归 A ::= Aα | β 而言，它如何匹配输入的字符串：
直到某一时刻，输入的内容匹配到了 β，最终我们匹配的结果为
当然，我们也可能在第一步的时候就直接匹配到了 β。因此，上面的语法匹配的字符为：以 β 开头的，后面紧接着任意数量的 α。
现在我们知道对于上面的规则来说，形如 βααα... 的输入，将会符合规则。并且上面的语法规则实际上是从右往左来匹配输入的。
为了使得我们的自上而下的解析器得以工作，我们重写后的规则需要满足：
规则 A 最左边的第一个(非)终结符不能为 A 自身
根据这两个原则，我们首先将 A 写成：
这样的目的就是先匹配 βααα... 中的第一个 β，这就满足了我们上面的两点重写需求。但是还没结束，我们接着 A' 要做的就是能够匹配重复出现的 α，因此我们可以将 A' 写成：
ε 表示匹配输入的结尾，作为匹配的终止条件。
我们将它们放到一起：
A ::= βA'
A' ::= αA' | ε
我们来试着使用重写后的规则，看看它将如何匹配输入：
因为 A' ::= αA'，将其右边带入上一步的右边、替换 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' 根据 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 类型：
TokenType.NUMBER = "number";
TokenType.MUL = "*";
TokenType.DIV = "/";
TokenType.ADD = "+";
TokenType.SUB = "-";
这些新增的类型即为我们接下来将要解析的 Token 类型，我们来修改一下 Lexer::next 方法：
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 的实现：
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;
}
如果输入的是数字的话，我们就不断的尝试读取接下来的数字，直到接下来的字符不是数字为止，这里我们只处理了整型数，并且没有特别考虑前导零和正负整数的情况。所以符合我们条件的数字面量的类型为：以可选前导零开头的任意整数。
处理操作符(运算符)的过程就很简单了，由于我们目前的操作符都是单个字符的，直接读取它们就行了。
完善语法解析器
我们继续看一下如何完善语法解析器。
首先，我们添加几个新的节点类型的定义：
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 表示的就是作为其唯一子节点的表达式节点。
为了对应新增的节点定义，我们也需要添加几个新的节点类型：
NodeType.EXPR_STMT = "exprStmt";
NodeType.BINARY_EXPR = "binaryExpr";
NodeType.NUMBER = "number";
和完善词法解析器的步骤相似，我们也从语法解析的入口方法开始完善：
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 只有唯一的表达式节点，所以对它的解析也很接单：
parseExprStmt() {
const node = new ExprStmt();
const expr = this.parseExpr();
node.loc = expr.loc;
node.value = expr;
return node;
}
parseExprStmt 只是简单地调用 parseExpr 方法，那么 parseExpr 实现为：
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 来说，调用的过程如下：
我们可以以一个 U 型的方式来看这个图，从左边开始往下，到了最底部时，转到右边往上。左边和中间左半边部分，表示我们的递归调用链、期间发生的参数传递、以及表达式字符串被不断读取的消减过程。右边和中间的右半部分表示了递归调用结束，不断返回并构造节点的过程。
上图中我们不仅分析了整个表达式解析的过程；还根据这个过程，演示了我们消除左递归后的右递归的执行过程。
在我们着手试一试完善的成果之前，我们先添加一个新的 Visitor - 「YamlVisitor」，它可以将我们的 AST 输出为 YAML 的格式，这个格式的好处就是既能体现我们树形结构的层级关系，格式上也显得更加清晰。
我们先往类「Visitor」中增加一些内容：
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」的实现：
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 语法序列化后的字符串。
我们尚未考虑如何消除间接左递归，因为消除直接左递归已经可以应对大部分情况了，我们不妨等遇到间接左递归的时候再考虑如何消除它。
最后通过一小段程序来检验这次的完成结果：
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));
幸运的话，将看到类似下面的输出：
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'
