上一篇博客講到了構(gòu)造符號表的事情。構(gòu)造完符號表之后，就要進(jìn)入語義分析的后一個階段了：構(gòu)造狀態(tài)機(jī)。跟我以前寫的如何實現(xiàn)正則表達(dá)式引擎的兩篇文章講的一樣，自動機(jī)先從Epsilon Nondeterministic Automaton開始，然后一步一步構(gòu)造成Deterministic Automaton。但是語法分析和正則表達(dá)式有很大不同，那么這個自動機(jī)是什么樣子的呢？

（對學(xué)術(shù)感興趣的人可以去wiki一下“下推自動機(jī)”）

下推自動機(jī)和有限自動機(jī)的區(qū)別是，下推自動機(jī)擴(kuò)展成普通的自動機(jī)的時候，他的狀態(tài)的數(shù)目是無限的（廢話）。但是無限的東西是沒辦法用編程來表達(dá)的，那怎么辦呢？那就加入一個不定長度的“狀態(tài)描述”。下面我舉一個簡單的文法：

ID = NAME
IDList = ID | IDList “,” ID

這樣就構(gòu)成了一個簡單的文法，用來分析帶逗號分割的名字列表的。那么寫成狀態(tài)機(jī)就是如下的形式：

ID0 = ● NAME
ID1 = NAME ●
IDList0 = ● (ID | IDList “," ID)
IDList1 = (ID | IDList “,” ID) ●
IDList2 = (ID | IDList ● “,” ID)
IDList3 = (ID | IDList “,” ● ID)

ID0 –> NAME –> ID1
IDList0 –> ID –> IDList1
IDList0 –> IDList –> IDList2
IDList2 –> “,” –> IDList3
IDList3 –> ID –> IDList1

可以很容易的看出，ID0和IDList0是文法的起始狀態(tài)，而ID1和IDList1是文法的終結(jié)狀態(tài)，畫成圖如下：

（PowerPoint畫圖復(fù)制到LiveWriter里面是一幅圖面簡直太方便了）

但是這樣還沒完。IDList0跳到IDList2的時候的輸入“IDList”其實還不夠，因為用作輸入的token其實只有NAME和","兩種。下一步即將演示如何從這個狀態(tài)機(jī)編程名副其實的下推狀態(tài)機(jī)。

在這里我先介紹幾個概念。第一個是移進(jìn)，第二個是規(guī)約。為什么要用這兩個名字呢？因為大部分人看的傻逼清華大學(xué)出版社的低能編譯原理課本都是這么講的，黑化分別叫Shift和Reduce。好了，什么是Shift呢？IDList0跳到IDList2的時候，要移進(jìn)IDList。IDList3跳到IDList1，要移進(jìn)到ID。IDList0跳到IDList1也要移進(jìn)到ID。這也就是說，狀態(tài)轉(zhuǎn)移經(jīng)過一條非終結(jié)符的邊的時候會移進(jìn)到另一條文法的狀態(tài)機(jī)里。ID1和IDList1作為ID和IDList的終結(jié)節(jié)點(diǎn)，要根據(jù)“從那里移進(jìn)來的”分別規(guī)約然后跳轉(zhuǎn)到“IDList2或者IDList1”。這也就是說，一旦你到達(dá)了一條聞法的狀態(tài)機(jī)的終結(jié)狀態(tài)，就要開始規(guī)約然后跳轉(zhuǎn)到上一級的狀態(tài)了。

有人要問，那我怎么知道規(guī)約結(jié)束的時候要跳轉(zhuǎn)去哪里呢？這個問題問得非常好。讓我們回想一下我以前寫的如何手寫語法分析器這一篇文章。里面怎么說的？當(dāng)你手寫遞歸下降的語法分析器的時候，每一條文法其實都是一個函數(shù)。那調(diào)用函數(shù)的時候程序怎么就知道函數(shù)結(jié)束的時候下一條指令是什么呢？那當(dāng)然是因為編譯器幫我們把“調(diào)用函數(shù)的時候的下一條指令的地址”給push進(jìn)了調(diào)用堆棧。但是我們現(xiàn)在不手寫語法分析器了，而用下推狀態(tài)機(jī)來做，道理也是一樣的。在“移進(jìn)”的時候，先把當(dāng)前的狀態(tài)push進(jìn)堆棧，規(guī)約的時候，就可以看一下“棧頂那幾個狀態(tài)都是什么”，配合一次向前查看（這就是Look Ahead。LALR的那個LA，LALR(1)就是在LA的時候偷看一個token），來決定規(guī)約到哪里去。至于LA在這里的深刻內(nèi)涵我將下一篇文章再說。因為現(xiàn)在我還沒有做到Nondeterministic到Deterministic的一步，里面有很多黑科技，我想集中討論。

那現(xiàn)在讓我們把上面那幅圖的兩個狀態(tài)機(jī)連起來，產(chǎn)生一個下推自動機(jī)。但是在這里我先做第一步。因為IDList0到IDList1的跳轉(zhuǎn)是一個左遞歸的過程，先暫時不管。

橙色的邊都是一個輸入非終結(jié)符的跳轉(zhuǎn)，所以實際上在下推狀態(tài)機(jī)里面是不存在的。在這張圖里面我們處理了兩條ID的邊。IDList0會shift（就是在堆棧里面push）自己然后跳轉(zhuǎn)到ID0，因此ID1在查看到棧頂是IDList0的時候，他就知道走的是IDList0 –> ID –> IDList1這條路，因此就reduce并跳轉(zhuǎn)到了IDList1。IDList3同理。

但是Shift的時候并沒有產(chǎn)生輸入，所以實際上應(yīng)該改成下面這個樣子。

這樣Shift邊也就有輸入了。而且ID0到ID1也廢掉了。實際上ID0自己也應(yīng)該廢掉。現(xiàn)在還有一個問題沒解決，就是左遞歸和Reduce不產(chǎn)生輸入的問題。這兩個問題實際上是一起的。我們先來考慮一下為什么這里沒辦法用相同的辦法來把Reduce處理成產(chǎn)生輸入的。實際上是因為，你在這一個階段還不知道究竟Reduce要輸入什么才能跳轉(zhuǎn)，特別是token已經(jīng)結(jié)束并且parse出了一個完整的IDList的時候。以前你們是不是在看《Parsing Techniques》和《龍書》都對為什么一個字符串結(jié)尾要產(chǎn)生一個$字符感到很困惑呢？實際上他是特別有用的。現(xiàn)在我們來給他加上大家就明白了。在這里，這個文法的目標(biāo)是產(chǎn)生一個IDList結(jié)構(gòu)，所以$當(dāng)然也要加在IDList的終結(jié)狀態(tài)——IDList1上：

然后就輪到Reduce。ID1應(yīng)該是Reduce到哪里了？第一步自然是Reduce到IDList1。那么IDList1又要Reduce到哪里呢？我們可以看到，在IDList結(jié)束的時候，要么就是跳到IDList2，要么就是跳到FINISH。但是IDList2是通過左遞歸產(chǎn)生的，我們先不管他。跳到FINISH需要什么條件呢？第一個是輸入$，第二個是Pop完狀態(tài)之后堆棧會為空。所以這個時候我們可以先修改一下ID1到IDList1的Reduce邊：

最后就是左遞歸了。左遞歸的處理有點(diǎn)像hack，因為實際上你不能預(yù)先判斷你要不要左遞歸（也就是看一下token stream有多少個逗號），然后先shift幾個IDList0進(jìn)去，再慢慢來。所以我們只有在滿足跳轉(zhuǎn)關(guān)系的時候臨時插入一些IDList0。那么這個關(guān)系是什么呢？左遞歸的IDList結(jié)束——也就是從IDList0跳到IDList2——之后只有一種可能，就是輸入","。而且所有指向IDList1的邊都是輸入ID，所以這條左遞歸的線應(yīng)該從ID1（ID的終結(jié)狀態(tài)）連到IDList2，并且在鏈接的時候補(bǔ)充“假shift IDList0”：

橙色的兩個狀態(tài)分別是整個parsing過程的起始狀態(tài)和終結(jié)狀態(tài)。這個時候我們把所有沒用的邊和狀態(tài)都干掉，就變成了：

是不是覺得特別親切呢，這不就是正則表達(dá)式NAME ( “,” NAME)*的狀態(tài)機(jī)嗎？這也是因為這個文法剛好可以表達(dá)為一個正則文法才有這樣的結(jié)果，如果我們給他加點(diǎn)兒括號改變點(diǎn)優(yōu)先級什么的，那就會變成一個復(fù)雜得多的狀態(tài)機(jī)了。好了。現(xiàn)在我們來模擬一下下推狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換和堆棧操作過程，來分析一下A,B,C$這個輸入吧。

在下面的標(biāo)示圖里面，我們用s|abc|def來分別表達(dá)當(dāng)前狀態(tài)s、當(dāng)前堆棧里的狀態(tài)abc（棧頂在右邊）和正在等待的輸入def。那么初始狀態(tài)肯定就是
IDList0 | null | A,B,C$

然后就開始了！（用文字表達(dá)實在是太難看了，所以貼成圖）

如果成功到達(dá)FINISH并且堆棧和輸入都全部沒有了的話，那就證明，parsing過程完美結(jié)束，沒有任何錯誤發(fā)生。

如何從文法生成下推自動機(jī)并完成parsing工作的大概過程就寫到這里了。目前開發(fā)進(jìn)度是到“生成非確定性下推自動機(jī)”這里。當(dāng)我完成了生成“確定性下推自動機(jī)”——也就是上面的最后一個狀態(tài)機(jī)圖的時候——就會開始寫下一篇文章，講面對復(fù)雜的文法的時候，下推自動機(jī)將要如何調(diào)整。同時將重點(diǎn)描述Look Ahead部分，以及為什么LALR(1)要設(shè)計成那個樣子。