问题标签 [left-recursion]

我想解决这个语法。
S->SS+
S->SS*
S->a

我想用 action 和 goto 构建 SLR 项目集和解析表。这个语法可以在不消除左递归的情况下解析吗？这是语法单反。

描述：

在阅读Compiler Design in C book 时，我遇到了以下描述上下文无关语法的规则：

一种语法，它识别一个或多个语句的列表，每个语句都是一个算术表达式，后跟一个分号。语句由一系列以分号分隔的表达式组成，每个表达式都包含一系列由星号（用于乘法）或加号（用于加法）分隔的数字。

这是语法：

该书指出，这种递归语法有一个主要问题。几个产生式的右侧出现在左侧，如产生式 3 中（并且此属性称为左递归），并且某些解析器（例如递归下降解析器）无法处理左递归产生式。他们只是永远循环。

您可以通过考虑解析器在替换具有多个右手边的非终端时如何决定应用特定产生式来理解问题。简单的情况在产生式 7 和 8 中很明显。解析器可以通过查看下一个输入符号来选择在扩展因子时应用哪个产生式。如果此符号是数字，则编译器将应用 Production 7 并用数字替换因子。如果下一个输入符号是一个左括号，则解析器将使用产生式 8。但是，无法通过这种方式解决产生式 5 和 6 之间的选择。在产生式 6 的情况下，术语的右侧以一个因子开头，而该因子又以一个数字或左括号开头。最后，当一个术语被替换并且下一个输入符号是一个数字或左括号时，解析器希望应用 Production 6。生产 5 - 另一个右手边 - 以一个术语开始，它可以以一个因子开始，它可以以数字或左括号开始，这些符号与用于选择生产 6 的符号相同。

问题：

这本书的第二句话让我完全迷失了。因此，通过使用一些语句的示例作为（例如）5 + (7*4) + 14：

1. 因子和期限有什么区别？使用相同的示例
2. 为什么递归下降解析器不能处理左递归产生式？（解释第二个引用）。

CFG 的著名形式之一是 CNF，如您所知，它有两个非终端作为其 RHS 或一个终端作为其 RHS 和空 RHS，如果存在，则仅出现在本Wiki中描述的根的 RHS 中，但我不是确定 CNF 允许我们进行左递归吗？

我有这个语法：

其中优先事项是：

我需要删除关于优先级的左递归（并全部用 JavaCC 编写）。

你能帮我删除递归吗？

我有一个有趣的间接递归问题，我想我已经解决了，但我不确定它是否正确。

开始语法：

我的解决方案是首先在 A 上进化：

现在，有了它，我看到了我在哪里有递归并删除它，得到：

完整的解决方案将是

这个语法正确吗？

作为练习，我正在使用以下 GADT 为 Haskell 中定义的极其简单的语言实现解析器（我的项目的真正语法涉及更多表达式，但这个摘录足以解决这个问题）：

解析函数如下：

由于表达式语法的左递归性质，当我尝试解析像1+1使用expr解析器这样简单的东西时，解析器会陷入无限循环。

我已经看到了如何使用以下转换来排除网络上的左递归的示例：

变成这样的东西：

但我正在努力解决如何将其应用于我的解析器。

为了完整起见，这里是实际实现解析器的代码：

问题是，PEG（解析表达式语法）不允许左递归规则。我已经阅读了有关该主题的可用答案，但问题具体（例如这个）或非常简单（例如x = symbol:(x '.')）。

我创建了以下非常简单的语法来说明问题

可以使用PEG.js 解析器生成器测试此语法。

能“流利”使用正式语言的人描述如何将这条规则/规则集重写为 PEG？还是有一种通用的方法/算法可以解决左递归？

编辑：我刚刚找到这个 Wikipedia 页面，它描述了一种删除左递归的方法，我将对其进行研究并尝试将其应用于上面显示的语法。

删除左递归

对于 + 和 *，我相信它应该是

但是对于 - 或 /，我不确定如何删除左递归，我想出了以下一个，它是否适合 - 和 /？举个例子，对于加号，a+b = b+a，但对于减号，a - b != b -a。所以如果我们使用下面的右递归，我们会遇到像ab这样的问题吗？

任何人都知道编译器向我解释？在此先感谢。

你能帮我举个例子吗？我应该如何用这种大小进行左递归消除？我知道如何做更简单的例子。

这是解决方案吗？

我收到错误

我不确切知道我的语法的哪一部分引发了这个错误。和 1 个其他相同的错误，用于 alt 3,4

我不知道哪个部分需要重新排列以删除左递归，如果有人能指出这一点，我将不胜感激。