项目实验1：将算法与数据结构分开 - λ-calculus in C++Blogs

项目实验1：将算法与数据结构分开

    现在的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都是有确切的类型的：

    一切都很美好是吧？访问者模式到这里就结束了，但是事情还没完。这里的大部分对象都是有子对象的（区别于子类，说的是都在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*    ErrLostOptR