i
i
icj
Search…
⌃K

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

算术表达式语法

到目前为止,我们的 hi 语言还是显得有些单薄了。接下来我们将给它添加计算数学表达式的功能。
未来我们在像 hi 语言中增加新的语法功能的时候,都将按照这样的步骤:
  1. 1.
    增加相应的语法规则,也就是在我们的 EBNF 中增加需要新增的语法规则
  2. 2.
    根据新增的语法规则,向词法解析器中增加适应新规则的内容
  3. 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 中写了 parseProgparseSayHi 两个方法,它们分别对应语法中的 progsay_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. 1.
    非终结符 A
  2. 2.
    不以 A 开头的(非)终结符 α
  3. 3.
    不以 A 开头的(非)终结符 β
有一点需要注意的是,上面的语法规则属于直接左递归,因为它的右边的规则内容立刻出现了自身。为了做为对比,我们看一下间接左递归:
A ::= Sα | β
S ::= Aβ
我们来看一下这个规则的匹配过程:
  1. 1.
    选取 A ::= Sα 这个分支
  2. 2.
    因为 S ::= Aβ,所以将其右边带入到上一步、替换其中的 S,得到:A ::= Aβα
这又符合了我们之前对左递归的定义。我们的自上而下的解析器同样无法处理间接左递归的语法。
我们先看一下对于直接左递归 A ::= Aα | β 而言,它如何匹配输入的字符串:
  1. 1.
    A ::= Aα
  2. 2.
    A ::= Aαα
  3. 3.
    A ::= Aααα
  4. 4.
    以此类推...
  5. 5.
    直到某一时刻,输入的内容匹配到了 β,最终我们匹配的结果为
  6. 6.
    A ::= βααα...
当然,我们也可能在第一步的时候就直接匹配到了 β。因此,上面的语法匹配的字符为:以 β 开头的,后面紧接着任意数量的 α
现在我们知道对于上面的规则来说,形如 βααα... 的输入,将会符合规则。并且上面的语法规则实际上是从右往左来匹配输入的。
为了使得我们的自上而下的解析器得以工作,我们重写后的规则需要满足:
  1. 1.
    规则 A 需要从左往右来匹配输入
  2. 2.
    规则 A 最左边的第一个(非)终结符不能为 A 自身
根据这两个原则,我们首先将 A 写成:
A ::= βA'
这样的目的就是先匹配 βααα... 中的第一个 β,这就满足了我们上面的两点重写需求。但是还没结束,我们接着 A' 要做的就是能够匹配重复出现的 α,因此我们可以将 A' 写成:
A' ::= αA' | ε
ε 表示匹配输入的结尾,作为匹配的终止条件。
我们将它们放到一起:
A ::= βA'
A' ::= αA' | ε
我们来试着使用重写后的规则,看看它将如何匹配输入:
  1. 1.
    A ::= βA' 匹配开头第一个 βA'
  2. 2.
    因为 A' ::= αA',将其右边带入上一步的右边、替换 A',可以匹配到 βαA'
  3. 3.
    继续上一步,可以继续匹配到 βααA'
  4. 4.
    继续上一步,可以继续匹配到 βαααA'
  5. 5.
    以此类推...
  6. 6.
    直到匹配到输入的结尾部分,满足 A' ::= ε
  7. 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 类型:
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());
}
没有什么特别新的东西,只是增加了两个预测分支,分别预测接下来选择解析数字还是解析运算符。接着我们看一下 readNumberreadOp 的实现:
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);
}
}
空着的方法留给子类去实现。visitStmtvisitExpr 做一个简单的任务派发,根据不同节点的类型,将它们派发到各自的处理方法中。
下面是「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'