上一篇博客寫到了如何給一個非終結(jié)符的文法規(guī)則構(gòu)造出一個壓縮過的下推狀態(tài)機(jī)，那么今天說的就是如何把所有的文法都連接起來。其實主要的idea在（三）和他的勘誤（三點五）里面已經(jīng)說得差不多了。但是今天我們要處理的是帶信息的transition，所以還有一些地方要注意一下。

所以在這里我們先把幾條文法的最后的狀態(tài)機(jī)都列出來（大圖）：

接下來的這一步，就是要對所有靠非終結(jié)符（Exp啊Term這些）進(jìn)行跳轉(zhuǎn)的transition都執(zhí)行上一篇文章所說的傳說中的交叉鏈接。在產(chǎn)生鏈接的時候，我們給shift和reduce的邊分別加上shift和reduce。而shift和reduce是有參數(shù)的——就是被shift走的狀態(tài)的id。這樣可以在parse的時候匹配和處理狀態(tài)堆棧。在這里我門對e3->e1這一步做一下操作做為例子。紅色的邊是被刪掉的，而粗壯的綠色邊是被新加進(jìn)去的：

紅色的邊變成了兩條綠色的邊，紅色的邊附帶的信息則被復(fù)制到了綠色的reduce邊上。當(dāng)我們使用這個狀態(tài)機(jī)的時候，shift(s3)就表示往堆棧里面壓入s3，reduce(s3)就表示從堆棧里面彈出(s3)。當(dāng)然彈出不一定會成功，所以如果不成功的話，這條邊就不能在當(dāng)時使用。因此這也就是為什么在e3跳轉(zhuǎn)到t0之后，t1知道往回跳的是e1而不是別的什么地方——就如同為什么C++的函數(shù)執(zhí)行完之后總是知道如何跳轉(zhuǎn)回調(diào)用它的地方一樣——因為把信息推入了堆棧。

那現(xiàn)在我們就來看一下，當(dāng)所有的非終結(jié)符跳轉(zhuǎn)都處理掉之后，會變成什么樣子吧（這個圖真是復(fù)雜和亂到我不想畫?。?，為了讓圖變得不那么糟糕，我把shift都變成紫色，reduce都變成綠色：

在添加shift和reduce邊之前，每一條邊都是有輸入token的。但是我們剛剛添加上去的shift和reduce邊卻是不輸入token的，所以他們是epsilon邊，下一步就是要消除他們。上面這個圖消除了epsilon邊之后，會變成一個狀態(tài)很少，但是每一條邊附帶的信息都會非常多，而且像n1這種經(jīng)常到達(dá)的狀態(tài)（因為四則運算里面有很多數(shù)字）將恢復(fù)射出無數(shù)條邊。到了這里這個狀態(tài)機(jī)已經(jīng)再也畫不出來了。所以我下面就只拿兩個例子來畫。下面要展示的是用Exp來parse單獨的一個數(shù)字會走的邊，當(dāng)然就是Exp –> Term –> Factor –> Number了：

就會被處理成：

注意邊上面的信息是要按順序重新疊加在一起的。當(dāng)所有的epsilon邊都去掉了之后，我們就得到了最終的一個狀態(tài)機(jī)。最重要的一件事情出現(xiàn)了。我們知道，發(fā)明LR和LALR這種東西就基本上是為了處理左遞歸的，所以這種圖就可以在去除epsilon邊的過程中自動發(fā)現(xiàn)左遞歸。這是怎么做到的呢？只要在去除epsilon邊的時候，發(fā)現(xiàn)了一條完全由shift這種epsilon邊組成的環(huán)，那么左遞歸就發(fā)現(xiàn)了。為了方便，我們可以只處理直接左遞歸——就是這種環(huán)的長度是1的。不包含間接左遞歸的問法是很容易寫出來的。當(dāng)然這種環(huán)并不一定是首尾相接的，譬如說我們在處理e0的時候就會發(fā)現(xiàn)e0->t0->t0這種環(huán)（當(dāng)然嚴(yán)格來說環(huán)只有最后一截的這個部分）。我們的程序要很好地應(yīng)對這種情況。因為我們只接受直接左遞歸，所以類似這種結(jié)構(gòu)的epsilon路徑可以直接的拋棄他，因為t0->t0會被t0狀態(tài)單獨處理掉。因此這樣做并不會漏掉什么。

細(xì)心的朋友可能會發(fā)現(xiàn)，這個結(jié)構(gòu)的圖是不能直接處理右遞歸的（總之左遞歸和右遞歸總要有一個會讓你的狀態(tài)機(jī)傻逼就是了?。?。關(guān)于如何處理有遞歸（其實內(nèi)容也不復(fù)雜）地方法會在“下篇”描述出來。那處理左遞歸有什么用呢？舉個例子，我們的e0->e2就是一個左遞歸，而他會在之前的步驟被處理成shift(e0->e0)和reduce(e1->e2)。我們要記下shift和reduce的對應(yīng)關(guān)系，那么當(dāng)我們找到一個左遞歸的shift之后，我們就可以把對應(yīng)的reduce給標(biāo)記成“left-recursive-reduce”。這是一個在構(gòu)造語法樹的時候，非常關(guān)鍵的一種構(gòu)造指令。

處理完這些之后，我們可以把左遞歸的shift邊全部刪掉，最后把token和state都統(tǒng)統(tǒng)處理成連續(xù)的數(shù)字，做成一張[state, token] –> [transitions]的二維表，每一個表的元素是transition的列表。為什么是這樣呢？因為我們對一個state輸入一個token之后，由于保存著state的堆棧（你還記得嗎？shift==push，reduce==pop）的棧頂若干個元素的不同，可能會走不通的路線。于是最后我們就得到了這么一張圖。

下面這張圖可以通過運行g(shù)ac.codeplex.com上面的Common\UnitTest\UnitTest.sln（VS2012限定）之后，在Common\UnitTest\TestFiles\Parsing.Calculator.Table.txt里面找到。這一組文件都是我在測試狀態(tài)機(jī)的時候log下來的。

如果大家有VS2012的話，通過運行我準(zhǔn)備的幾個輸入，譬如說“1*2+3*4”，就可以在Parsing.Calculator.[2].txt里面找到所有狀態(tài)跳轉(zhuǎn)的軌跡。因為我們總是需要parse一個Exp，所以我們從22: Exp.RootStart開始。我們假設(shè)token stream的第一個和最后一個分別是$TokenBegin和$TokenFinish。上圖的$TryReduce是為了應(yīng)對右遞歸而設(shè)計出來的一種特殊輸入。由于四則運算里面并沒有右遞歸，所以這一列就是空的：

StartState: 22[Exp.RootStart]
$TokenBegin => 23[Exp.Start]
    State Stack:
NUMBER[1] => 2[Number.1]
    State Stack: 23[Exp.Start], 21[Term.Start], 19[Factor.Start]
    Shift 23[Exp]
    Shift 21[Term]
    Shift 19[Factor]
    Assign value
    Create NumberExpression
MUL[*] => 5[Term.3]
    State Stack: 23[Exp.Start]
    Reduce 19[Factor]
    Using
    Reduce 21[Term]
    Using
    LR-Reduce 21[Term]
    Assign firstOperand
    Setter binaryOperator = Mul
    Create BinaryExpression
NUMBER[2] => 2[Number.1]
    State Stack: 23[Exp.Start], 5[Term.3], 19[Factor.Start]
    Shift 5[Term]
    Shift 19[Factor]
    Assign value
    Create NumberExpression
ADD[+] => 10[Exp.3]
    State Stack:
    Reduce 19[Factor]
    Using
    Reduce 5[Term]
    Assign secondOperand
    Reduce 23[Exp]
    Using
    LR-Reduce 23[Exp]
    Assign firstOperand
    Setter binaryOperator = Add
    Create BinaryExpression
NUMBER[3] => 2[Number.1]
    State Stack: 10[Exp.3], 21[Term.Start], 19[Factor.Start]
    Shift 10[Exp]
    Shift 21[Term]
    Shift 19[Factor]
    Assign value
    Create NumberExpression
MUL[*] => 5[Term.3]
    State Stack: 10[Exp.3]
    Reduce 19[Factor]
    Using
    Reduce 21[Term]
    Using
    LR-Reduce 21[Term]
    Assign firstOperand
    Setter binaryOperator = Mul
    Create BinaryExpression
NUMBER[4] => 2[Number.1]
    State Stack: 10[Exp.3], 5[Term.3], 19[Factor.Start]
    Shift 5[Term]
    Shift 19[Factor]
    Assign value
    Create NumberExpression
$TokenFinish => 11[Exp.RootEnd]
    State Stack:
    Reduce 19[Factor]
    Using
    Reduce 5[Term]
    Assign secondOperand
    Reduce 10[Exp]
    Assign secondOperand

我們把所有跳轉(zhuǎn)過的transition的信息都記錄下來，就可以構(gòu)造語法蘇了。我們想象一下，在執(zhí)行這些指令的時候，遇到NUMBER[4]就等于獲得了一個內(nèi)容為4的token，shift的話就是往堆棧里面push進(jìn)一個狀態(tài)的名字，而reduce則是彈出。

相對應(yīng)的，因為每一個文法都會創(chuàng)建一個對象，所以我們在初始化的時候，要先放一個空對象在堆棧上。shift一次就再創(chuàng)建一個空的對象push進(jìn)去，reduce的時候就把棧頂?shù)膶ο髲棾鰜碜鳛?#8220;待處理對象”，using了就把待處理對象和棧頂對象合并，left-reduce就是把棧頂對象彈出來作為待處理對象的同時，push一個空對象進(jìn)去。assign fieldName就是把“待處理對象”保存到棧頂對象的叫做fieldName的成員變量里面去。如果棧頂對象為空，那么被保存的對象就是剛剛輸入的那個token了。因此我們從頭到尾執(zhí)行一遍之后，就可以得到下面的一顆語法樹：

BinaryExpression {
    binaryOperator = [Add]
    firstOperand = BinaryExpression {
        binaryOperator = [Mul]
        firstOperand = NumberExpression {
            value = [1]
        }
        secondOperand = NumberExpression {
            value = [2]
        }
    }
    secondOperand = BinaryExpression {
        binaryOperator = [Mul]
        firstOperand = NumberExpression {
            value = [3]
        }
        secondOperand = NumberExpression {
            value = [4]
        }
    }
}

基本上parsing的過程就結(jié)束了。在“下篇”——也就是（六）——里面，我會講述如何處理右遞歸，然后這個系列基本上就要完結(jié)了。