如何使没有左递归的上下文无关文法包含左递归(而不改变语法的语言)？

Question

假设我们有一个上下文无关文法，如果它是在LL1中，那么它只有右联想！但是假设我想让上下文无关文法有左结合，那么它就不会停留在LL1中(这没问题)，我想为了让上下文无关文法有左结合，我应该让它有左递归。有没有一种方法可以在不改变语法语言的情况下将左递归包含到上下文无关的语法中？例如，如果我们有这个上下文无关文法：

1: S -> sum ( ELIST )
2: ELIST -> E , ELIST
3: ELIST -> E
4: E -> num
5: E -> id
6: E -> S

如何让它包含一个左递归，这样运算符"，“现在就是左关联的？

Answer 1

将您的第二个生产更改为：

2: ELIST -> ELIST，E

这不会改变语言，只会改变语言的解析方式。

此修改应适用于以级联优先样式编写的任何表达式语法。但它不是一种可以应用于任何语法的转换。