本文的思路來源于
http://m.shnenglu.com/vczh/archive/2008/05/21/50656.html首先先看代碼:
1 #include <stdio.h>
2
3 class Element
4 {
5 public:
6 Element() : start(0),length(0){}
7
8 int start;
9 int* data;
10 int length;
11 };
12
13 template<class T>
14 class Fail
15 {
16 public:
17 int Parser(T& s)
18 {
19 return 0;
20 }
21
22 bool same(T s1,T s2)
23 {
24 for(int i=s1.start;i<s2.length;i++)
25 if(s1.data[i] != s2.data[i])
26 return false;
27 return true;
28 }
29 };
30
31 template<class T>
32 class Ch : public Fail<T>
33 {
34 public:
35 int Parser(T& s1,T s2)
36 {
37 Fail<T> t;
38 if(s1.length >= s2.length)
39 if(same(s1,s2))
40 {
41 s1.start += s2.length;
42 return s2.length;
43 }
44 return t.Parser(s1);
45 }
46 };
47
48 template<class T>
49 class Seq : public Fail<T>
50 {
51 public:
52 int Parser(T& s1,T s2,T s3)
53 {
54 Fail<T> t;
55 Ch<T> ch1,ch2;
56 int n1 = ch1.Parser(s1,s2);
57 int n2 = ch2.Parser(s1,s3);
58 if(n1 && n2) return n1 + n2;
59 else return t.Parser(s1);
60 }
61 };
62
63 template<class T>
64 class Alt : public Fail<T>
65 {
66 public:
67 int Parser(T& s1,T s2,T s3)
68 {
69 Fail<T> t;
70 Ch<T> ch1,ch2;
71 int n1 = ch1.Parser(s1,s2);
72 int n2 = ch2.Parser(s1,s2);
73 if(n1) return n1;
74 else if(n2) return n2;
75 else return t.Parser(s1);
76 }
77 };
78
79 template<class T,int max>
80 class Any : public Fail<T>
81 {
82 public:
83 int Parser(T& s1,T s2)
84 {
85 Fail<T> t;
86 for(int i=0;i<max;i++)
87 if(!same(s1,s2))
88 return t.Parser(s1);
89 return s2.length * max;
90 }
91 };
92
93 void main()
94 {
95 Element s1;
96 Element s2,s3;
97 s1.data = new int[6];
98 s1.length = 6;
99 s1.data[0] = 0;
100 s1.data[1] = 1;
101 s1.data[2] = 2;
102 s1.data[3] = 3;
103 s1.data[4] = 4;
104 s1.data[5] = 5;
105 s2.data = new int[1];
106 s2.length = 1;
107 s2.data[0] = 0;
108 s3.data = new int[1];
109 s3.length = 1;
110 s3.data[0] = 1;
111
112 // Seq Test
113 Seq<Element> seq;
114 int n = seq.Parser(s1,s2,s3);
115 printf("Seq is:%d\n",n);
116
117 // Alt Test
118 s1.start = 0;
119 Alt<Element> alt;
120 n = alt.Parser(s1,s2,s3);
121 printf("Alt is:%d\n",n);
122
123 // Any Test
124 s1.start = 0;
125 s1.data[1] = 0;
126 Any<Element,2> any;
127 n = any.Parser(s1,s2);
128 printf("Any is:%d\n",n);
129
130 delete[] s1.data;
131 delete[] s2.data;
132 delete[] s3.data;
133 }
Element可理解為字符串結構,其中的start成員變量表示輸入串當前分析到的指針.
我們首先需要一個Fail,這個對象表示分析失敗,無論輸入是什么都返回0.
1 template<class T>
2 class Fail
3 {
4 public:
5 int Parser(T& s)
6 {
7 return 0;
8 }
9
10 bool same(T s1,T s2)
11 {
12 for(int i=s1.start;i<s2.length;i++)
13 if(s1.data[i] != s2.data[i])
14 return false;
15 return true;
16 }
17 };
same函數(shù)用于分析輸入串s1與待驗證串s2是否完全匹配.
然后我們需要一個Ch,這個對象分析輸入串和待匹配串是否相同.
1 template<class T>
2 class Ch : public Fail<T>
3 {
4 public:
5 int Parser(T& s1,T s2)
6 {
7 Fail<T> t;
8 if(s1.length >= s2.length)
9 if(same(s1,s2))
10 {
11 s1.start += s2.length;
12 return s2.length;
13 }
14 return t.Parser(s1);
15 }
16 };
比如輸入串為"abcdefg",匹配串為"abc",則Parser("abcdefg","abc")返回"abc"的長度3,如果匹配失敗則返回0.
然后我們需要一個Seq,這個對象分析輸入串和多個待匹配的連接串是否匹配,這里我們簡單設為2個待匹配串.
1 template<class T>
2 class Seq : public Fail<T>
3 {
4 public:
5 int Parser(T& s1,T s2,T s3)
6 {
7 Fail<T> t;
8 Ch<T> ch1,ch2;
9 int n1 = ch1.Parser(s1,s2);
10 int n2 = ch2.Parser(s1,s3);
11 if(n1 && n2) return n1 + n2;
12 else return t.Parser(s1);
13 }
14 };
比如輸入串為"abcdefg",匹配串為"ab"和"cd",則Parser("abcdefg","ab","cd")返回"abcd"的長度4,如果匹配失敗則返回0.
然后是Alt,這個對象分析輸入串和多個待匹配串中的一個是否匹配,這里我們也簡單的設為2個待匹配串.
1 template<class T>
2 class Alt : public Fail<T>
3 {
4 public:
5 int Parser(T& s1,T s2,T s3)
6 {
7 Fail<T> t;
8 Ch<T> ch1,ch2;
9 int n1 = ch1.Parser(s1,s2);
10 int n2 = ch2.Parser(s1,s2);
11 if(n1) return n1;
12 else if(n2) return n2;
13 else return t.Parser(s1);
14 }
15 };
比如輸入串為"abcdefg",匹配串為"ab"和"cd",則Parser("abcdefg","ab","cd")返回"ab"的長度2,如果匹配失敗則返回0.
最后是Any,這個對象分析輸入串和一個待匹配串的循環(huán)是否匹配.
1 template<class T,int max>
2 class Any : public Fail<T>
3 {
4 public:
5 int Parser(T& s1,T s2)
6 {
7 Fail<T> t;
8 for(int i=0;i<max;i++)
9 if(!same(s1,s2))
10 return t.Parser(s1);
11 return s2.length * max;
12 }
13 };
比如輸入串為"ababefg",匹配串為"ab",max=2,則Parser("abcdefg","ab")返回"ab"的長度2*2,如果匹配失敗則返回0.
然后我們來測試一下:
1 void main()
2 {
3 Element s1;
4 Element s2,s3;
5 s1.data = new int[6];
6 s1.length = 6;
7 s1.data[0] = 0;
8 s1.data[1] = 1;
9 s1.data[2] = 2;
10 s1.data[3] = 3;
11 s1.data[4] = 4;
12 s1.data[5] = 5;
13 s2.data = new int[1];
14 s2.length = 1;
15 s2.data[0] = 0;
16 s3.data = new int[1];
17 s3.length = 1;
18 s3.data[0] = 1;
19
20 // Seq Test
21 Seq<Element> seq;
22 int n = seq.Parser(s1,s2,s3);
23 printf("Seq is:%d\n",n);
24
25 // Alt Test
26 s1.start = 0;
27 Alt<Element> alt;
28 n = alt.Parser(s1,s2,s3);
29 printf("Alt is:%d\n",n);
30
31 // Any Test
32 s1.start = 0;
33 s1.data[1] = 0;
34 Any<Element,2> any;
35 n = any.Parser(s1,s2);
36 printf("Any is:%d\n",n);
37
38 delete[] s1.data;
39 delete[] s2.data;
40 delete[] s3.data;
41 }
結果為:
1 Seq is:2
2 Alt is:1
3 Any is:2
以上就是簡單的面向組合子測試了.
posted on 2011-01-22 17:11
lwch 閱讀(1663)
評論(4) 編輯 收藏 引用 所屬分類:
NScript