消除左递归

为什么要消除左递归? 在自顶向下的分析中，如果不消除左递归，就会陷入死循环。例如，在后面要说到的递归向下的分析中，就是一个“从前有座山，山里有个庙…”这样，一直递归下去；使用非递归的时候也是一样，需要计算一个FIRST集合，这个集合本身也是一个递归的计算方式，如果有左递归，同样会无限的递归下去。

消除左递归，就是为了可以进行自顶向下的语法分析

有如下文法： A→Aα|β 如果不明白要怎么消除，首先来看一下它能产生什么语言？

对开始符号A开始推导，如果用若干次A→Aα替换句型中的A，最终开始符号可以推导出一个句型Aααα...，如果想推导出一个句子，就一定会使用A→β这个产生式，所以，最终推导出的句子为β或βα...[1,∞)多个阿尔法

既然知道了语言，既可以重写它的文法：

经过分析，文法推导出的句子必然以β开头，后面跟0到多个α。

使用产生式A→βA'产生以β开头的句子，使用A'→αA'|ε产生[0,∞)个α。

所以文法被改写为 A→βA' A'→αA'|ε

消除下面文法的左递归： E→E+T|T T→T*F|F F→(E)|i

上面的文法有两条直接左递归

E→E+T|T和T→T*F|F，形如A→Aα|β，所以可以直接套上面的结论，或者也可以向上面的分析过程一样，通过它产生的语言进行消除左递归。

拿E→E+T|T再分析一遍，这两个产生式最终产生的句型/句子是T{+T}{+T}表示[0,+∞)个“+T”。

所以，使用E→TE'产生以T开头的句型/句子；使用E'→+TE'|ε产生若干个+T。

E→E+T消除左递归后变成： E→TE' E'→+TE'|ε 同理，T→T*F|F消除左递归： T→FT' T'→*FT'|ε

考虑如下文法：

A→Aα1|Aα2|…|Aαm|β1|β2|…|βn

产生的句子为：

βiαj1αj2…

所以，消除递归后文法为：

A→(β1|β2|…|βn)A’ 用来产生以βi开头的句型/句子 A’→(α1|α2|…|αm)A’|ε

间接左递归的消除方式，经过若干步推导，将间接左递归变成直接左递归，然后在使用消除直接左递归的方式消除间接左递归

A→Bc A→d B→aA B→Ab

首先，经过推导（替换），文法变为 A→Abc|aAc|d

A→Abc|aAc|d形如A→Aα|β|β'，消除直接左递归：

A→(aAc|d)A' A'→bcA'|ε

对于更复杂的文法，应用消除直接左递归和间接左递归的方式可能不能消除干净，所以接下来介绍更一般的方式

什么是有环文法？答：经过不少于1步推导，可以由A推导出A，这样的文法称作有环文法。

消除的算法：

1）按照某个顺序，将产生式排序为A1,A2,…,An

注意，一般将开始符号放在最后，因为接下来的步骤是将排在上面的符号带入下面的产生式，将开始符号放在最后，最终的结果就是开始符号→......

3)消除多余产生式

G(S): S→Qc|c Q→Rb|b R→Sa|a

Q→Rb|b R→Sa|a S→Qc|c

考察 Q→Rb|b

在这个产生式之前，没有其他产生式，所以不进行带入操作；然后，这个产生式也不存在直接左递归，这个产生式考察完毕。

每次考察都是带入，然后消除直接左递归（如果存在）

考察R→Sa|a

在这个产生式之前，存在Q→Rb|b，并不可以带入替换，所以带入操作完成，R→Sa|a不存在直接左递归，考察完成。

考察S→Qc|c

在这个产生式之前，存在Q→Rb|b和R→Sa|a；首先，带入第一个产生式，得到S→Rbc|bc|c，带入第二个产生式，S→Sabc|abc|bc|c，存在直接左递归，消除得到: S→(abc|bc|c)S' S'→abcS'|ε

消除多余的Q和R的产生式，最终得到文法： S→(abc|bc|c)S' S'→abcS'|ε

上面的例子并不能完全描述这个算法，还有一些细节的东西。

怎么保证一个文法中没有左递归？

将文法的非终结符进行排序后，如果存在形如Ai→Am…的产生式，若m>i成立，则不会产生左递归。

举个例子： A1→a A2→A3b A3→A4c A4→d

符合这样的文法的每一个产生式，如果能带入，则只能带入在他“下面”的产生式，也就是说，带入后产生式的右部即使是非终结符号，也不可能和左部相同。

应用上面的算法，外层循环每次选择一个产生式Ai，经过内层循环的替换、消除直接递归，最终，得到形如Ai→Am的产生式一定满足m>i