本來說這一篇文章要把構(gòu)造確定性狀態(tài)機(jī)和look ahead講完的，當(dāng)我真正要寫的時候發(fā)現(xiàn)東西太多，只好分成兩篇了。上一篇文章說道一個基本的狀態(tài)機(jī)是如何構(gòu)造出來的，但是根據(jù)第一篇文章的說法，這一次設(shè)計(jì)的文法是為了直接構(gòu)造出語法樹服務(wù)的，所以必然在執(zhí)行狀態(tài)機(jī)的時候就要獲得構(gòu)造語法樹的一切信息。如果自己開發(fā)過類似的東西就會知道，類似LALR這種東西，你可以很容易的把整個字符串分析完判斷他是不是屬于這個LALR狀態(tài)機(jī)描述的這個集合，但是你卻不能拿到語法分析所走的路徑，也就是說你很難直接拿到那顆分析樹。沒有分析樹肯定是做不出語法樹的。因此我們得把一些信息插入到狀態(tài)機(jī)里面，才能最終把分析樹（并不一定真的要表達(dá)成樹，像上一篇文章的“分析路徑”（其實(shí)就是分析樹的一種可能的表達(dá)形式）所確定的語法樹構(gòu)造出來。

就像《構(gòu)造正則表達(dá)式引擎》一般給狀態(tài)機(jī)添加信息的方法，就是把一些附加的數(shù)據(jù)加到狀態(tài)與狀態(tài)之間的跳轉(zhuǎn)箭頭里面去。為了形象的表達(dá)這個事情，我就拿第一篇文章的四則運(yùn)算式子來舉例。在這里我為了大家方便，重復(fù)一下這個文法的內(nèi)容（除去了語樹書聲明）：

token NAME = "[a-zA-Z_]/w*";
token NUMBER = "/d+(./d+)";
token ADD = "/+";
token SUB = "-";
token MUL = "/*";
token DIV = "//";
token LEFT = "/(";
token RIGHT = "/)";
token COMMA = ",";

rule NumberExpression Number
        = NUMBER : value;

rule FunctionExpression Call
        = NAME : functionName "(" [ Exp : arguments { "," Exp : arguments } ] ")";

rule Expression Factor
        = !Number | !Call;

rule Expression Term
        = !Factor;
        = Term : firstOperand "*" Factor : secondOperand as BinaryExpression with { binaryOperator = "Mul" };
        = Term : firstOperand "/" Factor : secondOperand as BinaryExpression with { binaryOperator = "Div" };

rule Expression Exp
        = !Term;
        = Exp : firstOperand "+" Term : secondOperand as BinaryExpression with { binaryOperator = "Add" };
        = Exp : firstOperand "-" Term : secondOperand as BinaryExpression with { binaryOperator = "Sub" };

那么我們把這個文發(fā)轉(zhuǎn)成狀態(tài)機(jī)之后，要給跳轉(zhuǎn)加上什么呢？從直覺上來說，跳轉(zhuǎn)的時候我們會有六種要干的事情：
1、Create：這個文法創(chuàng)建的語法樹節(jié)點(diǎn)是某個類型的（區(qū)別于在這一刻給這個問法創(chuàng)建一個返回什么類型的語法樹節(jié)點(diǎn)）
2、Set：給創(chuàng)建的語法樹節(jié)點(diǎn)的某個成員變量設(shè)置一個指定的值
3、Assign：給創(chuàng)建的語法樹節(jié)點(diǎn)的某個成員變量設(shè)置這一次跳轉(zhuǎn)的符號產(chǎn)生的語法樹節(jié)點(diǎn)（譬如說Exp = Exp: firstOperand “+” Term: secondOperand，走Term的時候，一個語法樹節(jié)點(diǎn)就會被assign給那個叫做secondOperand的成員變量）
4、Using：使用這一次跳轉(zhuǎn)的符號產(chǎn)生的語法樹節(jié)點(diǎn)來做這次文法的返回值（譬如說Factor = !Number | !Caller這一條）
5、Shift：略
6、Reduce：略

在這里我們并沒有標(biāo)記整個文法從哪一個非終結(jié)符開始，因?yàn)樵趯?shí)際過程中，其實(shí)分析師可以從任何一個文法開始的。譬如說寫IDE的時候，我們可能在某些情況下僅僅只需要分析一個表達(dá)式。所以考慮到每一個非終結(jié)符都有可能被用到，因此我們的“Token流開始”和“Token流結(jié)束”就會在每一個非終結(jié)符的狀態(tài)機(jī)中都出現(xiàn)。因此在第一步創(chuàng)建Epsilon PDA（下推自動機(jī)）的時候，就可以先直接生成。在這里我們拿Exp做例子：

雙虛線代表的是Token流和Token流結(jié)束，這并不是我們現(xiàn)在關(guān)心的事情。在剩下的轉(zhuǎn)換中，實(shí)現(xiàn)是具有輸入的轉(zhuǎn)換，而虛線則是沒有輸入的轉(zhuǎn)換（一般稱為epsilon邊）。

在這里我們要明確一個概念——分析路徑。分析路徑代表的是token在“流”過狀態(tài)機(jī)的時候，狀態(tài)是如何跳轉(zhuǎn)的。因此對于實(shí)際的分析過程，分析路徑其實(shí)就是分析樹的一種表達(dá)形式。而在狀態(tài)機(jī)里面，分析路徑則代表一條從開始到結(jié)尾的可能的路徑。譬如說在這里，分析路徑可以有三條：
$e –> e1 –> e2 –> e$
$e –> e3 –> e8 –> e7 –> e6 –> e5 –> e4 –> e$
$e –> e9 –> e14 –> e13 –> e12 –> e11 –> e10 –> e$

因此我們可以清楚，一條路徑上是不能出現(xiàn)多個create的，否則你就不知道應(yīng)該創(chuàng)建的是什么了。當(dāng)然create和using都不能同時出現(xiàn)，using也不能有多個。而且由于create和set都是在描述這個非終結(jié)符（在這里是Exp）所創(chuàng)建的語法樹節(jié)點(diǎn)的類型和屬性，跟執(zhí)行他們的時機(jī)無關(guān)，所以其實(shí)在同一條分析路徑里面，create和set放在哪里都沒關(guān)系。就譬如說在上面的第二條分析路徑里面，create是在e6->e5里面標(biāo)記出來的。就算他移動到了e3->e8，做的事情也一樣。反正只要一條路徑上標(biāo)記了create，那么他在這條路徑被確定之后，就一定會create所指定的具體類型的語法樹節(jié)點(diǎn)。這是相當(dāng)重要的，因?yàn)樵诤竺娴姆治鲋校覀兒芸赡苄枰苿觕reate和set的具體位置。

跟上一篇文章說的一樣，接下來的一步就是去除epsilon邊了。結(jié)果如下：

面對這種狀態(tài)機(jī)，去除epsilon邊就不能跟處理正則表達(dá)式一樣簡單的去除了。首先，所有的終結(jié)狀態(tài)——也就是所有經(jīng)過或者不經(jīng)過epsilon邊之后，通過“Token流結(jié)束”符號連接到最后一個狀態(tài)的狀態(tài)，在這里分別是e2、e6和e12——都是不能刪掉的。而且所有的“Token流開始”和“Token流結(jié)束”——也就是圖里面的$轉(zhuǎn)換——是不能帶有信息的。所以我們就會看到e6后面的信息全部被移動到了e7->e6這條邊上面。由于create和set的流動性，我們這么做對于狀態(tài)機(jī)的定義完全沒有影響。

到了這里還沒完，因?yàn)檫@個狀態(tài)機(jī)還是有很多冗余的狀態(tài)的。譬如說e8和e14、e7和e13、e2和e6和e12實(shí)際上是可以合并的。合并的策略其實(shí)十分簡單：

1、如果我們有跳轉(zhuǎn)e0->e1和e0->e2，并且兩個跳轉(zhuǎn)所攜帶的token輸入和信息完全一致的話，那么e1和e2就可以合并。
2、如果我們有跳轉(zhuǎn)e1->e0和e2->e0，并且兩個跳轉(zhuǎn)所攜帶的token輸入和信息完全一致的話，那么e1和e2就可以合并。

所以對于e8和e14我們是完全可以合并的。那么e7和e13怎么辦呢？根據(jù)create和set的流動性，我們只要把這兩個東西挪到他的前面一個或者若干個跳轉(zhuǎn)去，那這兩個狀態(tài)就可以合并了。為了讓算法更加的簡單，我們遇到兩個跳轉(zhuǎn)類似的時候，總是先挪動create和set，然后再看看是不是真的可以合并。所以這一步處理完之后就會變成下面這個樣子：

我們在不改變狀態(tài)機(jī)語義的情況下，把Exp的三個狀態(tài)機(jī)最終壓縮成了這個樣子。看過上一篇文章的同學(xué)們都知道，下一步就是要把所有的狀態(tài)機(jī)統(tǒng)統(tǒng)都連接起來了。關(guān)于在連接的時候如何具體操作轉(zhuǎn)換附帶的信息、以及做出一個確定性的下推狀態(tài)機(jī)的所有事情將在下一篇文章詳細(xì)解釋。大家敬請期待。