LR剖析器

**LR 剖析器**是一種由下而上（bottom-up）的上下文無關語法剖析器。**LR** 意指由左（**L**eft）至右處理輸入字串，並以最右邊優先衍生（**R**ight derivation）的推導順序（相對於 LL 剖析器）建構語法樹。能以此方式剖析的語法稱為 **LR 語法**。而在 **LR(k)** 這樣的名稱中，**k** 代表的是剖析時所需**前瞻符號**（lookahead symbol）的數量，也就是除了目前處理到的輸入符號之外，還得再向右參照幾個符號之意；省略 **（k）** 時即視為 LR (1)，而非 LR (0)。

由於 LR 剖析器嘗試由剖析樹的葉節點開始，向上一層層透過文法規則的化簡，最後規約回到樹的根部（起始符號），所以它是一種由下而上的剖析方法。許多程式語言使用 LR (1) 描述文法，因此許多編譯器都使用 LR 剖析器剖析原始碼的文法結構。LR 剖析的優點如下：

* 眾多的程式語言都可以用某種 LR 剖析器（或其變形）剖析文法。（C++ 是個著名的例外）
* LR 剖析器可以很有效率的建置。
* 對所有「由左而右」掃描原始碼的剖析器而言，LR 剖析器可以在最短的時間內偵測到文法錯誤（這是指文法無法描述的字串）。

然而 LR 剖析器很難以人工的方式設計，一般使用「剖析產生器（parser generator）」或「編譯器的編譯器（compiler-compiler，產生編譯器的工具）」來建構它。LR 剖析器可根據剖析表（parsing table）的建構方式，分類為「簡單 LR 剖析器（SLR, Simple LR parser）」、「前瞻 LR 剖析器（LALR, Look-ahead LR parser）」以及「正統 LR 剖析器 (Canonical LR parser)」。這些解析器都可以處理大量的文法規則，其中 LALR 剖析器較 SLR 剖析器強大，而正統 LR 剖析器又比 LALR 剖析器能處理更多的文法。著名的 Yacc 即是用來產生 LALR 剖析器的工具。

## LR 剖析器的結構

以表格為主（table-based）由下而上的剖析器可用圖一描述其結構，它包含：

* 一個輸入緩衝區，輸入的原始碼儲存於此，剖析將由第一個符號開始依序向後掃描。
* 一座堆疊，儲存過去的狀態與化簡中的符號。
* 一張_狀態轉移表_（goto table），決定狀態的移轉規則。
* 一張_動作表_（action table），決定目前的狀態碰到輸入符號時應採取的文法規則，輸入符號指的是終端符號（Terminals）與非終端符號（Non-terminals）。

### 剖析演算法

LR 剖析過程如下：

1. 將結尾字元 $ 與起始狀態 0 依序壓入空堆疊，之後的狀態與符號會被壓入堆疊的頂端。
2. 根據目前的狀態以及輸入的終端符號，到動作表中找到對應動作：
  * 移位（shift）s_n_:
    * 將目前的終端符號由輸入緩衝區中移出並壓入堆疊
    * 再將狀態 _n_ 壓入堆疊並成為最新的狀態
  * 化簡（reduce）r_m_:
    * 考慮第 m 條文法規則，假設該文法的_右邊（right-hand side）_ 有 X 個符號，則將 2X 個元素從堆疊中彈出
    * 此時過去的某個狀態會回到堆疊頂端
    * 在_狀態轉移表_中尋找此狀態遇到文法_左邊（left-hand side）_ 的符號時的狀態轉移
    * 將文法左手邊的符號壓入堆疊
    * 將尋找到的新狀態壓入堆疊
  * 接受，輸入字串解析完成。
  * 無對應動作，此情形即為文法錯誤。
3. 重複步驟二直到輸入的字串被接受或偵測到文法錯誤。

### 範例

考慮以下文法：

　
: (1) E → E \* B

　
: (2) E → E + B

　
: (3) E → B

　
: (4) B → 0

　
: (5) B → 1

待剖析的輸入字串是：

　
: **1 + 1**

#### 動作表與狀態轉移表

LR (0) 剖析器使用的表格如下：

**動作表**用以表示目前狀態遇到_終端符號_（包含結尾字元 $）的對應動作，欄位中可能有三種動作：

* _移位_，記為'shift' 'n'，表示下個狀態是 _n_
* _化簡_，記為 'reduce' 'm'，表示使用第 _m_ 條文法規則化簡堆疊中的內容。
* _接受_，記為 'accept'，表示剖析正確的完成，輸入的字串被文法所定義的語言接受・

**狀態轉移表**用以表示簡化後的狀態遇到_非終端符號_時的轉移規則。

#### 剖析過程

下表是剖析過程中的各步驟，堆疊的頂端在最右邊，狀態的轉移與堆疊的化簡都以上表為依據，而特殊字元 '$' 也被加到輸入串的尾端表示結尾。

#### 範例說明

剖析起始時堆疊會包含元素 $ 與 0：

　
: [**$** **0**]

剖析器首先從輸入緩衝區看到符號 '1'，根據_動作表_當狀態 **0** 碰到終端符號 '1' 時採用移位動作 **s2**，即是將 '1' 從輸入緩衝區中移出並推入堆疊，再將新的狀態 **2** 也推入堆疊，這時堆疊會變成：

　
: [**$** **0** '1' **2**]

（為避免終端符號與狀態混淆，故堆疊中的終端符號都加上單引號區別）

接著看到的終端符號是 '+'，根據**動作表**無論狀態 **2** 碰到任何終端符號，都執行 **r5** 動作（以第五條文法規則 **B → 1** 化簡堆疊內容）。此化簡的動作表示剖析器已經在堆疊中認出第五條文法規則的**右手邊**部分，因此可以用該規則的**左手邊**符號 _B_ 取代。因為**第五條文法的右邊有一個符號**，因此我們**將兩個元素（1 × 2 = 2）自堆疊彈出**，此時會回到狀態 **0**，再推入符號 _B_，並**尋找轉移表中狀態 0 遇到非終端符號 _B_ 後的新狀態**。新的狀態是 **4**，完成此步驟後的堆疊是：

　
: [**$** **0** _B_ **4**]

由於上一個終端符號 '+' 尚未被處理，因此仍保留在輸入緩衝區中。依據**動作表**，在狀態 **4** 碰到 '+' 時做 **r3** 化簡。根據第三條文法 **E → B**，我們將 **4** 與 _B_ 從堆疊彈出，回到狀態 **0**。接著壓入 _E_，根據**狀態轉移表**，當狀態 **0** 遇到非終端符號 _E_ 時需轉移至狀態 **3**，因此將 **3** 壓入堆疊：

　
: [**$** **0** _E_ **3**]

繼續尚未處理的符號 '+'，當狀態 **3** 遇到 '+' 時的對應動作是 **s6**，將 '+' 從輸入中移出並壓入堆疊，再將新的狀態 6 也壓入堆疊：

　
: [**$** **0** _E_ **3** '+' **6**]

下一個符號是 '1'，在狀態 **6** 看到 '1' 時的動作是 **s2**，將 '1' 從輸入中移出並壓入堆疊，再將新的狀態 2 也壓入堆疊：

　
: [**$** **0** E **3** '+' **6** '1' **2**]

最後看到的輸入符號是 $，狀態 2 遇到 $ 時的動作是 **r5**，以第五條文法規則化簡堆疊內容。此化簡動作與第二步驟相似，堆疊彈出兩個元素後回到狀態 **6**，這時再壓入符號 _B_ 後會進入狀態 **8**（根據狀態轉移表），因此也將 8 壓入堆疊：

　
: [**$** **0** E **3** '+' **6** B **8**]

在狀態 **8** 看到符號 $ 時剖析器會繼續化簡，根據**動作表**執行 **r2** 化簡動作，採用第二條文法規則 **E → E + B** 簡化堆疊。由於該規則的右手邊有三個符號，故從堆疊中彈出六個元素。這時回到狀態 **0**，將規則左邊的符號 _E_ 推入堆疊後，進入新狀態 **3**（根據狀態轉移表），將之壓入後堆疊為：

　
: [**$** **0** E **3**]

最後在狀態 3 看到符號 $，對應的動作是 acc，表示剖析順利完成。

## 建構 LR (0) 剖析表

### LR (0) 項目（Items）

建構剖析表的過程須使用 _LR (0) 項目_（以下簡稱為「項目」），這些**項目**是在文法規則的右手邊插入一個特殊的符號「・」所產生。例如文法 _E → E + B_ 有下列四個對應的項目：

　
: _E →·E + B_

　
: _E → E· + B_

　
: _E → E + ·B_

　
: _E → E + B·_

若文法規則的形式是 _A → ε_，則對應的唯一項目是：

　
: _A →·_

建立項目的用意是要決定剖析器的狀態，例如 _E → E· + B_ 的意義是「剖析器已經在輸入的符號中認出 _E_ 的部分，目前正等著看到一個 '+' 符號與接續的 _B_ 的部份」。

 

### 項目集合

在一般的情形中，剖析器不能預知未來要用哪一條文法規則來化簡堆疊內容，因此很難以單一個項目決定狀態。例如以下文法：

　
: _E → E + B_

　
: _E → E \* B_

當剖析器認出堆疊中的 _E_ 部分時，它無法預測未來會繼續看到 '+' 或 '\*'，因此這時的狀態須以兩個項目表示：

　
: _E → E· + B_

　
: _E → E·\* B_

故我們使用項目的集合 { _E → E· + B_, _E → E·\* B_ } 來表示「剖析器認出 _E_ 並期待 _+ B_ 或 _\* B_」的狀態。

 

### 項目集合的封閉集

如前段敘述，剖析器總是期待在下個輸入中看到項目中的 '・' 之後的符號。如果 '・' 之後的符號是**非終端符號**，則應加入該符號所推演出的文法規則，如此才能正確的描述狀態。例如規則：

　
: _E → E + B_

　
: _B → 0_

　
: _B → 1_

當我們來到狀態 _E → E + ·B_ 時，剖析器期待看到非終端符號 _B_，而 _B_ 又可推演為終端符號 _0_ 與 _1_。因此這時的狀態應表示為：

　
: _E → E + ·B_

　
: _B →·0_

　
: _B →·1_

即是「已辨認出 _E +_ 部分，目前期待看到 _B_，而 _B_ 也就是 '0' 與 '1'」之意。此現象可以描述為：

　
: 若項目集合中**包含 _A → x·By_ 形式**的項目，其中**_B_ 為非終端符號**，則對所有的文法規則 _B → w_ 而言，_B →·w_ 也會被加入項目集合中。

每個項目集合都應該以此規則擴充，將潛在的項目加到集合中**直到所有在・之後的非終端符號都處理過**。如此所產生的新集合**稱作該項目集合的「封閉集」** ，符號的表示為 **closure(_I_)** ，其中 _I_ 表示原項目集合。剖析過程中的各種狀態即是由這些封閉集所構成。

 

### 擴充文法

在決定狀態間的轉移前，我們必須先加入一條擴充文法：

　
: (0) _S → E_

其中 _S_ 是新的起始符號（start symbol）而 _E_ 是原先的起始符號。這一做法是為了使剖析器能有一個唯一的起始狀態，例如考慮以下文法：

　
: (1) _E → E \* B_

　
: (2) _E → E + B_

　
: (3) _E → B_

　
: (4) _B → 0_

　
: (5) _B → 1_

有三條規則從起始符號開始，剖析器不得不選擇一條作為起始狀態。加入擴充文法後，我們使用下列規則來決定項目集合與狀態：

　
: **（0）_S → E_**

　
: (1) _E → E \* B_

　
: (2) _E → E + B_

　
: (3) _E → B_

　
: (4) _B → 0_

　
: (5) _B → 1_

可見起始狀態唯一確定。

 

### 尋找可到達的集合與之間的轉移

建構剖析表的第一步是找出封閉集合之間的轉移。封閉集可以視為自動機中的狀態，而狀態間的轉移則由終端符號與非終端符號決定。起始狀態是由擴充的第 0 條文法規則對應的項目所形成的封閉集：

　
: **Item set 0**

　
: _S →·E_

　
: _E →·E \* B_

　
: _E →·E + B_

　
: _E →·B_

　
: _B →·0_

　
: _B →·1_

集合中的第一個項目是該集合的核心，透過集合的封閉規則，我們加入其他項目補足集合使其封閉。這組封閉集合是第一個狀態（I0），現在我們要找出這組狀態可能的轉移情形。

## 參考資料

* _Compilers: Principles, Techniques, and Tools_, Aho，Sethi，Ullman，Addison-Wesley，1986. ISBN 0-201-10088-6
* Internals of an LALR(1) parser generated by GNU Bison