context-free-grammar - 上下文无关语法中的左递归规则

Question

所以我一直在阅读的所有内容都说 CFG 中的左递归规则无限遍历并继续展示将其转换为右递归规则的过程，并使用 alpha 和 beta 术语来表示多个非终结符(我想我明白了)部分正确)。所以在我心里左递归规则=坏 在处理 LL 解析器时。

那么是否存在左递归规则可接受/可取的情况？如果不是，为什么除了糟糕的设计或术语来描述右递归规则的“逆”(用得很少)之外，为什么还存在左递归规则？

这在技术上不是家庭作业问题，但它与我的类(class)有关。

Answer 1

您问题的关键是左递归规则仅在处理 LL 解析器时才是糟糕的。如果您使用 LR 解析器，我经常会觉得语法变得更加清晰。以标准表达式语法为例

E : E + T | T
T : T * F | F
F : number | ( E )

这显然是左递归的，但比它的右递归变体更容易阅读。当所讨论的解析器在处理原始文法时没有问题时，将这个文法分解为右递归就没有意义了。

在这种情况下，您还可以获得不需要 epsilon 规则的语法的好处，而相应的 LL 兼容语法会这样做。