问题标签 [left-recursion]

我是左递归和左因子这个话题的新手，请帮助我确定这个语法是左递归还是左因子，如果是，那为什么？

S-> aAd | bBd | 阿贝 | 氨基酸 | 钙| CB

标准方法很容易将不是 LL(1) 的上下文无关文法转换为等价的文法。是否有任何可用的工具可以自动执行此过程？

在下面的示例中，我对非终端使用大写字母，对终端使用小写。

以下左递归非终结符：

可以转化为右递归形式：

请注意，左递归产生式规则确保表达式与左相关联，右递归产生式也是如此；因此语法修改也会改变表达式的关联性。

另一个问题是间接左递归，例如：

左因子也用于确保解析器只需要一个前瞻标记。以下产生式必须向前看两个标记：

这也可以重构；至：

是否有任何软件工具可以自动化这些语法转换？从而产生适用于 LL(1) 解析器的等效语法？

我很怀念，所以我决定写一个冒险游戏创作者，允许用户输入复杂的句子。

我已经手动滚动了一个使用访问者模式的词法分析器和解析器，它工作得很好，直到我遇到了我的 BNF（Backus-Naur 形式）规则之一的左递归问题：

按照这个 wiki 条目删除左递归后，这看起来正确吗？

编辑：

我按照此处给出的指南使用 C# 手动滚动词法分析器和解析器给出的指南使用 C# 手动滚动词法分析器和解析器。我没有为这个练习使用任何解析器生成器。

另外，我从这个网站获得了解析器的 BNF 规则。

我正在使用 Java 目标。我有以下简单的语法：

现在我希望我的解析器在进入规则 alpha 时Hello World for something打印。Hello World for otherthing所以我想通过以下方式修改我的语法：

但这会导致解析器抛出规则项相互左递归的错误。此错误是由于在左递归替代方案中使用了任何 {...} 语句。

我还有什么其他选择，因为这似乎是一个错误/可以在 ANTLR4 中改进？

下面是一个 ANTLR 语法的片段，它可以正常工作。

它旨在成为一个 tex 解析器。

如果我everywhere通过取消注释来修改规则| text，ANTLR 会报告规则中的左递归escSeq ，我认为这很有趣。
我找不到左递归：要么我是盲人，要么我误解了左递归是什么。

有什么建议么？

以下语法说明了这个问题：

给定输入“a，b，c”我得到监听器事件跟踪输出

其中(表示输入 punctuated，)表示exit punctuated，为了简洁明了，省略了所有其他规则。

通过检查，这种侦听器事件的顺序代表了一个右关联解析。

常见做法和 The Definitive Antlr 4 Reference 让我期待左关联解析，对应于以下侦听器事件跟踪

我的语法、我的期望、我对听众事件的解释或其他什么有问题吗？

有几次我在 Antlr 中编写语法时遇到了左递归，这就是为什么我问自己为什么没有自动工具可以删除它。在我做了一些研究之后，我发现了两种处理这个问题的方法 - Paull 算法和 Robert C. Moore 的工作中讨论的左角变换Removing Left Recursion from Context-Free Grammars, 2000。我注意到 Paull 的算法是一种非常不切实际的算法，但另一方面，左角变换只会增加语法规则的数量，O(n)但O(n^2)大多数时候比这要低得多，这使得该算法非常有效。所以我的问题是：左递归删除是不是故意将责任留给语法实现者，还是不被视为一种选择？

我正在尝试编写一个 lambda 演算解析器，我定义的语法似乎不在 LLR 中：

我减少左递归：

好像不对，有大神帮忙吗？

我想出了以下强制优先级的语法：

其中 ID 可以是一个字母，num 是一个整数。

问题

我可以解析以下字符串：

我无法解析以下字符串：

我的问题是 A 引入了递归问题。因为我不想做回溯。我必须通过重写语法来解决这个问题。我一直在看这个链接。但是，我尝试的修复也不起作用。有人可以帮忙吗？

尝试的解决方案：

但是，我认为这改变了我的语法定义，仍然是递归的，不允许我解决a[i] + 1 or a[a[i]*i]

附加信息：

我实际上是在 antlr 中实现的。我尝试使用语法谓词来解决这个问题，但这并没有帮助。也许我没有正确使用它们？

我将继续对此进行破解，但我越想越困惑。有人可以帮帮我吗？这是我遇到的一个概念问题，我认为如何正确设置没有回溯的语法。但是如果我想正确地制作自己的自定义工具，我将不得不这样做。

So, I was wondering what makes a parser like:

left recursive and invalid, while a parser like

is valid and works even though the definition of 'basic' still refers to 'expression'. In particular, I'd like to be able to parse expressions in the form of

without introducing operations acting on more than two operands.