編譯器設計-解析類型

Compiler Design - Types of Parsing

語法分析器遵循由上下文無關語法定義的產生式規則。生成規則的實現方式（派生）將解析分為兩種類型：自上而下解析和自下而上解析。

自頂向下分析Top-down Parsing

當解析器開始從開始符號構造解析樹，然后嘗試將開始符號轉換為輸入時，稱為自頂向下解析。

遞歸下降解析：它是自頂向下解析的一種常見形式。它被稱為遞歸，因為它使用遞歸過程來處理輸入。遞歸下降解析受到回溯的影響。

回溯：這意味著，如果產品的一個派生失敗，語法分析器將使用同一產品的不同規則重新啟動進程。這種技術可以多次處理輸入字符串以確定正確的生產。

自下而上分析Bottom-up Parsing

顧名思義，自底向上的解析從輸入符號開始，并嘗試構建解析樹直至開始符號。

Example:

Input string : a + b * c

Production rules:

S → E

E → E + T

E → E * T

E → T

T → id

Let us start bottom-up parsing

a + b * c

讀取輸入并檢查是否有任何生產與輸入匹配：

a + b * cT + b * cE + b * cE + T * cE * cE * TES

在上一章中，我們了解到自頂向下解析技術解析輸入，并開始從根節點逐漸向下移動到葉節點構建解析樹。

遞歸下降分析Recursive Descent Parsing

遞歸下降是一種自頂向下的解析技術，它從頂部構造解析樹，從左到右讀取輸入。它對每個終端和非終端實體使用過程。這種解析技術遞歸地解析輸入以生成解析樹，這可能需要也可能不需要回溯。但與之相關聯的語法（如果沒有保留因子）不能避免回溯。一種不需要任何回溯的遞歸下降解析稱為預測解析。

這種解析技術被認為是遞歸的，因為它使用的上下文無關語法本質上是遞歸的。

回溯Back-tracking

自上而下的解析器從根節點（開始符號）開始，并根據生產規則匹配輸入字符串以替換它們（如果匹配）。要理解這一點，請以CFG為例：

S → rXd | rZdX → oa | eaZ → ai

對于輸入字符串：read，自上而下的解析器，其行為如下：

它將從生產規則中的S開始，并將其收益率與輸入的最左邊的字母（即“r”）匹配。S（S→rXd）的產生與之相匹配。所以自上而下的解析器前進到下一個輸入字母（即“e”）。解析器嘗試展開非終端“X”，并從左側檢查其結果（X→oa）。它與下一個輸入符號不匹配。所以自上而下的解析器回溯以獲得X的下一個產生式規則（X→ea）。

現在解析器按順序匹配所有輸入字母。接受字符串。

預測分析器Predictive parser

Predictive parser是一種遞歸下降解析器，它能夠預測將使用哪個產品來替換輸入字符串。預測解析器不受回溯的影響。

為了完成它的任務，預測解析器使用一個前瞻指針，它指向下一個輸入符號。為了使解析器無需回溯，預測解析器對語法施加一些約束，只接受一類稱為LL（k）語法的語法。

預測性分析使用堆棧和分析表來分析輸入并生成分析樹。堆棧和輸入都包含一個結束符號$，表示堆棧為空并且輸入被消耗。解析器引用解析表來決定輸入和堆棧元素的組合。

在遞歸下降解析中，對于單個輸入實例，解析器可能有多個產品可供選擇，而在預測解析器中，每個步驟最多有一個產品可供選擇。可能存在沒有與輸入字符串匹配的產品的實例，從而導致分析過程失敗。

LL分析器LL Parser

LL語法分析器接受LL語法。LL文法是上下文無關文法的一個子集，但有一定的限制，要得到簡化的版本，才能實現容易。LL語法可以通過遞歸下降和表驅動兩種算法來實現。
LL解析器表示為LL（k）。第一個L in LL（k）從左到右解析輸入，第二個Lin LL（k）表示最左邊的派生，k本身表示look ahead的數量。一般k=1，所以LL（k）也可以寫成LL（1）。

LL解析算法 LL Parser Algorithm

對于解析器的解釋，我們可以使用確定性的LL（1），因為表的大小隨著k的值呈指數增長。其次，如果給定的語法不是LL（1），那么對于任何給定的k，通常都不是LL（k）。

下面給出了LL（1）解析的算法：

Input: string ω
parsing table M for grammar G Output:
If ω is in L(G)
then
left-most derivation of ω, error otherwise.
Initial State :
$Sonstack(withSbeingstartsymbol)\omega$ in the input buffer SET ip to point the first symbol of ω$.
repeat
let X be the top stack symbol and a the symbol pointed by ip.
if X∈ Vt or $
if X = a
POP X and advance ip.
else
error()
endif
else /* X is non-terminal /
if M[X,a] = X → Y1, Y2,… Yk
POP X
PUSH Yk, Yk-1,… Y1 / Y1 on top /
Output the production X → Y1, Y2,… Yk
else
error()
endif
endif
until X = $ / empty stack */

如果A→α|β是G的兩個不同乘積，則語法G是LL（1）：

對于無終端，α和β都導出以a開頭的字符串。

α和β中至多有一個可以導出空字符串。

如果β→t，則α不導出以跟隨（a）中的終端開始的任何字符串。

總結

以上是生活随笔為你收集整理的编译器设计-解析类型的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。