4.2 语法分析——递归下降的 LL(1) 语法分析器

语法分析器分为两大类：LL、LR，后者不论是在理解还是实现上都比 LL 复杂得多

课程介绍 LL 中比较简单的一类

语法分析要做的事情就是构建语法分析树

LL 是自顶向下，LR 是自底向上

图中的圈就是文法的表达能力

Antlr 使用的算法是 LL：Adaptive LL(*)

LL(1) 语法分析器特点：

• 自顶向下的

• 递归下降的【可以递归下降的实现并不是一定要这样实现，所有的递归都能改写成非递归形式】

• 基于预测分析表的

• 适用于LL(1) 文法的

对于中间节点的两个问题：

对于第二个问题——选择哪个产生式进行展开，可以暂时先放一下，即不管这个问题，先写一个语法分析器框架，如下【任何一个语法分析器的大框架都是基本类似的，它们不同的是对于非终结符怎么选择产生式（备选分支）】

为每个非终结符写一个递归函数，比如上面对 A 这个非终结符进行展开

例子：左边方框中的是语法规则

同样是展开非终结符 S, 为什么前两次选择了 S → (S + F), 而第三次选择了 S → F

因为它们面对的当前词法单元不同，根据当前看到的词法单元来决定选择哪个语法规则(备选分支)

前两次都是它看到的第一个字符是 ( ，因此选择第二个语法规则进行展开，第三次看到的不是括号，因此选择第一个进行展开

上面的决定过程在实现上是通过预测分析表来实现的（空白表示报错，即不能展开）

因为每个单元格只有一个产生式可选，因此只需要根据当前字符就能确定要选择哪个产生式

当有了预测分析表后，上面的框架就能具体化了：

LL(1)在预测展开时要选择哪个产生式，要考虑：

1. 【FIRST】使用的产生式后续的所有展开中，最左边的非终结符有没有我们想要的。

   如对于 prog 的展开是选择 func_call 还是 decl，根据第一个非终结符是不是 int 即可判断

2. 【FOLLOW】如果想展开的非终结符，它有个备选分支是 ε，那就要考虑这个非终结符展成 ε 后，它后面的那个字符有没有我们想要的

   如 int x; 在 optional_init 展开成 ε，那么就要看 optional_init 后面的 ; 在输入的字符串中有没有出现

形式化表述 FIRST和FOLLOW

FISRT(α) 其中 α 是产生式的右部，即冒号右边的部分，FISRT(α) 是 α 所能产生的所有的句型（α 当然可以继续产生右部）的最左边的终结符的集合

如上面的 prog 中 FISRT(prog)={int, ID}， FISRT(decl)={int}

FOLLOW 中包含文件结束符 $ (EOF)

A 是产生式的左部，因此会出现在某些产生式的右部的部分中，如 optional_init 是产生式的左部，出现在 del 和 arg 的右部中

FOLLOW(A) 是非终结符 A 在其他所有产生式右部中紧跟在 A 右部的终结符的集合。此外如果 A 是其他产生式 B 中最右边的一个，如上面的optional_init 是 arg 最右边的，那么 FOLLOW(arg) 一定是 FOLLOW(optional_init) 的子集

如 FOLLOW(optional_init) = {; , )}

计算 FIRST和FOLLOW

得到 FIRST和FOLLOW => 预测分析表 => LL(1)文法

FIRST

如果是非终结符，那么 FIRST(X) 包含 FIRST(Y₁)，Y₁ 有可能推出 ε，这里要把 ε 给去掉，如果有 ε，那么后面的 for 循环就是看 Y₂ 的 FIRST

在 9-10 行是只有当整个 Y₁~Y_k 能推出 ε 时，才把 ε 加入到 FIRST(X)

例子：

FOLLOW

follow 集合中一定终结符，不会有 ε

如之前的例子 FOLLOW(optional_init) = {; , )}

第一条产生式默认是开始符号，如果 X 是开始符号，那么要把 $ 加到 FOLLOW(X)，就像之前写的语法中的 prog，$ 是我们人为加进去的，prog 就是整个程序，程序结束自然是文件结束符 $

例子：

最开始的 FOLLOW 是空集，是一个个符号往里面加的，因此 FOLLOW(Z)是FOLLOW(Z)的子集，因此是空集，并且这也是不奇怪，在产生式中可以发现，在任何的产生式都不会在 Z 后有一个终结符

计算预测分析表

对于 LL(1)，每个输入都有确定唯一的产生式，只要看最开始的终结符即可，如果选择了之后后面无法继续推下去了，说明输入的句子不符合 LL(1)，即语法错误

例子

对于每个非终结符 A，逐个看它的所有产生式，根据上面的两条规则【规则(2)表示先看 FIRST 中有没有 ε，如果有，那么再看 t 是不是属于 FOLLOW】，t 满足其中一条即可在这个位置 [A,t] 中填入这个产生式子的序号，即表示要展开这个非终结符并且输入字符为 t 时，应该选择的产生式

显然上面的这个例子不是 LL(1) 文法

（最左推导指每次选择最左边的非终结符进行展开）

因此 LL(0) 意思就是不需要看输入字符就知道用哪个展开式，因此只适用于每个非终结符都只有一个产生式的情况（即不需要选择产生式）

非递归的预测分析算法

图中的 S 就表示开始符号

用栈的方式来实现非递归

第一个 else if 是指 X 不是 ip 所指的符号，同时又是一个终结符，说明输入的句子是语法错误的

注意压栈是要先压 Y_k，因为是最左推导，要先推导 Y₁

改造非 LL(1) 文法的文法

这两个方法都是比较老的技术，Antlr 采用的是另一种新技术

提取左公因子

比如 X→aB|aC，第一个字符都是 a，因此仍然无法判断选择哪个，因此可以把 a提取出来改写成 X→aD，D→B|C

消除左递归

要想让乘法比加法的优先级更高，那么就要在构建语法分析树的时候让乘法更靠近叶子节点。

要在文法中表达这个，那么就是引入一个中间的非终结符，如上面的 T，就是引入的新的，必须要 T 展开后才会去计算加法

对于这个左递归文法，如果用 LL(1) 算法来执行，在一开始的产生式中就要递归 E【如 E→E+T】，而不需要消耗任何词法单元，这样会造成死循环

把上面的文法改造成右递归，就可以让 LL(1) 处理

执行例子：

最后三行体现了 $ 的必要性，那么当输入已经没有了，而栈中还有元素，因此栈中的元素都是使用生成 ε 的产生式