这不是我的作业,我正在尝试理解 LALR(1) 语法。于是我找到了 this
S -> aEa | bEb | aFb | bFa
E -> e
F -> e
我写了LR项目,但我想不通
为什么这是 LR(1) 文法而不是 LALR(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]
现在有一个减少/减少冲突(顺便说一下,LR(1) 解析器中不存在的 LALR(1) 中的所有冲突都是减少/减少)。这解释了为什么语法是 LR(1) 而不是 LALR(1)。
希望这可以帮助!
关于parsing - 为什么这个 LR(1) 语法不是 LALR(1)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8496065/