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

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

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

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

剖析過程

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

目前的狀態	堆疊	輸入	將採取的動作
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