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）解析器。我们可以通过将所有状态与相同的作品融合在一起，忽略LookAheads，将其转换为LALR（1）解析器。如果您的LR（1）状态没有与任何东西合并，则LR（1）状态在LALR（1）解析器中逐字化。而且，由于LR（1）状态没有班次/减少或减少冲突，因此相应的LALR（1）解析器状态不会有任何冲突。

在SLR（1）方面，您可以最终获得不会发生LR（1）状态合并的状态，但会减少/减少冲突。其背后的直觉是，您可以拥有一个没有减少/减少LR（1）解析器冲突的状态，因为LookAheads具有足够的细节来解决冲突，但是当从LR（1）切换到SLR并扩展时LookAhead集合我们不小心引入了减少/减少冲突。这是语法发生的示例：

• 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.     [$]

该状态具有减少/减少$的冲突。