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

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

引用

CSDN

1.

https://blog.csdn.net/shuofxz/article/details/137476161

本文将详细介绍编译原理中语法分析器的构建方法，重点讲解递归下降算法和上下文无关文法，并通过具体的代码示例和AST树的生成过程，详细阐述如何处理左递归问题。

一、递归下降算法

还是这个例子：

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

这样就结束了，没有无限循环。

改写成算法是：