grammar - 消除左递归

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' -> ε 规则......