編譯器設計 - 自底向上分析器

自底向上分析從樹的葉子節點開始，向上工作直到到達根節點。在這裡，我們從一個句子開始，然後以相反的方式應用產生式規則，以便到達開始符號。下圖描述了可用的自底向上分析器。

移進-歸約分析

移進-歸約分析使用兩個獨特的步驟進行自底向上分析。這些步驟稱為移進步驟和歸約步驟。

• 移進步驟：移進步驟指的是輸入指標向下一個輸入符號（稱為移進符號）的推進。此符號被壓入堆疊。移進符號被視為語法樹的單個節點。

• 歸約步驟：當分析器找到一個完整的語法規則（RHS）並將其替換為（LHS）時，稱為歸約步驟。當堆疊頂部包含一個控制代碼時，就會發生這種情況。為了歸約，對堆疊執行 POP 函式，該函式彈出控制代碼並將其替換為 LHS 非終結符。

LR 分析器

LR 分析器是一種非遞迴的、移進-歸約的、自底向上的分析器。它使用廣泛的上下文無關語法，使其成為最有效的語法分析技術。LR 分析器也稱為 LR(k) 分析器，其中 L 表示從左到右掃描輸入流；R 表示反向構建最右推導，k 表示用於決策的前瞻符號數。

有三種廣泛使用的演算法可用於構建 LR 分析器

• SLR(1) – 簡單 LR 分析器
  • 適用於最小的語法類別
  • 狀態數少，因此表格非常小
  • 簡單快速的構建
• LR(1) – LR 分析器
  • 適用於完整的 LR(1) 語法集
  • 生成大型表格和大量狀態
  • 構建速度慢
• LALR(1) – 前瞻 LR 分析器
  • 適用於中等大小的語法
  • 狀態數與 SLR(1) 相同

LR 分析演算法

這裡我們描述了一個 LR 分析器的骨架演算法

token = next_token()

repeat forever
   s = top of stack
   
   if action[s, token] = “shift si” then
      PUSH token
      PUSH si 
      token = next_token()
      
   else if action[s, token] = “reduce A::= β“ then 
      POP 2 * |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]
      
   else if action[s, token] = “accept” then
      return
      
   else
      error()

LL 與 LR