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

Question

假设我们有一个上下文无关的语法，如果它在LL[1]中，那么它只有右Association！但假设我想让这个上下文无关语法有一个左联想，那么它就不会停留在LL[1]中(这没关系(我想，为了使上下文无关语法具有左联想，我应该使其具有左递归。有没有一种方法可以在不改变语法语言的情况下将左递归包含到上下文无关的语法中？例如，如果我们有这个上下文无关的语法：

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

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

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