编译原理语法分析.pptVIP

切断循环推导中的某个连接的方法： Step1. 对n个产生式中的某一个进行至多 n-1次替换, 使间接左递归变成直 接左递归, 再消除之。 例如, 消除上述文法G[S]中S,Q间的连接: S? Qc|c? Rbc|bc|c? Sabc|abc|bc|c 改写为: S→abcS|bcS|cS S→abcS|ε 消除左递归还需消除Q,R间的连接: Q? Rb|b? Sab|ab|Qab|b 再消除其直接左递归… Step2. 对其余n-1个产生式中的某一个进行 至多n-2次替换,再消除直接左递归。 … 考虑上述文法的后两个产生式: Q→Rb | b R→Sa | a | Qa 消除左递归算法: (1)文法的所有非终结符排序为A1,A2,…,An; (2)将间接左递归改为直接左递归,消除之; for (i=1; i=n; i++) {for (j=1; j=i?1; j++) 把Ai→Ajγ| ?及Aj→δ1|…|δk 改写为Ai→δ1γ|…|δkγ| ? ; 消除Ai的直接左递归; } (3)化简, 删去那些不可达元的产生式。 通过例子熟悉消除左递归算法执行过程: 例如, G[S]: S→Qc | c Q→Rb | b R→Sa | a (1) 将非终结符排序为R, Q, S; (2) 对于R (i=1, P1) 内层循环不执行; 消除R的直接左递归: R→Sa|a 对于Q (i=2, P2) 内层循环改写P2→ P1γ: Q→Sab|ab|b 消除Q的直接左递归: Q→Sab|ab|b 对于S (i=3, P3) 内层循环改写P3→P1γ和P3→P2γ: S→Sabc | abc | bc | c 消除S的直接左递归: S→abcS | bcS | cS S→abcS |ε 于是得文法G[S]: S→abcS | bcS | cS S→abcS |ε Q→Sab | ab | b R→Sa | a (3) 化简, 删去关于Q和R的产生式。 对消除左递归算法的两点说明: (1)消除左递归算法有两个限制条件:文法中不含回路(P P)和ε-生成式。该限制不会影响消除左递归算法的使用,因为后续课程《形式语言》中将学到,对任一CFG G, 存在一个不含ε-生成式和单一生成式的CFG G, 使得L(G)=L(G)-{ε}。 (2) 对非终结符的不同排序会导致文法形式上的不同, 但可证明它们等价。 上例若排序为S,Q,R, 则得文法G[S]: S→Qc | c Q→Rb | b R→bcaR |caR |aR R→bcaR |ε G[S]与G[S]等价的证明: 证明: S?…?abc(abc)*|bc(abc)*|c(abc)* L(G)={(abc|bc|c)(abc)i | i≥0} S?…?bca(bca)*bc|ca(bca)*bc| a(bca)*bc|bc|c L(G)={(abc|bc|c)(abc)i | i≥0} 有兴趣的同学课后以下述文法为例 熟悉消除左递归算法的执行过程: G[S]: S→Qc | c | Rc Q→Rb | b | Sb R→Sa | a