问题标签 [left-recursion]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
5127 浏览

recursion - 从 CFG 中删除左递归

以下文法有左递归:

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

0 投票
2 回答
1492 浏览

prolog - DCG 和左递归

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

0 投票
1 回答
1275 浏览

antlr - ANTLR:修复左递归和相互左递归

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

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

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

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

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

0 投票
1 回答
1343 浏览

antlr - 左递归 ANTLR 文法

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

我收到以下错误:

[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]]


更正语法

0 投票
0 回答
149 浏览

context-free-grammar - 需要帮助从 CFG 中消除左递归

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

我想出了这个:

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

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

0 投票
3 回答
432 浏览

prolog - 英语无约束语法序言

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

这是我的规则:(vp -> 动词短语,np -> 名词短语,ap -> adj 短语,pp -> prep 短语)

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

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

0 投票
2 回答
22066 浏览

parsing - 逐步消除这种间接左递归

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

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

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

0 投票
1 回答
2006 浏览

c++ - 解析 C++ 源代码时 ANTLR4 相互左递归错误

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

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

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

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

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

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

0 投票
3 回答
12285 浏览

grammar - 为什么 LL 语法不能是左递归的?

书中,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 的产生式?

0 投票
1 回答
1068 浏览

antlr - 用于嵌套布尔表达式的 antlr 左递归

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

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

我的语法看起来像:

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