上一篇文章中我們看到了可配置語法分析器使用起來的樣子，在這篇文章中我將告訴大家如何通過重載操作符的方法構(gòu)造文法表達(dá)式樹，從而使用遞歸向下法進(jìn)行語法分析的工作。

    在這之前我們將研究一下什么是文法表達(dá)式。我們將文法表達(dá)式看成分析器，于是復(fù)雜的文法表達(dá)式就是由簡單的分析器通過各種方法組合起來的復(fù)雜分析器。一個分析器有以下幾個屬性：

    1：輸入類型。輸入類型通常是一個字符串的指針還是迭代器什么的，具體類型不重要，重要的是輸入狀態(tài)必須能被復(fù)制，能跳到下一個元素。當(dāng)然wchar_t*也滿足這種要求，但是我們?yōu)榱送ㄓ眯裕ㄆ┤缈梢詾槟阕约旱娜萜鲾U(kuò)展出一個輸入迭代器）我們采用類似STL的迭代器的方法，也就是concept（這并沒有包含其技巧，只是概念）來實(shí)現(xiàn)。然后庫將為一些基本的東西提供默認(rèn)的迭代器，譬如IEnumerable<T>（嗯嗯，這不是C#，已經(jīng)被Vczh Library++實(shí)現(xiàn)了。容器采用了一種泛型+接口的方法，但是在不必要的情況下允許不支付虛函數(shù)的代價(jià)，不過這根本章內(nèi)容無關(guān)，以后再談），或者WString和AString。

    2：輸出類型。輸出類型一般包含兩個方面。第一個是成功后的結(jié)果，第二個是失敗后的錯誤信息。怎么讓可配置語法分析器在恰當(dāng)?shù)牡胤捷敵鲱愋鸵彩且粋€很復(fù)雜的問題，不過這根本章內(nèi)容無關(guān)，下一篇文章接著講這個細(xì)節(jié)。在這里我們先忽略錯誤信息，就如同正則表達(dá)式拒絕匹配一個字符串也不會告訴你為什么一樣。

    我們可以通過這兩種屬性來構(gòu)造出一個文法表達(dá)式的基類。表達(dá)式樹通常用基類+若干子類的方法來實(shí)現(xiàn)，有了基類等于定下了子類的基調(diào)。

    Maybe指的是里面可以有類型O的值，或者什么都沒有。這額外的信息可以添加一個bool來表達(dá)，這里就不贅敘了。到了這里我們明白一個表達(dá)式樹的重點(diǎn)不是其內(nèi)容，而是分析輸入的算法。因此我們可以組合出連接、分支和循環(huán)：

    這就是連接、分支和循環(huán)的聲明了。現(xiàn)在我們可以很清楚的了解什么是帶類型的文法了。類型主要指的是輸出類型，而輸入類型肯定是不能變化的。ParsingPair<A, B>就是一個帶兩個數(shù)據(jù)的結(jié)構(gòu)，而ParsingList<T>是一個鏈表。做成這樣主要是為了在傳遞他們的時(shí)候不要做太多浪費(fèi)的復(fù)制工作，在這里我們只需要了解其概念就好了。

    每一種組合都對子文法的類型有著一些要求，譬如說分支要求左右文法表達(dá)式的類型是一樣的。而且輸出類型是通過子文法的類型計(jì)算而得到的。Ptr<T>是智能指針，在這里使用主要是為了避免復(fù)制的時(shí)候出現(xiàn)問題。智能指針在這種數(shù)據(jù)結(jié)構(gòu)下還是十分好用的，反正構(gòu)造和析構(gòu)一條文法的效率都是無關(guān)緊要的，不要太慢就可以了。

    但是我們?nèi)绾沃剌d操作符來組合文法表達(dá)式呢？其實(shí)文法表達(dá)式最終產(chǎn)生的結(jié)果都是Ptr<Expression<I, O>>，Ptr的操作符重載是不能修改的，所以我們還要一個代理類：

    我們就可以在每一個操作符重載里面將各自Node的expression成員變量拿出來，然后通過構(gòu)造上面提供的Sequence、Alternate和Loop來構(gòu)造更加復(fù)雜的文法表達(dá)式，最后重新裝進(jìn)一個Node<I, O>里面就行了。

    這就是我們可以將文法寫進(jìn)C++的小技巧。下一篇文章我們將會了解到表達(dá)式的每一個Parse函數(shù)內(nèi)部都做了些什么。