问题标签 [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.
recursion - 从 CFG 中删除左递归
以下文法有左递归:
你如何去删除左递归。我阅读了维基百科的解释,但我对 CFG 相当陌生,所以它没有多大意义。任何帮助表示赞赏?一个简单的英文解释将更加感激。
prolog - DCG 和左递归
我正在尝试实现一个 dcg,它采用 {a,b,c,d}* 形式的一组字符串。我遇到的问题是,如果我有一个形式为 s([a,c,b], []),它返回 true,这是正确的答案,但是当我有一个 s([a,c,f],[]) 形式的查询时,它不返回答案并且它用完了本地堆栈。
antlr - ANTLR:修复左递归和相互左递归
这是我正在研究的语法的一部分,用于开发一个解析器工具,这对我的研究很重要。它在 ANTLR IDE 下给我一个错误在 eclipse 中说paraction, action, cspaction
是相互左递归的。
我已经在网上扫描了一个解决方案,但不知道我该怎么做。由于这种语言是研究领域的标准,我没有改变语言语义细节的先决条件。
我实际上正在尝试为“Circus”创建一个语法文件,它是一种状态丰富的形式建模语言,它结合了一种称为 Z 的规范语言和一种称为 CSP(通信顺序过程)的过程建模语言,所以是的,这是一个现有语言。由于正在开发中的语言,它现在在学术界使用。我有该语言的 EBNF,我正在尝试将 EBNF 翻译成 ANTLR 中的语法。我已经设法使以下两条规则起作用。但cspaction
似乎很难。
反斜杠是乳胶的一部分,现在可以省略,因为它们用作字符串。请在下面找到 Circus 的完整 EBNF。它来自已发表的论文,马戏团的指称语义。
马戏团的完整 EBNF - http://www.use.com/b1ad2df0609961615fff
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]]
更正语法
context-free-grammar - 需要帮助从 CFG 中消除左递归
我将如何消除此 CFG 中的左递归?
我想出了这个:
但似乎,当我尝试将其实现为递归下降解析器并解析诸如“ab”之类的简单字符串时,我得到了由concat
生产引起的无限循环。
我是否错误地消除了左递归?
prolog - 英语无约束语法序言
我在尝试在 prolog 中实现一个非常简单的无约束语法时遇到了一个无限递归问题。
这是我的规则:(vp -> 动词短语,np -> 名词短语,ap -> adj 短语,pp -> prep 短语)
我遇到的问题是ap的规则可以产生任意长的形容词字符串,所以在某些时候,我会通过尝试所有这些无限的可能性来满足查询。
例如,下面的查询永远不会产生 S = [put, the, red, block, on, the, green, block] 因为它会首先将左侧“red”的形容词短语扩展为无限可能,然后再尝试使用正确的。
c++ - 解析 C++ 源代码时 ANTLR4 相互左递归错误
我正在尝试解析 cpp 源语法的一个子集。以下 ANTLR4 解析器规则直接从 c++ 语言规范中复制而来(连字符被下划线代替):
但是当 org.antlr.v4.Tool 解析语法时出现此错误:
错误(119):cppProcessor.g4::: 以下规则集是相互左递归的 [direct_abstract_declarator]
好像是direct_abstract_declarator?左侧的语法会导致错误。我应该如何纠正它?为什么ANTLR4不支持?
手动将规则重构为这种形式不会产生错误:
那么ANTLR4在处理左递归规则时是否可以直接支持第一种语法呢?
grammar - 为什么 LL 语法不能是左递归的?
龙书中,LL语法定义如下:
语法是 LL 当且仅当对于任何产生式A -> a|b
,以下两个条件适用。
FIRST(a)
并且FIRST(b)
是不相交的。这意味着它们不能同时导出EMPTY
如果
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 - 用于嵌套布尔表达式的 antlr 左递归
我正在编写一个 antlr 语法,我希望能够在其中嵌套表达式,它可以是“简单”表达式或布尔表达式(带有可选括号)。一个简单的表达式只是一个带有 lhs 和 rhs 的表达式,例如a = 5
我希望能够支持这些类型的表达式:
我的语法看起来像:
我收到一个错误,expr
并且booleanExpr
是相互递归的。我理解为什么会发生这种情况,但是如果我希望能够在彼此之间嵌套布尔表达式,我不确定如何解决这个问题。