編譯原理 - 自頂向下解析

我們在上一章瞭解到，自頂向下解析技術從根節點開始解析輸入，逐步向下移動到葉節點，構建語法樹。自頂向下解析的型別如下所示

遞迴下降解析

遞迴下降是一種自頂向下的解析技術，它從頂部構建語法樹，並從左到右讀取輸入。它為每個終結符和非終結符實體使用過程。這種解析技術遞迴地解析輸入以生成語法樹，這可能需要或不需要回溯。但是，與其相關的語法（如果不是左因子化）則無法避免回溯。一種不需要任何回溯的遞迴下降解析形式稱為預測解析。

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

回溯

自頂向下解析器從根節點（開始符號）開始，並將輸入字串與產生式規則匹配以替換它們（如果匹配）。要理解這一點，請考慮以下 CFG 示例

S → rXd | rZd
X → oa | ea
Z → ai

對於輸入字串：read，自頂向下解析器將表現如下

它將從產生式規則中的 S 開始，並將它的結果與輸入的最左字母（即“r”）匹配。S 的產生式 (S → rXd) 與其匹配。因此，自頂向下解析器將前進到下一個輸入字母（即“e”）。解析器嘗試展開非終結符“X”並從左側檢查其產生式 (X → oa)。它與下一個輸入符號不匹配。因此，自頂向下解析器回溯以獲得 X 的下一個產生式規則 (X → ea)。

現在解析器以有序的方式匹配所有輸入字母。字串被接受。

預測分析器

預測分析器是一種遞迴下降分析器，它能夠預測要用於替換輸入字串的產生式。預測分析器不會出現回溯問題。

為了完成其任務，預測分析器使用一個向前看指標，該指標指向下一個輸入符號。為了使分析器免於回溯，預測分析器對語法施加了一些約束，並且只接受稱為 LL(k) 語法的語法類別。

預測分析使用堆疊和分析表來分析輸入並生成語法樹。堆疊和輸入都包含一個結束符號$，表示堆疊為空且輸入已消耗。解析器參考分析表來根據輸入和堆疊元素組合做出任何決策。

在遞迴下降分析中，解析器可能有多個產生式可供選擇，用於單個輸入例項，而在預測分析中，每個步驟最多隻有一個產生式可供選擇。在某些情況下，可能沒有與輸入字串匹配的產生式，導致解析過程失敗。

LL 分析器

LL 分析器接受 LL 語法。LL 語法是上下文無關語法的子集，但有一些限制以獲得簡化版本，以便於實現。LL 語法可以透過遞迴下降或表驅動兩種演算法來實現。

LL 分析器表示為 LL(k)。LL(k) 中的第一個 L 表示從左到右解析輸入，第二個 L 表示最左推導，k 本身表示向前看的數量。通常 k = 1，因此 LL(k) 也可寫為 LL(1)。

LL 解析演算法

為了方便解釋，我們可以堅持使用確定性 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 : $S on stack (with S being start symbol)
   ω$ 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 的兩個不同的產生式

• 則對於任何終結符，α 和 β 都不推匯出以 a 開頭的字串。

• α 和 β 中最多隻有一個可以推匯出空字串。

• 如果 β → t，則 α 不推匯出以 FOLLOW(A) 中的終結符開頭的任何字串。