考虑文法：
S → CC
C → c C | d
构建 LALR(1) 解析器的解析表。

解决方案

步骤1 − 构造 LR(1) 项目集。首先，应生成所有 LR(1) 项目集。

在这些状态中，状态 I₃ 和 I₆ 可以合并，因为它们具有相同的核心或第一部分，但展望符 (Look Ahead) 的第二部分不同。

同样，状态 I₄ 和 I₇ 是相同的。

同样，状态 I₈ 和 I₉ 是相同的。

因此，I₃ 和 I₆ 可以合并为 I₃₆。

I₄ 和 I₇ 合并为 I₄₇。

I₈ 和 I₉ 合并为 I₈₉。

所以，状态将是

∴ I₃ = goto(I₀, c)

但 I₃ , I₆ 合并为 I₃₆

∴ I₃₆ = goto(I₀, c)

∴ I₄ = goto(I₀, d)

但 I₄ , I₇ 合并为 I₄₇

∴ I₄₇ = goto(I₀, d)

∴ I₆ = goto(I₂, c)

∴ I₃₆ = goto(I₂, c)

∴ I₇ = goto(I₂, d)

∴ I₄₇ = goto(I₂, d)

∴ goto(I₃, C) = I₈

但 I₈ 现在是 I₈₉ 的一部分

∴ goto(I₃₆, C) = I₈₉

同样，goto(I₃, d) = I₄, goto(I₆, d) = I₇ ∴ goto(I₃₆, d) = I₄₇

LALR 解析表构建

填充“移进”项 (s)

考虑 goto(I₀, c) = I₃₆

∴ Action[0, c] = s36

∴ 在状态 0 行和 c 列前面写入 s36。

同样，考虑

goto(I₂, d) = I₄₇

∴ Action[2, d] = 47

∴ 在状态 2 行和 d 列前面写入 s47。

填充“归约”项 (r)

考虑 A → α ∙ 形式的产生式，

例如，考虑状态

I₄₇ = goto(I₀, d)

C → d ∙, c |d |$

∴ C → d ∙, c |d |$ 具有 A → α ∙ 的形式。

由于 C → d 是给定问题中第 (3) 个产生式。

∴ 在状态 47 行和 c、d、$ 列前面写入 r3。

因为 c、d 是产生式 C → d ∙ , c | d 中的展望符。

填充 goto 项

这只对非终结符才能找到。

例如，考虑

goto(I₀, S) = I₁

∴ goto[0, S] = 1

填充“接受”项

由于 S′ → S ∙ , $ 在 I₁ 中

∴ 在状态 1 行和 $ 列前面写入 accept。

LALR 解析表也可以通过合并 CLR 解析的组合状态的行来获得，即合并对应于 3、6 的行，然后是 4、7，然后是 8、9。

生成的 LALR 解析表将是：

Ginni

更新于：2021-11-02

6K+ 次浏览

启动你的职业生涯

完成课程获得认证

开始学习