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

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

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

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

這樣就構(gòu)成了一個(gè)簡(jiǎn)單的文法，用來分析帶逗號(hào)分割的名字列表的。那么寫成狀態(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里面是一幅圖面簡(jiǎn)直太方便了）

但是這樣還沒完。IDList0跳到IDList2的時(shí)候的輸入“IDList”其實(shí)還不夠，因?yàn)橛米鬏斎氲膖oken其實(shí)只有NAME和","兩種。下一步即將演示如何從這個(gè)狀態(tài)機(jī)編程名副其實(shí)的下推狀態(tài)機(jī)。

在這里我先介紹幾個(gè)概念。第一個(gè)是移進(jìn)，第二個(gè)是規(guī)約。為什么要用這兩個(gè)名字呢？因?yàn)榇蟛糠秩丝吹纳当魄迦A大學(xué)出版社的低能編譯原理課本都是這么講的，黑化分別叫Shift和Reduce。好了，什么是Shift呢？IDList0跳到IDList2的時(shí)候，要移進(jìn)IDList。IDList3跳到IDList1，要移進(jìn)到ID。IDList0跳到IDList1也要移進(jìn)到ID。這也就是說，狀態(tài)轉(zhuǎn)移經(jīng)過一條非終結(jié)符的邊的時(shí)候會(huì)移進(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)到上一級(jí)的狀態(tài)了。

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

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

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

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

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

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

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

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

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

在下面的標(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á)實(shí)在是太難看了，所以貼成圖）

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

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