跳至內容

LALR語法分析器

維基百科,自由的百科全書

上下文無關文法
語法分析器
· LL剖析器
· 算符優先分析器
· LR剖析器
· SLR剖析器
· LALR剖析器

在計算機科學中,LALR分析器是一種規範LR分析方法英語Canonical_LR_parser的簡化形式。它可以對上下無關文法進行語法分析。LALR即「Look-Ahead LR」。其中,Look-Ahead為「向前看」,L代表對輸入進行從左到右的檢查,R代表反向構造出最右推導序列。 LALR分析器可以根據一種程序設計語言的正式語法的產生式英語Production_(computer_science)而對一段文本程序輸入進行語法分析,從而在語法層面上判斷輸入程序是否合法。 實際應用中的LALR分析器並不是由人手工寫成的,而是由類似於yaccGNU Bison之類的LALR語法分析器生成工具英語LALR_parser_generator構成。由機器自動生成的代碼相比較於程序員手工的代碼,擁有更好的運行效率而且減少了程序員的工作量。

歷史

[編輯]

1965年,Donald Knuth發明了LR分析器。LR分析器可以在線性時間里分析一個確定的上下文無關文法的輸入[1]。但是,最右推導技術所需的分析表需要一個巨大的內存空間,所以在那個內存空間緊缺的年代,LR分析技術被認為是不可行的。 為了解決這個缺點,在1969年,Frank DeRemer提出了兩種LR分析方法的簡化版[2],即LALR分析器和SLR分析器英語Simple_LR_parser。這兩種方法所需的內存空間較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)分析法族。對於所有的kj的組合,都可以由LR(j+k)分析法導出[4]。但是這種觀點沒有任何的實際意義。 相比較與其他的LR分析器,LALR分析器在一次簡單的對輸入流進行從左到右掃描時,可以更直接的根據向前看的那個字符確定一個從下至上的分析方法。這些是歸功於LALR分析器不需要回溯。作為一個定位於向前看的語法分析器,LALR(1)即為最常用的形式。

關於實現

[編輯]

由於LALR分析器採用了最右推導而不是採用最左推導,因此,理解LALR分析器的工作方法變得十分困難。而這導致了手動構造一個LALR分析器是一個消耗巨大而且費時的工作。而且當出現語法錯誤時,LALR分析器可能並不會馬上報錯,而是執行幾次歸約動作。 無論如何,任意的LR(k>0)分析器中,由於要在出錯時枚舉每一個可能的字符, 讓錯誤恢復這項工作變得十分繁瑣。 由於這個原因,在一些時候遞歸下降分析器比LALR分析器更實用。由於其較低的語法分析功能,一個遞歸下降分析器需要更多的手寫代碼。但是為一個遞歸下降分析器編寫代碼並不像LALR分析器那樣的困難,這是因為遞歸下降分析器使用了最左推導。一個值得注意的例子就是Gnu Compiler Collection中的CC++語言的語法分析器。其中語法分析器起始是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)分析器進行比較。對於任意的kj,都存在有某種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)的。

參考

[編輯]
  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). 
  2. ^ DeRemer, Franklin L. Practical Translators for LR(k) languages (PDF) (學位論文). MIT. 1969 [2023-12-26]. (原始內容存檔 (PDF)於2013-08-19). 
  3. ^ Frank DeRemer, Thomas Pennello, Efficient Computation of LALR(1) Look-Ahead Sets, Sigplan Notices - SIGPLAN, vol. 14, no. 8, 1979: 176–187 
  4. ^ Parsing Techniques: A Practical Guide, by Dick Grune and Ceriel J. H. Jacobs, "9.7 LALR(1)", p. 302頁面存檔備份,存於網際網路檔案館
  5. ^ "GCC 3.4 Release Series Changes, New Features, and Fixes"頁面存檔備份,存於網際網路檔案館), GCC.gnu.org.
  6. ^ "GCC 4.1 Release Series Changes, New Features, and Fixes頁面存檔備份,存於網際網路檔案館)", GCC.gnu.org.
  7. ^ "7.9 LR(1) but not LALR(1)頁面存檔備份,存於網際網路檔案館)", CSE 756: Compiler Design and Implementation頁面存檔備份,存於網際網路檔案館), Eitan Gurari, Spring 2008
  8. ^ "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. 

參見

[編輯]