问题标签 [left-recursion]

我正在尝试从以下语法中删除左递归：

我尝试遵循https://en.wikipedia.org/wiki/Left_recursion提供的左递归删除算法，但该E -> E [ E ]行给我带来了问题，应该如何处理？我不想得到一个完整的解决方案，只是一些提示，所以我可以真正了解它是如何工作的。

到目前为止，我尝试过的是：

变成：

这是不正确的。我什至在正确的轨道上吗？

我正在为 COOL（面向对象的课堂语言）编写解析器/词法分析器。您可以在以下链接中查看语法：（手册的最后一页）

http://theory.stanford.edu/~aiken/software/cool/cool-manual.pdf

我正在使用 ANTLR 编写此程序，并使用以下输入，我希望得到以下输出：

输入 ：

输出 ：

但我得到的输出是：

这是我的解析器/词法分析器代码：

这是ANTLR中COOL语法的代码版本。主代码中注释的部分已消除歧义（意味着消除了歧义！），并在第二部分（数学规则）中消除了左递归。

谁能指出这哪里出错了，为什么我没有得到想要的输出？

提前致谢！

这是 SQL 选择语句的简单语法

该工具对sql_query定义和定义唠叨不休attribute_list。老实说，我在我的代码中没有看到任何左递归。

谁能解释发生了什么？

我想要一个仅包含二进制非终结符的语法和评估器（ANTLR parse tree walker），而无需在访问表达式节点以确定要执行的操作时打开运算符（例如左分解语法的情况） ，因为访问者会访问一个“additionNode”，所以访问者可以静态假设它必须进行添加）。

相当直接的问题。ANTLR 支持左递归，所以这是一个有效的语法

很漂亮，但是任何用于此的 walker/visitor/compiler-back-end 现在都必须对类型进行自己的调度，这很糟糕：

该策略的优缺点：

• antlr 为我构建了一个二叉树，其中（二进制）每个规则都有一个左右参数，这意味着我不必担心 kleene 闭包的 while 循环。我真的很喜欢这个
• 我必须手动调度（切换）令牌，而不是节点的类型。

使用更传统且已经左分解的语法

相应的访问者与上面的两个语法具有相反的优点和缺点：ANTLR 将为我执行此类型的调度——嗯，大多数情况下，仍然必须区分“+”和“-”——但现在我有了为那些 kleene 闭包包含 while 循环，因为我没有严格的二叉树了，这很烦人。

我想我理想的语法应该是这样的

这将解决我所有的问题，当然这在 ANTLR 中是非法的

但是在 A' 生产中仍然存在间接递归

那么如何删除这个或者我做错了什么

这是编译器原则实践和工具中的问题 4.3.1

我有这部分语法

我需要使用它来创建一些 SD 集，然后在解析表上创建。

但是，在此之前，我应该将其转换为自上而下的可解析语法。

我的问题是你是怎么做到的？我知道你必须摆脱左递归，但我该怎么做呢？

我阅读了维基百科的文章和其他一些来自大学的文章，但我无法理解我应该如何去做。

你能给我一些帮助吗？

我正在尝试转换以下语法产生式

到 Haskell 中的 Parsec 表达式。

显然问题是它是左递归的，所以我试图解析它递归上升的风格。我试图实现的伪代码是：

我尝试将其翻译成 Haskell 是：

其中primaryExpr有类型IParser Expr ，IParser 定义为

然而，这给了我以下类型错误：

如何修复此类型错误？

我正在学习 ANTLR4，我一度感到困惑。对于类似 Java 的语言，我正在尝试为成员链等结构添加规则，如下所示：

我收到一个错误，说我的两个规则是相互左递归的：

我想我明白为什么上述规则组合被认为是左递归的：因为memberAccess是的候选者expression并且memberAccess以expression.

但是，当我看到（通过查看Java 示例）如果我只是将 to 的内容移动memberAccess到expressionANTLR4 时，我的理解就崩溃了（即使它仍然没有解析我想要的内容，似乎陷入了一个循环）：

1. 为什么第一个例子是左递归的，而第二个不是？
2. 我该怎么做才能真正解析初始行？

我在 SO 上找到的每个解决方案都是“切换到 ANTLR4”，这并不是一个真正的选择，因为我正在使用antlr4ruby（这是 ANTLR3，4 的意思是“for”）。

我想建立一个属性访问规则，它应该匹配这样的内容：

这就是我所拥有的：

（VARIABLE并且ACCESS是稍后使用的解析器标记，NAME是一种字符串）。

这显然是左递归的，但我不知道如何解决这个问题。

我正在尝试创建自己的分析器/解析器。

我有一个问题，我理解它为什么不起作用，但我不确定如何解决它。

这是我的解析器问题部分的代码。

如您所见，问题来自OR 部分中三个选项中最后两个选项的Condition()方法。这是因为Expression()最终会变成“( Expression() )”，因此第三个和第二个选项都可以以左括号标记开头。

但是，我不确定如何解决这个问题。我之前在解析器中解决了一个类似的问题，但是由于Expression() --> Term() --> Factor()的方式和问题代码都是在Factor()方法中。

任何建议将不胜感激。

谢谢，

托马斯。

编辑：

有关更多信息，我将提供应该与此解析器一起使用但不会由于上述错误而导致的代码示例。

上述方法将成功运行，因为它使用了Condition()方法的第二种替代方法。

上述方法将失败，因为它需要使用第三种替代方法，但是由于 '(' 导致解析器调用第二种替代方法，它无法访问它。