現在的OOP都提倡將操作與數據結構結合在一起。為什么這里要提出將算法與數據結構分開呢？第一個原因是一個算法可能是用來處理一組數據結構的。第二個原因是算法并不屬于操作。我們可以借鑒訪問者模式來實現這個分離，但是這里有一個特別之處：我們要將訪問者模式帶給我們的那個接口實現得讓我們
用起來很漂亮。至于實現本身票不漂亮我是不管的，因為這種代碼應該讓電腦來替我們寫。
訪問者模式相信大家都很熟悉了，也被人講爛了，我就不重新教一次了。現在我們面對的問題是這樣的：我們有一組數據結構，這組數據結構是互相使用而且通過繼承關系結合在了一起。典型的譬如一個科學計算器的表達式數據結構，就有函數調用、數字、函數、運算符等不同的數據結構，但肯定繼承與一個類似于『抽象表達式』之類的東西。我這次要實現一個生成使用Syngram的代碼的代碼，于是需要把周邊的數據結構也一并搞定。我想到了一個模式，然后讓代碼生成器本身來使用，借以觀察是否能行。
一份文法的結構從數據結構上來看并不復雜。文法由詞法記號定義以及文法推導式定義組成，其中文法推導式子的表達式又有終結符、連接、分支以及可選等等。譬如下面的一份文法文件（給正在開發的代碼生成器用的）的內容是一種科學計算器的表達式文法。這個文法能夠分析數字、單目操作符、雙目操作符、括號以及函數調用：
1 lexical
2 {
3 num='\d+(.\d+)?'
4 ident='[a-zA-Z_]\w*'
5 plus='\+'
6 minus='\-'
7 mul='\*'
8 div='\\'
9 leftbrace='\('
10 rightbrace='\)'
11 comma=','
12 }
13 rule
14 {
15 factor=num ;
16 factor=[minus] factor ;
17 factor=leftbrace exp rightbrace ;
18 factor=ident[leftbrace param_list rightbrace] ;
19 term=factor ;
20 term=term (mul|div) factor ;
21 exp=term ;
22 exp=exp (plus|minus) term ;
23 param_list=exp [comma param_list] ;
24 program=exp ;
25 }
我們用什么樣的數據結構來記錄這些內容呢？答案并不復雜，做一個基類表示抽象文法樹，其他的都是簡單的結構：
1 /*********************************************************************************************************
2 語法樹
3 *********************************************************************************************************/
4
5 class GrammarAlgorithm;
6
7 class GrammarBase : public VL_Base
8 {
9 public:
10 typedef VL_AutoPtr<GrammarBase> Ptr;
11 typedef VL_List<Ptr , false , GrammarBase*> List;
12
13 virtual void Apply(GrammarAlgorithm* Algorithm)=0;
14 };
15
16 class GrammarBranch : public GrammarBase
17 {
18 public:
19 GrammarBase::List Expressions;
20
21 virtual void Apply(GrammarAlgorithm* Algorithm);
22 };
23
24 class GrammarSequence : public GrammarBase
25 {
26 public:
27 GrammarBase::List Expressions;
28
29 virtual void Apply(GrammarAlgorithm* Algorithm);
30 };
31
32 class GrammarOptional : public GrammarBase
33 {
34 public:
35 GrammarBase::Ptr Expression;
36
37 virtual void Apply(GrammarAlgorithm* Algorithm);
38 };
39
40 class GrammarUnit : public GrammarBase
41 {
42 public:
43 VUnicodeString Name;
44
45 virtual void Apply(GrammarAlgorithm* Algorithm);
46 };
47
48 class GrammarRule : public VL_Base
49 {
50 public:
51 typedef VL_AutoPtr<GrammarRule> Ptr;
52 typedef VL_List<Ptr , false , GrammarRule*> List;
53
54 VUnicodeString Name;
55 GrammarBase::Ptr Expression;
56
57 virtual void Apply(GrammarAlgorithm* Algorithm);
58 };
59
60 class LexicalDecl : public VL_Base
61 {
62 public:
63 typedef VL_AutoPtr<LexicalDecl> Ptr;
64 typedef VL_List<Ptr , false , LexicalDecl*> List;
65
66 VUnicodeString Name;
67 VUnicodeString RegularExpression;
68
69 virtual void Apply(GrammarAlgorithm* Algorithm);
70 };
71
72 class GrammarDescription : public VL_Base
73 {
74 public:
75 typedef VL_AutoPtr<GrammarDescription> Ptr;
76
77 LexicalDecl::List Tokens;
78 GrammarRule::List Rules;
79
80 virtual void Apply(GrammarAlgorithm* Algorithm);
81 };
大家注意到這里有一個GrammarAlgorithm，這個是訪問者模式所帶來的一個接口類。上面一共有7個類是有內容的，其中一部分類的基類GrammarBase是沒有內容的。因此GrammarAlgorithm類就有7個函數，分別用于接收不同對象的Apply函數的調用：
1 /*********************************************************************************************************
2 算法
3 *********************************************************************************************************/
4
5 class GrammarAlgorithm : public VL_Base
6 {
7 public:
8 virtual void Visit(GrammarBranch* Obj)=0;
9 virtual void Visit(GrammarSequence* Obj)=0;
10 virtual void Visit(GrammarOptional* Obj)=0;
11 virtual void Visit(GrammarUnit* Obj)=0;
12 virtual void Visit(GrammarRule* Obj)=0;
13 virtual void Visit(LexicalDecl* Obj)=0;
14 virtual void Visit(GrammarDescription* Obj)=0;
15 };
那么這些Visit函數是如何被調用的呢？這里是重載，重載當然有其好處了，因為子類們的this都是有確切的類型的：
1 /*********************************************************************************************************
2 語法樹
3 *********************************************************************************************************/
4
5 void GrammarBranch::Apply(GrammarAlgorithm* Algorithm)
6 {
7 Algorithm->Visit(this);
8 }
9
10 void GrammarSequence::Apply(GrammarAlgorithm* Algorithm)
11 {
12 Algorithm->Visit(this);
13 }
14
15 void GrammarOptional::Apply(GrammarAlgorithm* Algorithm)
16 {
17 Algorithm->Visit(this);
18 }
19
20 void GrammarUnit::Apply(GrammarAlgorithm* Algorithm)
21 {
22 Algorithm->Visit(this);
23 }
24
25 void GrammarRule::Apply(GrammarAlgorithm* Algorithm)
26 {
27 Algorithm->Visit(this);
28 }
29
30 void LexicalDecl::Apply(GrammarAlgorithm* Algorithm)
31 {
32 Algorithm->Visit(this);
33 }
34
35 void GrammarDescription::Apply(GrammarAlgorithm* Algorithm)
36 {
37 Algorithm->Visit(this);
38 }
一切都很美好是吧？訪問者模式到這里就結束了，但是事情還沒完。這里的大部分對象都是有子對象的（區別于子類，說的是都在Algorithm中出現的類作為了成員變量）。如果我們的算法需要有其他參數和返回結果，難道繼承一個Algorithm之后加一堆參數和返回值用的成員變量，然后每次調用前填好，SomeObj->Visit(Algorithm);，然后獲取返回值變量？這當然是在這個Algorithm中唯一的辦法，但是我們這么寫的話，代碼是很亂七八糟的，也不好維護。因此我們可以在不破壞已經存在的代碼的基礎上，添加新的Algorithm工具。
想象一下，如果我們要從上面這棵樹構造出一個字符串來，我們是需要遞歸很多次的。為了遞歸我們不得不將算法對象自己放到別的對象里面去Apply。如果我們可以result=obj->apply(this,parameters);就好了。不過話說回來，我們是不能動數據結構的代碼的。因為如果我們這樣做的話就白白破壞了訪問者模式所帶來的好處了。但是每一個算法的參數和返回值都是不同的。怎么辦呢？用C++的話，答案很清楚，就是模板類。
參數的個數我們不用考慮，多了的話我們可以用一個struct去解決。好了，現在我們得到了一個新的算法類的大概外觀：
template<typename _ResultType , typename _ParamType>
class NewAlgorithm : public GrammarAlgorithm{...};
這個NewAlgorithm肯定也要有自己的一組帶有返回結果和參數的Visit函數族了。于是我們可以在原來的Visit函數族里面做返回值和參數的間接處理，當然還是用成員變量最簡單了。不過為了保護，我們將繼承修改為private，然后用一個隱式轉換來得到GrammarAlgorithm的指針類型：
1 template<typename _ReturnType , typename _ParamType=void*>
2 class GrammarAlgorithmEx : private GrammarAlgorithm
3 {
4 private:
5 _ReturnType FReturnData;
6 _ParamType FParamData;
7
8 void Visit(GrammarBranch* Obj)
9 {
10 FReturnData=Visit(Obj,FParamData);
11 }
12
13 void Visit(GrammarSequence* Obj)
14 {
15 FReturnData=Visit(Obj,FParamData);
16 }
17
18 void Visit(GrammarOptional* Obj)
19 {
20 FReturnData=Visit(Obj,FParamData);
21 }
22
23 void Visit(GrammarUnit* Obj)
24 {
25 FReturnData=Visit(Obj,FParamData);
26 }
27
28 void Visit(GrammarRule* Obj)
29 {
30 FReturnData=Visit(Obj,FParamData);
31 }
32
33 void Visit(LexicalDecl* Obj)
34 {
35 FReturnData=Visit(Obj,FParamData);
36 }
37
38 void Visit(GrammarDescription* Obj)
39 {
40 FReturnData=Visit(Obj,FParamData);
41 }
42
43 operator GrammarAlgorithm*()
44 {
45 return this;
46 }
47 public:
48 template<typename _ObjectType>
49 _ReturnType Apply(_ObjectType* Obj , _ParamType ParamData)
50 {
51 FParamData=ParamData;
52 Obj->Apply(*this);
53 return FReturnData;
54 }
55
56 template<typename _ObjectType>
57 _ReturnType Apply(VL_AutoPtr<_ObjectType> Obj , _ParamType ParamData)
58 {
59 FParamData=ParamData;
60 Obj->Apply(*this);
61 return FReturnData;
62 }
63 public:
64 virtual _ReturnType Visit(GrammarBranch* Obj , _ParamType ParamData)=0;
65 virtual _ReturnType Visit(GrammarSequence* Obj , _ParamType ParamData)=0;
66 virtual _ReturnType Visit(GrammarOptional* Obj , _ParamType ParamData)=0;
67 virtual _ReturnType Visit(GrammarUnit* Obj , _ParamType ParamData)=0;
68 virtual _ReturnType Visit(GrammarRule* Obj , _ParamType ParamData)=0;
69 virtual _ReturnType Visit(LexicalDecl* Obj , _ParamType ParamData)=0;
70 virtual _ReturnType Visit(GrammarDescription* Obj , _ParamType ParamData)=0;
71 };
注意到我們也有自己的Apply函數吧。這個函數就是新的Algorithm的關鍵。我們可以隨便來一個什么對象就result=Apply(obj,parameters);，然后Apply填好參數，調用obj->Apply(*this);。這里*this調用operator GrammarAlgorithm*()得到需要的類型，然后由obj自己發配到原來的Visit上。原來的Visit填好返回值，Apply返回，調用成功！
當然，現在解決了Algorithm內部的調用問題。那么外部怎么辦呢？其實也要用Apply，不過我們需要創建對象。我們可以使用代碼result=YourAlgorithm().Apply(obj,parameters);來做到這件事情。這一來一回雖然不是一個好看的辦法，但是只要好用就好了。因為Algorithm將來是生成的，不需要人寫。
虛函數所帶來的好處就被這個新的Algorithm解決了。現在拿到一個非常復雜的充滿了繼承的數據結構也不用怕了。我們可以不破壞原有的代碼，建立起自己的“虛函數”了。說到這里，我來用一用這個Algorithm。我將文法文件讀入GrammarDescription之后，用一個算法對象來將結果轉換為字符串：
1 class GrammarToString : public GrammarAlgorithmEx<VUnicodeString , VUnicodeString>
2 {
3 public:
4 VUnicodeString Visit(GrammarBranch* Obj , VUnicodeString Prefix);
5 VUnicodeString Visit(GrammarSequence* Obj , VUnicodeString Prefix);
6 VUnicodeString Visit(GrammarOptional* Obj , VUnicodeString Prefix);
7 VUnicodeString Visit(GrammarUnit* Obj , VUnicodeString Prefix);
8 VUnicodeString Visit(GrammarRule* Obj , VUnicodeString Prefix);
9 VUnicodeString Visit(LexicalDecl* Obj , VUnicodeString Prefix);
10 VUnicodeString Visit(GrammarDescription* Obj , VUnicodeString Prefix);
11 };
12
13 /*********************************************************************************************************
14 GrammarToString
15 *********************************************************************************************************/
16
17 VUnicodeString GrammarToString::Visit(GrammarBranch* Obj , VUnicodeString Prefix)
18 {
19 VUnicodeString Result;
20 Result+=Prefix+L"branch {\r\n";
21 for(VInt i=0;i<Obj->Expressions.GetCount();i++)
22 {
23 Result+=Apply(Obj->Expressions[i],Prefix+L" ");
24 }
25 Result+=Prefix+L"}\r\n";
26 return Result;
27 }
28
29 VUnicodeString GrammarToString::Visit(GrammarSequence* Obj , VUnicodeString Prefix)
30 {
31 VUnicodeString Result;
32 Result+=Prefix+L"sequence {\r\n";
33 for(VInt i=0;i<Obj->Expressions.GetCount();i++)
34 {
35 Result+=Apply(Obj->Expressions[i],Prefix+L" ");
36 }
37 Result+=Prefix+L"}\r\n";
38 return Result;
39 }
40
41 VUnicodeString GrammarToString::Visit(GrammarOptional* Obj , VUnicodeString Prefix)
42 {
43 VUnicodeString Result;
44 Result+=Prefix+L"optional {\r\n";
45 Result+=Apply(Obj->Expression,Prefix+L" ");
46 Result+=Prefix+L"}\r\n";
47 return Result;
48 }
49
50 VUnicodeString GrammarToString::Visit(GrammarUnit* Obj , VUnicodeString Prefix)
51 {
52 return Prefix+Obj->Name+L"\r\n";
53 }
54
55 VUnicodeString GrammarToString::Visit(GrammarRule* Obj , VUnicodeString Prefix)
56 {
57 VUnicodeString Result;
58 Result+=Prefix+L"rule {\r\n";
59 Result+=Prefix+L" "+Obj->Name+L"\r\n";
60 Result+=Apply(Obj->Expression,Prefix+L" ");
61 Result+=Prefix+L"}\r\n";
62 return Result;
63 }
64
65 VUnicodeString GrammarToString::Visit(LexicalDecl* Obj , VUnicodeString Prefix)
66 {
67 VUnicodeString Result;
68 Result+=Prefix+L"lexical inference {\r\n";
69 Result+=Prefix+L" "+Obj->Name+L"\r\n";
70 Result+=Prefix+L" "+Obj->RegularExpression+L"\r\n";
71 Result+=Prefix+L"}\r\n";
72 return Result;
73 }
74
75 VUnicodeString GrammarToString::Visit(GrammarDescription* Obj , VUnicodeString Prefix)
76 {
77 VUnicodeString Result;
78 Result+=Prefix+L"lexical inferences {\r\n";
79 for(VInt i=0;i<Obj->Tokens.GetCount();i++)
80 {
81 Result+=Apply(Obj->Tokens[i],Prefix+L" ");
82 }
83 Result+=Prefix+L"}\r\n";
84 Result+=Prefix+L"syntax inferences {\r\n";
85 for(VInt i=0;i<Obj->Rules.GetCount();i++)
86 {
87 Result+=Apply(Obj->Rules[i],Prefix+L" ");
88 }
89 Result+=Prefix+L"}\r\n";
90 return Result;
91 }
看看結果吧！
1 lexical inferences {
2 lexical inference {
3 num
4 '\d+(.\d+)?'
5 }
6 lexical inference {
7 ident
8 '[a-zA-Z_]\w*'
9 }
10 lexical inference {
11 plus
12 '\+'
13 }
14 lexical inference {
15 minus
16 '\-'
17 }
18 lexical inference {
19 mul
20 '\*'
21 }
22 lexical inference {
23 div
24 '\\'
25 }
26 lexical inference {
27 leftbrace
28 '\('
29 }
30 lexical inference {
31 rightbrace
32 '\)'
33 }
34 lexical inference {
35 comma
36 ','
37 }
38 }
39 syntax inferences {
40 rule {
41 factor
42 num
43 }
44 rule {
45 factor
46 sequence {
47 optional {
48 minus
49 }
50 factor
51 }
52 }
53 rule {
54 factor
55 sequence {
56 leftbrace
57 exp
58 rightbrace
59 }
60 }
61 rule {
62 factor
63 sequence {
64 ident
65 optional {
66 sequence {
67 leftbrace
68 param_list
69 rightbrace
70 }
71 }
72 }
73 }
74 rule {
75 term
76 factor
77 }
78 rule {
79 term
80 sequence {
81 term
82 branch {
83 mul
84 div
85 }
86 factor
87 }
88 }
89 rule {
90 exp
91 term
92 }
93 rule {
94 exp
95 sequence {
96 exp
97 branch {
98 plus
99 minus
100 }
101 term
102 }
103 }
104 rule {
105 param_list
106 sequence {
107 exp
108 optional {
109 sequence {
110 comma
111 param_list
112 }
113 }
114 }
115 }
116 rule {
117 program
118 exp
119 }
120 }
至于分析器本身是怎么寫的呢？用了Vczh牌Syngram，一切都很美好。我只要把文法文件本身需要遵守的文法寫進C++，那么我就有了一個分析器了。能處理左遞歸的哦，跟某些受人崇拜的C++庫不一樣。
1 class InnerProvider : public VL_Base
2 {
3 public:
4 CompreSyner Syner;
5 GrammarProvider* Provider;
6
7 InnerProvider(GrammarProvider* aProvider):Syner(true)
8 {
9 Provider=aProvider;
10 Syner.AddLexicalErrorHandler(LexicalError_Handler);
11 Syner.SetUnexpectedEndOfFileHandler(SyntaxEOF_Handler);
12 Syner.SetDefaultHandler(SyntaxDefault_Handler);
13 Syner.SetLexicalData(Provider);
14 Syner.SetSemanticData(Provider);
15 Syner.SetErrorData(Provider);
16 Syner.Discard(L"\\s");
17
18 VSynTerm _Lexical = Syner.Token(L"\"lexical\"" ,L"lexical" );
19 VSynTerm _Rule = Syner.Token(L"\"rule\"" ,L"rule" );
20 VSynTerm Id = Syner.Token(L"<ID>" ,L"[a-zA-Z_]\\w*" );
21 VSynTerm Regex = Syner.Token(L"<REGEX>" ,L"\'(\'\'|[^\'])*\'" );
22 VSynTerm Infer = Syner.Token(L"\"=\"" ,L"=" );
23 VSynTerm Or = Syner.Token(L"\"|\"" ,L"\\|" );
24 VSynTerm OptLeft = Syner.Token(L"\"[\"" ,L"\\[" );
25 VSynTerm OptRight = Syner.Token(L"\"]\"" ,L"\\]" );
26 VSynTerm DeclLeft = Syner.Token(L"\"{\"" ,L"\\{" );
27 VSynTerm DeclRight = Syner.Token(L"\"}\"" ,L"\\}" );
28 VSynTerm ExpLeft = Syner.Token(L"\"(\"" ,L"\\(" );
29 VSynTerm ExpRight = Syner.Token(L"\")\"" ,L"\\)" );
30 VSynTerm Semicolon = Syner.Token(L"\";\"" ,L";" );
31
32 VSynTerm Name = Syner.Rule(L"Name");
33 VSynTerm LexInfer = Syner.Rule(L"Lexical");
34 VSynTerm RuleUnit = Syner.Rule(L"RuleUnit");
35 VSynTerm RuleSeq = Syner.Rule(L"RuleSeq");
36 VSynTerm RuleExp = Syner.Rule(L"RuleExp");
37 VSynTerm RuleInfer = Syner.Rule(L"Rule");
38 VSynTerm LexList = Syner.Rule(L"LexList");
39 VSynTerm RuleList = Syner.Rule(L"RuleList");
40 VSynTerm Program = Syner.Rule(L"Program");
41
42 IVL_ErrorHandler* ErrLostInfer = Syner.Err(LostInfer_Handler);
43 IVL_ErrorHandler* ErrLostRegex = Syner.Err(LostRegex_Handler);
44 IVL_ErrorHandler* ErrLostRule = Syner.Err(LostRule_Handler);
45 IVL_ErrorHandler* ErrLostOptRight = Syner.Err(LostOptRight_Handler);
46 IVL_ErrorHandler* ErrLostExpRight = Syner.Err(LostExpRight_Handler);
47 IVL_ErrorHandler* ErrLostDeclLeft = Syner.Err(LostDeclLeft_Handler);
48 IVL_ErrorHandler* ErrLostDeclRight = Syner.Err(LostDeclRight_Handler);
49 IVL_ErrorHandler* ErrLostSemicolon = Syner.Err(LostSemicolon_Handler);
50 IVL_ErrorHandler* ErrLostLexList = Syner.Err(LostLexList_Handler);
51 IVL_ErrorHandler* ErrLostRuleList = Syner.Err(LostRuleList_Handler);
52
53 Syner.Infer(Name_Handler, Name) = Id[0] | _Lexical[0] | _Rule[0];
54 Syner.Infer(LexInfer_Handler, LexInfer) = Name[0] + Infer[ErrLostInfer] + Regex[1][ErrLostRegex];
55 Syner.Infer(RuleUnit_Handler, RuleUnit) = Name[0];
56 Syner.Infer(Copy_Handler, RuleUnit) = ExpLeft + RuleExp[0][ErrLostRule] + ExpRight[ErrLostExpRight];
57 Syner.Infer(RuleOpt_Handler, RuleUnit) = OptLeft + RuleExp[0][ErrLostRule] + OptRight[ErrLostOptRight];
58 Syner.Infer(RuleSeq_Handler, RuleSeq) = RuleUnit[1] + Opt(RuleSeq[0]);
59 Syner.Infer(RuleExp_Handler, RuleExp) = RuleSeq[1] + Opt(Or + RuleExp[0]);
60 Syner.Infer(RuleInfer_Handler, RuleInfer) = Name[0] + Infer[ErrLostInfer] + RuleExp[1][ErrLostRule] + Semicolon[ErrLostSemicolon];
61 Syner.Infer(LexList_Handler, LexList) = LexInfer[1] + Opt(LexList[0]);
62 Syner.Infer(RuleList_Handler, RuleList) = RuleInfer[1] + Opt(RuleList[0]);
63
64 Syner.Infer(Program_Handler, Program) = _Lexical[ErrLostLexList] +
65 DeclLeft[ErrLostDeclLeft] +
66 LexList[0][ErrLostLexList] +
67 DeclRight[ErrLostDeclRight] +
68
69 _Rule[ErrLostRuleList] +
70 DeclLeft[ErrLostDeclLeft] +
71 RuleList[1][ErrLostRuleList] +
72 DeclRight[ErrLostDeclRight];
73
74 Syner.Initialize(Program);
75 }
76
77 ~InnerProvider()
78 {
79 }
80
81 GrammarDescription::Ptr Parse(VUnicodeString Code)
82 {
83 VL_SynMacInsListList Results;
84 VL_SynTokenErrorList Errors;
85 Provider->GetErrors().Clear();
86 Syner.Parse(Code,Results,Errors);
87
88 for(VInt i=0;i<Errors.GetCount();i++)
89 {
90 CompreSyner::TokenData& TokenData=Syner.GetLexicalResult()->GetDataOfPosition(Errors[i].Position);
91 if(&TokenData)
92 {
93 Provider->GetErrors().Add(Convert(TokenData,Errors[i].Message));
94 }
95 else
96 {
97 GrammarError Error;
98 Error.LineInFile=-1;
99 Error.PosInFile=-1;
100 Error.PosInLine=-1;
101 Provider->GetErrors().Add(Error);
102 }
103 }
104
105 if(Provider->GetErrors().GetCount())
106 {
107 return 0;
108 }
109 else
110 {
111 return Syner.Transform(Results[0]);
112 }
113 }
114 };
115 }
posted on 2008-09-02 04:43
陳梓瀚(vczh) 閱讀(2639)
評論(10) 編輯 收藏 引用 所屬分類:
腳本技術