什麼是 SLR(1) 分析器？

SLR 代表 “簡單 LR 分析器”。它非常簡單且執行效率高。但它無法為某些型別的語法建立分析表，這就是為什麼使用 CLR 和 LALR，它們主要實現了所有型別的語法。它構建分析表，幫助執行輸入字串的分析。

SLR(1) - 具有 SLR 分析表的語法被稱為 SLR(1)。

SLR 分析器的工作原理

如果給出上下文無關文法，則可以進行 SLR 分析。在 LR(0) 中，0 表示沒有前瞻符號。

LR(0) 專案的規範集合

語法 G 的 LR(0) 專案包含一個產生式，其中符號點 (.) 插入到產生式右部 (R.H.S) 的某個位置。

例如 - 對於產生式 S → ABC，生成的 LR(0) 專案將是 -

S →∙ ABC

S → A ∙ BC

S → AB ∙ C

S → ABC ∙

產生式 S → ε 只生成一個專案，即 S →∙

規範 LR(0) 集合有助於構建稱為簡單 LR (SLR) 分析器的 LR 分析器。

要為語法建立規範 LR(0) 集合，需要 3 個東西 -

• 增廣語法
• 閉包函式
• goto 函式

增廣語法 - 如果語法 G 具有起始符號 S，則增廣語法是具有新起始符號 S' 的新語法 G'。此外，它還將包含產生式 S' → S。

閉包 - 對於上下文無關文法 G，如果 I 是語法 G 的專案或狀態集，則 -

• I 中的每個專案都在閉包 (I) 中。

• 如果規則 A → α. B β 是閉包 (I) 中的一個規則，並且 B 有另一個規則，例如 B → γ，則閉包 (I) 將包含 A → α. Bβ 和 B → . γ

goto (I, X) - 如果 I 中存在產生式 A → α ∙ X β，則 goto (I, X) 定義為 A → α X ∙ β 專案集的閉包，其中 I 是專案集，X 是語法符號（非終結符）。

SLR 分析表的構建

SLR 分析表基本上有兩個部分

• 動作
• goto

可以使用以下演算法填充動作和 goto 表 -

演算法

輸入 - 增廣語法 G'

輸出 - SLR 分析表

方法

• 最初構建專案集

C = {I₀, I₁, I₂ … … I_n}，其中 C 是語法 LR(0) 專案的集合。

• 解析動作基於每個專案或狀態 I₁。

各種動作是 -

• 如果 A → α ∙ a β 在 I_i 中，並且 goto (I_i, a) = I_j，則設定 Action [i, a] = “移進 j”。
• 如果 A → α ∙ 在 I_i 中，則將 Action [i, a] 設定為“歸約 A → α”，對於所有符號 a，其中 a ∈ FOLLOW (A)。
• 如果 S' → S ∙ 在 I_i 中，則動作表 Action [i, $] 中的條目為“接受”。

• SLR 表的 goto 部分可以填充為 - 狀態 i 的 goto 轉移僅針對非終結符進行考慮。如果 goto (I_i, A) = I_j，則 goto [i, A] = j

• 所有未由規則 2 和 3 定義的條目都被認為是“錯誤”。

Ginni

更新於： 2021 年 11 月 2 日

6K+ 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習