parsing - 为什么这个 LR(1) 语法不是 LALR(1)？

Question

这不是我的作业，我正在尝试理解 LALR(1) 语法。所以我发现了这个

S -> aEa | bEb | aFb | bFa
E -> e
F -> e

我写了 LR 项目，但我不明白为什么这是 LR(1) 语法而不是 LALR(1)？

谁能帮我？谢谢

Answer 1

让我们从为语法构造 LR(1) 配置集开始：

 (1)
 S' -> .S [$]
 S  -> .aEa [$]
 S  -> .aFb [$]
 S  -> .bFa [$]
 S  -> .bEb [$]

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

 (3)
 S  -> a.Ea [$]
 S  -> a.Fb [$]
 E  -> .e   [a]
 F  -> .e   [b]

 (4)
 E  -> e.   [a]
 F  -> e.   [b]

 (5)
 S  -> aE.a [$]

 (6)
 S  -> aEa. [$]

 (7)
 S  -> aF.b [$]

 (8)
 S  -> aFb. [$]

 (9)
 S  -> b.Fa [$]
 S  -> b.Eb [$]
 E  -> .e   [b]
 F  -> .e   [a]

 (10)
 E  -> e.   [b]
 F  -> e.   [a]

 (11)
 S  -> bF.a [$]

 (12)
 S  -> bFa. [$]

 (13)
 S  -> bE.b [$]

 (14)
 S  -> bEb. [$]

如果您注意到，状态 (4) 和 (10) 具有相同的核心，因此在 LALR(1) 自动机中，我们会将它们合并在一起以形成新状态

 (4, 10)
 E -> e. [a, b]
 F -> e. [a, b]

现在其中有一个 reduce/reduce 冲突（顺便说一下，在 LR(1) 解析器中不存在的 LALR(1) 中的所有冲突都是 reduce/reduce）。这解释了为什么语法是 LR(1) 而不是 LALR(1)。

希望这可以帮助！