SLR (1)混淆

Question

​

​

S → ( S ) S
|   .

根据定义，0、2和4具有shift/reduce冲突。下面的一组S是")“。对于状态2中的SLR(1)，"(“不在下面的S集中，但是为什么这是一个SLR (1)？你能解释一下slr(1)的shift / reduce冲突规则吗?我可能对某些事情感到困惑。

Answer 1

让我们从你的语法开始：

S→(S)S |ε

为了为这个语法构建一个SLR(1)解析器，我们需要用一个新的开始规则来扩充它：

启动→S

S→(S)S |ε

请注意，以下(S)包含)、和$，不包含其他符号。

我们现在可以开始构建SLR(1)自动机，方法是构建LR(0)自动机，并使用以下集合增强每个产品：

(0)
Start -> .S      [$]
    S -> .(S)S   [$)]
    S -> .       [$)]

(1)
Start -> S.      [$]

(2)
    S -> (.S)S   [$)]
    S -> .(S)S   [$)]
    S -> .       [$)]

(3)
    S -> (S.)S   [$)]

(4)
    S -> (S).S   [$)]
    S -> .(S)S   [$)]
    S -> .       [$)]

(5)
    S -> (S)S.   [$)]

您声称状态0、2和4有移位/减少冲突，但我在这里并不这么认为。在状态(0)中，我们有完整的项目S→。，但是lookahead是$→)。这意味着我们只减少$和)。另一方面，这里唯一的移位操作发生在(符号上。

如果我们这里没有lookaheads，我们就会有一个shift/reduce冲突，但是因为lookaheads，我们知道如果我们看到a(如果我们看到就会减少)或者$，就会转移。如果您检查您已经标记的其他状态，您将看到同样的逻辑适用。

因此，这个语法实际上是SLR(1)。