LALR語法分析器
上下文無關文法 語法分析器 |
|---|
| · LL剖析器 |
| · 算符優先分析器 |
| · LR剖析器 |
| · SLR剖析器 |
| · LALR剖析器 |
在計算機科學中，LALR分析器是一種規範LR分析方法的簡化形式。它可以對上下無關文法進行語法分析。LALR即「Look-Ahead LR」。其中，Look-Ahead為「向前看」，L代表對輸入進行從左到右的檢查，R代表反向構造出最右推導序列。 LALR分析器可以根據一種程序設計語言的正式語法的產生式而對一段文本程序輸入進行語法分析，從而在語法層面上判斷輸入程序是否合法。 實際應用中的LALR分析器並不是由人手工寫成的，而是由類似於yacc和GNU Bison之類的LALR語法分析器生成工具構成。由機器自動生成的代碼相比較於程序員手工的代碼，擁有更好的運行效率而且減少了程序員的工作量。
歷史
[編輯]1965年，Donald Knuth發明了LR分析器。LR分析器可以在線性時間里分析一個確定的上下文無關文法的輸入[1]。但是，最右推導技術所需的分析表需要一個巨大的內存空間，所以在那個內存空間緊缺的年代，LR分析技術被認為是不可行的。 為了解決這個缺點，在1969年，Frank DeRemer提出了兩種LR分析方法的簡化版[2]，即LALR分析器和SLR分析器。這兩種方法所需的內存空間較LR分析法減少了許多。即使在後來的1977年，LR分析器的空間優化方式被提出，但是其空間效率依然比不過LALR這種簡化版本。
1979年，Frank DeRemer和Tom Pennello宣布了對於LALR分析器的新的優化方法，這再一次提高了LALR分析器的空間使用效率[3] 。
概括
[編輯]通常來說，LALR分析器是指LALR(1)分析器。其中(1)代表了向前看一個字符，分析器可以根據這前面的一個字符確定分析時使用的產生式。相類似的，還有向前看兩個字符的LALR(2)分析器、甚至向前看k個字符的LALR(k)分析器，但是實際使用中很少使用這類分析器。 LALR分析方法基於LR(0)分析法演化而來，因此對於一個LALR(k)分析法可以看成LA(k)LR(0)分析法。實際上考慮到LR分析法，有兩種參數存在的LA(k)LR(j)分析法族。對於所有的k和j的組合，都可以由LR(j+k)分析法導出[4]。但是這種觀點沒有任何的實際意義。 相比較與其他的LR分析器，LALR分析器在一次簡單的對輸入流進行從左到右掃描時，可以更直接的根據向前看的那個字符確定一個從下至上的分析方法。這些是歸功於LALR分析器不需要回溯。作為一個定位於向前看的語法分析器，LALR(1)即為最常用的形式。
關於實現
[編輯]由於LALR分析器採用了最右推導而不是採用最左推導，因此，理解LALR分析器的工作方法變得十分困難。而這導致了手動構造一個LALR分析器是一個消耗巨大而且費時的工作。而且當出現語法錯誤時，LALR分析器可能並不會馬上報錯，而是執行幾次歸約動作。 無論如何，任意的LR(k>0)分析器中，由於要在出錯時枚舉每一個可能的字符， 讓錯誤恢復這項工作變得十分繁瑣。 由於這個原因，在一些時候遞歸下降分析器比LALR分析器更實用。由於其較低的語法分析功能，一個遞歸下降分析器需要更多的手寫代碼。但是為一個遞歸下降分析器編寫代碼並不像LALR分析器那樣的困難，這是因為遞歸下降分析器使用了最左推導。一個值得注意的例子就是Gnu Compiler Collection中的C和C++語言的語法分析器。其中語法分析器起始是LALR分析器，但是之後卻被改寫成遞歸下降分析器。[5][6]
與其他語法分析器的關係
[編輯]LR分析器
[編輯]嚴格的來說，LALR(1)分析器的功能比LR(1)分析器要弱一些；但是卻比SLR(1)分析器強。由LALR引入的對LR的簡化在於存在相同核心的項集；但是在LR分析法中，下個字符是未知的。而這種簡化導致了LALR的分析功能的下降：不知道下個字符導致了語法分析器不知道選擇哪個產生式，從而產生了歸約/歸約衝突。而SLR(1)分析法採用了更多的合併，導致了相較於LALR(1)更多的額外衝突。 下述是一個標準的LR(1)文法，但是並不能由LALR(1)分析器進行分析[7][8]。
S -> a E c
-> a F d
-> b F c
-> b E d
E -> e
F -> e
在LALR分析表的構造中，有兩個狀態將會被合併成一個狀態。而之後的下個字符將會出現歧義。這個狀態如下
E -> e. {c,d}
F -> e. {c,d}
對於一個LR(1)分析器，將產生兩個不同的狀態而不會產生衝突。但是一個LALR(1)分析器，只會產生一個狀態，從而產生衝突（若下個輸入字符為c或d，可以歸約成E或F）。因此，上述文法對於LALR(1)是二義的。
LL分析器
[編輯]LALR(k)分析器無法與LL(k)分析器進行比較。對於任意的k和j，都存在有某種LALR(k)文法，但該文法卻不是LL(j)文法，反之亦然。實際上，一個給定的LL(1)文法是否能由一個LALR(k)分析器進行分析都是不確定的（其中）。
稱每一個LL(1)都是SLR(1)或者LALR(1)的說法經常是錯誤的；確實存在一些LL(1)文法不是LALR(1)的。但實際上，給一個LL(1)文法附加一系列的技術條件就可以是LALR(1)的；而這些條件僅僅是避免了一系列確實無用的產生式規則。所以，實際中用到的LL(1)文法通常都是LALR(1)的。
參考
[編輯]- ^ Donald E. Knuth. On the translation of languages from left to right. Information and Control: 607–639. [2018-04-02]. doi:10.1016/s0019-9958(65)90426-2. （原始內容存檔於2020-06-07）.
- ^ DeRemer, Franklin L. Practical Translators for LR(k) languages (PDF) (學位論文). MIT. 1969 [2023-12-26]. （原始內容存檔 (PDF)於2013-08-19）.
- ^ Frank DeRemer, Thomas Pennello, Efficient Computation of LALR(1) Look-Ahead Sets, Sigplan Notices - SIGPLAN, vol. 14, no. 8, 1979: 176–187
- ^ Parsing Techniques: A Practical Guide, by Dick Grune and Ceriel J. H. Jacobs, "9.7 LALR(1)", p. 302 （頁面存檔備份，存於網際網路檔案館）
- ^ "GCC 3.4 Release Series Changes, New Features, and Fixes" （頁面存檔備份，存於網際網路檔案館）, GCC.gnu.org.
- ^ "GCC 4.1 Release Series Changes, New Features, and Fixes （頁面存檔備份，存於網際網路檔案館）", GCC.gnu.org.
- ^ "7.9 LR(1) but not LALR(1) （頁面存檔備份，存於網際網路檔案館）", CSE 756: Compiler Design and Implementation （頁面存檔備份，存於網際網路檔案館）, Eitan Gurari, Spring 2008
- ^ "Why is this LR(1) grammar not LALR(1)? （頁面存檔備份，存於網際網路檔案館）"
John C. Beatty. On the relationship between LL(1) and LR(1) grammars. Journal of the ACM (JACM). 1982-10-01, 29 (4): 1007–1022 [2018-04-02]. ISSN 0004-5411. doi:10.1145/322344.322350.
