2.4 少許理論知識(shí)——LL（1）與LALR（1）

2.3.2節(jié)中手寫的解析器會(huì)對(duì)記號(hào)進(jìn)行預(yù)讀，并按照語(yǔ)法圖的流程讀入所有記號(hào)。這種類型的解析器叫作LL（1）解析器。LL（1）解析器所能解析的語(yǔ)法，叫作LL（1）語(yǔ)法。

采用LL（1）語(yǔ)法，當(dāng)然能制作出對(duì)應(yīng)的編程語(yǔ)言來(lái)。比如Pascal的語(yǔ)法就是LL（1）。

但是看了代碼清單2-9就能明白，LL（1）解析器在語(yǔ)法上需要非終結(jié)符與解析器內(nèi)部的函數(shù)一一對(duì)應(yīng)。也就是說(shuō)，只看第一個(gè)進(jìn)入的記號(hào)，還無(wú)法判斷需不需要繼續(xù)往下讀取，也不能知道當(dāng)前非終結(jié)符究竟是什么。

比如在Pascal中，goto語(yǔ)句使用的標(biāo)簽只能是數(shù)字，這樣限制的原因是，如果像C語(yǔ)言一樣允許英文字母作為標(biāo)識(shí)符的話，讀入第一個(gè)記號(hào)時(shí)，就沒(méi)有辦法區(qū)分這個(gè)記號(hào)究竟是賦值語(yǔ)句的一部分，還是標(biāo)簽語(yǔ)句的一部分。因?yàn)闊o(wú)論賦值語(yǔ)句還是標(biāo)簽語(yǔ)句，開始的標(biāo)識(shí)符是一樣的。由此可知，LL（1）語(yǔ)法所做出的解析器都比較簡(jiǎn)單，語(yǔ)法能表達(dá)的范圍比較狹窄。

那么，在把計(jì)算器的BNF改寫為語(yǔ)法圖的過(guò)程中，一些敏銳的讀者可能已經(jīng)有了這樣的疑問(wèn)：

不管是用BNF還是語(yǔ)法圖，都應(yīng)該只是表面上有區(qū)別，語(yǔ)法實(shí)現(xiàn)部分應(yīng)該是一樣的啊。但你寫的代碼怎么連算法都不一樣？我有種上當(dāng)了的感覺(jué)。

實(shí)際上確有此事，在把BNF置換為圖2-5所示的語(yǔ)法圖時(shí)，我運(yùn)用了一個(gè)小手法。在BNF中語(yǔ)法規(guī)則是這樣的：

      expression /＊ 表達(dá)式的規(guī)則 ＊/
              | expression ADD term /＊ 或 表達(dá)式 + 項(xiàng)目 ＊/

而在實(shí)現(xiàn)遞歸下降分析時(shí)，如果仍然按這個(gè)規(guī)則在parse_expression（）剛開始就調(diào)用parse_expression（），會(huì)造成死循環(huán)，一個(gè)記號(hào)也讀不了。

BNF這樣的語(yǔ)法稱為左遞歸，原封照搬左遞歸的語(yǔ)法規(guī)則，是無(wú)法實(shí)現(xiàn)遞歸下降分析的。

所以yacc生成的解析器稱為LALR（1）解析器，這種解析器能解析的語(yǔ)法稱為LALR（1）語(yǔ)法。LALR（1）解析器是LR解析器的一種。

LL（1）的第一個(gè)L，代表記號(hào)從程序源代碼的最左邊開始讀入。第二個(gè)L則代表最左推導(dǎo)（Leftmost derivation），即讀入的記號(hào)從左端開始置換為分析樹。而與此相對(duì)的LR解析器，從左端開始讀入記號(hào)與LL（1）解析器一致，但是發(fā)生歸約時(shí)（參看2.2.3節(jié)圖2-3），記號(hào)從右邊開始?xì)w約，這稱為最右推導(dǎo)（Rightmost derivation），即LR解析器中R字母的意思。

遞歸下降分析會(huì)按自上而下的順序生成分析樹，所以稱作遞歸“下降”解析器或遞歸“向下”解析器。而LR解析器則是按照自下而上的順序，所以也稱為“自底向上”解析器。

此外，LL（1）、LALR（1）等詞匯中的（1），代表的是解析時(shí)所需前瞻符號(hào)（lookahead symbol），即記號(hào)的數(shù)量。

LALR（1）開頭的LA兩個(gè)字母，是Look Ahead的縮寫，可以通過(guò)預(yù)讀一個(gè)記號(hào)判明語(yǔ)法規(guī)則中所包含的狀態(tài)并生成語(yǔ)法分析表。LALR也是由此得名的。

本章中實(shí)際制作的計(jì)算器是采用LL（1）語(yǔ)法作為解析器的，因?yàn)楸容^簡(jiǎn)單，所以適合手寫。如果是LALR（1）等LR語(yǔ)法的話，則更適合用yacc等工具自動(dòng)生成（這話可能已經(jīng)說(shuō)了太多遍了）。不過(guò)，最近像ANTLR、JavaCC等一些采用LL（k），即預(yù)讀任意個(gè)記號(hào)的LL解析器也開始普及起來(lái)。

      Hoge ＊hoge_p = NULL;