为什么消除左递归算法要求输入不能有空产生式 - 编译原理吧

level 3

初始状态0 楼主

如果文法中含有空产生式，会对算法有什么影响吗？
我尝试了这个文法：
S→Aa|b|ε
A→Aa|Sc|ε
最终可以得到消除后的文法：
S→Aa|b|ε
A→bcA'|cA'|A'
A'→aA'|acA'|ε
似乎空产生式对这个算法没有影响

2021年07月13日 09点07分 1

level 13

对什么算法有影响？这两者有关系吗？

2021年07月16日 00点07分 2

level 13

不要做无谓的联想，一个算法就管好一个算法要做的事，这个就是根除左递归的算法，照做就能消除左递归

2021年07月16日 00点07分 3

我想问的是，这个算法的输入不是要求了“不含空产生式的文法”吗，如果文法包含空产生式，这个算法还可以正确消除左递归吗

2021年07月16日 05点07分

这个算法为什么要特别强调不能有空产生式

2021年07月16日 05点07分

level 13

phusker

存在空产生式时，有可能存在隐性的左递归，情况复杂。
比方说如下这种情况：
S→ASb|d
A→Aa|ε

2021年08月01日 08点08分 4

理解了，谢谢

2021年08月01日 11点08分