剛剛發了上一篇文章之後就發現狀態機畫錯了。雖然LiveWriter有打開博客並修改文章的功能，不過為了讓我留下一個教訓，我還是決定發一篇勘誤。這個教訓就是，作分析的時候不要隨便“跳步”，該一步一步來就一步一步來。其實人呢，就是很容易忘掉以前的教訓的了。第一個告訴我不能這麼干的人其實是小學三年級的數學老師。當時我因為懶得寫字，所以計算應用題的時候省了幾步，被批評了。
故事就從狀態機開始。文法我就不重復了，見上一篇文章。現在我們從狀態機開始。第一個狀態機是直接從文法變過來的：
然後我們把所有的非終結符跳轉都通過Shift和Reduce連接到該非終結符所代表的狀態機的狀態上面，就會變成下面的圖。具體的做法是，對於每一條非終結符的跳轉，譬如說S0 –> Symbol –> S1。首先抹掉這條跳轉。然後增加兩條邊，分別是S0到Symbol的起始節點，操作是Shift<S0>。還有從Symbol的終結節點到S0，操作是Pop<S0> Reduce。Shift<S>等於把狀態S給push到堆棧裡，然後Pop<S>等於在狀態裡面彈出內容是S的棧頂元素。如果失敗了怎麼辦呢？那就不能用這條跳轉。跟上圖一樣，所有輸入$跳轉到Finish的邊，操作都是要Pop<Null>的。在剛開始分析的時候，堆棧有一個Null值，用來代表“語法分析從這裡開始”。
這個圖的粗虛邊代表所有跟左遞歸有關的跳轉。這些邊是成對的，分別是左遞歸跳轉的Shift和Reduce。如果不是為了實現高性能的語法分析的話，其實這個狀態機已經足夠了。這個圖跟語法分析的“狀態跳轉軌跡”有很大的關系。雖然IDList0你不知道第一步要跳轉到IDList0還是ID0，不過沒關系，現在我們先假設我們可以通過某種神秘的方法來預測到。那麼，當輸入是A,B,C$的時候，狀態跳轉軌跡就會是如下的樣子：
為什麼要這麼做呢？我們把這幅圖想象成為
1：想做的箭頭表示push一個狀態
2：向下的箭頭表示修改當前狀態
3：向右的狀態表示pop一個狀態並修改當前狀態
因此當輸入到B的時候，到達ID1，並跳轉到IDList1。這個時候IDList1【左邊】的所有【還留在堆棧裡】的狀態時Null和IDList0，當前狀態IDList1，輸入剩下,C$。這個圖特別的有用。當我們分析完並且把構造語法樹的指令附著在這些箭頭上面之後，按順序執行這些指令就可以構造出一顆完整的語法樹了。
但是在實際操作裡面，我們並沒有辦法預測“這裡要左遞歸兩次”，也沒辦法在多次reduce的時候選擇究竟要從哪裡跳到哪裡。所以實際上我們要學習從EpsilonNFA到DFA的那個計算過程，把Shift和Reduce當成Epsilon，把吃掉一個token當成非Epsilon邊，然後執行我之前寫的《構造可配置詞法分析器》一文中的那個去Epsilon邊算法（如何從Nondeterministic到Deterministic，以及相關的Look Ahead，是下一篇文章的內容），然後就可以把狀態機變成這樣：
本欄目
