上一篇文章中我們看到了可配置語法分析器使用起來的樣子，在這篇文章中我將告訴大家如何通過重載操作符的方法構造文法表達式樹，從而使用遞歸向下法進行語法分析的工作。
在這之前我們將研究一下什么是文法表達式。我們將文法表達式看成分析器，于是復雜的文法表達式就是由簡單的分析器通過各種方法組合起來的復雜分析器。一個分析器有以下幾個屬性：
1：輸入類型。輸入類型通常是一個字符串的指針還是迭代器什么的，具體類型不重要，重要的是輸入狀態必須能被復制，能跳到下一個元素。當然wchar_t*也滿足這種要求，但是我們為了通用性（譬如可以為你自己的容器擴展出一個輸入迭代器）我們采用類似STL的迭代器的方法，也就是concept（這并沒有包含其技巧，只是概念）來實現。然后庫將為一些基本的東西提供默認的迭代器，譬如IEnumerable<T>（嗯嗯，這不是C#，已經被Vczh Library++實現了。容器采用了一種泛型+接口的方法，但是在不必要的情況下允許不支付虛函數的代價，不過這根本章內容無關，以后再談），或者WString和AString。
2：輸出類型。輸出類型一般包含兩個方面。第一個是成功后的結果，第二個是失敗后的錯誤信息。怎么讓可配置語法分析器在恰當的地方輸出類型也是一個很復雜的問題，不過這根本章內容無關，下一篇文章接著講這個細節。在這里我們先忽略錯誤信息，就如同正則表達式拒絕匹配一個字符串也不會告訴你為什么一樣。
我們可以通過這兩種屬性來構造出一個文法表達式的基類。表達式樹通常用基類+若干子類的方法來實現，有了基類等于定下了子類的基調。
1 template<typename I, typename O>
2 class Expression
3 {
4 public:
5 virtual Maybe<O> Parse(I& input)=0;
6 };
Maybe指的是里面可以有類型O的值，或者什么都沒有。這額外的信息可以添加一個bool來表達，這里就不贅敘了。到了這里我們明白一個表達式樹的重點不是其內容，而是分析輸入的算法。因此我們可以組合出連接、分支和循環：
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 };
這就是連接、分支和循環的聲明了。現在我們可以很清楚的了解什么是帶類型的文法了。類型主要指的是輸出類型，而輸入類型肯定是不能變化的。ParsingPair<A, B>就是一個帶兩個數據的結構，而ParsingList<T>是一個鏈表。做成這樣主要是為了在傳遞他們的時候不要做太多浪費的復制工作，在這里我們只需要了解其概念就好了。
每一種組合都對子文法的類型有著一些要求，譬如說分支要求左右文法表達式的類型是一樣的。而且輸出類型是通過子文法的類型計算而得到的。Ptr<T>是智能指針，在這里使用主要是為了避免復制的時候出現問題。智能指針在這種數據結構下還是十分好用的，反正構造和析構一條文法的效率都是無關緊要的，不要太慢就可以了。
但是我們如何重載操作符來組合文法表達式呢？其實文法表達式最終產生的結果都是Ptr<Expression<I, O>>，Ptr的操作符重載是不能修改的，所以我們還要一個代理類：
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 //除了+以外，還可以繼承*啊，或者干脆寫個loop(node, min, max)什么的
15 template<typename I, typename O>
16 Node<I, ParsingList<O>> operator+(const Node<I, O>& element);
我們就可以在每一個操作符重載里面將各自Node的expression成員變量拿出來，然后通過構造上面提供的Sequence、Alternate和Loop來構造更加復雜的文法表達式，最后重新裝進一個Node<I, O>里面就行了。
這就是我們可以將文法寫進C++的小技巧。下一篇文章我們將會了解到表達式的每一個Parse函數內部都做了些什么。
posted on 2009-12-04 23:43
陳梓瀚(vczh) 閱讀(3209)
評論(1) 編輯 收藏 引用 所屬分類:
VL++3.0開發紀事