【编译原理笔记05】语法分析：FIRST集和FOLLOW集的计算，[非]递归的预测分析法，预测分析中的错误处理

本次笔记内容：
4-4 FIRST集和FOLLOW集
4-5 递归的预测分析法
4-6 非递归的预测分析法
4-7 预测分析法中的错误处理

本节课幻灯片，见于我的 GitHub 仓库：第5讲 语法分析_2.pdf

承接上一节课。上一节课提出了FIRST集和FOLLOW集的概念，这节课先来讨论如何计算这两个集合。

FIRST集和FOLLOW集的计算

计算文法符号X的FIRST(X)

• FIRST(X)：可以从X推导出的所有串首终结符构成的集合;
• 如果$X \Rightarrow * \epsilon$X⇒∗ϵ，那么ε∈FIRST(X)。

取决于产生式的右部：

• 比如2、4、5产生式，左部以终结符打头，这个终结符就是就是产生式可以推导出的终结符，于是加入到 FIRST 集合中；
• 对于非终结符，其依赖于自己的内容，比如F的FIRST为 {( id} ，则 T 的 FIRST 也为这个； E 依赖于 T ，则 E 的 FIRST 也是这个。

算法总结

不断应用下列规则，直到没有新的终结符或ε可以被加入到任何FIRST集合中为止。

• 如果X是一个终结符，那么FIRST ( X ) = { X }；
• 如果X是一个非终结符，且X→Y1…Yk∈P(k≥1)，那么如果对于某个i，a在FIRST (Yi ) 中且ε 在所有的FIRST(Y1) , … , FIRST(Yi-1)中(即Y1…Yi-1 $\Rightarrow$⇒* ε )，就把a加入到FIRST( X )中。如果对于所有的j = 1,2, . . . , k，ε在FIRST(Yj)中，那么将ε加入到FIRST( X )；
• 如果X→ε∈P，那么将ε加入到FIRST( X )中。

接着，计算串X1X2 …Xn的FIRST 集合

• 向FIRST($X_1X_2X_3$X1​X2​X3​)加入FIRST($X_1$X1​)中所有的非ε符号；
• 如果ε在FIRST($X_1$X1​)中，再加入FIRST($X_2$X2​)中的所有非ε符号；如果ε在FIRST($X_1$X1​)和FIRST($X_2$X2​)中，再加入FIRST($X_3$X3​)中的所有非ε符号，以此类推；
• 最后，如果对所有的i，ε都在FIRST($X_i$Xi​)中，那么将ε加入到FIRST($X_1X_2...X_n$X1​X2​...Xn​) 中。

计算非终结符A的FOLLOW(A)

• FOLLOW(A)：可能在某个句型中紧跟在A后边的终结符a的集合；
• $F O L L O W(A)=\left\{\mathrm{a} \mid S \Rightarrow^{*} \alpha A a \beta, \mathrm{a} \in V_{T}, \quad \alpha, \beta \in\left(V_{T} \cup V_{N}\right)^{*}\right\}$FOLLOW(A)={a∣S⇒∗αAaβ,a∈VT​,α,β∈(VT​∪VN​)∗}
• 如果A是某个句型的的最右符号，则将结束符“$”添加到FOLLOW(A)中。

例子如上，基于 FIRST 计算：

• 文法大E本身是一个句型，它也是这个句型的最右符号，因此将 $ 加入其 FOLLOW 集中；
• 接下来逐个分析产生式。
• 第一条产生式中，E’的FIRST集中的所有终结符可以跟在T的后面，所以将E’中的终结符，也就是 + 加入到T的 FOLLOW 集中；
• 由于 E’ 可以推出空串，那么能跟在 E 后面的符号，就能跟在 T 后面，因此，将E的FOLLOW的$添加到T的FOLLOW中；
• 对于E’，E’是产生式$E \rightarrow TE'$E→TE′中最右边的符号，因此能跟在E后面的，自然就能跟在E’后面，因此将E中的元素添加到E’中。
• 以此类推。
• 最后，各个产生式都过完一遍了，再回到第一个产生式。注意到由于E’可以是空串，那么E’后面的东西，也能出现在T后面，因此将E’中有的而T中没有的反括号)加入到T中；补充添加以此类推。

算法总结

不断应用下列规则，直到没有新的终结符可以被加入到任何FOLLOW集合中为止：

• 将$放入FOLLOW(S)中，其中S是开始符号，$是输入右端的结束标记；
• 如果存在一个产生式A→αBβ，那么FIRST(β)中除ε之外的所有符号都在FOLLOW(B)中；
• 如果存在一个产生式A→αB，或存在产生式A→αBβ且FIRST(β) 包含ε，那么FOLLOW(A)中的所有符号都在FOLLOW(B)中。

基于FIRST于FOLLOW计算SELECT集

• 第一个产生式，左部是T（非终结符），因此是T的FIRST集中的终结符；
• 第二个产生式，左部是终结符，因此就是终结符；
• 第三个产生式，左部是空串，因此就是其FOLLOW集。

可以看出：

• 第1个和第2个产生式，具有相同的左部，其SELECT集互不相交；
• 第4，5同理；
• 因此，这个算数表达式文法是LL(1)文法。
• 因此可以写预测分析表。

预测分析表

由上，我们得出了这个可以帮助我们大大提升效率，不需要再编译中回溯的预测分析表。

LL(1)文法的分析方法分为，将在后面介绍：

• 递归的预测分析法
• 非递归的预测分析法

递归的预测分析法

递归的预测分析法是指：在递归下降分析中，根据预测分析表进行产生式的选择。

根据每个非终结符的产生式和LL(1)文法的预测分析表，为每个非终结符编写对应的过程。

一个例子：

右边为递归下降分析的主程序。

其递归过程如下。

非终结符有自己对应的程序。

非递归的预测分析法

非递归的预测分析不需要为每个非终结符编写递归下降过程，而是根据预测分析表构造一个自动机，也叫表驱动的预测分析。

如图，为有穷自动机增加一个栈，用于增加记忆功能。比如对于上图中例子，输入a，压栈，输入b，b进栈，a出栈，最终可以判断a与b的数量是否一致。

如图，通过入栈出栈的形式，实现了预测分析。

表驱动的预测分析法总结：

递归的预测分析法vs.非递归的预测分析法

	递归的预测分析法	非递归的预测分析法
程序规模	程序规模较大，不需载入分析表	主控程序规模较小，需载入分析表（表较小）
直观性	较好	较差
效率	较低	分析时间大约正比于待分析程序的长度
自动生成	较难	较易

总结预测分析法实现步骤

1. 构造文法；
2. 改造文法：消除二义性、消除左递归、消除回溯；
3. 求每个变量的FIRST集和FOLLOW集，从而求得每个候选式的SELECT集；
4. 检查是不是LL(1)文法。若是，构造预测分析表；
5. 对于递归的预测分析，根据预测分析表为每一个非终结符编写一个过程；对于非递归的预测分析，实现表驱动的预测分析算法；

预测分析中的错误处理

预测分析中的错误检测

两种情况下可以检测到错误：

• 栈顶的终结符和当前输入符号不匹配；
• 栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空。

预测分析中的错误恢复

可以使用恐慌模式：

• 忽略输入中的一些符号，直到输入中出现由设计者选定的同步词法单元(synchronizing token)集合中的某个词法单元：
• • 其效果依赖于同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复；
• • 例如可以把FOLLOW(A)中的所有终结符放入非终结符A的同步记号集合；
• 如果终结符在栈顶而不能匹配，一个简单的办法就是弹出此终结符。

一个例子：

先由FOLLOW(X)得到SYNCH在哪里。