檢視 LALR語法分析器的原始碼

佇計算機科學內底，'''LALR 分析器'''是一種規範 LR 分析方法的簡化形式。伊會當對頂下無關文法進行語法分析。'''LALR'''即「'''L'''ook-'''A'''head'''LR'''」。 其中，Look-Ahead 為「向前看」，L 代表對輸入行對左右的檢查，R 代表反向構造出上正推導序列。'''LALR 分析器'''會當根據一種程序設計語言的正式語法的產生式來對著一段文本程序輸入來進行語法分析，對語法層面判斷輸入程序敢有合法。
實際應用中的 LALR 分析器並毋是由跤手工寫成的，是因為這種 yacc 和 GNU Bison 啥物彼款 LALR 語法分析器生成工具構成。是由機器自動生的代碼佮仝款比程式設計師手工的代碼，有閣較好的運行效率而且減少程式設計師的工作量。

==歷史==

一九六五年，Donald Knuth 發明矣 LR 分析器。LR 分析器會當佇線性時間里分析一个確定的上下文無關文法的輸入。猶毋過，上右推捒技術所需要的分析表需要一个誠大的內存空間，所以佇彼个內存空間欠缺的時代，LR 分析技術予人認為是不可行的。
為著欲解決這个缺點，佇一九六九年，Frank DeRemer 提出兩種 LR 分析方法的簡化版，即 LALR 分析器佮 SLR 分析器。這兩種方法所需要的內存空間較 LR 分析法減少了真濟。就算講佇後來的一九七七年，LR 分析器的空間優化的方式被提出，但是其實這个空間效率猶原比袂過 LALR 這種簡化版本。
一九七九年，Frank DeRemer 和 Tom Pennello 宣布矣對 LALR 分析器的新的優化方法，這就閣一改提高矣 LALR 分析器的空間使用效率。

==概括==

通常來講，LALR 分析器是講 LALR ( 一 ) 分析器。其中 ( 一 ) 代表著伊向前看一字符，分析器會當根據這頭前的一字符確定分析的時使用的產生式。相類似的，閣有向前看兩字符的 LALR ( 二 ) 分析器、甚至向前看 k 字符的 LALR ( _ k _ ) 分析器，毋過實際使用中真少使用這類分析器。
LALR 分析方法因為 LR ( 零 ) 分析法演化來，因此對著一个 LALR ( _ k _ ) 分析法會當看做 LA ( _ k _ ) LR ( 零 ) 分析法。實際上考慮著 LR 分析法，有兩種參數佇咧的 LA ( _ k _ ) LR ( _ j _ ) 分析法族。對所有的 _ k _ 和 _ j _ 的組合，攏會當由 LR ( _ j _ + _ k _ ) 分析法共導出。但是這種觀點無任何的實際意義。
相較佮其他的 LR 分析器，LALR 分析器佇一擺簡單的對輸入流進行對左到正掃描的時，會當閣較直接的根據向前看的彼字符確定一个對下至上的分析方法。這寡是歸功於著 LALR 分析器無需要回溯。做一个定位佇向前看的語法分析器，LALR ( 一 ) 就是上捷用的形式。

==關於著實現==

因為 LALR 分析器採用了上正推導毋是採用上倒推導，所以，理解 LALR 分析器的工作方法變甲十分困難。這致使手動構造一个 LALR 分析器是一个消磨誠大而且費時的工課。而且當出現語法錯誤的時陣，LALR 分析器可能並袂講隨報毋著，是執行幾擺歸約動作。
毋管按怎，任意的 LR ( _ k > 零 _ ) 分析器中，因為欲佇出錯時枚舉每一个可能的字符，予錯誤恢復這項工課變甲十分厚工。
因為這个原因，佇咧一寡時陣遞歸下降分析器比 LALR 分析器閣較實用。因為其他低的語法分析功能，一个遞歸下降分析器需要閣較濟的手寫代碼。毋過為一个遞歸下降分析器編寫代碼並無像 LALR 分析器彼款的困難，這是因為遞歸下降分析器使用了上左推導。一个值得注意的例就是 Gnu Compiler Collection 中的 C 和 C + + 語言的語法分析器。其中語法分析器開始是 LALR 分析器，毋過了後煞予人改寫做遞歸下降分析器。

==佮其他的語法分析器的關係==

===LR 分析器===

論真來講，LALR ( 一 ) 分析器的功能比 LR ( 一 ) 分析器愛弱一寡；但是咧煞比 SLR ( 一 ) 分析器強。由 LALR 引入的著 LR 的簡化佇咧講'''佮核心的項集'''；猶毋過佇咧 LR 分析法內底，後一个字符是未知的。這款簡單的致使著 LALR 的分析功能的降低：毋知下字符致使語法分析器毋知選擇佗一个產生式，從而產生了歸約 / 歸約衝突。而且 SLR ( 一 ) 分析法採用閣較濟合併，致使著相比並 LALR ( 一 ) 閣較濟的額外衝突。
下述是一個標準的 LR ( 一 ) 文法，但是並袂當由 LALR ( 一 ) 分析器進行分析。

佇咧 LALR 分析表的構造當中，有兩个狀態將會予人合做一个狀態。啊若了後的後一个字符將會出現歧義。這个狀態下對一个 LR ( 一 ) 分析器，共產生兩个無仝款的狀態袂產生衝突。但是一个 LALR ( 一 ) 分析器，干焦會產生一个狀態，從而產生衝突（若後壁入字符為 c 抑是 d，會當歸約做 E 抑是 F）。 所以，咧講文法對 LALR ( 一 ) 是二義的。

===LL 分析器===

LALR ( _ k _ ) 分析的家私無法度佮 LL ( _ k _ ) 分析器進行較。對任意的 _ k _ 和 _ j _，攏佇咧有某一種 LALR ( _ k _ ) 文法，但是文法煞毋是 LL ( _ j _ ) 文法，反之亦然。實際上，一个予定的 LL ( 一 ) 文法敢會當對一个 LALR ( _ k _ ) 分析器進行分析攏是無確定的（其中 $ k \ geq 零 $）。

稱每一个 LL ( 一 ) 攏是 SLR ( 一 ) 抑是講 LALR ( 一 ) 的講法定定是錯誤的；確實存在一寡 LL ( 一 ) 文法毋是 LALR ( 一 ) 的。但實際上，予一个 LL ( 一 ) 文法附加一系列的技術條件就會當是 LALR ( 一 ) 的；遮的條件干焦避免一系列確實無路用的產生式規則。所以乎，實際中用著的 LL ( 一 ) 文法通常攏是 LALR ( 一 ) 的。

==參考==

==參見==

* 編譯器
* 語法分析器

[[分類: 待校正]]