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

就像《構造正則表達式引擎》一般給狀態(tài)機添加信息的方法，就是把一些附加的數(shù)據(jù)加到狀態(tài)與狀態(tài)之間的跳轉箭頭里面去。為了形象的表達這個事情，我就拿第一篇文章的四則運算式子來舉例。在這里我為了大家方便，重復一下這個文法的內(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ā)轉成狀態(tài)機之后，要給跳轉加上什么呢？從直覺上來說，跳轉的時候我們會有六種要干的事情：
1、Create：這個文法創(chuàng)建的語法樹節(jié)點是某個類型的（區(qū)別于在這一刻給這個問法創(chuàng)建一個返回什么類型的語法樹節(jié)點）
2、Set：給創(chuàng)建的語法樹節(jié)點的某個成員變量設置一個指定的值
3、Assign：給創(chuàng)建的語法樹節(jié)點的某個成員變量設置這一次跳轉的符號產(chǎn)生的語法樹節(jié)點（譬如說Exp = Exp: firstOperand “+” Term: secondOperand，走Term的時候，一個語法樹節(jié)點就會被assign給那個叫做secondOperand的成員變量）
4、Using：使用這一次跳轉的符號產(chǎn)生的語法樹節(jié)點來做這次文法的返回值（譬如說Factor = !Number | !Caller這一條）
5、Shift：略
6、Reduce：略

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

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

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

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

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

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

到了這里還沒完，因為這個狀態(tài)機還是有很多冗余的狀態(tài)的。譬如說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怎么辦呢？根據(jù)create和set的流動性，我們只要把這兩個東西挪到他的前面一個或者若干個跳轉去，那這兩個狀態(tài)就可以合并了。為了讓算法更加的簡單，我們遇到兩個跳轉類似的時候，總是先挪動create和set，然后再看看是不是真的可以合并。所以這一步處理完之后就會變成下面這個樣子：

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

剛剛發(fā)了上一篇文章之后就發(fā)現(xiàn)狀態(tài)機畫錯了。雖然LiveWriter有打開博客并修改文章的功能，不過為了讓我留下一個教訓，我還是決定發(fā)一篇勘誤。這個教訓就是，作分析的時候不要隨便“跳步”，該一步一步來就一步一步來。其實人呢，就是很容易忘掉以前的教訓的了。第一個告訴我不能這么干的人其實是小學三年級的數(shù)學老師。當時我因為懶得寫字，所以計算應用題的時候省了幾步，被批評了。

故事就從狀態(tài)機開始。文法我就不重復了，見上一篇文章。現(xiàn)在我們從狀態(tài)機開始。第一個狀態(tài)機是直接從文法變過來的：

然后我們把所有的非終結符跳轉都通過Shift和Reduce連接到該非終結符所代表的狀態(tài)機的狀態(tài)上面，就會變成下面的圖。具體的做法是，對于每一條非終結符的跳轉，譬如說S0 –> Symbol –> S1。首先抹掉這條跳轉。然后增加兩條邊，分別是S0到Symbol的起始節(jié)點，操作是Shift<S0>。還有從Symbol的終結節(jié)點到S0，操作是Pop<S0> Reduce。Shift<S>等于把狀態(tài)S給push到堆棧里，然后Pop<S>等于在狀態(tài)里面彈出內(nèi)容是S的棧頂元素。如果失敗了怎么辦呢？那就不能用這條跳轉。跟上圖一樣，所有輸入$跳轉到Finish的邊，操作都是要Pop<Null>的。在剛開始分析的時候，堆棧有一個Null值，用來代表“語法分析從這里開始”。

這個圖的粗虛邊代表所有跟左遞歸有關的跳轉。這些邊是成對的，分別是左遞歸跳轉的Shift和Reduce。如果不是為了實現(xiàn)高性能的語法分析的話，其實這個狀態(tài)機已經(jīng)足夠了。這個圖跟語法分析的“狀態(tài)跳轉軌跡”有很大的關系。雖然IDList0你不知道第一步要跳轉到IDList0還是ID0，不過沒關系，現(xiàn)在我們先假設我們可以通過某種神秘的方法來預測到。那么，當輸入是A,B,C$的時候，狀態(tài)跳轉軌跡就會是如下的樣子：

為什么要這么做呢？我們把這幅圖想象成為
1：想做的箭頭表示push一個狀態(tài)
2：向下的箭頭表示修改當前狀態(tài)
3：向右的狀態(tài)表示pop一個狀態(tài)并修改當前狀態(tài)

因此當輸入到B的時候，到達ID1，并跳轉到IDList1。這個時候IDList1【左邊】的所有【還留在堆棧里】的狀態(tài)時Null和IDList0，當前狀態(tài)IDList1，輸入剩下,C$。這個圖特別的有用。當我們分析完并且把構造語法樹的指令附著在這些箭頭上面之后，按順序執(zhí)行這些指令就可以構造出一顆完整的語法樹了。

但是在實際操作里面，我們并沒有辦法預測“這里要左遞歸兩次”，也沒辦法在多次reduce的時候選擇究竟要從哪里跳到哪里。所以實際上我們要學習從EpsilonNFA到DFA的那個計算過程，把Shift和Reduce當成Epsilon，把吃掉一個token當成非Epsilon邊，然后執(zhí)行我之前寫的《構造可配置詞法分析器》一文中的那個去Epsilon邊算法（如何從Nondeterministic到Deterministic，以及相關的Look Ahead，是下一篇文章的內(nèi)容），然后就可以把狀態(tài)機變成這樣：

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

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

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

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

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

上一篇博客講到了構造符號表的事情。構造完符號表之后，就要進入語義分析的后一個階段了：構造狀態(tài)機。跟我以前寫的如何實現(xiàn)正則表達式引擎的兩篇文章講的一樣，自動機先從Epsilon Nondeterministic Automaton開始，然后一步一步構造成Deterministic Automaton。但是語法分析和正則表達式有很大不同，那么這個自動機是什么樣子的呢？

（對學術感興趣的人可以去wiki一下“下推自動機”）

下推自動機和有限自動機的區(qū)別是，下推自動機擴展成普通的自動機的時候，他的狀態(tài)的數(shù)目是無限的（廢話）。但是無限的東西是沒辦法用編程來表達的，那怎么辦呢？那就加入一個不定長度的“狀態(tài)描述”。下面我舉一個簡單的文法：

ID = NAME
IDList = ID | IDList “,” ID

這樣就構成了一個簡單的文法，用來分析帶逗號分割的名字列表的。那么寫成狀態(tài)機就是如下的形式：

ID0 = ● NAME
ID1 = NAME ●
IDList0 = ● (ID | IDList “," ID)
IDList1 = (ID | IDList “,” ID) ●
IDList2 = (ID | IDList ● “,” ID)
IDList3 = (ID | IDList “,” ● ID)

ID0 –> NAME –> ID1
IDList0 –> ID –> IDList1
IDList0 –> IDList –> IDList2
IDList2 –> “,” –> IDList3
IDList3 –> ID –> IDList1

可以很容易的看出，ID0和IDList0是文法的起始狀態(tài)，而ID1和IDList1是文法的終結狀態(tài)，畫成圖如下：

（PowerPoint畫圖復制到LiveWriter里面是一幅圖面簡直太方便了）

但是這樣還沒完。IDList0跳到IDList2的時候的輸入“IDList”其實還不夠，因為用作輸入的token其實只有NAME和","兩種。下一步即將演示如何從這個狀態(tài)機編程名副其實的下推狀態(tài)機。

在這里我先介紹幾個概念。第一個是移進，第二個是規(guī)約。為什么要用這兩個名字呢？因為大部分人看的傻逼清華大學出版社的低能編譯原理課本都是這么講的，黑化分別叫Shift和Reduce。好了，什么是Shift呢？IDList0跳到IDList2的時候，要移進IDList。IDList3跳到IDList1，要移進到ID。IDList0跳到IDList1也要移進到ID。這也就是說，狀態(tài)轉移經(jīng)過一條非終結符的邊的時候會移進到另一條文法的狀態(tài)機里。ID1和IDList1作為ID和IDList的終結節(jié)點，要根據(jù)“從那里移進來的”分別規(guī)約然后跳轉到“IDList2或者IDList1”。這也就是說，一旦你到達了一條聞法的狀態(tài)機的終結狀態(tài)，就要開始規(guī)約然后跳轉到上一級的狀態(tài)了。

有人要問，那我怎么知道規(guī)約結束的時候要跳轉去哪里呢？這個問題問得非常好。讓我們回想一下我以前寫的如何手寫語法分析器這一篇文章。里面怎么說的？當你手寫遞歸下降的語法分析器的時候，每一條文法其實都是一個函數(shù)。那調(diào)用函數(shù)的時候程序怎么就知道函數(shù)結束的時候下一條指令是什么呢？那當然是因為編譯器幫我們把“調(diào)用函數(shù)的時候的下一條指令的地址”給push進了調(diào)用堆棧。但是我們現(xiàn)在不手寫語法分析器了，而用下推狀態(tài)機來做，道理也是一樣的。在“移進”的時候，先把當前的狀態(tài)push進堆棧，規(guī)約的時候，就可以看一下“棧頂那幾個狀態(tài)都是什么”，配合一次向前查看（這就是Look Ahead。LALR的那個LA，LALR(1)就是在LA的時候偷看一個token），來決定規(guī)約到哪里去。至于LA在這里的深刻內(nèi)涵我將下一篇文章再說。因為現(xiàn)在我還沒有做到Nondeterministic到Deterministic的一步，里面有很多黑科技，我想集中討論。

那現(xiàn)在讓我們把上面那幅圖的兩個狀態(tài)機連起來，產(chǎn)生一個下推自動機。但是在這里我先做第一步。因為IDList0到IDList1的跳轉是一個左遞歸的過程，先暫時不管。

橙色的邊都是一個輸入非終結符的跳轉，所以實際上在下推狀態(tài)機里面是不存在的。在這張圖里面我們處理了兩條ID的邊。IDList0會shift（就是在堆棧里面push）自己然后跳轉到ID0，因此ID1在查看到棧頂是IDList0的時候，他就知道走的是IDList0 –> ID –> IDList1這條路，因此就reduce并跳轉到了IDList1。IDList3同理。

但是Shift的時候并沒有產(chǎn)生輸入，所以實際上應該改成下面這個樣子。

這樣Shift邊也就有輸入了。而且ID0到ID1也廢掉了。實際上ID0自己也應該廢掉。現(xiàn)在還有一個問題沒解決，就是左遞歸和Reduce不產(chǎn)生輸入的問題。這兩個問題實際上是一起的。我們先來考慮一下為什么這里沒辦法用相同的辦法來把Reduce處理成產(chǎn)生輸入的。實際上是因為，你在這一個階段還不知道究竟Reduce要輸入什么才能跳轉，特別是token已經(jīng)結束并且parse出了一個完整的IDList的時候。以前你們是不是在看《Parsing Techniques》和《龍書》都對為什么一個字符串結尾要產(chǎn)生一個$字符感到很困惑呢？實際上他是特別有用的。現(xiàn)在我們來給他加上大家就明白了。在這里，這個文法的目標是產(chǎn)生一個IDList結構，所以$當然也要加在IDList的終結狀態(tài)——IDList1上：

然后就輪到Reduce。ID1應該是Reduce到哪里了？第一步自然是Reduce到IDList1。那么IDList1又要Reduce到哪里呢？我們可以看到，在IDList結束的時候，要么就是跳到IDList2，要么就是跳到FINISH。但是IDList2是通過左遞歸產(chǎn)生的，我們先不管他。跳到FINISH需要什么條件呢？第一個是輸入$，第二個是Pop完狀態(tài)之后堆棧會為空。所以這個時候我們可以先修改一下ID1到IDList1的Reduce邊：

最后就是左遞歸了。左遞歸的處理有點像hack，因為實際上你不能預先判斷你要不要左遞歸（也就是看一下token stream有多少個逗號），然后先shift幾個IDList0進去，再慢慢來。所以我們只有在滿足跳轉關系的時候臨時插入一些IDList0。那么這個關系是什么呢？左遞歸的IDList結束——也就是從IDList0跳到IDList2——之后只有一種可能，就是輸入","。而且所有指向IDList1的邊都是輸入ID，所以這條左遞歸的線應該從ID1（ID的終結狀態(tài)）連到IDList2，并且在鏈接的時候補充“假shift IDList0”：

橙色的兩個狀態(tài)分別是整個parsing過程的起始狀態(tài)和終結狀態(tài)。這個時候我們把所有沒用的邊和狀態(tài)都干掉，就變成了：

是不是覺得特別親切呢，這不就是正則表達式NAME ( “,” NAME)*的狀態(tài)機嗎？這也是因為這個文法剛好可以表達為一個正則文法才有這樣的結果，如果我們給他加點兒括號改變點優(yōu)先級什么的，那就會變成一個復雜得多的狀態(tài)機了。好了。現(xiàn)在我們來模擬一下下推狀態(tài)機的狀態(tài)轉換和堆棧操作過程，來分析一下A,B,C$這個輸入吧。

在下面的標示圖里面，我們用s|abc|def來分別表達當前狀態(tài)s、當前堆棧里的狀態(tài)abc（棧頂在右邊）和正在等待的輸入def。那么初始狀態(tài)肯定就是
IDList0 | null | A,B,C$

然后就開始了！（用文字表達實在是太難看了，所以貼成圖）

如果成功到達FINISH并且堆棧和輸入都全部沒有了的話，那就證明，parsing過程完美結束，沒有任何錯誤發(fā)生。

如何從文法生成下推自動機并完成parsing工作的大概過程就寫到這里了。目前開發(fā)進度是到“生成非確定性下推自動機”這里。當我完成了生成“確定性下推自動機”——也就是上面的最后一個狀態(tài)機圖的時候——就會開始寫下一篇文章，講面對復雜的文法的時候，下推自動機將要如何調(diào)整。同時將重點描述Look Ahead部分，以及為什么LALR(1)要設計成那個樣子。

群號：31724825

在最近這幾年里，一起討論編譯器的人也不多，一般都是ooseven、@裝配腦袋、@空明流轉(<--高手，要跪)、@belleveinvis等這幾個人。而且也零星有一些我也不記得叫什么名字的在我的評論里面提出過一些很好的建議，讓我得到了充分的學習。因此我想，如果有興趣的人可以加進來一起討論的話，應該不僅對我，對大家也是有好處的。而且我本人喜歡的領域也比較分散，譬如圖形界面、軟件渲染、編譯原理、游戲開發(fā)等等。這幾個領域都有互相促進的作用，而且需要的背景知識交集又少，不同領域的人的思想和類型也不一樣。如果群里的人北京分布比較廣泛的話，也許還會有意想不到的idea出現(xiàn)。

所以只要滿足以下要求的人都熱烈歡迎。
1、熱愛編程
2、不是來求代碼的
3、不要問各種傻逼問題（譬如說為什么cout<<1+2<<endl;會有錯誤啊）和求寫大作業(yè)（我可沒時間管這些不見棺材不流淚的學生們）
4、可以交換知識就最好了

本窮丑矮不是VIP，故群人數(shù)有上限（不過我想應該是達不到的），先到先得。

引用http://www.shnenglu.com/vczh/archive/2012/11/29/195779.html的三樓

上一篇博客講到了構造語法樹的問題。有朋友在留言問我，為什么一定要讓語法分析器產(chǎn)生語法樹，而不是讓用戶自己決定要怎么辦呢？在這里我先解答這個問題。

1、大部分情況下都是真的需要有語法樹
2、如果要直接返回計算結果之類的事情的話，只需要寫一個visitor運行一下語法樹就好了，除去自動生成的代碼以外（反正這不用人寫，不計入代價），代碼量基本上沒什么區(qū)別
3、加入語法樹可以讓文法本身描述起來更簡單，如果要讓程序員把文法單獨放在一邊，然后自己寫完整的語義函數(shù)來讓他生成語法樹的話，會讓大部分情況（需要語法樹）變得特別復雜，而少數(shù)情況（不需要語法樹）又沒有獲得什么好處。

盡管類似yacc這樣的東西的確是不包含語法樹的內(nèi)容而要你自己寫的，但是用起來難道不是很難受嗎？

現(xiàn)在轉入正題。這一篇文章講的主要是構造符號表的問題。想要把符號表構造的好是一件很麻煩的問題。我曾經(jīng)嘗試過很多種方法，包括強類型的符號表，弱類型的符號表，基于map的符號表等等，最后還是挑選了跟Visual Studio自帶的用來讀pdb文件的DIA類其中的IDIASymbol（http://msdn.microsoft.com/en-us/library/w0edf0x4.aspx）基本上一樣的結構：所有的符號都只有這么一個symbol類，然后包羅萬象，什么都有。為什么最后選擇這么做呢？因為在做語義分析的時候，其實做的最多的事情不是構造符號表，而是查詢符號表。如果符號表是強類型的畫，譬如說類型要一個類，變量要一個類，函數(shù)要一個類之類的，總是需要到處cast來cast去，也找不到什么好方法來在完成相同事情的情況下，保留強類型而不在代碼里面出現(xiàn)cast。為什么語法樹就要用visitor來解決這個問題，而符號表就不行呢？因為通常我們在處理語法樹的時候都是遞歸的形式，而符號表并不是。在一個上下文里面，實際上我們是知道那個symbol對象究竟是什么東西的（譬如說我們查詢了一個變量的type，那這返回值肯定只能是type了）。這個時候我們要cast才能用，本身也只是浪費表情而已。這個時候，visitor模式就不是和面對這種情況了。如果硬要用visitor模式來寫，會導致語義分析的代碼分散得過于離譜導致可讀性幾乎就喪失了。這是一個辯證的問題，大家可以好好體會體會。

說了這么一大段，實際上就是怎么樣呢？讓我們來看“文法規(guī)則”本身的符號表吧。既然這個新的可配置語法分析器也是通過parse一個文本形式的文法規(guī)則來生成parser，那實際上就跟編譯器一樣要經(jīng)歷那么多階段，其中肯定有符號表：

class ParsingSymbol : public Object
{
public:
    enum SymbolType
    {
        Global,
        EnumType,
        ClassType,        // descriptor == base type
        ArrayType,        // descriptor == element type
        TokenType,
        EnumItem,        // descriptor == parent
        ClassField,        // descriptor == field type
        TokenDef,        // descriptor == token type
        RuleDef,        // descriptor == rule type
    };
public:
    ~ParsingSymbol();

    ParsingSymbolManager*            GetManager();
    SymbolType                        GetType();
    const WString&                    GetName();
    vint                            GetSubSymbolCount();
    ParsingSymbol*                    GetSubSymbol(vint index);
    ParsingSymbol*                    GetSubSymbolByName(const WString& name);
    ParsingSymbol*                    GetDescriptorSymbol();
    ParsingSymbol*                    GetParentSymbol();
    bool                            IsType();
    ParsingSymbol*                    SearchClassSubSymbol(const WString& name);
    ParsingSymbol*                    SearchCommonBaseClass(ParsingSymbol* classType);
};

因為文法規(guī)則本身的東西也不多，所以這里的symbol只能是上面記載的9種對象。這些對象其實特別的相似，所以我們可以看出唯一的區(qū)別就是當GetType返回值不一樣的時候，GetDescriptorSymbol返回的對象的意思也不一樣。而這個區(qū)別記載在了enum SymbolType的注釋里面。實際上這種做法在面對超級復雜的符號表（考慮一下C++編譯器）的時候并不太好。那好的做法究竟是什么呢？看上面IDIASymbol的鏈接，那就是答案。

不可否認，微軟設計出來的API大部分還是很有道理的，除了Win32的原生GUI部分。

我們還可以看到，這個ParsingSymbol類的幾乎所有成員函數(shù)都是用來查詢這個Symbol的內(nèi)容的。這里還有兩個特殊的函數(shù)，就是SearchClassSubSymbol和SearchCommonBaseClass——當且僅當symbol是ClassType的時候才起作用。為什么有了GetSubSymbolByName，還要這兩個api呢？因為我們在搜索一個類的成員的時候，是要搜索他的父類的。而一個類的父類的sub symbol并不是類自己的sub symbol，所以就有了這兩個api。所謂的sub symbol的意思現(xiàn)在也很明了了。enum類型里面的值就是enum的sub symbol，成員變量是類的sub symbol，總之只要是聲明在一個符號內(nèi)部的符號都是這個符號的sub symbol。這就是所有符號都有的共性。

當然，有了ParsingSymbol，還要有他的manager才可以完成整個符號表的操作：

class ParsingSymbolManager : public Object
{
public:
    ParsingSymbolManager();
    ~ParsingSymbolManager();

    ParsingSymbol*                    GetGlobal();
    ParsingSymbol*                    GetTokenType();
    ParsingSymbol*                    GetArrayType(ParsingSymbol* elementType);

    ParsingSymbol*                    AddClass(const WString& name, ParsingSymbol* baseType, ParsingSymbol* parentType=0);
    ParsingSymbol*                    AddField(const WString& name, ParsingSymbol* classType, ParsingSymbol* fieldType);
    ParsingSymbol*                    AddEnum(const WString& name, ParsingSymbol* parentType=0);
    ParsingSymbol*                    AddEnumItem(const WString& name, ParsingSymbol* enumType);
    ParsingSymbol*                    AddTokenDefinition(const WString& name);
    ParsingSymbol*                    AddRuleDefinition(const WString& name, ParsingSymbol* ruleType);

    ParsingSymbol*                    CacheGetType(definitions::ParsingDefinitionType* type, ParsingSymbol* scope);
    bool                            CacheSetType(definitions::ParsingDefinitionType* type, ParsingSymbol* scope, ParsingSymbol* symbol);
    ParsingSymbol*                    CacheGetSymbol(definitions::ParsingDefinitionGrammar* grammar);
    bool                            CacheSetSymbol(definitions::ParsingDefinitionGrammar* grammar, ParsingSymbol* symbol);
    ParsingSymbol*                    CacheGetType(definitions::ParsingDefinitionGrammar* grammar);
    bool                            CacheSetType(definitions::ParsingDefinitionGrammar* grammar, ParsingSymbol* type);
};

這個ParsingSymbolManager有著符號表管理器的以下兩個典型作用

1、創(chuàng)建符號。
2、講符號與語法樹的對象綁定起來。譬如說我們在一個context下面推導了一個expression的類型，那下次對于同樣的context同樣的expression就不需要再推導一次了（語義分析有很多個pass，對同一個expression求類型的操作經(jīng)常會重復很多次），把它cache下來就可以了。
3、搜索符號。具體到這個符號表，這個功能被做進了ParsingSymbol里面。
4、保存根節(jié)點。GetGlobal函數(shù)就是干這個作用的。所有的根符號都屬于global符號的sub symbol。

因此我們可以怎么使用他呢？首先看上面的Add函數(shù)。這些函數(shù)不僅會幫你在一個符號表里面添加一個sub symbol，還會替你做一些檢查，譬如說阻止你添加相同名字的sub symbol之類的。語法樹很復雜的時候，很多時候我們有很多不同的方法來給一個符號添加子符號，譬如說C#的成員變量和成員函數(shù)。成員變量不能同名，成員函數(shù)可以，但是成員函數(shù)和成員變量卻不能同名。這個時候我們就需要把這些添加操作封裝起來，這樣才可以在處理語法樹（聲明一個函數(shù)的方法可以有很多，所以添加函數(shù)符號的地方也可以有很多）的時候不需要重復寫驗證邏輯。

其次就是Cache函數(shù)。其實Cache函數(shù)這么寫，不是用來直接調(diào)用的。舉個例子，在分析一個文法的時候，我們需要把一個“類型”語法樹轉成一個“類型”符號（譬如說要決定一個文法要create什么類型的語法樹節(jié)點的時候）。因此就有了下面的函數(shù)：

ParsingSymbol* FindType(Ptr<definitions::ParsingDefinitionType> type, ParsingSymbolManager* manager, ParsingSymbol* scope, collections::List<Ptr<ParsingError>>& errors)
{
    ParsingSymbol* result=manager->CacheGetType(type.Obj(), scope);
    if(!result)
    {
        FindTypeVisitor visitor(manager, (scope?scope:manager->GetGlobal()), errors);
        type->Accept(&visitor);
        result=visitor.result;
        manager->CacheSetType(type.Obj(), scope, result);
    }
    return result;
}

很明顯，這個函數(shù)做的事情就是，查詢一個ParsingDefinitionType節(jié)點有沒有被查詢過，如果有直接用cache，沒有的話再從頭計算他然后cache起來。因此這些Cache函數(shù)就是給類似FindType的函數(shù)用的，而語義分析的代碼則直接使用FindType，而不是Cache函數(shù)，來獲取一個類型的符號。聰明的朋友們可以看出來，這種寫法蘊含著一個條件，就是語法樹創(chuàng)建完就不會改了（廢話，當然不會改！）。

這一篇的內(nèi)容就講到這里了。現(xiàn)在的進度是正在寫文法生成狀態(tài)機的算法。下一篇文章應該講的就是狀態(tài)機究竟是怎么運作的了。文法所需要的狀態(tài)機叫做下推狀態(tài)機（push down automaton），跟regex用的NFA和DFA不太一樣，理解起來略有難度。所以我想需要用單獨的一篇文章來通俗的講一講。

就像之前的博客文章所說的，（主要還是）因為GacUI的原因，我決定開發(fā)一個更好的可配置輕量級語法分析器來代替之前的落后的版本。在說這個文章之前，我還是想在此向大家推薦一本《編程語言實現(xiàn)模式》，這的確是一本好書，讓我相見恨晚。

其實說到開發(fā)語法分析器，我從2007年就已經(jīng)開始在思考類似的問題了。當時C++還處于用的不太熟練的時候，難免會做出一些傻逼的事情，不過總的來說當年的idea還是能用的。從那時候開始，我為了鍛煉自己，一直在實現(xiàn)各種不同的語言。所以給自己開發(fā)一個可配置語法分析器也是在所難免的事情了。于是就有：
第一版：http://hi.baidu.com/geniusvczh/archive/tag/syngram%E6%97%A5%E5%BF%97
第二版：http://www.shnenglu.com/vczh/archive/2009/04/06/79122.html
第三版：http://www.shnenglu.com/vczh/archive/2009/12/13/103101.html
還有第三版的教程：http://www.shnenglu.com/vczh/archive/2010/04/28/113836.html

上面的所有分析器都致力于在C++里面可以通過直接描述文法和一些語義行為來讓系統(tǒng)可以迅速構造出一個針對特定目的的用起來方便的語法分析器，而“第三版”就是到目前為止還在用的一個版本。至于為什么我要做一個新的——也就是第四版——之前的文章已經(jīng)說了。

而今天，第四版的開發(fā)已經(jīng)開始了有好幾天。如果大家關心進度的話，可以去GacUI的Codeplex頁面下載代碼，然后閱讀Common\Source\Parsing下面的源文件。對應的單元測試可以在Common\UnitTest\UnitTest\TestParsing.cpp里找到。

于是今天就說說關于構造語法樹的事情。

用C++寫過parser的人都知道，構造語法樹以及語義分析用的符號表是一件極其繁瑣，而且一不小心就容易寫出翔的事情。但是根據(jù)我寫過無窮多棵語法樹以及構造過無窮多個符號表以及附帶的副作用，翔，啊不，經(jīng)驗，做這個事情還是有一些方法的。

在介紹這個方法之前，首先要說一句，人肉做完下面的所有事情是肯定要瘋掉的，所以這一次的可配置語法分析器我已經(jīng)決定了一定要TMD寫出一個生成語法樹的C++代碼的工具。

一顆語法樹，其實就是一大堆互相繼承的類。一切成熟的語法樹結構所具有的共同特征，不是他的成員怎么安排，而是他一定會附帶一個visitor模式的機制。至于什么是visitor模式，大家請自行參考設計模式，我就不多說廢話了。這一次的可配置語法分析器是帶有一個描述性語法的。也就是說，跟Antlr或者Yacc一樣，首先在一個文本文件里面準備好語法樹結構和文法規(guī)則，然后我的工具會幫你生成一個內(nèi)存中的語法分析器，以及用C++描述的語法樹的聲明和實現(xiàn)文件。這個描述性語法就類似下面的這個大家熟悉到不能再熟悉的帶函數(shù)的四則運算表達式結構：

class Expression
{
}

class NumberExpression : Expression
{
    token value;
}

class BinaryExpression : Expression
{
    enum BinaryOperator
    {
        Add,
        Sub,
        Mul,
        Div,
    }

    Expression firstOperand;
    Expression secondOperand;
    BinaryOperator binaryOperator;
}

class FunctionExpression : Expression
{
    token functionName;
    Expression[] arguments;
}

token NAME = "[a-zA-Z_]/w*";
token NUMBER = "/d+(./d+)";
token ADD = "/+";
token SUB = "-";
token MUL = "/*";
token DIV = "http://";
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 "*" Factory : secondOperand as BinaryExpression with { binaryOperator = "Mul" };
        = Term : firstOperand "/" Factory : 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" };

上面的語法樹聲明借用的C#語法，描述起來特別簡單。但是要在C++里面達到可以使用的程度，肯定要有一個自帶的visitor模式。所以出來之后的代碼大概就類似于下面這個樣子：

class Expression;
class NumberExpression;
class BinaryExpression;
class FunctionExpression;

class Expression : public ParsingTreeCustomBase
{
public:
    class IVisitor : public Interface
    {
    public:
        virtual void Visit(NumberExpression* node)=0;
        virtual void Visit(BinaryExpression* node)=0;
        virtual void Visit(FunctionExpression* node)=0;
    };

    virtual void Accept(IVisitor* visitor)=0;
};

class NumberExpression : public Expression
{
public:
    TokenValue value;

    void Accept(IVisitor* visitor){visitor->Visit(this);}
};

class BinaryExpression : public Expression
{
public:
    enum BinaryOperator
    {
        Add, Sub, Mul, Div,
    };
    Ptr<Expression> firstOperator;
    Ptr<Expression> secondOperator;
    BinaryOperator binaryOperator;

    void Accept(IVisitor* visitor){visitor->Visit(this);}
};

class FunctionExpression : public Expression
{
public:
    TokenValue functionName;
    List<Ptr<Expression>> arguments;

    void Accept(IVisitor* visitor){visitor->Visit(this);}
};

為什么要這樣做呢？學習過面向對象開發(fā)方法的都知道，把一個明顯是繼承結構的東西寫成一堆union/struct和一個enum來判斷他們，是不對的。第一個不好的地方就是，如果其中的成員需要構造函數(shù)和析構函數(shù)，那union就用不了了，struct就一定會造成大量的內(nèi)存浪費。因為一顆語法樹是可以很大的。其次，當語法樹的結構（主要是添加刪除了新的語法樹類型）之后，我們根本不可能保證我們所有的swtich(node->enumType)語句都接受到了正確的更新。

那要如何解決這兩個問題呢？答案之一就是使用visitor模式。盡管剛開始寫起來的時候可能會有點別扭，但是我們只要把原本是swtich結構的代碼做一下Continuation Passing Style變換，就可以寫出使用visitor的版本了。在這里我做一個小小的演示，如何把一個“把上面的語法樹還原成四則運算式子的函數(shù)”給用Expression::IVisitor的框架下實現(xiàn)出來：

class FunctionExpression : public Expression
{
public:
    TokenValue functionName;
    List<Ptr<Expression>> arguments;

    void Accept(IVisitor* visitor){visitor->Visit(this);}
};

class ExpressionPrinter : public Expression::IVisitor
{
public:
    WString result;

    void Visit(NumberExpression* node)
    {
        result+=node->value.stringValue;
    }

    void Visit(BinaryExpression* node)
    {
        result+=L"(";
        node->firstOperand->Accept(this);
        switch(binaryOperator)
        {
        case Add: result+=L" + "; break;
        case Sub: result+=L" - "; break;
        case Mul: result+=L" * "; break;
        case Div: result+=L" / "; break;
        }
        node->secondOperand->Accept(this);
        result+=L")";
    }

    void Visit(FunctionExpression* node)
    {
        result+=node->functionName.stringValue+L"(";
        for(int i=0;i<arguments.Count();i++)
        {
            if(i>0) result+=L", ";
            arguments[i]->Accept(this);
        }
        result+=L")";
    }
};

WString PrintExpression(Ptr<Expression> expression)
{
    ExpressionPrinter printer;
    expression->Accept(&printer);
    return printer.result;
}

其實大家可以看到，使用了visitor模式，代碼量其實也沒有多大變化，本來是遞歸的地方還是遞歸，本來該計算什么還計算什么，唯一不同的就是原本這個“函數(shù)”的參數(shù)和返回值都跑到了一個visitor類的成員變量里面去了。當然，為了便于使用，一般來說我們會把原本的函數(shù)的原型寫出來，并且在里面調(diào)用visitor模式，就像上面的PrintExpression函數(shù)一樣。如果我們高興的話，完全可以在ExpressionPrinter這個visitor類里面使用PrintExpression，無非就是在里面構造新的ExpressionPrinter然后獲取結構罷了。一般來說，visitor類都是非常的輕量級的，在現(xiàn)今的CPU性能下面，構造多幾個完全不會帶來多大影響。

可配置語法分析器既然擁有一個描述性語法，那么我肯定也針對這個描述性語法寫了一顆語法樹的。這顆語法樹的代碼在Common\Source\Parsing\ParsingDefinition.h里面，而ParsingLogging.cpp則是跟上面說的一樣，用visitor的方法寫了一個龐大的把語法樹轉回描述性語法的函數(shù)。這個函數(shù)非常有用，不僅可以用來打log，還可以用來保存程序生成的一個語法規(guī)則（反正可以parse回來，所以保存成文本是一件特別方便的事情），甚至是生成錯誤消息的片段等等。

今天就先講到這里了。現(xiàn)在的可配置語法分析器的開發(fā)進度是正在寫語義分析的部分。等到語義分析寫完了，我會再寫一篇紀事來說明開發(fā)語義分析程序和構造符號表的一般做法。

由于接下去要用uniscribe（這是一個可以告訴我們在渲染一個超長unicode字符串的時候，什么地方可以換行，什么地方要換順序，什么字符要用一種神奇的方法來渲染之類的庫）做可以插入圖片和其它亂七八糟東西的rich text box，為了更方便做實驗，而且也考慮到很多軟件也需要直接繪圖的功能，所以我寫了這么兩個Demo：

1、Rendering.RawAPI.GDI（http://www.gaclib.net/Demos/Rendering.RawAPI.GDI/Demo.html）
2、Rendering.RawAPI.Direct2D（http://www.gaclib.net/Demos/Rendering.RawAPI.Direct2D/Demo.html）

由于這兩個Demo很像，而且Direct2D的比較復雜，所以我在這里介紹一下這個Direct2D的demo。

在Demo里面可以看到，我們可以使用GuiGDIElement或者GuiDirect2DElement來進行手工的繪圖操作。這兩個Element的使用有限制。當GacUI使用GDI繪圖（SetupWindowsGDIRenderer）的時候才可以使用GuiGDIElement，對于Direct2D也是一樣的。在使用它們進行繪圖的時候，坐標用的是窗口的坐標。但是GacUI會在繪制的時候先加入一個clip，這樣我們在繪制的時候就算繪制出了邊界，也不會有任何不好的影響。而且這個clip的矩形范圍會在渲染事件觸發(fā)的時候給出。在這里我們先來看一下Direct2D的demo。

首先，整個程序的框架是這樣子的：

#include "..\..\Public\Source\GacUI.h"
#include <math.h>
#include <Windows.h>

int CALLBACK WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int CmdShow)
{
    // SetupWindowsDirect2DRenderer() is required for GuiDirect2DElement
    return SetupWindowsDirect2DRenderer();
}

class Direct2DWindow : public GuiWindow
{
protected:

    // arguments.rt is ID2D1RenderTarget.
    void element_Rendering(GuiGraphicsComposition* sender, GuiDirect2DElementEventArgs& arguments)
    {
    }

    // The render target is going to be destroyed, any binded resources should be released.
    void element_BeforeRenderTargetChanged(GuiGraphicsComposition* sender, GuiDirect2DElementEventArgs& arguments)
    {
    }

    // The new render target is prepared, any binded resources are allowed to recreate now.
    void element_AfterRenderTargetChanged(GuiGraphicsComposition* sender, GuiDirect2DElementEventArgs& arguments)
    {
    }
public:
    Direct2DWindow()
        :GuiWindow(GetCurrentTheme()->CreateWindowStyle())
    {
        SetText(L"Rendering.RawAPI.Direct2D");
        SetClientSize(Size(640, 480));
        GetBoundsComposition()->SetPreferredMinSize(Size(640, 480));
        MoveToScreenCenter();
        {
            GuiDirect2DElement* element=GuiDirect2DElement::Create();
            element->Rendering.AttachMethod(this, &Direct2DWindow::element_Rendering);
            element->BeforeRenderTargetChanged.AttachMethod(this, &Direct2DWindow::element_BeforeRenderTargetChanged);
            element->AfterRenderTargetChanged.AttachMethod(this, &Direct2DWindow::element_AfterRenderTargetChanged);

            GuiBoundsComposition* composition=new GuiBoundsComposition;
            composition->SetAlignmentToParent(Margin(0, 0, 0, 0));
            composition->SetOwnedElement(element);
            GetContainerComposition()->AddChild(composition);
        }
    }
};

void GuiMain()
{
    Direct2DWindow window;
    GetApplication()->Run(&window);
}

在構造函數(shù)里面，我們創(chuàng)建了一個GuiDirect2DElement，然后把它放進一個會自動充滿整個窗口的composition里面。然后我們需要監(jiān)聽三個事件（GDI只有一個，就是Rendering）：
1、Rendering。這個事件在窗口被繪制的時候調(diào)用。GacUI才用了一個低功耗的方法讓程序不斷的繪制自己，所以我們并不需要擔心“如何刷新窗口”的這個問題。
2、BeforeRenderTargetChanged。在這個時候我們要清理掉我們創(chuàng)建出來的資源，譬如說畫刷等等。
3、AfterRenderTargetChanged。在這個時候我們要建立一些繪圖資源，譬如說畫刷等等。

為什么下面兩個函數(shù)那么蛋疼呢？因為Direct2D的類似畫刷這樣的東西，是必須跟一個ID2D1RenderTarget綁定在一起的，不同的render target之間的畫刷不能共享。而且那個可憐的render target還有可能會失效，這個時候GacUI就要重新創(chuàng)建他們。所以無論如何，都必須監(jiān)聽這三個對象，除非我們只用GuiDirect2DElement來渲染文字（因為文字相關的資源是IDWriteFactory控制的，跟render target無關）。

在這個Demo里面，我們要畫的是一個會動的鐘。在這個鐘里面我們要繪制4種線形：邊框、時針、分針、秒針。因此我們需要4個不同的ID2D1SolidColorBrush。由于操作COM對象的時候總要去記得操作那個引用計數(shù)，特別的麻煩，而且還容易忘掉。所以我特地為大家提供了一個叫做ComPtr的東西。所以我們就可以這么聲明、創(chuàng)建和釋放他們：

ComPtr<ID2D1SolidColorBrush>            borderBrush;
ComPtr<ID2D1SolidColorBrush>            secondBrush;
ComPtr<ID2D1SolidColorBrush>            minuteBrush;
ComPtr<ID2D1SolidColorBrush>            hourBrush;

// The render target is going to be destroyed, any binded resources should be released.
void element_BeforeRenderTargetChanged(GuiGraphicsComposition* sender, GuiDirect2DElementEventArgs& arguments)
{
    borderBrush=0;
    secondBrush=0;
    minuteBrush=0;
    hourBrush=0;
}

// The new render target is prepared, any binded resources are allowed to recreate now.
void element_AfterRenderTargetChanged(GuiGraphicsComposition* sender, GuiDirect2DElementEventArgs& arguments)
{
    ID2D1SolidColorBrush* brush;
    {
        brush=0;
        arguments.rt->CreateSolidColorBrush(D2D1::ColorF(0.0f, 0.0f, 0.0f), D2D1::BrushProperties(), &brush);
        borderBrush=brush;
    }
    {
        brush=0;
        arguments.rt->CreateSolidColorBrush(D2D1::ColorF(0.0f, 0.0f, 1.0f), D2D1::BrushProperties(), &brush);
        secondBrush=brush;
    }
    {
        brush=0;
        arguments.rt->CreateSolidColorBrush(D2D1::ColorF(0.0f, 1.0f, 0.0f), D2D1::BrushProperties(), &brush);
        minuteBrush=brush;
    }
    {
        brush=0;
        arguments.rt->CreateSolidColorBrush(D2D1::ColorF(1.0f, 0.0f, 0.0f), D2D1::BrushProperties(), &brush);
        hourBrush=brush;
    }
}

想必大家都應該看清楚了。Before和After事件里面，GacUI都會提供用來繪圖的ID2D1RenderTarget，這個時候必須正確的創(chuàng)建和釋放資源。只要這些資源都建立了起來，那么剩下的就只有把一個時鐘畫出來了。畫一個時鐘還是很容易的，只需要那么幾行代碼就行了：

static const int                        Radius=200;
static const int                        LongScale=10;
static const int                        ShortScale=5;
static const int                        SecondLength=180;
static const int                        MinuteLength=150;
static const int                        HourLength=120;

float GetAngle(float second)
{
    return (second-15.0f)*3.1416f/30.0f;
}

void DrawLine(ID2D1RenderTarget* rt, ComPtr<ID2D1SolidColorBrush> brush, float angle, int width, int startLength, int endLength, int x, int y)
{
    float s=sin(angle);
    float c=cos(angle);
    float x1=(c*startLength)+(float)(x+Radius);
    float y1=(s*startLength)+(float)(y+Radius);
    float x2=(c*endLength)+(float)(x+Radius);
    float y2=(s*endLength)+(float)(y+Radius);
    rt->DrawLine(D2D1::Point2F(x1, y1), D2D1::Point2F(x2, y2), brush.Obj(), (float)width);
}

// arguments.rt is ID2D1RenderTarget.
void element_Rendering(GuiGraphicsComposition* sender, GuiDirect2DElementEventArgs& arguments)
{
    int w=arguments.bounds.Width();
    int h=arguments.bounds.Height();
    int x=arguments.bounds.Left()+(w-Radius*2)/2;
    int y=arguments.bounds.Left()+(h-Radius*2)/2;

    arguments.rt->DrawEllipse(D2D1::Ellipse(D2D1::Point2F((float)(x+Radius), (float)(y+Radius)), (float)Radius, (float)Radius), borderBrush.Obj());
    for(int i=0;i<60;i++)
    {
        int scale=i%5==0?LongScale:ShortScale;
        float angle=GetAngle((float)i);
        DrawLine(arguments.rt, borderBrush, angle, 1, Radius-scale, Radius, x, y);
    }

    DateTime dt=DateTime::LocalTime();
    {
        float angle=GetAngle(dt.hour*5+dt.minute/12.0f+dt.second/720.0f);
        DrawLine(arguments.rt, hourBrush, angle, 5, 0, HourLength, x, y);
    }
    {
        float angle=GetAngle(dt.minute+dt.second/60.0f);
        DrawLine(arguments.rt, minuteBrush, angle, 3, 0, MinuteLength, x, y);
    }
    {
        float angle=GetAngle((float)dt.second);
        DrawLine(arguments.rt, secondBrush, angle, 1, 0, SecondLength, x, y);
    }
}

然后我們就獲得了下圖：（LiveWrite真是太好了，cppblog的傻逼編輯器每次插入圖片都會插入到一個詭異的位置中去）

這樣我們就完成了一個時鐘的制作了，而且也學會了如何在GacUI里面直接使用GDI和Direct2D繪圖了。

因為GacUI需要實現(xiàn)一個文本描述的窗口描述格式，再加上C++經(jīng)常需要處理xml和json等常用數(shù)據(jù)結構，還有自己還要時不時開發(fā)一些語言來玩一玩之類的理由，每一次遇到自己的技術革新的時候，總是免不了要對可配置語法分析器做出修改。上一個版本的可配置語法分析器可以見之前的博客文章《Vczh Library++ 語法分析器開發(fā)指南》。

為什么要重寫vlpp的這一部分呢？因為經(jīng)過多次可配置語法分析器的開發(fā)，我感覺到了C++直接用來表達文法有很多弱點：

1、C++自身的類型系統(tǒng)導致表達出來的文法會有很多噪音。當然這并不是C++的錯，而是通用的語言做這種事情總是會有點噪音的。無論是《Monadic Parser Combinators using C# 3.0》也好，我大微軟研究院的基于Haskell的Parsec也好，還是boost的spirit也好，甚至是F#的Fsyacc也好，都在展示了parser combinator這個強大的概念的同時，也暴露出了parser combinator的弱點：在語法分析結果和語言的數(shù)據(jù)結構的結合方面特別的麻煩。這里的麻煩不僅在于會給文法造成很多噪音，而且復雜的parser還會使得你的結構特別的臃腫（參考Antlr的某些復雜的應用，這里就不一一列舉了）。

2、難以維護。如果直接用C++描述一個強類型文法的話，勢必是要借助parser combinator這個概念的。概念本身是很厲害的，而且實現(xiàn)的好的話開發(fā)效率會特別的高。但是對于C++這種非函數(shù)式語言來說，parser combinator這種特別函數(shù)式的描述放在C++里面就會多出很多麻煩，譬如閉包的語法不夠漂亮啦、沒有垃圾收集器的問題導致rule與rule的循環(huán)引用問題還要自行處理啦（在很早以前的一篇博客論證過了，只要是帶完整閉包功能的語言，都一定不能是用引用計數(shù)來處理內(nèi)存，而必須要一個垃圾收集器的）。盡管我一直以來都還是沒做出過這方面的bug，但是由于（主要是用來處理何時應該delete對象部分的）邏輯復雜，導致數(shù)據(jù)結構必須為delete對象的部分讓步，代碼維護起來也相當?shù)牡疤邸?/p>

3、有些優(yōu)化無法做。舉個簡單的例子，parser combinator就根本沒辦法處理左遞歸。沒有左遞歸，寫起某些文法來也是特別的蛋疼。還有合并共同前綴等等的優(yōu)化也不能做，這導致我們必須為了性能犧牲本來就已經(jīng)充滿了噪音的文法的表達，轉而人工作文法的共同前綴合并，文法看起來就更亂了。

當然上面三個理由看起來好像不太直觀，那我就舉一個典型的例子。大家應該還記得我以前寫過一個叫做NativeX的語言，還給它做了一個帶智能提示的編輯器（還有這里和這里）。NativeX是一個C++實現(xiàn)的C+template+concept mapping的語言，語法分析器當然是用上一個版本的可配置語法分析器來做的。文法規(guī)則很復雜，但是被C++這么以表達，就更加復雜了（.\Library\Scripting\Languages\NativeX\NativeXParser.cpp），已經(jīng)到了不仔細看就無法維護的地步了。

綜上所述，做一個新的可配置語法分析器出來理由充分，勢在必得。但是形式上是什么樣子的呢？上面說過我以前給NativeX寫過一個帶智能提示的編輯器。這個編輯器用的是WinForm，那當然也是用C#寫的，因此那個對性能要求高到離譜的NativeX編輯器用的語法分析器當然也是用C#寫的。流程大概如下：
1、用C#按照要求聲明語法樹結構
2、使用我的庫用C#寫一個文法
3、我的庫會執(zhí)行這個文法，生成一大段C#寫的等價的遞歸下降語法分析器的代碼
當時我把這個過程記錄在了這篇博客文章里面。

因此現(xiàn)在就有一個計劃，這個新的可配置語法分析器當然還是要完全用C++，但是這就跟正則表達式一樣：
1、首先語法樹結構和文法都聲明在一個字符串里面
2、可配置語法分析器可以在內(nèi)存中動態(tài)執(zhí)行這段文法，并按照給定的語法樹結構給出一個在內(nèi)存中的動態(tài)的數(shù)據(jù)結構
3、可配置語法分析器當然還要附帶一個命令行工具，用來讀文法生成C++代碼，包括自帶Visitor模式的語法樹結構，和C++寫的遞歸下降語法分析器

所以現(xiàn)在就有一個草稿，就是那個“聲明在字符串里面”的語法樹結構和文法的說明。這是一個很有意思的過程。

首先，這個可配置語法分析器需要在內(nèi)存中表達語法樹結構，和一個可以執(zhí)行然后產(chǎn)生動態(tài)數(shù)據(jù)結構的文法。因此我們在使用它的時候，可以選擇直接在內(nèi)存中堆出語法樹結構和文法的描述，而不是非得用那個字符串的表達形式。當然，字符串的表達形式肯定是十分緊湊的，但這不是必須的，只是推薦的。

其次，parse這個“語法樹結構和文法都聲明”當然也需要一個語法分析器是不是？所以我們可以用上面的方法，通過直接在內(nèi)存中堆出文法來用自己構造出一個自己的語法分析器。

再者，有了一個內(nèi)存中的語法分析器之后，我就可以將上面第三步的命令行工具做出來，然后用它來描述自己的文法，產(chǎn)生出一段C++寫的遞歸下降語法分析器，用來分析“語法樹結構和文法都聲明”，然后就有了一對C++代碼文件。

最后，把產(chǎn)生出來的這對C++代碼文件加進去，我們就有了一個C++直接寫，而不是在內(nèi)存中動態(tài)構造出來的“語法樹結構和文法都聲明”的分析器了。然后這個分析器就可以替換掉命令行工具里面那個原先動態(tài)構造出來的語法分析器。當然那個動態(tài)構造出來的語法分析器這個時候已經(jīng)沒用了，因為有了生成的C++語法分析器，我們就可以直接使用“語法樹結構和文法都聲明”來描述自己，得到這么一個描述的字符串，然后隨時都可以用這個字符串來動態(tài)生成語法分析器了。

總而言之就是
1、實現(xiàn)可配置語法分析器，可以直接用數(shù)據(jù)結構做出一個產(chǎn)生動態(tài)數(shù)據(jù)結構的parser combinator，記為PC。
2、用PC做一個“語法樹結構和文法都聲明”的語法分析器。這個“語法樹結構和文法都聲明”記為PC Grammar。
3、PC Grammar當然可以用來表達PC Grammar自己，這樣我們就得到了一個專門用來說明什么是合法的“語法樹結構和文法都聲明”的描述的字符串的這么個文法，記為PC Grammar Syntax Definition。
4、通過這份滿足PC Grammar要求的PC Grammar Syntax Definition，我們就可以用PC來解釋PC Grammar Syntax Definition，動態(tài)產(chǎn)生一個解釋PC Grammar的語法分析器
5、有了PC Grammar的語法分析器PC Grammar Parser (in memory version)，之后我們就可以把“文法->C++代碼”的代碼生成器做出來，稱之為PC Grammar C++ Codegen。
6、有了PC Grammar C++ Codegen，我們就可以用他讀入PC Grammar Syntax Definition，產(chǎn)生一個直接用C++寫的PC Grammar的語法分析器，叫做PC Grammar Parser (C++ version)。

到此為止，我們獲得的東西有
1、PC （Parser Combinator）
2、PC Grammar
3、PC Grammar Syntax Definition
4、PC Grammar Parser (in memory version)
5、PC Grammar Parser (C++ version)
6、PC Grammar C++ Codegen

其中，1、3、4、5、6都是可以執(zhí)行的，2是一個“標準”。到了這一步，我們就可以用PC Grammar Parser (C++ version)來替換掉PC Grammar C++ Codegen里面的PC Grammar Parser (in memory version)了。這就跟gcc要編譯一個小編譯器來編譯自己得到一個完整的gcc一樣。這個過程還可以用來測試PC Grammar C++ Codegen是否寫的足夠好。

那么“語法樹結構和文法都聲明”到地是什么樣子的呢？我這里給出一個簡單的文法，就是用來parse諸如int、vl::collections::List<WString>、int*、int&、int[]、void(int, WString, double*)的這些類型的字符串了。下面首先展示如何用這個描述來解決上面的“類型”的語法書聲明：

class Type{}

class DecoratedType : Type
{
    enum Decoration
    {
        Pointer,
        Reference,
        Array,
    }
    Decoration        decoration;
    Type            elementType;
}

class PrimitiveType : Type
{
    token            name;
}

class GenericType : Type
{
    Type            type;
    Type[]            arguments;
}

class SubType : Type
{
    Type            type;
    token            name;
}

class FunctionType : Type
{
    Type            returnType;
    Type[]            arguments;
}

然后就是聲明語法分析器所需要的詞法元素，用正則表達式來描述：

token SYMBOL        = <|>|\[|\]|\(|\)|,|::|\*|&
token NAME            = [a-zA-Z_]\w*

這里只需要兩種token就可以了。接下來就是兩種等價的對于這個文法的描述，用來展示全部的功能。

========================================================

Type SubableType    = NAME[name] as PrimitiveType
                    = SubableType[type] '<' Type[arguments] { ',' Type[arguments] } '>' as GenericType
                    = SubableType[type] '::' NAME[name] as SubType

Type Type            = @SubableType
                    = Type[elementType](
                            ( '*' {decoration = DecoratedType::Pointer}
                            | '&' {decoration = DecoratedType::Reference}
                            | '[' ']' {decoration = ecoratedType::Array}
                            )
                        ) as DecoratedType
                    = Type[returnType] '(' Type[arguments] { ',' Type[arguments] } ')' as FunctionType

========================================================

rule PrimitiveType    PrimitiveType    = NAME[name]
rule GenericType    GenericType        = SubableType[type] '<' Type[arguments] { ',' Type[arguments] } '>'
rule SubType        SubType            = SubableType[type] :: NAME[name]
rule Type            SubableType        = @PrimitiveType | @GenericType | @SubType

rule DecoratedType    DecoratedType    = Type[elementType] '*' {decoration = DecoratedType::Pointer}
                                    = Type[elementType] '&' {decoration = DecoratedType::Reference}
                                    = Type[elementType] '[' ']' {decoration = DecoratedType::Array}
rule FunctionType    FunctionType    = Type[returnType] '(' Type[arguments] { ',' Type[arguments] } ')'
rule Type            Type            = @SubableType | @DecoratedType | @FunctionType

========================================================

如果整套系統(tǒng)開發(fā)出來的話，那么我就會提供一個叫做ParserGen.exe的命令行工具，把上面的字符串轉換為一個可讀的、等價與這段文法的、使用遞歸下降方法來描述的、C++寫出來的語法分析器和語法樹聲明了。

在S1死程群@kula的鼓勵下，我開始使用kula提供的api來操作那個傻逼的“鳥窩”網(wǎng)站（https://www.niaowo.me）。不過由于我自己在業(yè)余時間寫的程序都喜歡用C++和Windows API，因此我琢磨了幾天，真的讓我用C++給寫了出來。

我寫了一個HttpUtility庫來實現(xiàn)C++操作http/https服務的功能，這份代碼可以在這里獲得：

HttpUtility.h：http://gac.codeplex.com/SourceControl/changeset/view/95641#2295555
HttpUtility.cpp：http://gac.codeplex.com/SourceControl/changeset/view/95641#2295554

使用的時候很簡單，只需要HttpRequest里面填滿了參數(shù)，然后就可以用HttpQuery參數(shù)獲得一個HttpResponse類型，這個類型里面寫滿了http服務器的返回值、返回內(nèi)容和cookie等的數(shù)據(jù)。譬如說用來post來登陸鳥窩，然后拿到cookie之后查詢首頁的所有帖子，大概就可以這么寫：

WString NestleGetSession(const WString& username, const WString& password, const WString& apiKey, const WString& apiSecret)
{
    WString body=L"api_key="+apiKey+L"&api_secret="+apiSecret+L"&username="+username+L"&password="+password;

    HttpRequest request;
    HttpResponse response;

    request.SetHost(L"https://www.niaowo.me/account/token/");
    request.method=L"POST";
    request.contentType=L"application/x-www-form-urlencoded";
    request.SetBodyUtf8(body);
    HttpQuery(request, response);

    if(response.statusCode==200)
    {
        return response.cookie;
    }
    else
    {
        return L"";
    }
}

WString NestleGetXml(const WString& path, const WString& cookie)
{
    HttpRequest request;
    HttpResponse response;

    request.SetHost(L"https://www.niaowo.me"+path+L".xml");
    request.method=L"GET";
    request.cookie=cookie;
    request.acceptTypes.Add(L"application/xml");
    HttpQuery(request, response);
   

    if(response.statusCode==200)
    {
        return response.GetBodyUtf8();
    }
    else
    {
        return L"";
    }
}

于是我們終于獲得了一個保存在vl::WString的xml字符串了，那怎么辦呢？這個時候需要出動IXMLDOMDocument2來解析我們的xml。只要裝了IE的計算機上都是有IXMLDOMDocument2的，而不裝IE的Windows PC是不存在的，因此我們總是可以大膽的使用。當然，用IXMLDOMDocument直接來遍歷什么東西特別的慢，所以我們需要的是xpath。xpath對于xml就跟regex對于字符串一樣，可以直接查詢出我們要的東西。首先看一下如何操作IXMLDOMDocument2接口：

IXMLDOMNodeList* XmlQuery(IXMLDOMNode* pDom, const WString& xpath)
{
    IXMLDOMNodeList* nodes=0;
    BSTR xmlQuery=SysAllocString(xpath.Buffer());
    if(xmlQuery)
    {
        HRESULT hr=pDom->selectNodes(xmlQuery, &nodes);
        if(FAILED(hr))
        {
            nodes=0;
        }
        SysFreeString(xmlQuery);
    }
    return nodes;
}

WString XmlReadString(IXMLDOMNode* node)
{
    WString result;
    BSTR text=0;
    HRESULT hr=node->get_text(&text);
    if(SUCCEEDED(hr))
    {
        const wchar_t* candidateItem=text;
        result=candidateItem;
        SysFreeString(text);
    }
    return result;
}

void XmlReadMultipleStrings(IXMLDOMNodeList* textNodes, List<WString>& candidates, int max)
{
    candidates.Clear();
    while((int)candidates.Count()<max)
    {
        IXMLDOMNode* textNode=0;
        HRESULT hr=textNodes->nextNode(&textNode);
        if(hr==S_OK)
        {
            candidates.Add(XmlReadString(textNode));
            textNode->Release();
        }
        else
        {
            break;
        }
    }
}

IXMLDOMDocument2* XmlLoad(const WString& content)
{
    IXMLDOMDocument2* pDom=0;
    HRESULT hr=CoCreateInstance(__uuidof(DOMDocument60), NULL, CLSCTX_INPROC_SERVER, IID_PPV_ARGS(&pDom));
    if(SUCCEEDED(hr))
    {
        pDom->put_async(VARIANT_FALSE);
        pDom->put_validateOnParse(VARIANT_FALSE);
        pDom->put_resolveExternals(VARIANT_FALSE);

        BSTR xmlContent=SysAllocString(content.Buffer());
        if(xmlContent)
        {
            VARIANT_BOOL isSuccessful=0;
            hr=pDom->loadXML(xmlContent, &isSuccessful);
            if(!(SUCCEEDED(hr) && isSuccessful==VARIANT_TRUE))
            {
                pDom->Release();
                pDom=0;
            }
            SysFreeString(xmlContent);
        }
    }
    return pDom;
}

有了這幾個函數(shù)之后，我們就可以干下面的事情，譬如說從鳥窩首頁下載第一頁的所有topic的標題：

WString xml=NestleGetXml(L”/topics”, cookie);
IXMLDOMDocument2* pDom=XmlLoad(xml);
List<WString> titles;
IXMLNodeList* nodes=XmlQuery(pDom, L”/hash/topics/topic/title/text()”);
XmlReadMultipleStrings(nodes, titles, 100);

為什么上面的xpath是hash/topics/topic/title/text()呢?因為這個xml的內(nèi)容大概類似于：
<hash>
    <topics>
        <topic>
            <title>TITLE</title>
…

剩下的大家就去看代碼吧。這個故事告訴我們，只要有一個合適的封裝，C++寫起這些本來應該讓C#來寫的東西也不是那么的煩人的，啊哈哈哈哈。