可配置語法分析器開發紀事（三點五）——生成下推自動機的具體步驟

剛剛發了上一篇文章之后就發現狀態機畫錯了。雖然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，是下一篇文章的內容），然后就可以把狀態機變成這樣：

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

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

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

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

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