消除

Question

我想从以下语法删除左递归：

S -> id = E 
S -> id [ E ] = E 
E -> E [ E ] 
E -> id 

我试图遵循呈现在https://en.wikipedia.org/wiki/Left_recursion左递归去除算法，但E -> E [ E ]行带给我的问题，应该怎么它被处理？ 我不想得到一个完整的解决方案，只是一些提示，所以我实际上可以学习如何工作。

我至今尝试过是这样的：

E -> E [ E ] 
E -> id 

变为：

E -> id E' 
E' -> [ E ] E' 

这是不正确。我是否在正确的轨道上？

Answer 1

按照您链接的算法，您想要A - > A α | β，你有

E -> E [ E ] | id 

所以A是E，α是[ E ]和β是id。去除左递归的结果是A→β A'和A'→ε | α A“所以你得到的规则：

E -> id E' 
E' -> ε | [ E ] E' 

因此，它看起来像你有正确的结果，你只是离开了E” - >＆小量;规则...