问题标签 [left-recursion]

以下文法有左递归：

你如何去删除左递归。我阅读了维基百科的解释，但我对 CFG 相当陌生，所以它没有多大意义。任何帮助表示赞赏？一个简单的英文解释将更加感激。

我正在尝试实现一个 dcg，它采用 {a,b,c,d}* 形式的一组字符串。我遇到的问题是，如果我有一个形式为 s([a,c,b], [])，它返回 true，这是正确的答案，但是当我有一个 s([a,c,f],[]) 形式的查询时，它不返回答案并且它用完了本地堆栈。

这是我正在研究的语法的一部分，用于开发一个解析器工具，这对我的研究很重要。它在 ANTLR IDE 下给我一个错误在 eclipse 中说paraction, action, cspaction是相互左递归的。

我已经在网上扫描了一个解决方案，但不知道我该怎么做。由于这种语言是研究领域的标准，我没有改变语言语义细节的先决条件。

我实际上正在尝试为“Circus”创建一个语法文件，它是一种状态丰富的形式建模语言，它结合了一种称为 Z 的规范语言和一种称为 CSP（通信顺序过程）的过程建模语言，所以是的，这是一个现有语言。由于正在开发中的语言，它现在在学术界使用。我有该语言的 EBNF，我正在尝试将 EBNF 翻译成 ANTLR 中的语法。我已经设法使以下两条规则起作用。但cspaction似乎很难。

反斜杠是乳胶的一部分，现在可以省略，因为它们用作字符串。请在下面找到 Circus 的完整 EBNF。它来自已发表的论文，马戏团的指称语义。

马戏团的完整 EBNF - http://www.use.com/b1ad2df0609961615fff

我写了一个语法，但得到一个左递归错误。

我收到以下错误：

[12:41:35] 错误（210）：以下规则集是相互左递归的 [primary_expression、logical_and_expression、logical_or_expression、expression]
[12:41:35] 中止，因为以下规则是相互左递归的：[ [Lang.primary_expression,index=2,line=19], [Lang.logical_and_expression,index=5,line=36], [Lang.logical_or_expression,index=4,line=31], [Lang.expression,index=3 ,线=24]]

更正语法

我将如何消除此 CFG 中的左递归？

我想出了这个：

但似乎，当我尝试将其实现为递归下降解析器并解析诸如“ab”之类的简单字符串时，我得到了由concat生产引起的无限循环。

我是否错误地消除了左递归？

我在尝试在 prolog 中实现一个非常简单的无约束语法时遇到了一个无限递归问题。

这是我的规则：（vp -> 动词短语，np -> 名词短语，ap -> adj 短语，pp -> prep 短语）

我遇到的问题是ap的规则可以产生任意长的形容词字符串，所以在某些时候，我会通过尝试所有这些无限的可能性来满足查询。

例如，下面的查询永远不会产生 S = [put, the, red, block, on, the, green, block] 因为它会首先将左侧“red”的形容词短语扩展为无限可能，然后再尝试使用正确的。

我已经看到这个算法应该能够用来删除所有左递归。然而，我遇到了这种特殊语法的问题：

无论我尝试什么，我最终都会陷入循环或仍然是间接左递归的语法。

在这个语法上正确实现这个算法的步骤是什么？

我正在尝试解析 cpp 源语法的一个子集。以下 ANTLR4 解析器规则直接从 c++ 语言规范中复制而来（连字符被下划线代替）：

但是当 org.antlr.v4.Tool 解析语法时出现此错误：

错误（119）：cppProcessor.g4::: 以下规则集是相互左递归的 [direct_abstract_declarator]

好像是direct_abstract_declarator？左侧的语法会导致错误。我应该如何纠正它？为什么ANTLR4不支持？

手动将规则重构为这种形式不会产生错误：

那么ANTLR4在处理左递归规则时是否可以直接支持第一种语法呢？

龙书中，LL语法定义如下：

语法是 LL 当且仅当对于任何产生式A -> a|b，以下两个条件适用。

1. FIRST(a)并且FIRST(b)是不相交的。这意味着它们不能同时导出EMPTY

2. 如果b可以导出EMPTY，则a不能导出任何以 开头的字符串FOLLOW(A)，即FIRST(a)并且FOLLOW(A)必须是不相交的。

而且我知道LL语法不能递归，但是形式上的原因是什么？我猜左递归语法会与规则 2 相矛盾，对吧？例如，我写了以下语法：

因为FIRST(SA) = {a, empty}and FOLLOW(S) ={$, a}, then FIRST(SA)andFOLLOW(S)不是不相交的，所以这个文法不是 LL。但我不知道是左递归makeFIRST(SA)而FOLLOW(S)不是不相交，还是有其他原因？换句话说，是否每个左递归文法都会有一个违反 LL 文法条件 2 的产生式？

我正在编写一个 antlr 语法，我希望能够在其中嵌套表达式，它可以是“简单”表达式或布尔表达式（带有可选括号）。一个简单的表达式只是一个带有 lhs 和 rhs 的表达式，例如a = 5

我希望能够支持这些类型的表达式：

我的语法看起来像：

我收到一个错误，expr并且booleanExpr是相互递归的。我理解为什么会发生这种情况，但是如果我希望能够在彼此之间嵌套布尔表达式，我不确定如何解决这个问题。