parsing - 为什么这个语法在 LR(0) 中有 Reduce/Reduce 冲突？

Question

我有以下语法：

S -> a b D E
S -> A B E F
D -> M x
E -> N y
F -> z
M -> epsilon
N -> epsilon

我的教科书说 LR(0) 中存在 Reduce/Reduce 冲突。我建了一个图，发现有一个状态：

S -> a b . D E
S -> A B . E F
D -> . M x
E -> . N y
M -> .
N -> .

教科书说这是一个减少/减少冲突。我试图找出原因。如果我构建 SLR 表，我会得到以下行（3 是上面的状态）：

那是因为：

• Follow(M)={x} 所以我们可以从状态 3 归约到规则 6。
• Follow(N)={y} 所以我们可以从状态 3 归约到规则 7。

有人告诉我，如果有一个带有 S/R 的单元格，则存在冲突 S/R，如果有一个带有 R/R 的单元格，则存在冲突 R/R。但我没有在表格的同一个单元格中看到两个 Rs。那么为什么它是一个减少/减少冲突呢？

标签： parsingcompilationgrammarlr

Answer 1

您展示了一个 SLR(1) 解析表，其中的列对应于长度为 1 的前瞻。它是正确的，并且没有冲突。

但是这里我们讨论的是没有前瞻的 LR(0) 机器。（这是 LR(0) 中的 0。）机器可以做出的唯一决定是移位或减少，并且由于它不能使用前瞻，它只能使用状态本身。给定状态必须是 shift 状态或 reduce 状态（如果是 reduce 状态，则表示正在减少哪个生产）。

（如果它令人困惑，而且通常是，前瞻的概念并不是指使用移位符号来决定转换到哪个状态。转换是基于移位符号进行的，在那个点不再前瞻的一部分。）

所以在那种状态下，不可能有换档动作；在项目集中的所有项目中，点位于末尾或下一个符号是非终结符（暗示从归约返回后执行 GOTO 操作）。

但是状态并没有唯一的减少。根据前瞻，解析器需要选择减少 M 或减少 N。由于没有前瞻，因此无法做出决定，因此这是一个冲突。