什麼是 LALR(1) 解析器？

LALR 解析器是前瞻 LR 解析器。它的功能介於 SLR 和 CLR 解析器之間。它是 CLR 解析器的壓縮版本，因此由此獲得的表格將比 CLR 解析表更小。

在這裡，首先，我們將構建 LR(1) 專案。接下來，我們將查詢具有相同第一個組成部分的專案，並將它們合併以形成單個專案集。這意味著狀態具有相同的第一個組成部分，但不同的第二個組成部分可以整合到單個狀態或專案中。

例如。

假設如果

I₄: C → d ∙ , c | d

I₇: C → d ∙ , $

這兩個專案或狀態 (I₄ 和 I₇) 具有相同的第一個組成部分，即 d ∙ ，但第二個組成部分不同，即 I₄ 中的 c | d 和 I₇ 中的 $。

∴ 這些狀態可以合併為

I₄₇: C → d ∙ , c |d | $

LALR 解析表的構造

演算法

輸入 - 增廣文法 G′

輸出 - LALR 解析表

方法

• 構造 LR(1) 專案集，即構造

  C = {I₀, I₁, I₂ … . . I_n}

• 選擇具有相同核心或第一個組成部分的相似狀態，並將它們合併為一個。

  令 C′ = {J₀, J₁, J₂ … . . J_m} 為結果集。

• 為狀態 J₁ 構造解析動作，類似於 CLR 構造。如果解析表中存在衝突，則可以認為該演算法無法生成 LALR 解析器。

• 構造 goto 動作如下。

令 goto [J,∗] = K，其中 J 是 C 的一個或多個狀態的並集。

即，J = I₁ ∪ I₂ … .∪ I_m，則

則 K = goto (I₁,∗) ∪ goto (I₂,∗) … .∪ goto (I_m,∗)

LALR 解析器的運作

LALR 文法 - 如果 LALR 解析表中沒有多個表示的條目，則該文法被稱為 LALR(1) 或 LALR 文法。

Ginni

更新於: 2021 年 11 月 2 日

4K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習