3 消除左递归
这里所说的左递归是指这样的推导（\alpha 是一个串）： $$ A\Rightarrow^+A\alpha $$ 我们后面要用自根向下的分析方法，这样的产生式在构建分析树时会导致无限循环，所以要消除左递归。
观察到左递归导致的串集可能是 $$ A\alpha\alpha\alpha\cdots $$ 形式的，我们的思路是把左递归改成右递归。假设原来的左递归产生式是
- A→A\alpha|\beta
可以用相应的非左递归文法
- A→\beta A'
- A'→\alpha A'|\varepsilon
来替代。
更一般地，产生式
- A→A\alpha_1|...|A\alpha_m|\beta_1|...|\beta_n
可以用
- A→\beta_1A'|...|\beta_nA'
- A'→\alpha_1A'|...|\alpha_mA'|\varepsilon
来替代。
只要理解了左递归文法产生的句型结构，就不难写。
间接左递归
如何消除两步或多步推导产生的左递归？
- S→Aa|b
- A→Sd|\varepsilon
这里 S\Rightarrow Aa\Rightarrow Sda 是左递归形式的，我们可以把多次推导直接带入到第二个产生式里，即第二个产生式变成
- A→Aad|bd|\varepsilon
对这个式子消除直接的左递归即可。
隐藏左递归
间接左递归的特例，如
- A→BAd
- B→\varepsilon
根据上面的思路来操作。
左递归消除算法
- 把所有形如 A_i→A_j\alpha （即右部以非终结符开头的）的产生式，用 A_j→\delta_1|...|\delta_k （所有的 A_j 产生式）来替换 A_j，直到不含这种产生式为止
- 消除替换后的文法的左递归