剛剛發(fā)了上一篇文章之后就發(fā)現(xiàn)狀態(tài)機畫錯了。雖然LiveWriter有打開博客并修改文章的功能，不過為了讓我留下一個教訓，我還是決定發(fā)一篇勘誤。這個教訓就是，作分析的時候不要隨便“跳步”，該一步一步來就一步一步來。其實人呢，就是很容易忘掉以前的教訓的了。第一個告訴我不能這么干的人其實是小學三年級的數(shù)學老師。當時我因為懶得寫字，所以計算應用題的時候省了幾步，被批評了。

故事就從狀態(tài)機開始。文法我就不重復了，見上一篇文章?，F(xiàn)在我們從狀態(tài)機開始。第一個狀態(tài)機是直接從文法變過來的：

然后我們把所有的非終結(jié)符跳轉(zhuǎn)都通過Shift和Reduce連接到該非終結(jié)符所代表的狀態(tài)機的狀態(tài)上面，就會變成下面的圖。具體的做法是，對于每一條非終結(jié)符的跳轉(zhuǎn)，譬如說S0 –> Symbol –> S1。首先抹掉這條跳轉(zhuǎn)。然后增加兩條邊，分別是S0到Symbol的起始節(jié)點，操作是Shift<S0>。還有從Symbol的終結(jié)節(jié)點到S0，操作是Pop<S0> Reduce。Shift<S>等于把狀態(tài)S給push到堆棧里，然后Pop<S>等于在狀態(tài)里面彈出內(nèi)容是S的棧頂元素。如果失敗了怎么辦呢？那就不能用這條跳轉(zhuǎn)。跟上圖一樣，所有輸入$跳轉(zhuǎn)到Finish的邊，操作都是要Pop<Null>的。在剛開始分析的時候，堆棧有一個Null值，用來代表“語法分析從這里開始”。

這個圖的粗虛邊代表所有跟左遞歸有關(guān)的跳轉(zhuǎn)。這些邊是成對的，分別是左遞歸跳轉(zhuǎn)的Shift和Reduce。如果不是為了實現(xiàn)高性能的語法分析的話，其實這個狀態(tài)機已經(jīng)足夠了。這個圖跟語法分析的“狀態(tài)跳轉(zhuǎn)軌跡”有很大的關(guān)系。雖然IDList0你不知道第一步要跳轉(zhuǎn)到IDList0還是ID0，不過沒關(guān)系，現(xiàn)在我們先假設我們可以通過某種神秘的方法來預測到。那么，當輸入是A,B,C$的時候，狀態(tài)跳轉(zhuǎn)軌跡就會是如下的樣子：

為什么要這么做呢？我們把這幅圖想象成為
1：想做的箭頭表示push一個狀態(tài)
2：向下的箭頭表示修改當前狀態(tài)
3：向右的狀態(tài)表示pop一個狀態(tài)并修改當前狀態(tài)

因此當輸入到B的時候，到達ID1，并跳轉(zhuǎn)到IDList1。這個時候IDList1【左邊】的所有【還留在堆棧里】的狀態(tài)時Null和IDList0，當前狀態(tài)IDList1，輸入剩下,C$。這個圖特別的有用。當我們分析完并且把構(gòu)造語法樹的指令附著在這些箭頭上面之后，按順序執(zhí)行這些指令就可以構(gòu)造出一顆完整的語法樹了。

但是在實際操作里面，我們并沒有辦法預測“這里要左遞歸兩次”，也沒辦法在多次reduce的時候選擇究竟要從哪里跳到哪里。所以實際上我們要學習從EpsilonNFA到DFA的那個計算過程，把Shift和Reduce當成Epsilon，把吃掉一個token當成非Epsilon邊，然后執(zhí)行我之前寫的《構(gòu)造可配置詞法分析器》一文中的那個去Epsilon邊算法（如何從Nondeterministic到Deterministic，以及相關(guān)的Look Ahead，是下一篇文章的內(nèi)容），然后就可以把狀態(tài)機變成這樣：

上面粗體的Pop<IDList0>表示，這一個Pop是對應于那個左遞歸Shifting操作的。實際上這是做了一個怎樣的變化呢？從“物理解釋”上來講，其實是把“狀態(tài)跳轉(zhuǎn)軌跡”里面那些除了左遞歸shifting之外的所有不吃掉token的邊都去掉了：

在這里我們可以看到，為什么當堆棧是IDList0, IDList0和IDList0, IDList3的時候，從ID0都可以通過吃掉一個”,”從而跳轉(zhuǎn)到IDList3。在上面這張“狀態(tài)跳轉(zhuǎn)軌跡”里面，這兩個事情都發(fā)生了，分別是第一條向左的箭頭和第二條向左的方向。而且這兩條邊剛好對應于上圖帶有藍色粗體文字的跳轉(zhuǎn)，屬于左遞歸Reducing操作。

所以，其實在這個時候，我們同時解決了“應該在什么時候進行左遞歸Shifting”的問題。只要當左遞歸Reducing已發(fā)生，我們立刻在軌跡上面補上一條左遞歸Shifting就好了。因此，我們在一開始做parsing的時候，根本不需要預先做左遞歸Shifting。所以當剛剛輸入A的時候，“狀態(tài)跳轉(zhuǎn)軌跡”是這樣子的：

然后遇到一個”,”，發(fā)現(xiàn)之前“做漏”了一個左遞歸Shifting，因此就變成下面這個樣子：

這也就是上一篇文章那個Fake-Shift所做的事情了。