今天在測試封裝在FreeScript內(nèi)的正則表達(dá)式接口的時候發(fā)現(xiàn)了一個垃圾收集器的Bug，不過很容易就看出來了，于是立刻fix掉。出錯的原因在于垃圾收集的時候只標(biāo)記了運(yùn)算堆棧的內(nèi)容，忘了標(biāo)記調(diào)用堆棧的內(nèi)容。
這個新的Syngram包含了三個工具，分別是正則表達(dá)式、詞法分析器和語法分析器。
正則表達(dá)式分純、安全和貪婪三種。純正則表達(dá)式僅僅用于匹配，速度非?？欤ㄒ郧暗臏y試表明一秒鐘可以匹配44萬次），但是沒有預(yù)查和捕獲等功能。安全和貪婪兩種正則表達(dá)式則是通過不同的搜索方法來匹配字符串的內(nèi)容，雖然慢了一點(diǎn)，不過有了預(yù)查和捕獲等功能。
之前的文章有提到過關(guān)于一個少回溯多捕獲的測試用例下的速度。安全分析法回溯將會占用很多時間，而貪婪分析法則回溯基本是沒什么消耗的。
詞法分析器則可以輸入不同的正則表達(dá)式，然后將字符串切割成匹配和不匹配的段落，并告訴你匹配的部分實(shí)際上是匹配了哪一條正則表達(dá)式。這個功能在分析很多字符串的時候都是相當(dāng)好用的。
至于語法分析器，則是實(shí)現(xiàn)了一個上下文無關(guān)文法庫。語法分析器可以通過接受支持Choice、Sequence、Option等操作的上下文無關(guān)文法（介于BNF和EBNF中間的一種表示）來講一個字符串分析之后執(zhí)行用戶指定的語義規(guī)則。自己以前寫的Syngram for C++的一大優(yōu)勢是支持左遞歸，使用Boost::Spirit來分析具有明顯左遞歸性質(zhì)的文法的話你將不得不接受一個線性表來表示原本應(yīng)該是樹的結(jié)構(gòu)，這樣的話很難簡潔地搞定很多復(fù)雜的分析過程。Syngram for C++解決了這個問題。于是我將Syngram for C++包裝進(jìn)了FreeScript，于是腳本也具有這個能力來分析復(fù)雜但是有遞歸結(jié)構(gòu)的字符串了。
在此貼一個例子。正則表達(dá)式大家都很熟悉就不貼了，這里貼一個語法分析器分析四則運(yùn)算式子的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("表達(dá)式過早結(jié)束。");
14
15 Parser.SetRule("TERM","number",func(items)
16 {
17 return items[0];
18 });
19 Parser.SetRule("TERM","left EXP:\"括號后缺少表達(dá)式。\" right:\"缺少右括號。\"",func(items)
20 {
21 return items[1];
22 });
23 Parser.SetRule("TERM","add TERM:\"單目操作符后缺少表達(dá)式。\"",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:\"雙目操作符后缺少表達(dá)式。\"",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:\"雙目操作符后缺少表達(dá)式。\"",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("輸入一個四則運(yùn)算式子：")));
59 },
60 func(errmsg)
61 {
62 writeln("格式錯誤：",errmsg);
63 }
64 );
這段程序輸入一個四則運(yùn)算式子，如果輸入錯誤則顯示配置進(jìn)去的相應(yīng)的錯誤信息，否則則使用綁定的語義規(guī)則（Parse.SetRule中的func(items)）來計算整個式子的結(jié)果。Syngram for C++的文法并不是使用字符串表示的，但是Syner在開發(fā)的時候FreeScript尚未實(shí)現(xiàn)操作符重載，于是就算了，懶得重新封裝一個。封裝的那一層用了Syngram for C++實(shí)現(xiàn)了字符串到文法的分析器，然后套上一層新的Syngram for C++來分析FreeScript的代碼所要分析的內(nèi)容。事實(shí)上這個分析器是Syngram
2。
好了，現(xiàn)在貼出Syngram for FreeScript的代碼：
1 /****************************************************************
2 本庫需要【Collections.free】的支持
3
4 RegexpMatch：正則表達(dá)式匹配結(jié)果
5 Captures ：匿名捕獲只讀表
6 Storages ：命名捕獲多值表
7 Position ：匹配位置
8 Text ：匹配結(jié)果
9 Matched ：是否成功匹配
10 RegexpBase：正則表達(dá)式基類
11 Find({value}Text) ：在字符串中尋找所有匹配的只讀表
12 Split({value}Text) ：使用正則表達(dá)式分割字符串的只讀表
13 Cut({value}Text) ：將字符串分割成匹配或不匹配正則表達(dá)式的部分的只讀表
14 Match({value}Text) ：在字符串中尋找第一個匹配
15 MatchHead({value}Text) ：返回從第一個字符開始的匹配
16 MatchWhole({value}Text) ：返回匹配整個字符串的匹配
17
18 RegexpPure：純匹配正則表達(dá)式
19 constructor({value}Expression) ：使用字符串構(gòu)造正則表達(dá)式
20 RegexpSafe：安全正則表達(dá)式
21 constructor({value}Expression) ：使用字符串構(gòu)造正則表達(dá)式
22 RegexpGreed：貪婪正則表達(dá)式
23 constructor({value}Expression) ：使用字符串構(gòu)造正則表達(dá)式
24
25 LexerToken：詞法分析器記號
26 Data ：自定義數(shù)據(jù)
27 Position ：位置
28 Text ：記號內(nèi)容
29 Lexer：詞法分析器
30 constructor() ：構(gòu)造詞法分析器
31 Add({value}Exp,Data) ：添加類型并綁定自定義數(shù)據(jù)
32 Initialize() ：初始化
33 Parse({value}Input) ：分析字符串，返回LexerToken的只讀表
34
35
36 Syner：上下文無關(guān)文法分析器
37 SetDiscard(Regex) ：設(shè)置詞法分析后需要刪掉的記號的正則表達(dá)式
38 SetToken(Name,Regex) ：設(shè)置有效記號的名字和對應(yīng)的正則表達(dá)式
39 SetRule(Name,Rule,Func) ：設(shè)置推導(dǎo)式的名字、推導(dǎo)式和語義回調(diào)函數(shù)
40 Initialize(Nonterminator) ：設(shè)置初始符號并初始化
41 IsReady() ：返回是否已經(jīng)初始化
42 Parse(Text) ：分析字符串
43 SetDefaultError(Text) ：一般錯誤返回的消息
44 SetUnexpectedEndError(Text) ：過早結(jié)束返回的消息
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; /*設(shè)置詞法分析后需要刪掉的記號類型*/
206 local SetToken=null; /*設(shè)置有效記號*/
207 local SetRule=null; /*設(shè)置推到規(guī)則以及綁定該規(guī)則的語義處理函數(shù)*/
208 local Initialize=null; /*設(shè)置起始非終結(jié)符并完成整個分析器的建立*/
209 local IsReady=null; /*返回是否已經(jīng)完成分析器的建立*/
210 local Parse=null; /*分析一個字符串并返回該字符串經(jīng)過語義處理函數(shù)處理的結(jié)果*/
211 local SetDefaultError=null; /*設(shè)置一般錯誤拋出的異常*/
212 local SetUnexpectedEndError=null; /*設(shè)置由于表達(dá)式不完整導(dǎo)致的錯誤拋出的異常*/
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) 閱讀(1643)
評論(4) 編輯 收藏 引用 所屬分類:
Vczh Free Script