这篇文章上次修改于 902 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

1 理解代码：编译器的前端技术

编译器分为前端和后端：

• 前端：编译器对程序代码的分析和理解过程。
• 后端：生成目标代码的过程，跟目标机器有关。

前端分为词法分析、语法分析、语义分析三部分，主要涉及形式语言和自动机。

2 词法分析

识别 Token，比如 if、else、int 等关键字，main、printf 等标识符，+、- 等操作符，花括号、圆括号等符号，以及数字、字符串等等。

首先需要写出每个词法的正则表达式，并画出有限自动机，用代码在不同的状态之间迁移，从而解析除 Token。

可以手写词法规则，也可以用词法分析器的生成工具生成，比如 Lex，它们可以读入正则表达式，生成”有限自动机“算法来完成具体的词法分析工作。

3 语法分析

在词法分析的基础上，识别程序的语法结构，通常是一棵 AST （Abstract Syntax Tree，抽象语法）树。

可以采用递归下降算法构造 AST，也可以采用现成的工具如 Antlr 生成。

正则文法是上下文无关文法的一个子集，正则文法不允许递归，而上下文无关文法允许递归。

3.1 消除左递归一

去除乘法后的加法文法：

additiveExpression
    :   IntLiteral
    |   additiveExpression Plus IntLiteral
    ;

在解析 ”2 + 3" 时：

• 首先匹配是不是整型变量，发现不是。
• 然后匹配是不是加法表达式，这里是递归调用。
• 会重复上面两步，无穷无尽。

左递归是递归下降算法无法处理的。

解决：把“additiveExpression”调换到加号后面。

additiveExpression
    :   multiplicativeExpression
    |   multiplicativeExpression Plus additiveExpression
    ;

但是加法运算的结合性规则发生了改变。比如计算 2 + 3 + 4 时，先计算了 3 + 4。

3.2 消除左递归二

将左递归的文法改成非左递归的文法：

add -> mul add'
add' -> + mul add' | ε

用 EBNF 方式表达：

add -> mul (+ mul)* 

可以将 (+ mul)* 这部分写成一个循环，而不是一次次的递归调用。

4 语义分析

消除模棱两可。比如是否要做自动转换，有多个相同名称的变量时应该用哪个等。

会处理上下文相关文法。

参考

宫文学. 编译原理之美.