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

（對學術感興趣的人可以去wiki一下“下推自動機”）

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

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

這樣就構成了一個簡單的文法，用來分析帶逗號分割的名字列表的。那么寫成狀態機就是如下的形式：

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是文法的起始狀態，而ID1和IDList1是文法的終結狀態，畫成圖如下：

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

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

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

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

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

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

但是Shift的時候并沒有產生輸入，所以實際上應該改成下面這個樣子。

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

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

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

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

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

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

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

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

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