问题标签 [left-recursion]

试图弄清楚在上下文无关语法中删除左递归。我习惯了某些形式，但这个让我有点困惑。

我还必须设计一个像样的解析器，我可以做到。然而，弄清楚这个左递归（尤其是第一个递归）让我感到困惑。

如何删除以下规则的左递归：

S -> aSAbb | 氨基酸

我了解如何在 S -> SA 上执行它 | 一个

变成 S -> A | 作为'; S' -> A | AS'，但终端在这个问题上让我失望。

编辑：

抱歉，显然我对左递归是什么感到困惑。我应该问如何从右侧删除左侧符号。

我有一个我正在尝试构建的新通用编程语言的语法文件。我试图使该语言健壮且易于使用（它深受 Ruby 等的启发），并且在此过程中我引入了一些左递归规则。

我见过一些似乎表明以下左递归规则的示例：

可以通过将其更改为非左递归：

对我来说，这看起来会有不同的问题并且仍然会失败。我是对的，还是这“行得通”？

我试图（查找和）消除的特定左递归可在此语法文件中找到。我不确定哪些规则会受到影响，但至少有一些规则被指出具有左递归。（顺便说一句，我试图通过收紧范围规则来消除他提到的特定范围问题。）

我们有一些非程序员编写的 vb6 代码片段（仅使用功能的子集）。这些被称为规则。对于编写这些的人来说，他们很难调试，所以有人写了一种附加的解析器来评估子表达式，从而更好地显示问题所在。

这个临时解析器非常糟糕，并且不能真正工作。所以我试图编写一个真正的解析器（因为我是手工编写的（没有解析器生成器我可以用 vb6 后端理解）我想使用递归体面的解析器）。我不得不对语法进行逆向工程，因为我可以找到任何东西。（最终我发现了一些东西http://www.notebar.com/GoldParserEngine.html但它的 LALR 和它的方式比我需要的要大）

这是VB子集的语法。

总而言之，它工作得很好，这里有一些简单的例子：

好像

现在我的问题是什么？

如果你有这样的代码，(( true OR false ) AND true)我有一个无限递归，但真正的问题是 (true OR false) AND true（在第一个之后( expr )）被理解为 only (true or false)。

这是Parstree：

那么如何解决这个问题。我应该以某种方式更改语法还是使用一些实施技巧？

万一你需要它，一些很难的例子。

我有一个小的自定义脚本语言，我正在尝试更新它以允许布尔表达式，例如a > 2and a > 2 and (b < 3 or c > 5)。这是我在这里遇到麻烦的括号表达式。

这是一个（根据@Bart Kiers 的回答从原始帖子开始编辑）显示问题的完整语法。这是我实际语法的精简版，但问题也出现在这里。

我尝试a > 2 or (b < 3)在规则中的注释行中容纳括号布尔表达式atom。当我取消注释这一行并将其包含在语法中时，ANTLR 给了我这个错误：

[致命] 规则原子具有非 LL(*) 决策，因为可以从 alts 1,2 访问递归规则调用。通过左分解或使用句法谓词或使用 backtrack=true 选项来解决。

我想通过删除递归来解决这个问题，但我似乎无法从维基百科关于如何删除左递归的描述过渡到我自己的东西。

在使用这种语法时，有时我希望将statement输入用作根，例如abc = 2 + 3，它为名为 abc 的变量分配一个值。其他时候，我想使用语法来评估一个boolean以输入为根的表达式，例如abc > 3 and (xyz < 5 or xyz > 10). 当我尝试使用@Bart 的答案作为模型时，它运行良好，直到我尝试将 bystatement使用的语法部分与boolean. 他们都应该能够使用expression，但这就是我遇到这个左递归错误的地方。

那么，我怎样才能既处理括号又避免左递归问题呢？

我正在尝试在 prolog 中解决 DCG 语法并成功了，我一直在评估涉及这些大括号的表达式。 expr( T, [’(’, 5, +, 4, ’)’, *, 7], []),

我明天要复习考试，并且要复习前几年的考试。

在测试是语法。

我已经尝试并花了几个小时研究如何做到这一点，但无法弄清楚。

我看过用epsilion代替东西，但没有信心。

我认为我需要创建一个 Foo' 和一个 Bar' 然后添加 epsilon 规则，但我不确定。

有人可以告诉我（简单）_如何将其更改为具有 LL(1) 能力的语法

提前致谢

我正在为咖啡脚本语法编写 Antlr/Xtext 解析器。现在才刚刚开始，我只是移动了原始语法的一个子集，而且我被表达式所困。这是可怕的“规则表达式具有非 LL(*) 决策”错误。我在这里找到了一些相关的问题，Help with left factoring a grammar to remove left recursion和ANTLR Grammar for expressions。我还尝试了 How to remove global backtracking from your grammar，但它只是演示了一个我在现实生活中无法使用的非常简单的案例。关于ANTLR Grammar Tip: LL() and Left Factoring的帖子给了我更多的见解，但我仍然无法掌握。

我的问题是如何修复以下语法（对不起，我无法简化它并仍然保留错误）。我想麻烦制造者是term规则，所以我很感激对它进行本地修复，而不是改变整个事情（我试图保持接近原始语法的规则）。也欢迎指针提示如何在您的脑海中“调试”这种错误的语法。

更新：最终解决方案将使用 Xtext 和外部词法分析器，以避免处理重要空白的复杂性。这是我的 Xtext 版本的一个片段：

我的策略是首先在没有可用 AST 的情况下制作一个可以工作的 Antlr 解析器。（好吧，如果这是一种可行的方法，那么值得提出一个单独的问题。）所以我现在不关心令牌，它们被包括在内是为了使开发更容易。

我知道原始语法是LR。我不知道在变身为LL时我能离它有多近。

UPDATE2 和解决方案：我可以通过从 Bart 的回答中获得的见解来简化我的问题。这是一个有效的玩具语法，用于处理带有函数调用的简单表达式来说明它。之前的评论expression显示了我的洞察力。

我的语言使用带有一个附加功能的 s 表达式 - 用于访问数组或结构中的元素的点运算符。

目前，我的解析器使用access运算符处理此代码 -

但是，我想使用像这样的点运算符添加备用解析 -

它们都将解析为等效的 AST。左递归在这里很重要，因为像这样的表达式(f x).y应该像这样解析出来(access :m:y (f x))

但是，我不知道如何让 FParsec 处理这种类型的左递归解析，或者我有什么替代左递归的方法。

我正在尝试使用 ANTLR 解析一种语言，它可以包含以下语法：

这是我到目前为止提出的 ANTLR 语法，并access_operation抛出错误

The following sets of rules are mutually left-recursive [access_operation, expression]：

到目前为止，我可以管理的是重构生成 AST 的access_operation规则，'.' expression其中access_operation节点仅包含操作的右侧。

我正在寻找的是这样的东西：

在这种情况下如何解决左递归问题？