LR分析器

LR 分析器是一種對下跤起去（bottom-up）的頂下文無關係語法的分析器。LR意指由左（Left）至正處理輸入字串，並以上正爿優先衍生（Right derivation）的推導順序（相對的是 LL 分析器）建構語法樹。會當用這个方式來解破的方法共號做LR 語法。啊若佇咧LR ( k )按呢的名中間，k代表的是剖析時間需要前瞻符號（lookahead symbol）的數量，也就是除了目前處理甲的輸入符號以外，著閣向正爿參照幾个符號的意思；省略（k）時即看為 LR ( 一 )，毋是 LR ( 零 )。

因為 LR 分析器試由分析樹仔的葉節點開始，向頂頭一層透過文法規則的化簡，最後規約轉去樹仔的根部（先符號）， 所以伊是一種由下而上的分析方法。真濟程式語言使用 LR ( 一 ) 來講文法，所以足濟編譯器攏使用 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 分析過程如下：

一 . 共結尾字元 $ 佮起始狀態零依序壓入空堆疊，了後的狀態佮符號會予人壓入疊著的頂懸。 二 . 根據目前的狀態佮輸入的終端符號，去動作表內底揣著對應動作：

• 徙位（shift）s _ n _ :
• 共目前的終端符號由輸入緩衝區內底移出閣壓入疊
• 才將狀態 _ n _ 壓入疊出來閣成做上新的狀態
• 化簡（reduce）r _ m _ :
• 考慮第 m 條文法規則，假使講文法的 _ 正爿（right-hand side）_ 有 X 個符號，則將二 X 個元素對疊著彈出
• 這个時陣過去的某一个狀態會轉來疊頂懸
• 佇咧 _ 狀態轉移表 _ 走揣這个狀態拄著文法 _ 倒爿（left-hand side）_ 彼號符號的狀態轉移
• 共文法倒手爿的符號壓入疊
• 將走揣著新的狀態壓入疊著
• 接受，輸入字串解析完成。
• 無對應動作，此情形就算是文法錯誤。

三 . 重複步數二直到輸入的字串被接受或者是偵測著文法錯誤。

範例

考慮以下文法：

( 一 ) E → E \ * B

( 二 ) E → E + B

( 三 ) E → B

( 四 ) B → 零

( 五 ) B → 待剖析的輸入字串是：

一 + 一

動作表佮狀態轉移表

LR ( 零 ) 分析器使用的格如下：

動作表用表示目前狀態拄著 _ 終端符號 _（包含結尾字元 $）的對應動作，欄位內底可能有三種動作：

• _ 徙位 _，記為'shiftn'，表示後一个狀態是 _ n _
• _ 化簡 _，記為'reducem'，表示使用第 _ m _ 條文法規則化簡堆疊中的內容。
• _ 接受 _，記為'accept'，表示破析正確的完成，輸入的字串予文法所定義的語言接受 ・

狀態轉移表用表示簡化了後的狀態拄著 _ 非終端符號 _ 時的轉移規則。

分析過程

下表是分析過程中的各部份，疊的頂頭佇上正爿，狀態的轉移佮規堆的化簡單攏以上表為依據，猶閣特殊字元'$'嘛加到輸入攕的尾溜表示結尾。

範例說明

分析起頭的時陣疊會包含元素 $ 和零：

['$'零]

分析器頭先對輸入緩衝區看著符號'一'，根據 _ 動作表 _ 做狀態零拄著終端符號'一'的時陣用徙位動作s 二，即是將'一'對輸入緩衝區內底移出閣推入堆疊，閣將新的狀態二嘛疊起來，這个時陣疊起來變：

['$'零'一'二]

（ 為著避免終端符號佮狀態濫份，故堆疊著的終端符號攏加上單引號區別）

來看著的終端符號是'+'，根據動作表無論狀態二拄著任何終端符號，攏執行r 五動作（以第五條文法規則B → 一化簡堆疊內容）。 此化簡的動作表示破析器已經佇堆疊中認出第五條文法規則的正手爿部份，所以會當用這个規則的倒手爿符號 _ B _ 取代。因為乎第五條文法的正爿有一个符號，因此阮共兩个元素（一 × 二=二）自堆疊彈出，現此時會轉來狀態零，閣推入去符號 _ B _，並走揣轉移表中狀態零拄著非終端符號 _ B _ 後的新的狀態。新的狀態是四，完成這步數了後的疊起來是：

['$'零_ B _四]

因為頂一个總端符號'+'閣猶未予人處理，所以猶原保留佇輸入緩衝區內底。依據動作表，咧狀態四拄著'+'時做r 三化簡。根據第三條文法E → B，阮共四佮 _ B _ 從堆疊彈出，轉去狀態零。來壓入去 _ E _，根據狀態轉移表，做狀態零拄著非終端符號 _ E _ 愛轉移到狀態三，因此將三壓入疊：

['$'零_ E _三]

繼續猶未處理的符號'+'，做狀態三遇著'+'時陣的對應動作是s 六，將'+'對輸入中移出閣壓入疊，閣將新的狀態六嘛壓入疊：

['$'零_ E _三'+'六]

後一个符號是'一'，咧狀態六看著'一'時的動作是s 二，將'一'對輸入中移出閣壓入疊，閣將新的狀態二嘛壓入相疊：

['$'零E三'+'六'一'二]

最後看著的輸入符號是 $，狀態二拄著 $ 時的動作是r 五，以第五條文法規則化簡堆疊內容。此化簡動作佮第二步仝款，疊彈出兩个元素了後轉來狀態六，這當陣閣壓入符號 _ B _ 了後會進入狀態八（根據狀態轉移表）， 因此嘛共八壓入疊起來：

['$'零E三'+'六B八]

咧狀態八看著符號 $ 時間分析器會繼續化簡，根據動作表執行r 二化簡動作，採用第二條文法規則E → E + B簡化疊。因為這个規則的正手爿有三个符號，故從堆疊中彈出六个元素。這陣轉來狀態零，將規則倒爿的符號 _ E _ 疊起來了後，進入新的狀態三（根據狀態轉移表）， 共壓入後疊做：

['$'零E三]

落尾咧狀態三看著符號 $，對應的動作是 acc，表示分析順利完成。

建構 LR ( 零 ) 分析表

LR ( 零 ) 項目（Items）

建構破析表的過程愛使用 _ LR ( 零 ) 項目 _（以下簡稱做「項目」）， 這是項目是佇文法規則的正手爿插入一个特殊的符號「・」所產生。比如講文法 _ 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 → 零 _

_ B → 一 _

當咱來到狀態 _ E → E +·B _ 時，分析器期待看著非終端符號 _ B _，而且 _ B _ 閣會當推演為終端符號 _ 零 _ 佮 _ 一 _。所以這个時陣的狀態應表示：

_ E → E +·B _

_ B →·零 _

_ B →·一 _

即是「已經認出來 _ E + _ 部份，目前期待看著 _ B _，而且 _ B _ 也就是講'零'佮'一'」之意。現象會當共伊講：

若項目集合中包含 _ A → x·By _ 形式的項目，其中_ B _ 為非終端符號，則對所有的文法規則 _ B → w _ 來講，_ B →·w _ 嘛會予人加入項目集合內底。

逐个項目集合攏應該按呢規則擴充，共藏佇的項目加到集合內底一直到所有咧 ・ 了後的非終端符號攏處理過。遮爾所產生的新集合講這个項目集合的「封閉集」，符號的表示為closure ( _ I _ )，其中 _ I _ 表示原項目集合。分析過程中的各種狀態也就是由遮的封閉集所構成。

擴充文法

咧決定狀態中間的轉移前，咱著愛先加入一條擴充文法：

( 零 ) _ S → E _

其中 _ S _ 是新的起頭符號（start symbol）而且 _ E _ 是原先的起頭符號。這做法是為著使破析器能有一个唯一的起始狀態，譬如講考慮以下文法：

( 一 ) _E → E \ * B _

( 二 ) _ E → E + B _

( 三 ) _ E → B _

( 四 ) _ B → 零 _

( 五 ) _ B → 一 _

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

（零）_ S → E _

( 一 ) _ E → E \ * B _

( 二 ) _ E → E + B _

( 三 ) _ E → B _

( 四 ) _ B → 零 _

( 五 ) _ B → 一 _

可見起先狀態唯一確定。

走揣會當到的集合佮之間的轉移

建構破析表的頭一步是揣出封閉集合之間的轉移。封閉集會當看做是自動機中的狀態，若狀態間的轉移是由終端符號佮非終端符號決定。起先的狀態是由擴充的第零條文法規則對應的項目所形成的封閉集：

Item set 零

_ S →·E _

_ E →·E \ * B _

_ E →·E + B _

_ E →·B _

_ B →·零 _

_ B →·一 _

集合內底的頭一个項目是該集合的核心，透過集合的封閉規則，咱加入其他的項目補足集合使其實封閉。這組封閉集合是頭一个狀態（I 零）， 這馬咱欲揣出這組狀態可能的轉移情形。

參考資料

• _ Compilers : Principles , Techniques , and Tools _ , Aho，Sethi，Ullman，Addison-Wesley，一千九百八十六 . ISBN 空九二百空一四一曝空八十八分六
• Internals of an LALR ( 一 ) parser generated by GNU Bison