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

Question

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

S -> E + S | E
E -> 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...In
Compute GOTO(I0,X)
Add in X productions and LOOKAHEAD token

在示例中

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

首先，

S’ -> . S       $

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

S -> . E + S    $                     ...1
S -> . 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) 项集时正确且有效的方法吗？