国防科技大学：《编译原理》课程电子教案（PPT教学课件）第4章 语法分析——自上而下分析

消除左递归的算法： 1.把文法G的所有非终结符按任一种顺序排列成P1， P2,,Pn:按此顺序执行； 2.FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如P→PY的规则改写成 P1→δlδ2l.…δkY; (其中P→δ⑧2.…⑧k是关于P的所有规则) 消除关于P规则的直接左递归性 END 3.化简由2所得的文法。去除那些从开始符号出发永 远无法到达的非终结符的产生规则。 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 消除左递归的算法: 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) S→Qclc Q→Rbb R→Sala ■令它的非终结符的排序为R、Q、S。 ■对于R,不存在直接左递归。 ■ 把R代入到Q的有关候选后，把Q的规则 变为 Q-Sab ab|b 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 例 考虑文法G(S) S→Qc|c Q→Rb|b R→Sa|a ◼ 令它的非终结符的排序为R、Q、S。 ◼ 对于R，不存在直接左递归。 ◼ 把R代入到Q的有关候选后，把Q的规则 变为 Q→Sab | ab | b

■ 例考虑文法G(S) SQc|c Q→Rblb R-Sala ■令它的非终结符的排序为R、Q、S。 ■( Q的规则变为 Q→Sab ab b ■现在的Q不含直接左递归，把它代入到S 的有关候选后，S变成 S→Sabc abc bc|c 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 例 考虑文法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→Rblb R→Sala ■ S变成 S→Sabc abc bc c ■消除S的直接左递归后： S→abcS'|bcS'|cs' S'→abcS'|e Q→Sab |ab b R→Saa 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 例 考虑文法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) S→Qclc Q→Rblb R-Sala ■消除S的直接左递归后： S→abcS'|bcS'|cS' S'→abcS'|e QSab |ab|b R-Sala ■关于Q和R的规则已是多余的，化简为： S-abcS'bcS'cS' S'→abcS'le (4.4) 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 例 考虑文法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)