下推自動機與語法分析

語法分析用於使用文法的產生式規則推匯出字串。它用於檢查字串的可接受性。編譯器用於檢查字串在語法上是否正確。解析器接收輸入並構建語法樹。

解析器可以分為兩種型別：

• 自頂向下解析器 - 自頂向下解析從頂部開始符號開始，使用語法樹推匯出字串。

• 自底向上解析器 - 自底向上解析從底部的字串開始，使用語法樹到達開始符號。

自頂向下解析器的設計

對於自頂向下解析，PDA 有以下四種類型的轉換：

• 彈出堆疊頂部產生式左側的非終結符，並壓入其右側字串。

• 如果堆疊的頂部符號與正在讀取的輸入符號匹配，則將其彈出。

• 將開始符號“S”壓入堆疊。

• 如果輸入字串完全讀取並且堆疊為空，則轉到最終狀態“F”。

示例

為表示式“x+y*z”設計一個自頂向下解析器，該解析器適用於具有以下產生式規則的文法 G：

P: S → S+X | X, X → X*Y | Y, Y → (S) | id

解答

如果 PDA 是 (Q, ∑, S, δ, q₀, I, F)，則自頂向下解析為：

(x+y*z, I) ⊢(x +y*z, SI) ⊢ (x+y*z, S+XI) ⊢(x+y*z, X+XI)

⊢(x+y*z, Y+XI) ⊢(x+y*z, x+XI) ⊢(+y*z, +XI) ⊢ (y*z, XI)

⊢(y*z, X*YI) ⊢(y*z, y*YI) ⊢(*z,*YI) ⊢(z, YI) ⊢(z, zI) ⊢(ε, I)

自底向上解析器的設計

對於自底向上解析，PDA 有以下四種類型的轉換：

• 將當前輸入符號壓入堆疊。

• 將堆疊頂部產生式的右側替換為其左側。

• 如果堆疊頂部的元素與當前輸入符號匹配，則將其彈出。

• 如果輸入字串完全讀取，並且只有開始符號“S”保留在堆疊中，則將其彈出並轉到最終狀態“F”。

示例

為表示式“x+y*z”設計一個自頂向下解析器，該解析器適用於具有以下產生式規則的文法 G：

P: S → S+X | X, X → X*Y | Y, Y → (S) | id

解答

如果 PDA 是 (Q, ∑, S, δ, q₀, I, F)，則自底向上解析為：

(x+y*z, I) ⊢ (+y*z, xI) ⊢ (+y*z, YI) ⊢ (+y*z, XI) ⊢ (+y*z, SI)

⊢(y*z, +SI) ⊢ (*z, y+SI) ⊢ (*z, Y+SI) ⊢ (*z, X+SI) ⊢ (z, *X+SI)

⊢ (ε, z*X+SI) ⊢ (ε, Y*X+SI) ⊢ (ε, X+SI) ⊢ (ε, SI)