现在的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) 阅读(2575)
评论(10) 编辑 收藏 引用 所属分类:
脚本技术