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

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

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

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

那現在我們就來看一下，當所有的非終結符跳轉都處理掉之后，會變成什么樣子吧（這個圖真是復雜和亂到我不想畫啊），為了讓圖變得不那么糟糕，我把shift都變成紫色，reduce都變成綠色：

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

就會被處理成：

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

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

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

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

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

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

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

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

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的過程就結束了。在“下篇”——也就是（六）——里面，我會講述如何處理右遞歸，然后這個系列基本上就要完結了。