●消除左递归的算法 1.把文法G的所有非终结符按任一种顺序排列 成P1,P2, n;按此顺序执行 2. FoR i: =1 To n Do BEGIN FOR j: =1 TO i-1DO 把形如P→P們的规则改写成 P>61y/|62…|6ky; (其中P→8162…16k是关于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) s→Qc|c Q→Rbb R→→Sa|a ●令它的非终结符的排序为R、Q、S 对于R,不存在直接左递归。 把R代入到Q的有关候选后,把Q的规则 变为 Q-Sab b
例 考虑文法G(S) S→Qc|c Q→Rb|b R→Sa|a 令它的非终结符的排序为R、Q、S。 对于R，不存在直接左递归。 把R代入到Q的有关候选后，把Q的规则 变为 Q→Sab | ab | b
●现在的Q不含直接左递归,把它代入到S 的有关候选后,S变成 s-Sabc|abc丨bc|c ●消除S的直接左递归后: s-abcS|bcs′|cs s′→abcS|E Q→sab|ablb R→→Sa|a ●关于Q和R的规则已是多余的,化简为 s- abcs' bcs|cS'′ s′-abcs|E (44)
现在的Q不含直接左递归，把它代入到S 的有关候选后，S变成 S→Sabc | abc | bc | c 消除S的直接左递归后： S→abcS | bcS | cS S→abcS | Q→Sab |ab | b R→Sa|a 关于Q和R的规则已是多余的，化简为： S→abcS | bcS | cS S→abcS | (4.4)
●注:对非终结符排序不同,最后所得的文法在 形式上可能不一样。但不难证明,它们都是等 价的。 ●例如,若对文法43的非终结符排序选为S、 Q、R,那么,最后所得的无左递归文法是 (课堂练习5分钟): s→Qc|c Q→Rb|b R→bcaR| cara r (4.5) R→bcaR|e 文法(44)和(45)的等价性是显然的
注：对非终结符排序不同，最后所得的文法在 形式上可能不一样。但不难证明，它们都是等 价的。 例如，若对文法(4.3)的非终结符排序选为S、 Q、R，那么，最后所得的无左递归文法是 （课堂练习5分钟）： S→Qc | c Q→Rb | b R→bcaR | caR |a R (4.5) R→ bca R | 文法(4.4)和(4.5)的等价性是显然的
2432消除回溯、提左因子 ●为了消除回溯就必须保证:对文法的任何非终 结符,当要它去匹配输入串时,能够根据它所 面临的输入符号准确地指派它的一个候选去执 行任务,并且此候选的工作结果应是确信无疑 的 ●A→a|a2..|an P A
2.4.3.2 消除回溯、提左因子 为了消除回溯就必须保证：对文法的任何非终 结符，当要它去匹配输入串时，能够根据它所 面临的输入符号准确地指派它的一个候选去执 行任务，并且此候选的工作结果应是确信无疑 的。 A→ 1 | 2 | … | n a…. S IP ... A