消除左递归的算法: 1.把文法G的所有非终结符按任一种顺序排列成P1 P2,Pn按此顺序执行; 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO Py的规则改写成 把形如P P 81y82y... Okr (其中P→1是关于P的所有规则) 消除关于P规则的直接左递归性 END 3.化简由2所得的文法。去除那些从开始符号出发永 远无法到达的非终结符的产生规则。 编译原理
编译原理 ◼ 消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列成P1， P2，…，Pn；按此顺序执行； 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如Pi→Pj 的规则改写成 Pi→1 |2 |…|k ; (其中Pj→1 |2 |…|k是关于Pj的所有规则) 消除关于Pi规则的直接左递归性 END 3. 化简由2所得的文法。去除那些从开始符号出发永 远无法到达的非终结符的产生规则
例考虑文法G(S) →Qc|c Q→Rb|b R→Sa|a 令它的非终结符的排序为R、Q、S 对于R,不存在直接左递归。 把R代入到Q的有关候选后,把Q的规则 变为 Q→Sab|ab|b 编译原理
编译原理 ◼ 例 考虑文法G(S) S→Qc|c Q→Rb|b R→Sa|a ◼ 令它的非终结符的排序为R、Q、S。 ◼ 对于R，不存在直接左递归。 ◼ 把R代入到Q的有关候选后，把Q的规则 变为 Q→Sab | ab | b
例考虑文法G(S) s→Qc|c →→→ Q→Rb|b R→Sa|a 令它的非终结符的排序为R、Q、S ■Q的规则变为 Q→Sab|ab|b ■现在的Q不含直接左递归,把它代入到S 的有关候选后,S变成 s→ Sabc abc bc|c 编译原理
编译原理 ◼ 例 考虑文法G(S) S→Qc|c Q→Rb|b R→Sa|a ◼ 令它的非终结符的排序为R、Q、S。 ◼ Q的规则变为 Q→Sab | ab | b ◼ 现在的Q不含直接左递归，把它代入到S 的有关候选后，S变成 S→Sabc | abc | bc | c
例考虑文法G(S) S→Qc|c Q→Rb|b R→Sa|a ■S变成 s→Sabc abc bc 消除S的直接左递归后: s→abcs'bcs'c s'→abcs' Q→Sab|ab|b R→Sa|a 编译原理
编译原理 ◼ 例 考虑文法G(S) S→Qc|c Q→Rb|b R→Sa|a ◼ S变成 S→Sabc | abc | bc | c ◼ 消除S的直接左递归后： S→abcS | bcS | cS S→abcS | Q→Sab |ab | b R→Sa|a
例考虑文法G(S) →Qc|c Q→Rb|b R→Sa|a 消除S的直接左递归后: s→abcs'bcs'cs s'→abcs'| Q→ Sab lab R→Sa|a 关于Q和R的规则已是多余的,化简为: s→abcs'bcs'cs s'→abcs' (4.4) 编译原理
编译原理 ◼ 例 考虑文法G(S) S→Qc|c Q→Rb|b R→Sa|a ◼ 消除S的直接左递归后： S→abcS | bcS | cS S→abcS | Q→Sab |ab | b R→Sa|a ◼ 关于Q和R的规则已是多余的，化简为： S→abcS | bcS | cS S→abcS | (4.4)