我们知道Yacc和Bison都是产生C++的代码作为编译器的前端的。但是有时候我们需要动态地产生一个编译器前端，极端一点讲，譬如“文法调试器”。调试器总不能动态生成.y文件，让yacc编译，让gcc再度编译，然后execute，最后将程序的输出结果读进来。这样就太麻烦了，于是我们需要重新写一个生成编译器前端的程序。
趁着今天有空，我写了一段代码用来测试Syngram是否能很好的动态生成语法分析器。Syngram设计的初衷是让C++可以直接写文法，不过通过今天的实验发现Syngram也是可以很好的处理动态输入的东西的，譬如说动态的文法、动态的错误处理程序以及动态的语义处理函数等等。作为一个编译器生成器的实验，能否处理Syngram所有的结果是一件很值得注意的事情。
这个程序仍然使用了上一篇文章所描述的
Algorithm架构来处理文法。程序读入两个文件，一个是文法描述文件，另一个是被这个文法处理的字符串文件。程序使用Syngram处理第一个文件，将文件内容动态转换为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 discard='\s+'
13 }
14 rule
15 {
16 factor=num ;
17 factor=[minus] factor ;
18 factor=leftbrace exp rightbrace ;
19 factor=ident[leftbrace param_list rightbrace] ;
20 term=factor ;
21 term=term (mul|div) factor ;
22 exp=term ;
23 exp=exp (plus|minus) term ;
24 param_list=exp [comma param_list] ;
25 program=exp ;
26 }
如果我们把factor=leftbrace exp rightbrace修改为factor=leftbrace | exp | rightbrace的话，由于出现了exp->term->factor->exp的无效循环引用，Syngram会报告文法的错误：
1 规则<factor>存在长度为3的间接左递归。
2 规则<exp>存在长度为3的间接左递归。
3 规则<term>存在长度为3的间接左递归。
4 规则<program>[0]不能产生字符串。
5 规则<exp>[0]不能产生字符串。
6 规则<exp>[1]不能产生字符串。
7 规则<param_list>[0]不能产生字符串。
8 规则<term>[0]不能产生字符串。
9 规则<term>[1]不能产生字符串。
10
<term>[0]的意思是term的第1条推导式子。
好了，现在我们让他读入一个表达式来进行测试：
1 (1+sin(2))**(sin(log(2,3))+4)
这个表达式明显是错误的，因为中间有两个乘号。于是Syngram就会报告错误：
1 --------------------------------------------------------------------------------
2 (1+sin(2))**(sin(log(2,3))+4)
3 --------------------------------------------------------------------------------
4 遭遇第9个记号，类型5，状态<term>[1] = term[0] ( mul[1] | div[2] )* factor[3] 。
第9个记号指的就是第二个乘号了。因为(1+sin(2))是一个factor，factor是一个term，因此term=term (*|/) factor走到了factor那里发现输入的竟然是乘号，于是报错。
好了。我们把其中一个乘号去掉，现在Syngram就会给出分析的结果了：
1 --------------------------------------------------------------------------------
2 (1+sin(2))*(sin(log(2,3))+4)
3 --------------------------------------------------------------------------------
4 program = {
5 exp = {
6 term = {
7 term = {
8 factor = {
9 leftbrace = (
10 exp = {
11 exp = {
12 term = {
13 factor = {
14 num = 1
15 }
16 }
17 }
18 plus = +
19 term = {
20 factor = {
21 ident = sin
22 leftbrace = (
23 param_list = {
24 exp = {
25 term = {
26 factor = {
27 num = 2
28 }
29 }
30 }
31 }
32 rightbrace = )
33 }
34 }
35 }
36 rightbrace = )
37 }
38 }
39 mul = *
40 factor = {
41 leftbrace = (
42 exp = {
43 exp = {
44 term = {
45 factor = {
46 ident = sin
47 leftbrace = (
48 param_list = {
49 exp = {
50 term = {
51 factor = {
52 ident = log
53 leftbrace = (
54 param_list = {
55 exp = {
56 term = {
57 factor = {
58 num = 2
59 }
60 }
61 }
62 comma = ,
63 param_list = {
64 exp = {
65 term = {
66 factor = {
67 num = 3
68 }
69 }
70 }
71 }
72 }
73 rightbrace = )
74 }
75 }
76 }
77 }
78 rightbrace = )
79 }
80 }
81 }
82 plus = +
83 term = {
84 factor = {
85 num = 4
86 }
87 }
88 }
89 rightbrace = )
90 }
91 }
92 }
93 }
94
东西这么长是因为一个数字"1"要经过exp->term->factor->num来到达。这里表示的仅仅是文法的推导过程，实际的文法经常使用一组继承的数据结构来消除这些多余的数据，譬如说表达式类ExpressionBase的子类经常会出现NumberExpression、BinaryOperatorExpression、MethodInvokeExpression等等。这些结构消除的就是【一个数字"1"要经过exp->term->factor->num来到达】这种类型的复杂度了。
现在给出程序的代码。一部分代码已经在上一篇文章中提供了。首先是main函数：
1 #include "..\..\..\Library\Platform\VL_Console.h"
2 #include "..\..\..\Library\Data\VL_Stream.h"
3 #include "..\..\..\Library\Data\VL_System.h"
4 #include "..\Utility\GrammarTree.h"
5 #include "..\Utility\GrammarAlgorithms.h"
6
7 using namespace vl;
8 using namespace vl::platform;
9 using namespace vl::stream;
10 using namespace vl::system;
11 using namespace compiler;
12
13 void vlmain(VL_Console& Con)
14 {
15 Con.SetTitle(L"Compile Syntax/Semantic Builder");
16 Con.SetTestMemoryLeaks(true);
17 Con.SetPauseOnExit(true);
18
19 VUnicodeString TestDataPath=VFileName(Con.GetAppPath()).MakeAbsolute(L"..\\TestData\\").GetStrW();
20 VUnicodeString GrammarText;
21 VL_TextInput(new VL_FileInputStream(TestDataPath+L"计算器文法.txt"),true,vceBOM).Read(GrammarText);
22
23 GrammarProvider Provider;
24 GrammarDescription::Ptr gd=Provider.Parse(GrammarText);
25 if(Provider.GetErrors().GetCount()==0)
26 {
27 {
28 GrammarValidateParam ValidateParam;
29 ValidateParam.Structure=new GrammarStructure;
30 if(!GrammarValidate().Apply(gd,ValidateParam))
31 {
32 for(VInt i=0;i<ValidateParam.Structure->Errors.GetCount();i++)
33 {
34 GrammarValidateError Error=ValidateParam.Structure->Errors[i];
35 VUnicodeString Line;
36 if(Error.TokenError)
37 {
38 Line+=L"词法错误，";
39 }
40 else if(Error.RuleError)
41 {
42 Line+=L"文法错误，";
43 }
44 else
45 {
46 Line+=L"未知错误，";
47 }
48 Line+=L"位置：第"+VUnicodeString(Error.Index)+L"个定义，";
49 Line+=Error.Message;
50 Con.Write(Line+L"\r\n");
51 }
52 return;
53 }
54 }
55 GrammarSimulateParam SimulateParam;
56 {
57 SimulateParam.Simulator=new GrammarSimulator;
58 GrammarSimulate Algorithm;
59 Algorithm.Apply(gd,&SimulateParam);
60 if(SimulateParam.ErrorMessages.GetCount())
61 {
62 for(VInt i=0;i<SimulateParam.ErrorMessages.GetCount();i++)
63 {
64 Con.Write(SimulateParam.ErrorMessages[i]+L"\r\n");
65 }
66 return;
67 }
68 }
69 {
70 Con.Write(GrammarToCode().Apply(gd,L""));
71 Con.Write(L"--------------------------------------------------------------------------------");
72 VUnicodeString InputExpression=L"";
73 VL_TextInput(new VL_FileInputStream(TestDataPath+L"计算器表达式.txt"),true,vceBOM).Read(InputExpression);
74 Con.Write(InputExpression+L"\r\n");
75 VL_LexerFactoryPtr LexerResult;
76 GrammarSimulatorNode::List SynerResult;
77 SimulateParam.Simulator->Parse(InputExpression,LexerResult,SynerResult);
78 if(SimulateParam.Simulator->ParseErrors.GetCount())
79 {
80 Con.Write(L"--------------------------------------------------------------------------------");
81 for(VInt i=0;i<SimulateParam.Simulator->ParseErrors.GetCount();i++)
82 {
83 Con.Write(SimulateParam.Simulator->ParseErrors[i].Message+L"\r\n");
84 }
85 }
86 for(VInt i=0;i<SynerResult.GetCount();i++)
87 {
88 Con.Write(L"--------------------------------------------------------------------------------");
89 Con.Write(SynerResult[i]->ToString(L""));
90 }
91 }
92 }
93 else
94 {
95 for(VInt i=0;i<Provider.GetErrors().GetCount();i++)
96 {
97 Con.Write(Provider.GetErrors()[i].Message+L"\r\n");
98 }
99 }
100 }
其次是四个算法，分别用于将文法的语法树转换为字符串、将语法树转换为文法文件的字符串、检查文法依赖关系以及检查文法的逻辑关系。这同时证明了上一篇文章的Algorithm架构是可以在心理上帮助程序员写出独立性较强的算法的，大大降低了维护的难度。
头文件：
1 #ifndef GRAMMARALGORITHM
2 #define GRAMMARALGORITHM
3
4 #include "GrammarTree.h"
5 #include "..\..\..\Library\Data\Data\VL_Data_Map.h"
6 #include "..\..\..\Library\Data\Grammar2\VL_SynTools.h"
7
8 namespace compiler
9 {
10 using namespace grammar;
11
12 class GrammarValidateError : public VL_Base
13 {
14 public:
15 typedef VL_List<GrammarValidateError , false> List;
16
17 VBool TokenError;
18 VBool RuleError;
19 VInt Index;
20 VUnicodeString Message;
21 };
22
23 /*********************************************************************************************************
24 GrammarToString
25 *********************************************************************************************************/
26
27 class GrammarToString : public GrammarAlgorithmEx<VUnicodeString , VUnicodeString>
28 {
29 public:
30 VUnicodeString Visit(GrammarBranch* Obj , VUnicodeString Prefix);
31 VUnicodeString Visit(GrammarSequence* Obj , VUnicodeString Prefix);
32 VUnicodeString Visit(GrammarOptional* Obj , VUnicodeString Prefix);
33 VUnicodeString Visit(GrammarUnit* Obj , VUnicodeString Prefix);
34 VUnicodeString Visit(GrammarRule* Obj , VUnicodeString Prefix);
35 VUnicodeString Visit(LexicalDecl* Obj , VUnicodeString Prefix);
36 VUnicodeString Visit(GrammarDescription* Obj , VUnicodeString Prefix);
37 };
38
39 /*********************************************************************************************************
40 GrammarToCode
41 *********************************************************************************************************/
42
43 class GrammarToCode : public GrammarAlgorithmEx<VUnicodeString , VUnicodeString>
44 {
45 public:
46 VUnicodeString Visit(GrammarBranch* Obj , VUnicodeString Prefix);
47 VUnicodeString Visit(GrammarSequence* Obj , VUnicodeString Prefix);
48 VUnicodeString Visit(GrammarOptional* Obj , VUnicodeString Prefix);
49 VUnicodeString Visit(GrammarUnit* Obj , VUnicodeString Prefix);
50 VUnicodeString Visit(GrammarRule* Obj , VUnicodeString Prefix);
51 VUnicodeString Visit(LexicalDecl* Obj , VUnicodeString Prefix);
52 VUnicodeString Visit(GrammarDescription* Obj , VUnicodeString Prefix);
53 };
54
55 /*********************************************************************************************************
56 GrammarValidate
57 *********************************************************************************************************/
58
59 class GrammarStructure : public VL_Base
60 {
61 public:
62 typedef VL_ListedMap<VUnicodeString , VL_AutoPtr<VL_List<VInt , true>>> _MultiIntMap;
63 typedef VL_ListedMap<VUnicodeString , VInt> _IntMap;
64 public:
65 _IntMap Tokens;
66 _MultiIntMap Rules;
67 GrammarValidateError::List Errors;
68 };
69 class GrammarValidateParam : public VL_Base
70 {
71 public:
72 VL_AutoPtr<GrammarStructure> Structure;
73 VInt Index;
74 };
75 class GrammarValidate : public GrammarAlgorithmEx<VBool , GrammarValidateParam>
76 {
77 public:
78 VBool Visit(GrammarBranch* Obj , GrammarValidateParam Param);
79 VBool Visit(GrammarSequence* Obj , GrammarValidateParam Param);
80 VBool Visit(GrammarOptional* Obj , GrammarValidateParam Param);
81 VBool Visit(GrammarUnit* Obj , GrammarValidateParam Param);
82 VBool Visit(GrammarRule* Obj , GrammarValidateParam Param);
83 VBool Visit(LexicalDecl* Obj , GrammarValidateParam Param);
84 VBool Visit(GrammarDescription* Obj , GrammarValidateParam Param);
85 };
86
87 /*********************************************************************************************************
88 GrammarSimulate
89 *********************************************************************************************************/
90
91 class GrammarSimulatorNode : public VL_Base
92 {
93 public:
94 typedef VL_AutoPtr<GrammarSimulatorNode> Ptr;
95 typedef VL_List<Ptr , false , GrammarSimulatorNode*> List;
96
97 VUnicodeString TerminatorName;
98 VUnicodeString Value;
99 List SubExpressions;
100
101 VUnicodeString ToString(VUnicodeString Prefix);
102 };
103 class GrammarSimulator : public VL_Base
104 {
105 public:
106 typedef VL_SynRuleHandler<GrammarSimulatorNode::Ptr> RuleTransformer;
107 typedef RuleTransformer::Handler RuleHandler;
108 typedef VL_List<VL_AutoPtr<RuleHandler> , false , RuleHandler*> RuleHandlerList;
109 typedef VL_ListedMap<VInt , VUnicodeString> TokenIDMap;
110 public:
111 typedef VL_AutoPtr<GrammarSimulator> Ptr;
112 typedef VL_AutoPtr<VL_LexerHandler> LexerHandler;
113
114 VL_Lexer Lexer;
115 VL_Syner Syner;
116 RuleTransformer Transformer;
117 RuleHandlerList Handlers;
118 TokenIDMap TokenIDs;
119 GrammarError::List ParseErrors;
120 LexerHandler LexerErrorHandler;
121
122 GrammarSimulator();
123
124 VInt Parse(VUnicodeString Input , VL_LexerFactoryPtr& LexerResult , GrammarSimulatorNode::List& Result);
125 };
126 class GrammarSimulateParam : public VL_Base
127 {
128 typedef VL_ListedMap<VUnicodeString , VSynTerm> TermMap;
129 typedef VL_List<VUnicodeString , false> StringList;
130 public:
131 GrammarSimulator::Ptr Simulator;
132 TermMap Terms;
133 VInt UsedStorageIndex;
134 StringList ErrorMessages;
135 };
136 class GrammarSimulate : public GrammarAlgorithmEx<VSynTerm , GrammarSimulateParam*>
137 {
138
139 VSynTerm Visit(GrammarBranch* Obj , GrammarSimulateParam* Param);
140 VSynTerm Visit(GrammarSequence* Obj , GrammarSimulateParam* Param);
141 VSynTerm Visit(GrammarOptional* Obj , GrammarSimulateParam* Param);
142 VSynTerm Visit(GrammarUnit* Obj , GrammarSimulateParam* Param);
143 VSynTerm Visit(GrammarRule* Obj , GrammarSimulateParam* Param);
144 VSynTerm Visit(LexicalDecl* Obj , GrammarSimulateParam* Param);
145 VSynTerm Visit(GrammarDescription* Obj , GrammarSimulateParam* Param);
146 };
147 }
148
149 #endif
实现：
1 #include "GrammarAlgorithms.h"
2 #include "..\..\..\Library\Data\Grammar2\VL_Regexp.h"
3
4 using namespace vl::grammar;
5
6 namespace compiler
7 {
8
9 /*********************************************************************************************************
10 GrammarToString
11 *********************************************************************************************************/
12
13 VUnicodeString GrammarToString::Visit(GrammarBranch* Obj , VUnicodeString Prefix)
14 {
15 VUnicodeString Result;
16 Result+=Prefix+L"branch {\r\n";
17 for(VInt i=0;i<Obj->Expressions.GetCount();i++)
18 {
19 Result+=Apply(Obj->Expressions[i],Prefix+L" ");
20 }
21 Result+=Prefix+L"}\r\n";
22 return Result;
23 }
24
25 VUnicodeString GrammarToString::Visit(GrammarSequence* Obj , VUnicodeString Prefix)
26 {
27 VUnicodeString Result;
28 Result+=Prefix+L"sequence {\r\n";
29 for(VInt i=0;i<Obj->Expressions.GetCount();i++)
30 {
31 Result+=Apply(Obj->Expressions[i],Prefix+L" ");
32 }
33 Result+=Prefix+L"}\r\n";
34 return Result;
35 }
36
37 VUnicodeString GrammarToString::Visit(GrammarOptional* Obj , VUnicodeString Prefix)
38 {
39 VUnicodeString Result;
40 Result+=Prefix+L"optional {\r\n";
41 Result+=Apply(Obj->Expression,Prefix+L" ");
42 Result+=Prefix+L"}\r\n";
43 return Result;
44 }
45
46 VUnicodeString GrammarToString::Visit(GrammarUnit* Obj , VUnicodeString Prefix)
47 {
48 return Prefix+Obj->Name+L"\r\n";
49 }
50
51 VUnicodeString GrammarToString::Visit(GrammarRule* Obj , VUnicodeString Prefix)
52 {
53 VUnicodeString Result;
54 Result+=Prefix+L"rule {\r\n";
55 Result+=Prefix+L" "+Obj->Name+L"\r\n";
56 Result+=Apply(Obj->Expression,Prefix+L" ");
57 Result+=Prefix+L"}\r\n";
58 return Result;
59 }
60
61 VUnicodeString GrammarToString::Visit(LexicalDecl* Obj , VUnicodeString Prefix)
62 {
63 VUnicodeString Result;
64 Result+=Prefix+L"lexical inference {\r\n";
65 Result+=Prefix+L" "+Obj->Name+L"\r\n";
66 Result+=Prefix+L" "+Obj->ProcessedRegex+L"\r\n";
67 Result+=Prefix+L"}\r\n";
68 return Result;
69 }
70
71 VUnicodeString GrammarToString::Visit(GrammarDescription* Obj , VUnicodeString Prefix)
72 {
73