LR剖析器

LR 剖析器是一種由下而上（bottom-up）的上下文無關語法剖析器。LR 意指由左（Left）至右處理輸入字串，並以最右邊優先衍生（Right 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） sn:
     • 將目前的終端符號由輸入緩衝區中移出並壓入堆疊
     • 再將狀態 n 壓入堆疊並成為最新的狀態
   • 化簡（reduce） rm:
     • 考慮第 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) 剖析器使用的表格如下：

	動作						狀態轉移
狀態	*	+	0	1	$		E	B
0			s1	s2			3	4
1	r4	r4	r4	r4	r4
2	r5	r5	r5	r5	r5
3	s5	s6			acc
4	r3	r3	r3	r3	r3
5			s1	s2				7
6			s1	s2				8
7	r1	r1	r1	r1	r1
8	r2	r2	r2	r2	r2

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

• 移位，記為 'sn'，表示下個狀態是 n
• 化簡，記為 'rm'，表示使用第 m 條文法規則化簡堆疊中的內容。
• 接受，記為 'acc'，表示剖析正確的完成，輸入的字串被文法所定義的語言接受．

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

剖析過程

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

目前的狀態	堆疊	輸入	將採取的動作
0	$ 0	1+1$	Shift 2
2	$ 0 '1' 2	+1$	Reduce 5
4	$ 0 B 4	+1$	Reduce 3
3	$ 0 E 3	+1$	Shift 6
6	$ 0 E 3 + 6	1$	Shift 2
2	$ 0 E 3 + 6 '1' 2	$	Reduce 5
8	$ 0 E 3 + 6 B 8	$	Reduce 2
3	$ 0 E 3	$	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 的部份」。

結論：LR(0)項目是由文法規則所產生

項目集合

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

E → E + B

E → E * B

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

E → E ‧ + B

E → E ‧ * B

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

結論：LR(0)項目可以形成集合並描述剖析過程的狀態

項目集合的封閉集

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

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