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

故事就從狀態(tài)機(jī)開(kāi)始。文法我就不重復(fù)了，見(jiàn)上一篇文章。現(xiàn)在我們從狀態(tài)機(jī)開(kāi)始。第一個(gè)狀態(tài)機(jī)是直接從文法變過(guò)來(lái)的：

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

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

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

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

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

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

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

所以，其實(shí)在這個(gè)時(shí)候，我們同時(shí)解決了“應(yīng)該在什么時(shí)候進(jìn)行左遞歸Shifting”的問(wèn)題。只要當(dāng)左遞歸Reducing已發(fā)生，我們立刻在軌跡上面補(bǔ)上一條左遞歸Shifting就好了。因此，我們?cè)谝婚_(kāi)始做parsing的時(shí)候，根本不需要預(yù)先做左遞歸Shifting。所以當(dāng)剛剛輸入A的時(shí)候，“狀態(tài)跳轉(zhuǎn)軌跡”是這樣子的：

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

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