編譯器設計中LR解析器的組成部分是什麼？

LR解析器是一種自下而上的解析器，用於解析上下文無關文法。LR解析也稱為LR(K)解析。LR解析器是一種移進-規約解析器，它利用確定性有限自動機，透過從下往上讀取棧來識別所有適用的字首。

它決定是否存在可用的控制代碼。右句型的可行字首是指包含控制代碼但不包含控制代碼右側任何符號的字首。因此，如果構造了一個識別右句型可行字首的有限狀態機，則可以使用它來指導移進-規約解析器中的控制代碼選擇。

LR解析器棧包含兩種型別的符號——狀態符號可以識別DFA的狀態和語法符號。解析器從DFA的初始狀態I₀開始，位於棧頂。解析器透過考慮下一個輸入符號'a'和棧頂的狀態符號I_i來執行。

LR解析器有以下幾個組成部分。

• 輸入緩衝區——它包含要解析的字串，後跟$，這是一個用作字串右端標記的符號，表示字串的結尾。
• 棧——它用於儲存語法符號和狀態。

         s₀X₁s₁X₂……………………X_ms_m$

       其中X₁, X₂……………….X_m是語法符號

       而s₀, s₁, s₂………………..s_m是狀態

• 分析表：分析表分為兩個部分——
  • 動作：動作可以是移進、規約、接受和錯誤。
  • goto：它以狀態和語法符號為引數，併產生一個狀態示例，goto(s, X)。
• 分析程式：這是一個驅動程式，執行以下功能
  • 它維護初始配置(s₀,w$)，其中s₀是起始狀態，w是字串。
  • 它支援以下配置

  • s₀X₁s₁X₂ … … X_mS_m, a_i, a_i+1 … … a_n$
         棧           輸入字串(w)

  • 它確定S_m（當前位於棧頂的狀態）和a_i（當前輸入符號）。
  • 它根據分析表中的條目action[S_m,a_i]採取動作。
• 動作——解析器採取的動作有以下幾種型別：
• 移進——如果Action[S_m, a_i] = shift s，則將a_i與狀態s一起移入棧中，即配置變為。

• 規約——如果Action[S_m, a_i] = reduce A → β，則解析器執行規約，即配置變為。

              這裡

                 s = goto[s_m−r, A]

                 r = β的長度

彈出符號的數量 = 2r（r個狀態符號 + r個語法符號）

• 接受——如果Action[s_m, a_i] = accept，則解析完成。
• 錯誤——如果Action[s_m, a_i] = error，則解析器呼叫錯誤校正函式。

Ginni

更新於：2021年11月3日

958 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習