问题标签 [lr]

我很难理解如何计算 LR(1) 项的前瞻。

可以说我有这个语法：

LR(1)-item 是具有前瞻功能的 LR(0) 项。所以我们将得到状态 0 的以下 LR(0)-item：

状态：1

有人可以解释如何计算前瞻吗？一般的做法是什么？

先感谢您

我正在制作一个 LR(1) 解析器，并且在各个地方都遇到了性能瓶颈。

我想尝试优化解析器的数据结构，但为了做到这一点，我需要大致了解有多少状态、规则和终端符号对于（可能很复杂）计算机语言（如 C++）是合理的。

我的猜测是，复杂语言的典型语法将具有：

• ≤ 100 个终端符号
• ≤ 50 个符号/产品
• ≤ 2,000 条规则
• ≤ 10,000 个州

但我真的不知道它们有多正确。

请注意，我假设每个规则的形式为非终结符→符号 符号 符号...，因此看起来像的单个复合“规则”foo: (bar | baz)+实际上可能包含 5 条规则，而不仅仅是 1 条规则。

它们合理吗？如果没有，我在哪里可以找到这些数字？

我在哪里可以找到 LR(1) 解析器生成器的简单（尽可能多，但不简单！）实现？

我不是在寻找性能，只是在寻找生成 LR(1) 状态（项目集）的能力。
C++、C#、Java 和 Python 都适合我。

我曾经认为 C++ 是一个“奇怪”的语言，它与<and有所有的歧义>，但在尝试实现一个解析器之后，我想我找到了一个例子，它打破了几乎所有使用<and>泛型类型的语言：

这可以在语法上被解释为一个通用的方法调用（g），或者它可以被解释为给出f两个比较的结果。

这些语言（尤其是 Java，我认为它应该是 LALR(1) 可解析的？）如何解决这种句法歧义？

我只是无法想象任何非 hacky/上下文无关的方式来处理这个问题，而且我对任何这样的语言如何可以是上下文无关的感到困惑，更不用说 LALR(1) 可解析了......

（值得注意的是，即使是 GLR 解析器也无法在没有上下文的情况下为该语句返回单个解析！！）

我一直在 Wikipedia 中阅读这两个内容，并注意到尽管存在 LR(0) 解析器，但没有 LL(0) 解析器之类的东西。

从我读到的内容，我了解到 LL(k)/LR(k) 中的 k 表示解析器可以在当前正在处理的当前字符之外看到多少个字符。

所以我的问题是，为什么没有 LL(0) 解析器之类的东西，即使 LR(0) 存在？

我创建了一个语法，其精简版本如下所示：

我相信这种语言是明确的，应该是 LR 可解析的。（如果我错了，请告诉我！）

但是，当我尝试为此语法生成 LR(1) 解析器时，我会遇到移位/归约冲突，因为当解析器看到exp3前瞻?时，它不知道是移位还是归约：

有没有一种合理的方法可以使这种语言 LR(1) 可解析（没有冲突）？

还是 GLR（或者可能是 LR(2)？）对于这样的语言，我唯一现实的选择是什么？
（或者我认为语言一开始是明确的，我什至是错误的？）

作为参考，我生成的模棱两可的状态机如下（其中 ♦ 是 EOF）：

我有一个练习，其中我有 LR(2) 语法，我想转换为 LR(1) 语法。但我不明白我怎么能做到这一点。我有这个语法（4条规则）：

• e->真| 假 | 编号 | e ^ e | 前夕 | (e)
• i -> 如果 e 则 i | 如果 e 那么我 否则我 | id = e | (一) | 嘛
• 马 -> 一个 | 一个^马
• a -> id = e

这种语法的问题是她产生了减少/减少冲突（没有人喜欢这样）。所以我需要在 LR(1) 中改变这个语法，但我真的看不到这样做的算法。请帮忙 ：）

我写了以下语法：

e 代表“空字符串”

所以这个文法识别的语言包括所有左右括号匹配的字符串，比如()、(())、(()())等。

而且这个语法不是 SLR，这是我构造 SLR 解析表的方式：

1. 扩充这个语法：

   S1->S S->S(S)S S->e

2. 然后为它构造LR(0)自动机：

   I0：S1->.S S->.S(S)S S->.e

   I1：S1->S。S->S.(S)S

...

请注意，对于 I0，输入符号 '(' 没有移位或归约操作，这是该语法生成​​的任何字符串的第一个标记。

所以 SLR 解析表会产生错误，因为在状态 I0，它不知道解析字符串时要做什么：(())。

我的问题是：

使这个语法不是 SLR 的罪魁祸首是什么？它是空字符串生产吗？即：S->e。?

而在一般意义上，单反语法可以有空产生式吗？例如，在本例中为 S->e。谢谢。

我canonical LR Method用来构造解析表。

考虑语法：

我正在阅读的书中提到了第一个关闭状态：

在该州

从哪里来？A_ item所有项目都有$一个Look ahead 符号，第三个项目有A。

请解释一下。

有人问我 LL(3) 是否是 LR(2) 的子集，反之亦然。

我成功地证明了 LL(3) 不是 LR(2) 的子集：

在 LL(3) 中，我们可以在读取开头的 3 个字符后识别规则。

在 LR(2) 中，我们可以在读取 2 个字符后识别规则。

因此，假设规则为空（upsilon），那么 LL(3) 会给我们比 LR(2) 更多的信息。因此，LL(3) 不包含在 LR(2) 中。

我如何证明另一种方式？