问题标签 [lr]

几天前我问了一个问题 SLR(1) 和 LALR(1) 和 Reduce，我做了很多搜索并联系了一些教授，但我无法总结第二个问题的解决方案是对还是错。我们有 2 个不同年份的入学考试题。

两题是选择题。在 2010 年的问题中，我们有：

1) 我们有一个 SLR(1) 语法 G，如下所示。我们使用 SLR(1) 解析器生成器并为 G 生成解析表 S。我们使用 LALR(1) 解析器生成器并为 G 生成解析表 L。

问题设计者选择解决方案为：

两年后，问题设计师提出：

2) 假设 T1、T2 是用 SLR(1) 和 LALR(1) 为任意文法 G 创建的。如果 G 是 SLR(1) 文法，以下哪项是正确的？

a) T1 和 T2 没有任何区别。

b) T1 中非错误条目的总数低于 T2

c) T1 中的错误条目总数低于 T2

解决方案：

我的问题是：

有人在上一篇文章中回答说两个解决方案是正确的，但没有很好地描述它。

无论如何，我在等待一位专家让我摆脱困惑！

在实现真实世界（TM）语言时，我经常会遇到这样的情况：

显然（以函数式风格），最好将部分解析的collection记录传递给 和 的语义操作的每次调用，parseA并parseB相应地更新列表元素。

这甚至可以使用menhir，还是必须使用使用可变全局变量的丑陋技巧？

我目前正在研究 LR 解析，需要一个在线 LR(1) 解析器来验证我的结果。我已经偶然发现了这个（LL（1）），在那里我能够验证我的第一个并遵循集合，但我也想验证我的解析图。

谁能给我一个这样的工具的链接？

为了完整性；我需要验证以下语法：

有人告诉我，如果没有添加规则 S->S'，我们可能会接受语法语言中不存在的单词，有人能想出一个很好的例子吗？此外，您是否有减少 SLR 解析到多个状态的示例？

我正在尝试解决有关 LR(1) 语法的问题：

我在以下情况下陷入状态 4：

a并A转移到其他状态并A在同一状态下减少我是否应该因为这种冲突而认为该语法不是 LR(1) 和 SLR(1) ？

考虑以下 LR 语法的尝试，其中引用的字符串被假定为终端符号：

看起来这应该是一个无冲突的 LR(1) 文法，因为它等价于

然而，我认为（？）任何现实世界的解析器都会机械地将它翻译成

其中U和V是在解析树中由其子代直接替换的符号。

得到的文法现在是 LR(∞)；它对 LR(k < ∞) 有减少-减少冲突——尽管它确实不应该！

现在，我意识到可以让这个例子变得更复杂（比如说，使用重复和析取）；事实上，据我所知，检测这种情况可以简化为测试两个上下文无关语法的等价性，这（如果我没记错的话）是一个无法确定的问题。

我的问题是：

1. 我是否正确地认为这是一个实际问题，还是我错过了一个实际的解决方案？

2. 处理这个问题的最佳方法是什么？报告冲突是最好的方法，还是在实践中使用启发式方法来解决问题？

LL(1) 解析器需要一个前瞻符号才能决定使用哪个产生式。这就是为什么我一直认为使用术语“前瞻”的原因，当解析器查看下一个输入标记而不“消耗”它时（即它仍然可以通过下一个操作从输入中读取）。然而，LR(0) 解析器让我怀疑这是正确的：

我见过的每个 LR(0) 解析器示例也使用下一个输入标记来决定是移位还是减少。在减少的情况下，不消耗输入令牌。

我使用免费软件工具“ParsingEmu”生成 LR 表并在下面对“aab”一词执行 LR 评估。如您所见，列标题包含标记。从评估中，您可以看到解析器通过查看下一个输入标记来决定使用哪一列。但是当解析器在步骤 4 - 6 中减少时，输入不会改变（尽管解析器在执行到下一个状态的转换时需要知道下一个输入标记“$”）。

语法：

桌子：

评估：

由于我的困惑，现在我做了以下假设：

1. 我对“前瞻”定义的假设（前瞻 = 未使用输入令牌）是错误的。对于 LL 解析器或 LR 解析器，前瞻只是意味着两种不同的东西。如果是这样，那么如何定义“前瞻”呢？

2. LR 解析器（从理论的角度来看，当您使用下推自动机时）具有额外的内部状态，它们通过将输入标记放在堆栈上来消耗输入标记，因此只需查看即可做出移位减少决策在堆栈上。

3. 上面显示的评估是 LR(1)。如果为真，LR(0) 评估会是什么样子？

现在什么是正确的，1、2 或 3 还是完全不同的？

有点困惑这个语法是否模棱两可

我尝试为此构建 DFA，但我在其中一个州得到了这个：

这不是一个移位减少冲突，所以它肯定意味着语法不是 LR(1) 吗？或者它是否会减少，因为 $ 和 u 都在后面的 C 集中？

赋值表达式是可以使用 C 运算符的任何赋值表达式=, +=, -=, *=, /=。

marker并且Next都是EMPTY规则

上述语法规则和实现的问题是表达式为 as 时无法生成正确的代码

它期望 assignment-expression 必须包含reloporOR或ANDto generate correct code。因为在这种情况下，我们对relop相同的情况进行比较，适用于OR和AND。

但是由于上面的代码不包含任何东西，所以它无法生成正确的代码。可以使用以下规则生成正确的代码，但这会导致two reduce-reduce conflict.

我应该在语法规则中做哪些修改才能使其按预期工作？

我从这里以及从龙书尝试了IF ELSE 语法规则，但无法解决这个问题。完整的语法可以在这里找到Github

我正在阅读本书中有关 LR(0) 解析器的内容：Java 中的现代编译器实现。下面是基于这本书的解析表的样子。 http://postimg.org/image/hyowddu1h/

开始符号：S --> E$

制作：

(1) E --> T + E

(2) E --> T

(3) T --> x

我尝试根据给出的产品制作解析表，但我没有得到与书中相同的解析表。我想我正确地移动了符号。只是我的解析表与书中的解析表不同。（注意：我从状态 0 开始，而不是书中的状态 1）

那么解析表是唯一的，还是有什么经验法则可以决定首先将哪个符号转移到堆栈或如何正确标记解析状态？我总是先移动终端符号，然后移动非终端符号，如下所示： http: //postimg.org/image/76vbu2vu3/

提前致谢！