compiler-construction - 证明不是 LALR(1) 的 LR(1) 文法必须只有 reduce/reduce 冲突

Question

有人可以向我解释为什么不是 LALR(1) 的 LR(1) 语法必须只有减少/减少冲突

Answer 1

因为如果存在移位归约冲突，它也将存在于 LR(1) 解析器中。

证明很好地出现在每本介绍 LALR 解析的教科书中。LALR 算法将具有相同状态集的状态合并，因此在合并状态中可能的移位动作与在每个原始状态中的相同。此外，合并状态下的每个归约动作都至少处于原始状态之一。因此，如果合并状态中的归约动作与转移动作冲突，它也必须与出现归约动作的原始状态中的转移动作冲突。