什麼是移進規約分析器？

移進規約分析器是一種自底向上的分析器。它從葉子節點生成語法樹到根節點。在移進規約分析器中，輸入字串將被規約到起始符號。這種規約可以透過反向處理最右推導來產生，即從起始符號到輸入字串。

移進規約分析器需要兩種資料結構

  • 輸入緩衝區
  • 棧

移進規約分析的步驟如下：

移進規約分析的步驟如下：

  • 它使用一個棧和一個輸入緩衝區。

  • 在棧的底部和輸入緩衝區輸入字串的右端插入$。

  • 移進 - 分析器將零個或多個輸入符號移入棧，直到控制代碼位於棧頂。

  • 規約 - 分析器規約或替換棧頂的控制代碼為產生式的左部，即彈出產生式的右部，並壓入左部。

  • 接受 - 重複步驟 3 和步驟 4，直到檢測到錯誤或棧包含起始符號 (S) 且輸入緩衝區為空，即包含$。

示例 1 - 對給定字串和語法執行自底向上分析，即顯示以下語法中字串 abbcde 的規約

S → a A B e

A → A b c | b

B → d

它可以透過在每一步應用最右推導的反向將字串 abbcde 規約到起始符號 S。

控制代碼 - 在上述過程中，用左部替換產生式的右部被稱為“規約”，每次替換被稱為“控制代碼”。

示例 2 - 考慮以下語法

E → E + E 

E → E * E 

E → (E) 

E → id

執行最右推導字串 id1 + id2 * id3。在每一步找到控制代碼。

每一步的控制代碼

右句型
控制代碼
使用的產生式
id1 + id2 * id3
id1
E → id1
E + id2 * id3
id2
E → id2
E + E * id3
id3
E → id3
E + E * E
E * E
E → E ∗ E
E + E
E + E
E → E + E
E


示例 3 - 考慮以下語法

S → CC

C → cC

C → d

使用移進規約分析檢查輸入字串“ccdd”是否被接受。

棧
輸入字串
動作
$
ccdd$
   移進
$ c
cdd$
   移進
$ cc
dd$
   移進
$ ccd
d$
   根據 C → id 規約
$ ccC
d$
   根據 C → cC 規約
$cC
d$
   根據 C → cC 規約
$C
d$
   移進
$Cd
$
   根據 C → d 規約
$CC
$
   根據 S → CC 規約
$S
$
   接受

∴ 最後，棧包含起始符號 S，輸入緩衝區為空。它將接受該字串。

更新於： 2021年11月2日

12K+ 瀏覽量

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告