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

Question

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

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

Answer 1

有趣的问题！答案是

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

对于第一点，假设您有一个名为LR(1)的语法，这样就可以形成它的LR(1)解析器。我们可以将其转换为LALR(1)解析器，方法是将所有状态与相同的结果合并在一起，而忽略查找头。如果您的LR(1)状态没有与任何内容合并，那么LR(1)状态将逐字出现在LALR(1)解析器中。由于LR(1)状态没有移位/减少或减少/减少冲突，相应的LALR(1)解析器状态将不会有任何冲突。

在SLR(1)方面，您可以以没有LR(1)状态合并的状态结束，但是存在一个减少/减少冲突。这背后的直觉是，在LR(1)解析器中可以有一个没有减少/减少冲突的状态，因为查找头有足够的细节来解决冲突，但是当从LR(1)切换到SLR(1)和扩展查找集时，我们意外地引入了一个减少/减少冲突。下面是发生这种情况的语法示例：

• S→aTb aR 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)解析器中具有的项集相同。还请注意，下面(T)= {$，b}。这意味着LR(1)状态

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

被转换为SLR(1)状态

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

它在$上具有减少/减少冲突。