【编译原理笔记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推导出的所有串首终结符构成的集合;
- 如果,那么ε∈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 * ε ),就把a加入到FIRST( X )中。如果对于所有的j = 1,2, . . . , k,ε在FIRST(Yj)中,那么将ε加入到FIRST( X );
- 如果X→ε∈P,那么将ε加入到FIRST( X )中。
接着,计算串X1X2 …Xn的FIRST 集合
- 向FIRST()加入FIRST()中所有的非ε符号;
- 如果ε在FIRST()中,再加入FIRST()中的所有非ε符号;如果ε在FIRST()和FIRST()中,再加入FIRST()中的所有非ε符号,以此类推;
- 最后,如果对所有的i,ε都在FIRST()中,那么将ε加入到FIRST() 中。
计算非终结符A的FOLLOW(A)
- FOLLOW(A):可能在某个句型中紧跟在A后边的终结符a的集合;
- 如果A是某个句型的的最右符号,则将结束符“$”添加到FOLLOW(A)中。
例子如上,基于 FIRST 计算:
- 文法大E本身是一个句型,它也是这个句型的最右符号,因此将 $ 加入其 FOLLOW 集中;
- 接下来逐个分析产生式。
- 第一条产生式中,E’的FIRST集中的所有终结符可以跟在T的后面,所以将E’中的终结符,也就是
+
加入到T的 FOLLOW 集中; - 由于 E’ 可以推出空串,那么能跟在 E 后面的符号,就能跟在 T 后面,因此,将E的FOLLOW的$添加到T的FOLLOW中;
- 对于E’,E’是产生式中最右边的符号,因此能跟在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.非递归的预测分析法
递归的预测分析法 | 非递归的预测分析法 | |
---|---|---|
程序规模 | 程序规模较大,不需载入分析表 | 主控程序规模较小 ,需载入分析表(表较小) |
直观性 | 较好 |
较差 |
效率 | 较低 | 分析时间大约正比于待分析程序的长度 |
自动生成 | 较难 | 较易 |
总结预测分析法实现步骤
- 构造文法;
- 改造文法:消除二义性、消除左递归、消除回溯;
- 求每个变量的FIRST集和FOLLOW集,从而
求得每个候选式的SELECT集
; - 检查是不是LL(1)文法。若是,
构造预测分析表
; - 对于
递归的
预测分析,根据预测分析表为每一个非终结符编写一个过程;对于非递归的
预测分析,实现表驱动的预测分析算法;
预测分析中的错误处理
预测分析中的错误检测
两种情况下可以检测到错误:
- 栈顶的终结符和当前输入符号不匹配;
- 栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空。
预测分析中的错误恢复
可以使用恐慌模式:
- 忽略输入中的一些符号,直到输入中出现由设计者选定的
同步词法单元(synchronizing token)
集合中的某个词法单元: -
- 其效果依赖于
同步集合的选取
。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复
;
- 其效果依赖于
-
- 例如可以把
FOLLOW(A)中的所有终结符
放入非终结符A的同步记号集合;
- 例如可以把
- 如果终结符在栈顶而不能匹配,一个简单的办法就是弹出此终结符。
一个例子:
先由FOLLOW(X)得到SYNCH在哪里。