上一篇博客講到了構造符號表的事情。構造完符號表之後，就要進入語義分析的後一個階段了：構造狀態機。跟我以前寫的如何實現正則表達式引擎的兩篇文章講的一樣，自動機先從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的時候並沒有產生輸入，所以實際上應該改成下面這個樣子。
本欄目
最後就是左遞歸了。左遞歸的處理有點像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)要設計成那個樣子。
