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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

故事就從狀態(tài)機(jī)開(kāi)始。文法我就不重復(fù)了，見(jiàn)上一篇文章。現(xiàn)在我們從狀態(tài)機(jī)開(kāi)始。第一個(gè)狀態(tài)機(jī)是直接從文法變過(guò)來(lái)的：

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

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

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

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

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

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

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

所以，其實(shí)在這個(gè)時(shí)候，我們同時(shí)解決了“應(yīng)該在什么時(shí)候進(jìn)行左遞歸Shifting”的問(wèn)題。只要當(dāng)左遞歸Reducing已發(fā)生，我們立刻在軌跡上面補(bǔ)上一條左遞歸Shifting就好了。因此，我們?cè)谝婚_(kāi)始做parsing的時(shí)候，根本不需要預(yù)先做左遞歸Shifting。所以當(dāng)剛剛輸入A的時(shí)候，“狀態(tài)跳轉(zhuǎn)軌跡”是這樣子的：

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

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

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

（對(duì)學(xué)術(shù)感興趣的人可以去wiki一下“下推自動(dòng)機(jī)”）

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

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

這樣就構(gòu)成了一個(gè)簡(jiǎn)單的文法，用來(lái)分析帶逗號(hào)分割的名字列表的。那么寫(xiě)成狀態(tài)機(jī)就是如下的形式：

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是文法的終結(jié)狀態(tài)，畫(huà)成圖如下：

（PowerPoint畫(huà)圖復(fù)制到LiveWriter里面是一幅圖面簡(jiǎn)直太方便了）

但是這樣還沒(méi)完。IDList0跳到IDList2的時(shí)候的輸入“IDList”其實(shí)還不夠，因?yàn)橛米鬏斎氲膖oken其實(shí)只有NAME和","兩種。下一步即將演示如何從這個(gè)狀態(tài)機(jī)編程名副其實(shí)的下推狀態(tài)機(jī)。

在這里我先介紹幾個(gè)概念。第一個(gè)是移進(jìn)，第二個(gè)是規(guī)約。為什么要用這兩個(gè)名字呢？因?yàn)榇蟛糠秩丝吹纳当魄迦A大學(xué)出版社的低能編譯原理課本都是這么講的，黑化分別叫Shift和Reduce。好了，什么是Shift呢？IDList0跳到IDList2的時(shí)候，要移進(jìn)IDList。IDList3跳到IDList1，要移進(jìn)到ID。IDList0跳到IDList1也要移進(jìn)到ID。這也就是說(shuō)，狀態(tài)轉(zhuǎn)移經(jīng)過(guò)一條非終結(jié)符的邊的時(shí)候會(huì)移進(jìn)到另一條文法的狀態(tài)機(jī)里。ID1和IDList1作為ID和IDList的終結(jié)節(jié)點(diǎn)，要根據(jù)“從那里移進(jìn)來(lái)的”分別規(guī)約然后跳轉(zhuǎn)到“IDList2或者IDList1”。這也就是說(shuō)，一旦你到達(dá)了一條聞法的狀態(tài)機(jī)的終結(jié)狀態(tài)，就要開(kāi)始規(guī)約然后跳轉(zhuǎn)到上一級(jí)的狀態(tài)了。

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

那現(xiàn)在讓我們把上面那幅圖的兩個(gè)狀態(tài)機(jī)連起來(lái)，產(chǎn)生一個(gè)下推自動(dòng)機(jī)。但是在這里我先做第一步。因?yàn)镮DList0到IDList1的跳轉(zhuǎn)是一個(gè)左遞歸的過(guò)程，先暫時(shí)不管。

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

但是Shift的時(shí)候并沒(méi)有產(chǎn)生輸入，所以實(shí)際上應(yīng)該改成下面這個(gè)樣子。

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

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

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

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

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

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

然后就開(kāi)始了！（用文字表達(dá)實(shí)在是太難看了，所以貼成圖）

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

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

群號(hào)：31724825

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

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

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

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

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

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

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

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

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

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

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

不可否認(rèn)，微軟設(shè)計(jì)出來(lái)的API大部分還是很有道理的，除了Win32的原生GUI部分。

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

當(dāng)然，有了ParsingSymbol，還要有他的manager才可以完成整個(gè)符號(hào)表的操作：

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

這個(gè)ParsingSymbolManager有著符號(hào)表管理器的以下兩個(gè)典型作用

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

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

其次就是Cache函數(shù)。其實(shí)Cache函數(shù)這么寫(xiě)，不是用來(lái)直接調(diào)用的。舉個(gè)例子，在分析一個(gè)文法的時(shí)候，我們需要把一個(gè)“類型”語(yǔ)法樹(shù)轉(zhuǎn)成一個(gè)“類型”符號(hào)（譬如說(shuō)要決定一個(gè)文法要create什么類型的語(yǔ)法樹(shù)節(jié)點(diǎn)的時(shí)候）。因此就有了下面的函數(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;
}

很明顯，這個(gè)函數(shù)做的事情就是，查詢一個(gè)ParsingDefinitionType節(jié)點(diǎn)有沒(méi)有被查詢過(guò)，如果有直接用cache，沒(méi)有的話再?gòu)念^計(jì)算他然后cache起來(lái)。因此這些Cache函數(shù)就是給類似FindType的函數(shù)用的，而語(yǔ)義分析的代碼則直接使用FindType，而不是Cache函數(shù)，來(lái)獲取一個(gè)類型的符號(hào)。聰明的朋友們可以看出來(lái)，這種寫(xiě)法蘊(yùn)含著一個(gè)條件，就是語(yǔ)法樹(shù)創(chuàng)建完就不會(huì)改了（廢話，當(dāng)然不會(huì)改！）。

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

就像之前的博客文章所說(shuō)的，（主要還是）因?yàn)?a target="_blank">GacUI的原因，我決定開(kāi)發(fā)一個(gè)更好的可配置輕量級(jí)語(yǔ)法分析器來(lái)代替之前的落后的版本。在說(shuō)這個(gè)文章之前，我還是想在此向大家推薦一本《編程語(yǔ)言實(shí)現(xiàn)模式》，這的確是一本好書(shū)，讓我相見(jiàn)恨晚。

其實(shí)說(shuō)到開(kāi)發(fā)語(yǔ)法分析器，我從2007年就已經(jīng)開(kāi)始在思考類似的問(wèn)題了。當(dāng)時(shí)C++還處于用的不太熟練的時(shí)候，難免會(huì)做出一些傻逼的事情，不過(guò)總的來(lái)說(shuō)當(dāng)年的idea還是能用的。從那時(shí)候開(kāi)始，我為了鍛煉自己，一直在實(shí)現(xiàn)各種不同的語(yǔ)言。所以給自己開(kāi)發(fā)一個(gè)可配置語(yǔ)法分析器也是在所難免的事情了。于是就有：
第一版：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++里面可以通過(guò)直接描述文法和一些語(yǔ)義行為來(lái)讓系統(tǒng)可以迅速構(gòu)造出一個(gè)針對(duì)特定目的的用起來(lái)方便的語(yǔ)法分析器，而“第三版”就是到目前為止還在用的一個(gè)版本。至于為什么我要做一個(gè)新的——也就是第四版——之前的文章已經(jīng)說(shuō)了。

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

于是今天就說(shuō)說(shuō)關(guān)于構(gòu)造語(yǔ)法樹(shù)的事情。

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

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

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

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

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

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

為什么要這樣做呢？學(xué)習(xí)過(guò)面向?qū)ο箝_(kāi)發(fā)方法的都知道，把一個(gè)明顯是繼承結(jié)構(gòu)的東西寫(xiě)成一堆union/struct和一個(gè)enum來(lái)判斷他們，是不對(duì)的。第一個(gè)不好的地方就是，如果其中的成員需要構(gòu)造函數(shù)和析構(gòu)函數(shù)，那union就用不了了，struct就一定會(huì)造成大量的內(nèi)存浪費(fèi)。因?yàn)橐活w語(yǔ)法樹(shù)是可以很大的。其次，當(dāng)語(yǔ)法樹(shù)的結(jié)構(gòu)（主要是添加刪除了新的語(yǔ)法樹(shù)類型）之后，我們根本不可能保證我們所有的swtich(node->enumType)語(yǔ)句都接受到了正確的更新。

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

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

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

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

今天就先講到這里了。現(xiàn)在的可配置語(yǔ)法分析器的開(kāi)發(fā)進(jìn)度是正在寫(xiě)語(yǔ)義分析的部分。等到語(yǔ)義分析寫(xiě)完了，我會(huì)再寫(xiě)一篇紀(jì)事來(lái)說(shuō)明開(kāi)發(fā)語(yǔ)義分析程序和構(gòu)造符號(hào)表的一般做法。

由于接下去要用uniscribe（這是一個(gè)可以告訴我們?cè)阡秩疽粋€(gè)超長(zhǎng)unicode字符串的時(shí)候，什么地方可以換行，什么地方要換順序，什么字符要用一種神奇的方法來(lái)渲染之類的庫(kù)）做可以插入圖片和其它亂七八糟東西的rich text box，為了更方便做實(shí)驗(yàn)，而且也考慮到很多軟件也需要直接繪圖的功能，所以我寫(xiě)了這么兩個(gè)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）

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

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

首先，整個(gè)程序的框架是這樣子的：

#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);
}

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

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

在這個(gè)Demo里面，我們要畫(huà)的是一個(gè)會(huì)動(dòng)的鐘。在這個(gè)鐘里面我們要繪制4種線形：邊框、時(shí)針、分針、秒針。因此我們需要4個(gè)不同的ID2D1SolidColorBrush。由于操作COM對(duì)象的時(shí)候總要去記得操作那個(gè)引用計(jì)數(shù)，特別的麻煩，而且還容易忘掉。所以我特地為大家提供了一個(gè)叫做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;
    }
}

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

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的傻逼編輯器每次插入圖片都會(huì)插入到一個(gè)詭異的位置中去）

這樣我們就完成了一個(gè)時(shí)鐘的制作了，而且也學(xué)會(huì)了如何在GacUI里面直接使用GDI和Direct2D繪圖了。

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

為什么要重寫(xiě)vlpp的這一部分呢？因?yàn)榻?jīng)過(guò)多次可配置語(yǔ)法分析器的開(kāi)發(fā)，我感覺(jué)到了C++直接用來(lái)表達(dá)文法有很多弱點(diǎn)：

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

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

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

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

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

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

所以現(xiàn)在就有一個(gè)草稿，就是那個(gè)“聲明在字符串里面”的語(yǔ)法樹(shù)結(jié)構(gòu)和文法的說(shuō)明。這是一個(gè)很有意思的過(guò)程。

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

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

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

最后，把產(chǎn)生出來(lái)的這對(duì)C++代碼文件加進(jìn)去，我們就有了一個(gè)C++直接寫(xiě)，而不是在內(nèi)存中動(dòng)態(tài)構(gòu)造出來(lái)的“語(yǔ)法樹(shù)結(jié)構(gòu)和文法都聲明”的分析器了。然后這個(gè)分析器就可以替換掉命令行工具里面那個(gè)原先動(dòng)態(tài)構(gòu)造出來(lái)的語(yǔ)法分析器。當(dāng)然那個(gè)動(dòng)態(tài)構(gòu)造出來(lái)的語(yǔ)法分析器這個(gè)時(shí)候已經(jīng)沒(méi)用了，因?yàn)橛辛松傻腃++語(yǔ)法分析器，我們就可以直接使用“語(yǔ)法樹(shù)結(jié)構(gòu)和文法都聲明”來(lái)描述自己，得到這么一個(gè)描述的字符串，然后隨時(shí)都可以用這個(gè)字符串來(lái)動(dòng)態(tài)生成語(yǔ)法分析器了。

總而言之就是
1、實(shí)現(xiàn)可配置語(yǔ)法分析器，可以直接用數(shù)據(jù)結(jié)構(gòu)做出一個(gè)產(chǎn)生動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)的parser combinator，記為PC。
2、用PC做一個(gè)“語(yǔ)法樹(shù)結(jié)構(gòu)和文法都聲明”的語(yǔ)法分析器。這個(gè)“語(yǔ)法樹(shù)結(jié)構(gòu)和文法都聲明”記為PC Grammar。
3、PC Grammar當(dāng)然可以用來(lái)表達(dá)PC Grammar自己，這樣我們就得到了一個(gè)專門用來(lái)說(shuō)明什么是合法的“語(yǔ)法樹(shù)結(jié)構(gòu)和文法都聲明”的描述的字符串的這么個(gè)文法，記為PC Grammar Syntax Definition。
4、通過(guò)這份滿足PC Grammar要求的PC Grammar Syntax Definition，我們就可以用PC來(lái)解釋PC Grammar Syntax Definition，動(dòng)態(tài)產(chǎn)生一個(gè)解釋PC Grammar的語(yǔ)法分析器
5、有了PC Grammar的語(yǔ)法分析器PC Grammar Parser (in memory version)，之后我們就可以把“文法->C++代碼”的代碼生成器做出來(lái)，稱之為PC Grammar C++ Codegen。
6、有了PC Grammar C++ Codegen，我們就可以用他讀入PC Grammar Syntax Definition，產(chǎn)生一個(gè)直接用C++寫(xiě)的PC Grammar的語(yǔ)法分析器，叫做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是一個(gè)“標(biāo)準(zhǔn)”。到了這一步，我們就可以用PC Grammar Parser (C++ version)來(lái)替換掉PC Grammar C++ Codegen里面的PC Grammar Parser (in memory version)了。這就跟gcc要編譯一個(gè)小編譯器來(lái)編譯自己得到一個(gè)完整的gcc一樣。這個(gè)過(guò)程還可以用來(lái)測(cè)試PC Grammar C++ Codegen是否寫(xiě)的足夠好。

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

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

然后就是聲明語(yǔ)法分析器所需要的詞法元素，用正則表達(dá)式來(lái)描述：

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

這里只需要兩種token就可以了。接下來(lái)就是兩種等價(jià)的對(duì)于這個(gè)文法的描述，用來(lái)展示全部的功能。

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

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)開(kāi)發(fā)出來(lái)的話，那么我就會(huì)提供一個(gè)叫做ParserGen.exe的命令行工具，把上面的字符串轉(zhuǎn)換為一個(gè)可讀的、等價(jià)與這段文法的、使用遞歸下降方法來(lái)描述的、C++寫(xiě)出來(lái)的語(yǔ)法分析器和語(yǔ)法樹(shù)聲明了。

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

我寫(xiě)了一個(gè)HttpUtility庫(kù)來(lái)實(shí)現(xiàn)C++操作http/https服務(wù)的功能，這份代碼可以在這里獲得：

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

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

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

于是我們終于獲得了一個(gè)保存在vl::WString的xml字符串了，那怎么辦呢？這個(gè)時(shí)候需要出動(dòng)IXMLDOMDocument2來(lái)解析我們的xml。只要裝了IE的計(jì)算機(jī)上都是有IXMLDOMDocument2的，而不裝IE的Windows PC是不存在的，因此我們總是可以大膽的使用。當(dāng)然，用IXMLDOMDocument直接來(lái)遍歷什么東西特別的慢，所以我們需要的是xpath。xpath對(duì)于xml就跟regex對(duì)于字符串一樣，可以直接查詢出我們要的東西。首先看一下如何操作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;
}

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

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()呢?因?yàn)檫@個(gè)xml的內(nèi)容大概類似于：
<hash>
    <topics>
        <topic>
            <title>TITLE</title>
…

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