今天在测试封装在FreeScript内的正则表达式接口的时候发现了一个垃圾收集器的Bug，不过很容易就看出来了，于是立刻fix掉。出错的原因在于垃圾收集的时候只标记了运算堆栈的内容，忘了标记调用堆栈的内容。
这个新的Syngram包含了三个工具，分别是正则表达式、词法分析器和语法分析器。
正则表达式分纯、安全和贪婪三种。纯正则表达式仅仅用于匹配，速度非常快（以前的测试表明一秒钟可以匹配44万次），但是没有预查和捕获等功能。安全和贪婪两种正则表达式则是通过不同的搜索方法来匹配字符串的内容，虽然慢了一点，不过有了预查和捕获等功能。
之前的文章有提到过关于一个少回溯多捕获的测试用例下的速度。安全分析法回溯将会占用很多时间，而贪婪分析法则回溯基本是没什么消耗的。
词法分析器则可以输入不同的正则表达式，然后将字符串切割成匹配和不匹配的段落，并告诉你匹配的部分实际上是匹配了哪一条正则表达式。这个功能在分析很多字符串的时候都是相当好用的。
至于语法分析器，则是实现了一个上下文无关文法库。语法分析器可以通过接受支持Choice、Sequence、Option等操作的上下文无关文法（介于BNF和EBNF中间的一种表示）来讲一个字符串分析之后执行用户指定的语义规则。自己以前写的Syngram for C++的一大优势是支持左递归，使用Boost::Spirit来分析具有明显左递归性质的文法的话你将不得不接受一个线性表来表示原本应该是树的结构，这样的话很难简洁地搞定很多复杂的分析过程。Syngram for C++解决了这个问题。于是我将Syngram for C++包装进了FreeScript，于是脚本也具有这个能力来分析复杂但是有递归结构的字符串了。
在此贴一个例子。正则表达式大家都很熟悉就不贴了，这里贴一个语法分析器分析四则运算式子的FreeScript代码：
1 _run(_global,readfile(apppath++"Syngram.free"));
2 using Syngram;
3
4 Parser=Syner.new();
5
6 Parser.SetDiscard("\\s+");
7 Parser.SetToken("number","\\d+(.\\d+)?");
8 Parser.SetToken("left","\\(");
9 Parser.SetToken("right","\\)");
10 Parser.SetToken("add","\\+|\\-");
11 Parser.SetToken("mul","\\*|/");
12 Parser.SetDefaultError("未知错误。");
13 Parser.SetUnexpectedEndError("表达式过早结束。");
14
15 Parser.SetRule("TERM","number",func(items)
16 {
17 return items[0];
18 });
19 Parser.SetRule("TERM","left EXP:\"括号后缺少表达式。\" right:\"缺少右括号。\"",func(items)
20 {
21 return items[1];
22 });
23 Parser.SetRule("TERM","add TERM:\"单目操作符后缺少表达式。\"",func(items)
24 {
25 if(items[0]=="+")
26 return items[1];
27 else
28 return -items[1];
29 });
30 Parser.SetRule("FACTOR","TERM",func(items)
31 {
32 return items[0];
33 });
34 Parser.SetRule("FACTOR","FACTOR mul TERM:\"双目操作符后缺少表达式。\"",func(items)
35 {
36 if(items[1]=="*")
37 return items[0]*items[2];
38 else
39 return items[0]/items[2];
40 });
41 Parser.SetRule("EXP","FACTOR",func(items)
42 {
43 return items[0];
44 });
45 Parser.SetRule("EXP","EXP add FACTOR:\"双目操作符后缺少表达式。\"",func(items)
46 {
47 if(items[1]=="+")
48 return items[0]+items[2];
49 else
50 return items[0]-items[2];
51 });
52
53 Parser.Initialize("EXP");
54
55 try_catch(
56 func()
57 {
58 writeln(Parser.Parse(read("输入一个四则运算式子：")));
59 },
60 func(errmsg)
61 {
62 writeln("格式错误：",errmsg);
63 }
64 );
这段程序输入一个四则运算式子，如果输入错误则显示配置进去的相应的错误信息，否则则使用绑定的语义规则（Parse.SetRule中的func(items)）来计算整个式子的结果。Syngram for C++的文法并不是使用字符串表示的，但是Syner在开发的时候FreeScript尚未实现操作符重载，于是就算了，懒得重新封装一个。封装的那一层用了Syngram for C++实现了字符串到文法的分析器，然后套上一层新的Syngram for C++来分析FreeScript的代码所要分析的内容。事实上这个分析器是Syngram
2。
好了，现在贴出Syngram for FreeScript的代码：
1 /****************************************************************
2 本库需要【Collections.free】的支持
3
4 RegexpMatch：正则表达式匹配结果
5 Captures ：匿名捕获只读表
6 Storages ：命名捕获多值表
7 Position ：匹配位置
8 Text ：匹配结果
9 Matched ：是否成功匹配
10 RegexpBase：正则表达式基类
11 Find({value}Text) ：在字符串中寻找所有匹配的只读表
12 Split({value}Text) ：使用正则表达式分割字符串的只读表
13 Cut({value}Text) ：将字符串分割成匹配或不匹配正则表达式的部分的只读表
14 Match({value}Text) ：在字符串中寻找第一个匹配
15 MatchHead({value}Text) ：返回从第一个字符开始的匹配
16 MatchWhole({value}Text) ：返回匹配整个字符串的匹配
17
18 RegexpPure：纯匹配正则表达式
19 constructor({value}Expression) ：使用字符串构造正则表达式
20 RegexpSafe：安全正则表达式
21 constructor({value}Expression) ：使用字符串构造正则表达式
22 RegexpGreed：贪婪正则表达式
23 constructor({value}Expression) ：使用字符串构造正则表达式
24
25 LexerToken：词法分析器记号
26 Data ：自定义数据
27 Position ：位置
28 Text ：记号内容
29 Lexer：词法分析器
30 constructor() ：构造词法分析器
31 Add({value}Exp,Data) ：添加类型并绑定自定义数据
32 Initialize() ：初始化
33 Parse({value}Input) ：分析字符串，返回LexerToken的只读表
34
35
36 Syner：上下文无关文法分析器
37 SetDiscard(Regex) ：设置词法分析后需要删掉的记号的正则表达式
38 SetToken(Name,Regex) ：设置有效记号的名字和对应的正则表达式
39 SetRule(Name,Rule,Func) ：设置推导式的名字、推导式和语义回调函数
40 Initialize(Nonterminator) ：设置初始符号并初始化
41 IsReady() ：返回是否已经初始化
42 Parse(Text) ：分析字符串
43 SetDefaultError(Text) ：一般错误返回的消息
44 SetUnexpectedEndError(Text) ：过早结束返回的消息
45 ****************************************************************/
46 Syngram=namespace
47 {
48 fixed RegexpMatch=class()
49 {
50 local Captures=null;
51 local Storages=null;
52 local Position=null;
53 local Text=null;
54 local Matched=null;
55
56 local constructor=func(Item)
57 {
58 Matched=matched(Item);
59 Text=text(Item);
60 Position=pos(Item);
61 Captures=ReadonlyList.new(catched(Item));
62 Storages=MultiMap.new();
63 for(name in allstorages(Item))
64 Storages.Add(name,storage(Item,name));
65 };
66 };
67
68 fixed RegexpBase=class()
69 {
70 local Find=null;
71 local Split=null;
72 local Cut=null;
73 local Match=null;
74 local MatchHead=null;
75 local MatchWhole=null;
76
77 local constructor=func()
78 {
79 local Engine=null;
80
81 local TransformResult=multifunc
82 {
83 func({array}Items)
84 {
85 return ReadonlyList.new(Items).Map(func(Item)return RegexpMatch.new(Item););
86 }
87 func(Item)
88 {
89 return RegexpMatch.new(Item);
90 }
91 };
92
93 Find=func({value}Text)
94 {
95 return TransformResult(find(Engine,Text));
96 };
97
98 Split=func({value}Text)
99 {
100 return TransformResult(split(Engine,Text));
101 };
102
103 Cut=func({value}Text)
104 {
105 return TransformResult(cut(Engine,Text));
106 };
107
108 Match=func({value}Text)
109 {
110 return TransformResult(match(Engine,Text));
111 };
112
113 MatchHead=func({value}Text)
114 {
115 return TransformResult(matchhead(Engine,Text));
116 };
117
118 MatchWhole=func({value}Text)
119 {
120 return TransformResult(matchwhole(Engine,Text));
121 };
122
123 return func(Regexp)
124 {
125 Engine=Regexp;
126 };
127 }();
128 };
129
130 fixed RegexpPure=class(RegexpBase)
131 {
132 local constructor=func({value}Expression)
133 {
134 base.constructor(regexppure(Expression));
135 };
136 };
137
138 fixed RegexpSafe=class(RegexpBase)
139 {
140 local constructor=func({value}Expression)
141 {
142 base.constructor(regexpsafe(Expression));
143 };
144 };
145
146 fixed RegexpGreed=class(RegexpBase)
147 {
148 local constructor=func({value}Expression)
149 {
150 base.constructor(regexpgreed(Expression));
151 };
152 };
153
154 fixed LexerToken=class()
155 {
156 local Data=null;
157 local Position=-1;
158 local Text="";
159 };
160
161 fixed Lexer=class()
162 {
163 local Add=null;
164 local Initialize=null;
165 local Parse=null;
166
167 local constructor=func()
168 {
169 local DataMap=Map.new();
170 local Engine=lexercreate();
171
172 local TransformResult=func(Item)
173 {
174 local Result=LexerToken.new();
175 Result.Position=Item.Position;
176 Result.Text=Item.Text;
177 if(Item.Type!=-1)
178 Result.Data=DataMap[Item.Type];
179 return Result;
180 };
181
182 Add=func({value}Expression,Data)
183 {
184 DataMap.Add(lexeradd(Engine,Expression),Data);
185 };
186
187 Initialize=func()
188 {
189 lexerbuild(Engine);
190 };
191
192 Parse=func({value}Text)
193 {
194 return ReadonlyList.new(lexerparse(Engine,Text)).Map(TransformResult);
195 };
196
197 return func()
198 {
199 };
200 }();
201 };
202
203 fixed Syner=class()
204 {
205 local SetDiscard=null; /*设置词法分析后需要删掉的记号类型*/
206 local SetToken=null; /*设置有效记号*/
207 local SetRule=null; /*设置推到规则以及绑定该规则的语义处理函数*/
208 local Initialize=null; /*设置起始非终结符并完成整个分析器的建立*/
209 local IsReady=null; /*返回是否已经完成分析器的建立*/
210 local Parse=null; /*分析一个字符串并返回该字符串经过语义处理函数处理的结果*/
211 local SetDefaultError=null; /*设置一般错误抛出的异常*/
212 local SetUnexpectedEndError=null; /*设置由于表达式不完整导致的错误抛出的异常*/
213
214 constructor=func()
215 {
216 local _IsReady=false;
217 local _Grammar="";
218 local _Processors=[];
219 local _RuleCount=0;
220 local _Analyzer=null;
221
222 local _TextProcess=func(Text)
223 {
224 local Result="";
225 for(c in Text)
226 {
227 if(c=="\"")Result=Result++"\\\"";
228 else Result=Result++c;
229 }
230 return Result;
231 };
232
233 SetDiscard=func(Regex)
234 {
235 if(!_IsReady)
236 {
237 _Grammar=_Grammar++"discard "++Regex++"\r\n";
238 }
239 };
240
241 SetToken=func(Name,Regex)
242 {
243 if(!_IsReady)
244 {
245 _Grammar=_Grammar++Name++"="++Regex++"\r\n";
246 }
247 };
248
249 SetRule=func(Name,Rule,Func)
250 {
251 if(!_IsReady)
252 {
253 local NonTerminator=Name++"._"++_RuleCount;
254 _RuleCount=_RuleCount+1;
255 _Grammar=_Grammar++NonTerminator++"->"++Rule++"\r\n";
256 _Processors[#_Processors:0]=[[NonTerminator,Func]];
257 }
258 };
259
260 Initialize=func(NonTerminator)
261 {
262 if(!_IsReady)
263 {
264 _Grammar=_Grammar++"init "++NonTerminator;
265 _Analyzer=buildsyner(_Grammar,_Processors);
266 _IsReady=true;
267 }
268 };
269
270 IsReady=func()
271 {
272 return _IsReady;
273 };
274
275 Parse=func(Text)
276 {
277 return runsyner(_Analyzer,Text);
278 };
279
280 SetDefaultError=func(Text)
281 {
282 if(!_IsReady)
283 {
284 _Grammar=_Grammar++"default \""++_TextProcess(Text)++"\"\r\n";
285 }
286 };
287
288 SetUnexpectedEndError=func(Text)
289 {
290 if(!_IsReady)
291 {
292 _Grammar=_Grammar++"end \""++_TextProcess(Text)++"\"\r\n";
293 }
294 };
295 };
296 };
297 };
posted on 2008-05-19 00:56
陈梓瀚(vczh) 阅读(1628)
评论(4) 编辑 收藏 引用 所属分类:
Vczh Free Script