compiler-construction - 如何解析给定的 LALR(1) 语法

Question

我无法使用 LALR 方法解析以下语法。

s -> y
y -> dX | ydX
X -> e | Zd
z -> F | epsilon

一开始我没问题，这里是项目状态 0：（分隔前瞻状态的 , ）

s -> .y, $
y -> .dX, $d
y -> .ydX, $d

现在这很好，但是当您从广告终端转到状态 1 时，我会感到困惑。我的书的状态 2 如下：

y -> d.X, $d
X -> .e, $d
X -> .Zd, $d
Z -> .f, d
Z -> ., d

X非终端中的前瞻终端“d”来自哪里？我以为 dX 来自 .dX，它有前瞻终端“$”和 $d”。但是在进行 E-closure 时，前瞻不应该是 $d 的第一个，即“$”？为什么是“$”，或“d”？我认为它可能来自另一个州，因为这是 LALR，但我最终合并状态 1 的状态也没有前瞻广告。有人可以向我解释为什么有一个“d”配对在这个状态的前瞻中有“$”？谢谢。

Answer 1

S$->Y$->dX$ 在 d 之后的这个推导序列中 X 之后是 {$}

S$->Y$->ydX$->dXdX$ 在第一个 d 之后的这个推导中，X 之后是 {d}

在覆盖输入'd'中的第一个符号后，两个推导序列都覆盖在相同的状态