上下文无关文法中的左递归规则 [英] Left Recursive Rules in Context Free Grammar

问题描述

因此，我一直在阅读的内容都说CFG中的左递归规则无限遍历，并显示了将其转换为右递归规则的过程，并使用alpha和beta术语来表示多个非终结符（我认为我说对了）。所以在我看来，处理LL解析器时左递归规则=坏。

So everything I have been reading says that left recursive rules in a CFG traverses infinitely and proceeds to show a process of converting it to right recursive rule and accomplishes this using using alpha and beta terms to represent multiple non-terminals (I think I got that part right). So in my mind left recursive rules=bad when dealing with LL parsers.

那么是否存在左递归规则可接受/理想的情况？ ？如果不是这样，为什么左递归规则除了设计不良或用来描述右递归规则的逆（轻度使用的术语）之外还存在？

So is there a situation that left recursive rules are acceptable/desirable? If not, why do left recursive rules exist asside from bad design or term to describe the 'inverse' (term used lightly) of right recursive rules?

一个家庭作业问题，但这与我的课堂有关。

This is not technically a homework question, but it is related to my class.

推荐答案

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

The key to your question is that left recursive rules are only bad when dealing with LL parsers. If you're using a LR parser I often feel the grammar becomes much clearer. Takes for instance the standard expression grammar

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

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

Which clearly is left recursive, but is easier to read than its right recursive variant. When the parser in question has no problem dealing with the original grammar, then there would be no point in factoring this grammar to be right-recursive.

获得具有不需要epsilon规则的语法的好处，而相应的LL兼容语法则需要。

In this case you also get the benefit of having a grammar that will not require epsilon rules, which the corresponding LL compatible grammar would.

这篇关于上下文无关文法中的左递归规则的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！