问题标签 [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 回答
360 浏览

parsing - 消除左递归

所以我有一些语法不适用于自上而下的解析器,因为它有左递归:

所以为了解决这个问题,我必须删除左递归。为此,我做了一些类似替代的事情:

A然后转向(我相信):

我相当肯定我是正确的(不过,如果我不是,也不会感到惊讶)。我现在正在苦苦挣扎的地方是从“B b b”中删除左递归。我已经尝试了很多方法,但我认为它们中的任何一个都不起作用。这似乎是最合乎逻辑的,但也很丑陋(因此说它可能是错误的)。从操作 B::= b B b | 开始 巴

所以我想展示最终确定的 B 是什么:

这似乎太丑了,不正确。特别是因为我必须将它插入我创建的新“A”终端。

有人可以帮我吗?不知道我是否以正确的方式解决这个问题。之后我应该能够创建一个 LL(1) 解析表(应该能够自己完成那部分)。

谢谢。

0 投票
1 回答
1063 浏览

java - 相互左递归 ANTLR 4

我很抱歉再问一个关于相互左递归的问题,我觉得我的情况对我来说是独一无二的,或者至少我想不出足以将它与其他人的语法联系起来。我对comp sci世界有点陌生(我是用java自学的,这是我的目标语言,现在是ANTLR4)所以如果可能的话,请用外行术语来描述事物,而不是CS主要术语。

我正在编写一个需要代数和符号导数的程序,当然这需要解析事物,并对树进行操作,但我什至不会担心这一点,因为我认为 ANTLR4 支持直接左递归,但是显然它不以某种方式。在输出中,它一直告诉我我的方法 [表达式] 是相互左递归的,显然这是不允许的......?我的问题:

1)有人可以解释左递归/相互左递归和直接左递归之间的区别(如果有的话)?

2)解释我的语法中是什么导致了这种递归烦恼,以及如何解决它?而且我不确定这是否是主题:

3)人们谈论替代品和标签替代品(我认为他们的意思是#label符号)。那个有什么用?

0 投票
2 回答
262 浏览

recursion - 消除 XText 中的左递归

这是 NuSMV 语言语法的一部分:

不幸的是,XText 抛出了一个异常,指出该语法中存在左递归。我该如何解决?

谢谢。

0 投票
1 回答
114 浏览

intellij-idea - Intellij Antlr4 插件左直接递归不起作用

我正在尝试使用 Antlr4 为 sql select 语句制作解析器,其中包含以下部分

我想这条规则将允许以下结果集:

但是在图中它显示它无法解析

有谁知道为什么它不能像我预期的那样被解析?

0 投票
2 回答
2533 浏览

parsing - 为什么自顶向下解析器不能处理左递归?

我想知道为什么自上而下的解析器不能处理左递归,我们需要消除左递归,正如龙书中提到的那样。

0 投票
1 回答
116 浏览

antlr3 - 由于递归规则调用,使用 Antlr3 解析嵌套列表,非 LL(*) 决策

我有以下语法来使用 Antlr3 解析嵌套列表

我无法找出导致错误的原因或如何消除错误:

'/ListParseTest/src/ListParse.g:17:13: [fatal] 规则 list_element 具有非 LL(*) 决定,因为可以从 alts 1,2 访问递归规则调用。通过左分解或使用句法谓词或使用 backtrack=true 选项来解决。|---> 列表元素:'

我认识到这与list,list_element和之间的递归关系有关tree_,但我无法解决问题。

有人可以帮忙吗?

0 投票
0 回答
140 浏览

compiler-construction - 如何在语法上执行左因子,使其成为 LL(1)

这是我拥有的不递归的语法。我必须使它成为 LL(1)。我该怎么做呢?

0 投票
0 回答
71 浏览

compiler-construction - 左递归去除,得到等价文法

我知道 Y 是左递归的,但为什么 Z 不是左递归的?

对于Y,我得到了

然后因式分解

其中“e”为空

0 投票
1 回答
191 浏览

compiler-construction - 构造具有替换、分解和左递归删除的 LL(1) 文法

使用任何技术(替换、因式分解、左递归删除),构造一个接受与 G 相同语言的 LL(1) 文法。

到目前为止,我这样做了:

X 是左递归的,所以:

我还需要做什么来构造一个 LL(1),我可以考虑 Y 吗?

0 投票
1 回答
170 浏览

antlr4 - ANTLR4 又一个左递归

我很惭愧地问...我为从 int 到 bool 的类型转换的语言编写了一个语法,反之亦然。

但是 antlr 告诉我“以下规则集是相互左递归的 [logic_expr, expr, math_expr]”我无法理解我的语法有什么问题?