parsing - 构建 LR(1) 配置前瞻

Question

在构建 LR(1) 项目集时，我确实在预测前瞻方面遇到了一些麻烦，我尝试了来自不同站点的一些讲义，但仍然......我的例子是

S -> E + S | EE -> num | ( S )

该项目集是

I0:S’ -> . S       $S -> . E + S    $S -> . E        $E -> . num      +,$E -> . ( S )    +,$I1:S ->E .+ S      $S ->E .         $

集合 I0 中的第一项

S’ -> . S     $

正在初始化。

集合 I0 中的第二项

S -> . E + S     $

表示堆栈上没有任何内容，我们希望读取 E+S，然后当 E+S 后面的标记为 $ 时减少。

集合 I0 中的第三项

S -> . E        $

表示我们期望读取 E 并减少当且仅当 E 后面的标记是 $。

然后我对集合 I0 中的第四项感到困惑，

E -> . num      +,$

我不知道为什么会有 + 和 $ 标记。

如果有人可以用简单的英语为我解释一下。对于 I 中的每个配置 [A –> u•Bv, a]，对于 G' 中的每个产生式 B –> w，以及First(va) 中的每个终结点 b 使得 [B –> •w, b] 不在 I 中:将 [B –> •w, b] 添加到 I。

谢谢!!!

Answer 1

我想我已经明白了。我正在使用的算法

for set I0:Begin with [S' -> .S, $]Match [A -> α.Bβ, a]Then add in [B -> .γ, b]Where terminal b is FIRST(βa)for set I1...InCompute GOTO(I0,X)Add in X productions and LOOKAHEAD token

在示例中

S -> E + S S -> EE -> num E -> ( S )

首先，

S’ -> . S       $

我们尝试将其匹配到[A -> α.Bβ, a]，即A = S'，α = ε，B = S，β = ε，a = $ 且第一(βa) = {$}添加[B -> .γ, b]，即

S -> . E + S    $                     ...1S -> . E        $                     ...2

在 I0 中。

然后，我们需要将 E 的产生式添加为 1 和 2。在这种情况下，我们的 [A -> α.Bβ, a] 是 1 和 2。因此，FIRST(βa) = { + , $ }，我们有

E -> . num      +,$E -> . ( S )    +,$

现在，我们计算 GOTO(I0, X)对于 X = E我们将点移动一位，发现不需要添加任何作品。所以我们只需添加

中的第二个组件 $

S -> . E + S    $S -> . E        $

这给了我们 I1

S ->E .+ S      $S ->E .         $

等等...

那么，这是构建 LR(1) 项集时正确且有效的方法吗？