檢視 LR分析器的原始碼

'''LR 分析器'''是一種對下跤起去（bottom-up）的頂下文無關係語法的分析器。'''LR'''意指由左（'''L'''eft）至正處理輸入字串，並以上正爿優先衍生（'''R'''ight 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 ( 零 ) 分析器使用的格如下：

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

* _ 徙位 _，記為'shift''n'，表示後一个狀態是 _ n _
* _ 化簡 _，記為'reduce''m'，表示使用第 _ 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

[[分類: 待校正]]