compiler-construction - 每个 LR(0) 语法都是 SLR(1) 但反之亦然不一定是真的，为什么？

Question

每个 LR(0) 语法都是 SLR(1) 但反之亦然不一定是真的，为什么？

Answer 1

基本上，SLR(1) 文法可以解决相应 LR(0) 文法中存在的移位归约冲突。以 Wikipedia 的SLR 解析器页面上的示例语法为例（它以更低、更严格的级别对此进行了解释）：

1. S → E
2. E → 1 E
3. E → 1

当 LR(0) 解析器正在解析E并且“1”是下一个输入符号时，它可以识别E并归约（规则 3），或者它可以转换以解析后面的 E（规则 2）。因为它不能向前看，所以 LR(0) 不能确定要做什么。如果我们查看 LR(0) 在遇到“1”时可能正在处理的项目（已添加字符串结尾符号），这将变得更加明显：

• E → 1 • E $
• E → 1 • $

第一个需要转变，第二个需要减少。

使用上述文法，SLR(1) 文法可以向前看一个符号并确定要采取的行动。E后面只能跟 $，所以 reduce 动作只在字符串末尾有效。这对应于第二项，您可以在其中看到下一个符号是“$”。

有关 SLR(1) 而不是 LR(0) 的另一个示例语法，请参阅德克萨斯大学的Fegaras 对 CSE 5317/4305 的注释。