compiler-construction - 我在哪里可以找到好的 LR(1) 和 LALR(1) 状态生成示例或阅读材料？

Question

我正在使用 Kenneth Louden 的 Compiler Construction 书，但它缺少示例，而且说明如何进行的规则真的很难遵循。我不确定如何进入 LR(1) 状态。此外，不知道如何从 LR(1) 状态转到 LALR(1) 状态。

例如，这些 LR(1) 状态：

我了解“S -> .XX, $”是如何到达那里的，但接下来看看“X -> .aX, a/b”。为什么 $ 不是其中的一部分？它不是从一个有 $ 的规则生成的，所以它不是必须有一个 $ 吗？a/b是怎么出现的？根据这本书，如果 A -> alpha.Bgama,a 和 B 是非终结符，则 B -> .beta, b 为每个 B -> beta 添加 b 在第一个（gamaalpha）中。所以，据我了解：

S -> .XX, $ and X -> aX and X -> b => X -> aX, $ and X -> b, $
X -> .aX, $ and X -> b, $ => 没有任何反应
A -> .a, $ => 没有任何反应

但鉴于上面的例子，这似乎完全错误。

Answer 1

我了解“S -> .XX, $”是如何到达那里的，然后看看“X -> .aX, a/b”。为什么 $ 不是其中的一部分？

您是指项目集 I0 中的第 2 项和第 3 项吗？

$表示输入符号是空字符串。输入符号为 a/b 的 a/ b。

你的终端集是 { a, b, $ }，非终端集是 { S' , S , X }

需要注意的是 LR(n),SLR,LALR(1) 都是自底向上的解析器。它们从终端开始，一直到开始符号 S'。

Answer 2

FIRST(X) is {a, b}，因此例如在状态 I0 中，S->.XX,$我们将X->aX|a在first(X).

A → α•Bγ, Χ, X是前瞻符号

Y = FIRST(γ) if epsilon ∈ FIRST(γ), ή Y = (FIRST(γ)-{epsilon}) ∪ X αν epsilon ∈ FIRST(γ)
B → •β ,Y

Answer 3

我最近写了一篇关于这个确切问题的博客文章。基本上，它与第一组以及点右侧的符号是否可以为空有关。我试图用尽可能非数学的术语来表达自己。

计算 LR1 闭包