SLR(1) 和 LALR(1) 语法冲突

Question

假设你有一个语法 G，我们为它找到了一个 LR(1) 自动机。我们可以通过状态合并和转换规则将其转换为 LALR(1) 或 SLR(1) 解析器，但可能会出现冲突。

我的问题如下：所有问题都必须出现在合并状态吗？未合并的非冲突 LR(1) 状态是否可能在 LALR(1) 或 SLR(1) 自动机中发生冲突？

Answer 1

有趣的问题！答案是

如果语法是 LR(1)，则 LALR(1) 解析器中的任何冲突都必须发生在合并状态中，但是
如果一个文法是LR(1)，LR(1)状态可能会出现未合并的冲突。

对于第一点，假设你有一个 LR(1) 语法，所以你可以形成它的 LR(1) 解析器。我们可以通过将具有相同产生式的所有状态合并在一起，忽略先行，将其转换为 LALR(1) 解析器。如果你有一个不与任何东西合并的 LR(1) 状态，那么这个 LR(1) 状态会逐字地出现在 LALR(1) 解析器中。并且由于 LR(1) 状态没有 shift/reduce 或 reduce/reduce 冲突，相应的 LALR(1) 解析器状态不会有任何冲突。

在 SLR(1) 前端，您最终可能会遇到不会发生 LR(1) 状态合并的状态，但存在 reduce/reduce 冲突。这背后的直觉是你可以在 LR(1) 解析器中有一个没有 reduce/reduce 冲突的状态，因为前瞻有足够的细节来解决冲突，但是当从 LR(1) 切换到 SLR(1) 时并扩展前瞻集，我们不小心引入了 reduce/reduce 冲突。这是发生这种情况的语法示例：

S → aTb |一个R | cT
T → d
R→d

这是 LR(1) 配置集：

(1)
   S' -> .S    [$]
   S  -> .aTb  [$]
   S  -> .aR   [$]
   S  -> .cT   [$]

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

(3)
   S -> a.Tb   [$]
   S -> a.R    [$]
   T -> .d     [b]
   R -> .d     [$]

(4)
   T -> d.     [b]
   R -> d.     [$]

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

(6)
   S -> aTb.   [$]

(7)
   S -> aR.    [$]

(8)
   S -> c.T    [$]
   T -> .d     [$]

(9)
   T -> d.     [$]
   
(10)
   S -> cT.    [$]

这些是您在 SLR(1) 解析器中拥有的相同项目集。另请注意，FOLLOW(T) = {$, b}。这意味着 LR(1) 状态

(4)
   T -> d.     [b]
   R -> d.     [$]

转换为SLR(1)状态

(4)
   T -> d.     [b, $]
   R -> d.     [$]

在 $.

上有 reduce/reduce 冲突

SLR(1) 和 LALR(1) 语法冲突

SLR(1) and LALR(1) grammar conflicts

parsing

grammar

context-free-grammar

lr