上一篇文章中我們看到了可配置語(yǔ)法分析器使用起來(lái)的樣子，在這篇文章中我將告訴大家如何通過(guò)重載操作符的方法構(gòu)造文法表達(dá)式樹(shù)，從而使用遞歸向下法進(jìn)行語(yǔ)法分析的工作。
在這之前我們將研究一下什么是文法表達(dá)式。我們將文法表達(dá)式看成分析器，于是復(fù)雜的文法表達(dá)式就是由簡(jiǎn)單的分析器通過(guò)各種方法組合起來(lái)的復(fù)雜分析器。一個(gè)分析器有以下幾個(gè)屬性：
1：輸入類型。輸入類型通常是一個(gè)字符串的指針還是迭代器什么的，具體類型不重要，重要的是輸入狀態(tài)必須能被復(fù)制，能跳到下一個(gè)元素。當(dāng)然wchar_t*也滿足這種要求，但是我們?yōu)榱送ㄓ眯裕ㄆ┤缈梢詾槟阕约旱娜萜鲾U(kuò)展出一個(gè)輸入迭代器）我們采用類似STL的迭代器的方法，也就是concept（這并沒(méi)有包含其技巧，只是概念）來(lái)實(shí)現(xiàn)。然后庫(kù)將為一些基本的東西提供默認(rèn)的迭代器，譬如IEnumerable<T>（嗯嗯，這不是C#，已經(jīng)被Vczh Library++實(shí)現(xiàn)了。容器采用了一種泛型+接口的方法，但是在不必要的情況下允許不支付虛函數(shù)的代價(jià)，不過(guò)這根本章內(nèi)容無(wú)關(guān)，以后再談），或者WString和AString。
2：輸出類型。輸出類型一般包含兩個(gè)方面。第一個(gè)是成功后的結(jié)果，第二個(gè)是失敗后的錯(cuò)誤信息。怎么讓可配置語(yǔ)法分析器在恰當(dāng)?shù)牡胤捷敵鲱愋鸵彩且粋€(gè)很復(fù)雜的問(wèn)題，不過(guò)這根本章內(nèi)容無(wú)關(guān)，下一篇文章接著講這個(gè)細(xì)節(jié)。在這里我們先忽略錯(cuò)誤信息，就如同正則表達(dá)式拒絕匹配一個(gè)字符串也不會(huì)告訴你為什么一樣。
我們可以通過(guò)這兩種屬性來(lái)構(gòu)造出一個(gè)文法表達(dá)式的基類。表達(dá)式樹(shù)通常用基類+若干子類的方法來(lái)實(shí)現(xiàn)，有了基類等于定下了子類的基調(diào)。
1 template<typename I, typename O>
2 class Expression
3 {
4 public:
5 virtual Maybe<O> Parse(I& input)=0;
6 };
Maybe指的是里面可以有類型O的值，或者什么都沒(méi)有。這額外的信息可以添加一個(gè)bool來(lái)表達(dá)，這里就不贅敘了。到了這里我們明白一個(gè)表達(dá)式樹(shù)的重點(diǎn)不是其內(nèi)容，而是分析輸入的算法。因此我們可以組合出連接、分支和循環(huán)：
1 template<typename I, typename O1, typename O2>
2 class Sequence : public Expression<I, ParsingPair<O1, O2>>;
3 {
4 public:
5 Ptr<Expression<I, O1>> left;
6 Ptr<Expression<I, O2>> right;
7
8 Maybe<ParsingPair<O1, O2>> Parse(I& input);
9 };
10
11 template<typename I, typename O>
12 class Alternate : public Expression<I, O>;
13 {
14 public:
15 Ptr<Expression<I, O>> left;
16 Ptr<Expression<I, O>> right;
17
18 Maybe<O> Parse(I& input);
19 };
20
21 template<typename I, typename O>
22 class Loop : public Expression<I, ParsingList<O>>;
23 {
24 public:
25 Ptr<Expression<I, O>> element;
26 int min;
27 int max;
28
29 Maybe<ParsingList<O>> Parse(I& input);
30 };
這就是連接、分支和循環(huán)的聲明了。現(xiàn)在我們可以很清楚的了解什么是帶類型的文法了。類型主要指的是輸出類型，而輸入類型肯定是不能變化的。ParsingPair<A, B>就是一個(gè)帶兩個(gè)數(shù)據(jù)的結(jié)構(gòu)，而ParsingList<T>是一個(gè)鏈表。做成這樣主要是為了在傳遞他們的時(shí)候不要做太多浪費(fèi)的復(fù)制工作，在這里我們只需要了解其概念就好了。
每一種組合都對(duì)子文法的類型有著一些要求，譬如說(shuō)分支要求左右文法表達(dá)式的類型是一樣的。而且輸出類型是通過(guò)子文法的類型計(jì)算而得到的。Ptr<T>是智能指針，在這里使用主要是為了避免復(fù)制的時(shí)候出現(xiàn)問(wèn)題。智能指針在這種數(shù)據(jù)結(jié)構(gòu)下還是十分好用的，反正構(gòu)造和析構(gòu)一條文法的效率都是無(wú)關(guān)緊要的，不要太慢就可以了。
但是我們?nèi)绾沃剌d操作符來(lái)組合文法表達(dá)式呢？其實(shí)文法表達(dá)式最終產(chǎn)生的結(jié)果都是Ptr<Expression<I, O>>，Ptr的操作符重載是不能修改的，所以我們還要一個(gè)代理類：
1 template<typename I, typename O>
2 class Node
3 {
4 public:
5 Ptr<Expression<I, O>> expression;
6 };
7
8 template<typename I, typename O>
9 Node<I, O> operator|(const Node<I, O>& left, const Node<I, O>& right);
10
11 template<typename I, typename O1, typename O2>
12 Node<I, ParsingPair<O1, O2>> operator+(const Node<I, O1>& left, const Node<I, O2>& right);
13
14 //除了+以外，還可以繼承*啊，或者干脆寫個(gè)loop(node, min, max)什么的
15 template<typename I, typename O>
16 Node<I, ParsingList<O>> operator+(const Node<I, O>& element);
我們就可以在每一個(gè)操作符重載里面將各自Node的expression成員變量拿出來(lái)，然后通過(guò)構(gòu)造上面提供的Sequence、Alternate和Loop來(lái)構(gòu)造更加復(fù)雜的文法表達(dá)式，最后重新裝進(jìn)一個(gè)Node<I, O>里面就行了。
這就是我們可以將文法寫進(jìn)C++的小技巧。下一篇文章我們將會(huì)了解到表達(dá)式的每一個(gè)Parse函數(shù)內(nèi)部都做了些什么。