【编译原理】手工打造语法分析器

重点：

• 语法分析的原理
• 递归下降算法（Recursive Descent Parsing）
• 上下文无关文法（Context-free Grammar，CFG）

关键点：

• 左递归问题
• 深度遍历求值 - 后续遍历

上一篇「词法分析器」将字符串拆分为了一个一个的 token。
本篇我们将 token 变成语法树。

一、递归下降算法#

还是这个例子 int age = 45
我们给出这个语法的规则：

intDeclaration : Int Identifier ('=' additiveExpression)?;

如果翻译为程序的话，伪代码如下

// 伪代码
MatchIntDeclare(){
  MatchToken(Int)；        // 匹配 Int 关键字
  MatchIdentifier();       // 匹配标识符
  MatchToken(equal);       // 匹配等号
  MatchExpression();       // 匹配表达式
}

输出的 AST 类似于：

Programm Calculator
    IntDeclaration age
        AssignmentExp =
            IntLiteral 45

上面的过程，称为「递归下降算法」。
从顶部开始不断向下生成节点，其中还会有递归调用的部分。

二、上下文无关文法#

上面的例子比较简单，还可以用正则表达式文法来表示。
但如果是个算数表达式呢？正则文法就很难表示了。

• 2+3*5
• 2*3+5
• 2*3

这时我们可以用递归的规则来表示

additiveExpression
    :   multiplicativeExpression
    |   additiveExpression Plus multiplicativeExpression
    ;
 
multiplicativeExpression
    :   IntLiteral
    |   multiplicativeExpression Star IntLiteral
    ;

生成的 AST 为：

如果要计算表达式的值，只需要对根节点求值就可以了。
这个就叫做「上下文无关文法」。

但你把上述规则翻译为代码逻辑时，会发现一个问题，无限递归。
我们先用个最简单的示例：

	additiveExpression
    :   IntLiteral
    |   additiveExpression Plus IntLiteral
    ;

比如输入 2+3：

• 先判断其是不是 IntLiteral，发现不是
• 然后匹配 additiveExpression Plus IntLiteral，此时还没有消耗任何的 token
• 先进入的是 additiveExpression，此时要处理的表达式还是 2+3
• 又回到开始，无限循环

这里要注意的一个问题：
并不是觉得 2+3 符合 additiveExpression Plus IntLiteral 就能直接按照 + 拆分为两部分，然后两部分分别去匹配。
这里是顺序匹配的，直到匹配到该语法规则的结束符为止。
在 additiveExpression Plus IntLiteral 中 additiveExpression 的部分，也是在处理完整的 token 的（2+3）。

三、左递归解决方案#

改为右递归#

如何处理这个左递归问题呢？
我们可以把表达式换个位置：

	additiveExpression
    :   IntLiteral
    |   IntLiteral Plus additiveExpression
    ;

先匹配 IntLiteral 这样就能消耗掉一个 token，就不会无限循环了。
比如还是 2+3

• 2+3 不是 IntLiteral，跳到下面
• 2+3 的第一个字符是 2 被 IntLiteral 消耗掉，并结束 IntLiteral 匹配
• 然后 + 被 Plus 消耗掉
• 最后 3 进入 additiveExpression，匹配为第一条规则 IntLiteral

这样就结束了，没有无限循环。
改写成算法是：

private SimpleASTNode additive(TokenReader tokens) throws Exception {
    SimpleASTNode child1 = IntLiteral();  // 计算第一个子节点
    SimpleASTNode node = child1;  // 如果没有第二个子节点，就返回这个
    Token token = tokens.peek();
    if (child1 != null && token != null) {
        if (token.getType() == TokenType.Plus) {
            token = tokens.read();
            SimpleASTNode child2 = additive(); // 递归地解析第二个节点
            if (child2 != null) {
                node = new SimpleASTNode(ASTNodeType.AdditiveExp, token.getText());
                node.addChild(child1);
                node.addChild(child2);
            } else {
                throw new Exception("invalid additive expression, expecting the right part.");
            }
        }
    }
    return node;
}

但也有问题：
比如 2+3+4，你会发现它的计算顺序变为了 2+(3+4) 后面 3+4 作为一个 additiveExpression 先被计算，然后才会和前面的 2 相加。改变了计算顺序。

消除左递归#

上面右递归解决了无限递归的问题，但是又有了结合优先级的问题。
那么我们再改写一下左递归：

additiveExpression
  :   IntLiteral additiveExpression'
  ;

additiveExpression'
  :		'+' IntLiteral additiveExpression'
  | 	ε
  ;

文法中，ε（读作 epsilon）是空集的意思。
语法树 AST 就变成了下图左边的样子，虽然没有无限递归，但是按照前面思路，使用递归下降算法，结合性还是不对。
我们期望的应该是右边的 AST 树样子。那么怎么才能变成右边的样子呢？

这里我们插入一个知识点：
前面语法规则的表示方式成为：「巴科斯范式」，简称 BNF
我们把下面用正则表达式简化表达的方式，称为「扩展巴科斯范式 (EBNF)」
add -> mul (+ mul)*

那么我们把上面的表达式改写成 EBNF 形式，变为：

additiveExpression -> IntLiteral ('+' IntLiteral)*

这里写法的变化，就能让我们的算法逻辑产生巨大的变化。

重点：
前面左递归也好、右递归也好，变来变去都是递归调用，导致无限循环、结合性的问题。如果我们干掉递归，用循环来代替，就能按照我们期待的方式来执行了。
这里的区别是：前面递归计算过程是后序，把最后访问到的节点先计算，然后再一步步的返回；而循环迭代是前序，先计算再往后访问。

我们再写出计算逻辑：

private SimpleASTNode additive(TokenReader tokens) throws Exception {
    SimpleASTNode child1 = IntLiteral(tokens);  // 应用 add 规则
    SimpleASTNode node = child1;
    if (child1 != null) {
        while (true) {                              // 循环应用 add'
            Token token = tokens.peek();
            if (token != null && (token.getType() == TokenType.Plus)) {
                token = tokens.read();              // 读出加号
                SimpleASTNode child2 = IntLiteral(tokens);  // 计算下级节点
                node = new SimpleASTNode(ASTNodeType.Additive, token.getText());
                node.addChild(child1);              // 注意，新节点在顶层，保证正确的结合性
                node.addChild(child2);
                child1 = node;
            } else {
                break;
            }
        }
    }
    return node;
}

消除了递归，只有循环迭代。你可以和上面递归的代码对比下。

再提一个概念：「尾递归」
尾递归就是函数的最后一句是递归的调用自身，可以理解为先序。而这种尾递归通常都可以转化为一个循环语句。

四、执行代码#

前面我们已经把一个语句转换为了一个 AST 树，接下来我们遍历这个语法树，就能实现计算求值了。
以 2+3+4 为例，简化后的语法树长这样：

遍历的伪代码如下：

evaluate(node) {
    if node.type == TYPE.ADD:
        left_res = evaluate(node.getChild(0))
        right_res = evaluate(node.getChild(1))
        return left_res + right_res
    else if node.type == TYPE.INT:
        return node.val
}

五、小结#

✌️至此，我们实现了一个计算器。

• 可以实现词法分析：对输入的文本拆分为一个一个的 token
• 生成语法树：将 token 变为一个 AST 树
• 计算求值：遍历 AST 树，就能得到最终的计算结果

后面你可以在此基础上进行扩展，增加更多的运算符。以及扩充为一个脚本语言解释器，添加变量赋值、计算等等操作咯。