考慮文法：
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+ 次瀏覽

啟動你的職業生涯

完成課程獲得認證

開始學習