可配置語法分析器開發紀事（四）——構造一個真正能用的狀態機（上）

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

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

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" };

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

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

雙虛線代表的是Token流和Token流結束，這并不是我們現在關心的事情。在剩下的轉換中，實現是具有輸入的轉換，而虛線則是沒有輸入的轉換（一般稱為epsilon邊）。

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

因此我們可以清楚，一條路徑上是不能出現多個create的，否則你就不知道應該創建的是什么了。當然create和using都不能同時出現，using也不能有多個。而且由于create和set都是在描述這個非終結符（在這里是Exp）所創建的語法樹節點的類型和屬性，跟執行他們的時機無關，所以其實在同一條分析路徑里面，create和set放在哪里都沒關系。就譬如說在上面的第二條分析路徑里面，create是在e6->e5里面標記出來的。就算他移動到了e3->e8，做的事情也一樣。反正只要一條路徑上標記了create，那么他在這條路徑被確定之后，就一定會create所指定的具體類型的語法樹節點。這是相當重要的，因為在后面的分析中，我們很可能需要移動create和set的具體位置。

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

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

到了這里還沒完，因為這個狀態機還是有很多冗余的狀態的。譬如說e8和e14、e7和e13、e2和e6和e12實際上是可以合并的。合并的策略其實十分簡單：

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

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

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