繼
《面向組合子的一些測試》 進一步完善代碼,制作出詞法分析器.
我們首先需要一個Fail基類,他有一個純虛函數Parser.
1 class Fail
2 {
3 public:
4 virtual NWString Parser(NWString& input)=0;
5 };
Parser的輸入為要分析的字符串,輸出為分析完成后剩余的字符串.
然后我們需要一個Ch和一個Str分別用來分析單個字符和一個字符串.
1 class Ch : public Fail
2 {
3 public:
4 Ch(WCHAR _value) : value(_value){}
5
6 NWString Parser(NWString& input);
7
8 WCHAR Value();
9 protected:
10 WCHAR value; // 待匹配串
11 };
12
13 class Str : public Fail
14 {
15 public:
16 Str(NWString _value) : value(_value){}
17
18 NWString Parser(NWString& input);
19 protected:
20 NWString value; // 待匹配串
21 };
然后是Seq,Alt和Any,分別表示組合,選擇和循環.
1 class Seq : public Fail
2 {
3 public:
4 Seq(const NAutoPtr<Fail>& _left,const NAutoPtr<Fail>& _right) : left(_left),right(_right){}
5
6 NWString Parser(NWString& input);
7 protected:
8 NAutoPtr<Fail> left;
9 NAutoPtr<Fail> right;
10 };
11
12 class Alt : public Fail
13 {
14 public:
15 Alt(const NAutoPtr<Fail>& _left,const NAutoPtr<Fail>& _right) : left(_left),right(_right){}
16
17 NWString Parser(NWString& input);
18 protected:
19 NAutoPtr<Fail> left;
20 NAutoPtr<Fail> right;
21 };
22
23 class Any : public Fail
24 {
25 public:
26 Any(const NAutoPtr<Fail>& _left,const int _count) : left(_left),count(_count){}
27
28 NWString Parser(NWString& input);
29 protected:
30 NAutoPtr<Fail> left;
31 int count;
32 };
最后我們需要一個Node類型來存放以上這幾類對象.
1 class Node
2 {
3 public:
4 Node(){}
5 Node(const NAutoPtr<Fail>& _left) : left(_left){}
6
7 friend NAutoPtr<Node> operator+(const NAutoPtr<Node>& left,const NAutoPtr<Node>& right);
8 friend NAutoPtr<Node> operator|(const NAutoPtr<Node>& left,const NAutoPtr<Node>& right);
9 friend NAutoPtr<Node> operator-(const NAutoPtr<Node>& left,const NAutoPtr<Node>& right);
10
11 static NAutoPtr<Node> OnceMore(NAutoPtr<Node> node);
12 static NAutoPtr<Node> More(NAutoPtr<Node> node);
13 static NAutoPtr<Node> NewCh(WCHAR input);
14 static NAutoPtr<Node> NewStr(NWString input);
15
16 NWString Parser(NWString& input);
17
18 NAutoPtr<Fail>& Value();
19 protected:
20 NAutoPtr<Fail> left;
21 };
下面來分析一下Node里的函數:
+:對應于Seq,用于將兩個Node連接起來.
|:對應與Alt,用于選擇兩個Node.
-:只有left和right的Value()都是NAutoPtr<Ch>時才可使用,內部有類型轉換,表示從哪個字符到哪個字符.
OnceMore:重復1次及以上.
More:重復0次以上.
NewCh:生成一個NAutoPtr<Ch>的Node對象.
NewStr:生成一個NAutoPtr<Str>的Node對象.
下面我們需要4個宏.
1 #define ONCEMORE(N) Node::OnceMore(N)
2 #define MORE(N) Node::More(N)
3 #define NEWCH(N) Node::NewCh(N)
4 #define NEWSTR(N) Node::NewStr(N)
這4個宏僅為了輸入方便
然后我們來測試一下:
1 NAutoPtr<Node> Symbol = ONCEMORE(NEWCH('_') | NEWCH('a') - NEWCH('z')) | (NEWCH('A') - NEWCH('Z'))
2 + MORE(NEWCH('_') | (NEWCH('0') - NEWCH('9')) | (NEWCH('a') - NEWCH('z')) | (NEWCH('A') - NEWCH('Z')));
3 NAutoPtr<Node> Number = ONCEMORE(NEWCH('0') - NEWCH('9'));
4 NAutoPtr<Node> Real = Number + NEWCH('.') + Number;
相信對正則表達式有一定認識的同學已經知道這3條語句分別對應于什么正則表達式.
Symbol->[_a-zA-Z]+[_0-9a-zA-Z]*
Number->[0-9]+
Real->[0-9]+.[0-9]+
定義一個待分析的字符串.
1 NWString str = L"abcce_fg123.459agetr";
對其分析.
1 wprintf(L"%s\n",str);
2 wprintf(L"%s\n",Symbol->Parser(str));
3 wprintf(L"%s\n",Real->Parser(str));
4 wprintf(L"%s\n",Symbol->Parser(str));
分析結果.
1 abcce_fg123.459agetr
2 123.459agetr
3 agetr
4
因為沒有考慮分析效率問題,所以使用NWString作為輸入和輸出,在實際使用中可用LPTSTR來代替NWString,同時修改響應代碼.
最后給出
源代碼
posted on 2011-01-26 22:11
lwch 閱讀(2470)
評論(9) 編輯 收藏 引用 所屬分類:
NScript