雖然說分析語法樹依賴于遞歸，但是你真的去寫遞歸那是一件很煩的事情，個人覺得煩事煩在你每次都要去RegexExpression.h里面聲明所有的虛函數之后復制過來一一運行。有沒有辦法僅編輯.cpp文件就能做到呢？也就是說，在如何不修改Expression一系列類的接口的情況下給Expression添加算法？一般來說對付樹形結構都是使用Visitor模式的。
首先對于
上一篇文章定義的樹來看，我們需要設計一個通用的Visitor接口：
1 class IRegexExpressionAlgorithm : public Interface
2 {
3 public:
4 virtual void Visit(CharSetExpression* expression)=0;
5 virtual void Visit(LoopExpression* expression)=0;
6 virtual void Visit(SequenceExpression* expression)=0;
7 virtual void Visit(AlternateExpression* expression)=0;
8 virtual void Visit(BeginExpression* expression)=0;
9 virtual void Visit(EndExpression* expression)=0;
10 virtual void Visit(CaptureExpression* expression)=0;
11 virtual void Visit(MatchExpression* expression)=0;
12 virtual void Visit(PositiveExpression* expression)=0;
13 virtual void Visit(NegativeExpression* expression)=0;
14 virtual void Visit(UsingExpression* expression)=0;
15 };
接口定義好了之后，就給所有的表達式樹添加一個Apply（虛）函數來訪問相應的Visit函數：
1 void CharSetExpression::Apply(IRegexExpressionAlgorithm& algorithm)
2 {
3 algorithm.Visit(this);
4 }
5
6 void LoopExpression::Apply(IRegexExpressionAlgorithm& algorithm)
7 {
8 algorithm.Visit(this);
9 }
10
11 void SequenceExpression::Apply(IRegexExpressionAlgorithm& algorithm)
12 {
13 algorithm.Visit(this);
14 }
15
16 void AlternateExpression::Apply(IRegexExpressionAlgorithm& algorithm)
17 {
18 algorithm.Visit(this);
19 }
20
21 void BeginExpression::Apply(IRegexExpressionAlgorithm& algorithm)
22 {
23 algorithm.Visit(this);
24 }
25
26 void EndExpression::Apply(IRegexExpressionAlgorithm& algorithm)
27 {
28 algorithm.Visit(this);
29 }
30
31 void CaptureExpression::Apply(IRegexExpressionAlgorithm& algorithm)
32 {
33 algorithm.Visit(this);
34 }
35
36 void MatchExpression::Apply(IRegexExpressionAlgorithm& algorithm)
37 {
38 algorithm.Visit(this);
39 }
40
41 void PositiveExpression::Apply(IRegexExpressionAlgorithm& algorithm)
42 {
43 algorithm.Visit(this);
44 }
45
46 void NegativeExpression::Apply(IRegexExpressionAlgorithm& algorithm)
47 {
48 algorithm.Visit(this);
49 }
50
51 void UsingExpression::Apply(IRegexExpressionAlgorithm& algorithm)
52 {
53 algorithm.Visit(this);
54 }
于是我們可以去實現一個IRegexExpressionAlgorithm了。但是事情還沒完。如果每一個算法都要去實現一個IRegexExpressionAlgorithm的話，我們會發現因為算法所需要的參數不同，為了使用Visit這種無參數的函數，我們都需要為每一個具體的Apply實現一次參數的緩存工作。但是因為參數是未知的，而且模板函數又不能是虛函數（所以不能把Expression::Apply寫成模板函數），所以IRegexExpressionAlgorithm的Visit系列函數是沒有參數的。因此一個輔助類就應運而生了。
這個輔助類用來給你很直接地寫具有一個參數的算法。你只要創建它，然后寫完所有的（算法類里面的）Apply函數就行了。那么你怎么在一個表達式上面調用你自己的算法呢？假設參數是p，我們希望只需要簡單地執行Invoke(expression, p)就可以調用到自己了。所以這里實現了一個RegexExpressionAlgorithm<ReturnType, ParameterType>。當然對于ReturnType==void的時候，我們還需要再特化一個，不過這個就不說了：
1 template<typename ReturnType, typename ParameterType=void*>
2 class RegexExpressionAlgorithm : public Object, public IRegexExpressionAlgorithm
3 {
4 private:
5 ReturnType returnValue;
6 void* parameterValue;
7 public:
8
9 ReturnType Invoke(Expression* expression, ParameterType parameter)
10 {
11 parameterValue=(void*)¶meter;
12 expression->Apply(*this);
13 return returnValue;
14 }
15
16 ReturnType Invoke(Expression::Ref expression, ParameterType parameter)
17 {
18 parameterValue=(void*)¶meter;
19 expression->Apply(*this);
20 return returnValue;
21 }
22
23 virtual ReturnType Apply(CharSetExpression* expression, ParameterType parameter)=0;
24 virtual ReturnType Apply(LoopExpression* expression, ParameterType parameter)=0;
25 virtual ReturnType Apply(SequenceExpression* expression, ParameterType parameter)=0;
26 virtual ReturnType Apply(AlternateExpression* expression, ParameterType parameter)=0;
27 virtual ReturnType Apply(BeginExpression* expression, ParameterType parameter)=0;
28 virtual ReturnType Apply(EndExpression* expression, ParameterType parameter)=0;
29 virtual ReturnType Apply(CaptureExpression* expression, ParameterType parameter)=0;
30 virtual ReturnType Apply(MatchExpression* expression, ParameterType parameter)=0;
31 virtual ReturnType Apply(PositiveExpression* expression, ParameterType parameter)=0;
32 virtual ReturnType Apply(NegativeExpression* expression, ParameterType parameter)=0;
33 virtual ReturnType Apply(UsingExpression* expression, ParameterType parameter)=0;
34 public:
35 void Visit(CharSetExpression* expression)
36 {
37 returnValue=Apply(expression, *((ParameterType*)parameterValue));
38 }
39
40 void Visit(LoopExpression* expression)
41 {
42 returnValue=Apply(expression, *((ParameterType*)parameterValue));
43 }
44
45 void Visit(SequenceExpression* expression)
46 {
47 returnValue=Apply(expression, *((ParameterType*)parameterValue));
48 }
49
50 void Visit(AlternateExpression* expression)
51 {
52 returnValue=Apply(expression, *((ParameterType*)parameterValue));
53 }
54
55 void Visit(BeginExpression* expression)
56 {
57 returnValue=Apply(expression, *((ParameterType*)parameterValue));
58 }
59
60 void Visit(EndExpression* expression)
61 {
62 returnValue=Apply(expression, *((ParameterType*)parameterValue));
63 }
64
65 void Visit(CaptureExpression* expression)
66 {
67 returnValue=Apply(expression, *((ParameterType*)parameterValue));
68 }
69
70 void Visit(MatchExpression* expression)
71 {
72 returnValue=Apply(expression, *((ParameterType*)parameterValue));
73 }
74
75 void Visit(PositiveExpression* expression)
76 {
77 returnValue=Apply(expression, *((ParameterType*)parameterValue));
78 }
79
80 void Visit(NegativeExpression* expression)
81 {
82 returnValue=Apply(expression, *((ParameterType*)parameterValue));
83 }
84
85 void Visit(UsingExpression* expression)
86 {
87 returnValue=Apply(expression, *((ParameterType*)parameterValue));
88 }
89 };
好了，讓我們使用它來實現之前提到過的IsEqual功能吧。首先實現一個IsEqualAlgorithm：
1 class IsEqualAlgorithm : public RegexExpressionAlgorithm<bool, Expression*>
2 {
3 public:
4 bool Apply(CharSetExpression* expression, Expression* target)
5 {
6 CharSetExpression* expected=dynamic_cast<CharSetExpression*>(target);
7 if(expected)
8 {
9 if(expression->reverse!=expected->reverse)return false;
10 if(expression->ranges.Count()!=expected->ranges.Count())return false;
11 for(int i=0;i<expression->ranges.Count();i++)
12 {
13 if(expression->ranges[i]!=expected->ranges[i])return false;
14 }
15 return true;
16 }
17 return false;
18 }
19
20 bool Apply(LoopExpression* expression, Expression* target)
21 {
22 LoopExpression* expected=dynamic_cast<LoopExpression*>(target);
23 if(expected)
24 {
25 if(expression->min!=expected->min)return false;
26 if(expression->max!=expected->max)return false;
27 if(!Invoke(expression->expression, expected->expression.Obj()))return false;
28 return true;
29 }
30 return false;
31 }
32
33 bool Apply(SequenceExpression* expression, Expression* target)
34 {
35 SequenceExpression* expected=dynamic_cast<SequenceExpression*>(target);
36 if(expected)
37 {
38 if(!Invoke(expression->left, expected->left.Obj()))return false;
39 if(!Invoke(expression->right, expected->right.Obj()))return false;
40 return true;
41 }
42 return false;
43 }
44
45 bool Apply(AlternateExpression* expression, Expression* target)
46 {
47 AlternateExpression* expected=dynamic_cast<AlternateExpression*>(target);
48 if(expected)
49 {
50 if(!Invoke(expression->left, expected->left.Obj()))return false;
51 if(!Invoke(expression->right, expected->right.Obj()))return false;
52 return true;
53 }
54 return false;
55 }
56
57 bool Apply(BeginExpression* expression, Expression* target)
58 {
59 BeginExpression* expected=dynamic_cast<BeginExpression*>(target);
60 if(expected)
61 {
62 return true;
63 }
64 return false;
65 }
66
67 bool Apply(EndExpression* expression, Expression* target)
68 {
69 EndExpression* expected=dynamic_cast<EndExpression*>(target);
70 if(expected)
71 {
72 return true;
73 }
74 return false;
75 }
76
77 bool Apply(CaptureExpression* expression, Expression* target)
78 {
79 CaptureExpression* expected=dynamic_cast<CaptureExpression*>(target);
80 if(expected)
81 {
82 if(expression->name!=expected->name)return false;
83 if(!Invoke(expression->expression, expected->expression.Obj()))return false;
84 return true;
85 }
86 return false;
87 }
88
89 bool Apply(MatchExpression* expression, Expression* target)
90 {
91 MatchExpression* expected=dynamic_cast<MatchExpression*>(target);
92 if(expected)
93 {
94 if(expression->name!=expected->name)return false;
95 if(expression->index!=expected->index)return false;
96 return true;
97 }
98 return false;
99 }
100
101 bool Apply(PositiveExpression* expression, Expression* target)
102 {
103 PositiveExpression* expected=dynamic_cast<PositiveExpression*>(target);
104 if(expected)
105 {
106 if(!Invoke(expression->expression, expected->expression.Obj()))return false;
107 return true;
108 }
109 return false;
110 }
111
112 bool Apply(NegativeExpression* expression, Expression* target)
113 {
114 NegativeExpression* expected=dynamic_cast<NegativeExpression*>(target);
115 if(expected)
116 {
117 if(!Invoke(expression->expression, expected->expression.Obj()))return false;
118 return true;
119 }
120 return false;
121 }
122
123 bool Apply(UsingExpression* expression, Expression* target)
124 {
125 UsingExpression* expected=dynamic_cast<UsingExpression*>(target);
126 if(expected)
127 {
128 if(expression->name!=expected->name)return false;
129 return true;
130 }
131 return false;
132 }
133 };
譬如看AlternateExpression的IsEqual方法。AlternateExpression跟Expression是否相等只需要通過比較兩個子表達式是否相等即可，于是代碼就變成了：
1 bool Apply(AlternateExpression* expression, Expression* target)
2 {
3 AlternateExpression* expected=dynamic_cast<AlternateExpression*>(target);
4 if(expected)
5 {
6 if(!Invoke(expression->left, expected->left.Obj()))return false;
7 if(!Invoke(expression->right, expected->right.Obj()))return false;
8 return true;
9 }
10 return false;
11 }
如果將AlternateExpression* expression變為AlternateExpression* const this，將Invoke(a, b)換成a->IsEqual(b)，就跟直接寫IsEqual虛函數沒兩樣了。于是自己調用自己還是很方便的。但是我們最終還是想做成a->IsEqual(b)的，于是還要在Expression基類中寫一點：
1 bool Expression::IsEqual(vl::regex_internal::Expression *expression)
2 {
3 IsEqualAlgorithm algorithm;
4 return algorithm.Invoke(this, expression);
5 }
于是IsEqual的實現就結束了。雖然Visitor直接使用會很麻煩，但是我們可以通過稍微的改造一下讓其更好用。當然這里跟Visitor其實還不是完全一致，細節問題就不詳細討論了。至少文章的目標“不通過修改Expression的接口而添加新功能”的目標已經實現了。就結果來講，添加一個新的功能還是很方便的。
posted on 2009-10-17 17:34
陳梓瀚(vczh) 閱讀(2028)
評論(0) 編輯 收藏 引用 所屬分類:
VL++3.0開發紀事