在編譯器設計中，移進規約分析的棧實現是什麼？

移進規約分析器是一種自下而上的分析器。它使用一個棧來儲存語法符號。分析器不斷將輸入符號移入棧中，直到棧頂出現控制代碼。當棧頂出現控制代碼時，它執行規約操作。

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

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

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

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

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

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

• 錯誤：發出語法錯誤發現訊號，並呼叫錯誤恢復例程。

例如，考慮以下文法：

S → aAcBe
A → Ab|b
B → d

字串為 abbcde。

它可以將此字串規約為 S。它可以掃描字串 abbcde，查詢與某個產生式右部匹配的子串。子串 b 和 d 符合條件。

讓我們選擇最左邊的 b 並將其替換為 A（產生式 A → b 的左部），得到字串 aAbcde。可以識別 Ab、b 和 d 各自與某個產生式的右部連線。假設這次可以選擇將子串 Ab 用 A（產生式 A → Ab 的左部）替換，可以得到 aAcde。

因此，將 d 替換為 B（產生式 B → d 的左部），可以得到 aAcBe。可以將此字串替換為 S。上述過程中，將產生式的右部替換為左部的每個替換都稱為規約。

移進規約分析的缺點

• 移進/規約衝突 − 有時，SR 分析器無法確定是移進還是規約。

• 規約/規約衝突 − 有時，分析器無法確定應該使用哪個產生式進行規約。

示例 − 為進行移進規約分析的棧實現，考慮以下文法：

E → E + E
E → E ∗ E
E → (E)
E → id

輸入字串為 $id_{1} + id_{2} * id_{3}$。

Ginni

更新於：2021年10月29日

6K+ 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習