问题标签 [left-recursion]

我的语法似乎有间接左递归的情况，看了一些其他类似的问题，无法在它们和我的语法之间建立心理联系，我不知道如何解决它。

A'A从but A'is cor调用A，这导致了左递归，如何在消除左递归的同时将其重新排列为等效语法？

我有以下 antlr4 语法，我得到相互左递归错误，我该如何解决？

我正在使用具有以下形式的左递归语法的 Scala 的 PackratParsers（解析器组合器）

我希望二元运算符“：”是左关联的，这样表单的表达式x1:x2:...:xn将被解析为(((x1:x2):x3):...:xn)，即导致表单的 AST FunctionCall(":", FunctionCall(":", FunctionCall(":", x1, x2), x3), ...)。

令人惊讶的是，使用上面定义的 PackratParsers 语法，生成的 AST 仍然是右关联的。为什么会出现这种情况，可以做些什么来改变这种情况？

我发现了这个关于 Scala 解析器组合器和运算符关联性的讨论，但它似乎没有在这里回答我的问题。

无限期地重复function_call.parseAll("aaa(1)")。很明显，是因为 1 不能插入名字，而名字进入了function_call，它尝试了名字，进入了函数调用。您如何解决此类情况？

有一种解决方案可以将名称简化为简单标识符

但我不喜欢这样做，因为name ::= identifier | function_call在 VHDL 规范中是 BNF-ed，并且function_call可能在其他地方共享。出于同样的原因，此处发现的左递归消除是不可取的

顺便说一句，我还想知道，如果我修复了错误，name.parseAll 会仅使用“aaa”作为名称规则中的第一个替代方案，还是使用整个“aaa(1)”？如何在仅消费 aaa 之前命名以消费整个 aaa(1)？我想我应该将 function_call 作为名称中的第一个替代项，但在这种情况下它会更加急切地堆栈溢出？

我目前正在研究一种Xtext语法，并遇到了左递归图的一些问题。我已经在我的语法中消除了所有直接左递归，但现在我有一些间接左递归，它们在 IDE 中显示为消息This rule call is part of a left recursive call graph.

这是我的问题的一个例子：

我怎样才能解决这样的左递归？

从以下语法中删除左递归：

Q.1

Q.2

我知道删除左递归的规则，但我很困惑。因此，如果有人请发布此语法的答案，那将很有帮助。

从评论更新：

我知道这 2 是左递归语法：

而且我知道如何从这些语法中删除左递归，但是其他语法呢？

我知道与递归下降解析器一起使用的语法有两种类型的限制。

1. 语法不能有任何左递归产生式
2. 语法不能要求超过标记前瞻。

我理解第一个，但对第二个限制有点迷茫。为什么这个限制是必要的，没有它，生产甚至可以存在吗？

我正在为布尔表达式编写递归下降解析器，例如：

其中 1 是“真”，0 是“假”，+ 是“或”，* 是“和”，~ 是“非”，“c”只是一些变量名（它可以是任何单个字母）。我计划使用括号而不是实现某种操作顺序。

我当前的解析器可以识别以下表达形式

但我不确定我将如何在此之上实现 + 和 *。从我所读到的明显实现中，我相当确定

会导致无限循环，因为它是“左递归”的。我不确定如何更改它以消除这种无限递归。

我的语法在第六个生产规则中有左递归的情况。

我通过像这样替换规则 6 和 7 解决了这个问题：

我在这个语法中找不到任何间接的左递归。

唯一困扰我的是最终的生产规则，它有一个终端被两个非终端包围。

我的两个问题是：

• 我解决的左递归是否正确？
• 最终的生产规则是左递归吗？我不确定如何处理这种特殊情况。

我试图解决一个练习题，但是当我尝试将示例答案与我的答案进行比较时遇到了一个问题。这是转换前的语法：

开始符号是E，其他非终结符号是S和D。

我的回答是：

在示例答案中，他们没有S-> DS'，而 E 变为E-> DS'*。由于书中使用的去除左递归的方法，

应该有一个S-> DS'。我现在对此感到困惑，也许我只是不明白这种方法。任何人都可以给我任何提示吗？还有你能告诉我这里星号的含义*吗？非常感谢！