DFA與捕獲和預查結合起來的話很麻煩，不能用一張表來迭代，而是要用回溯，然后在回溯的時候記下狀態。至此正則表達式的所有算法都完成了，接下來是詳細介紹。
每一個回溯的記錄都需要一張帶有所有捕獲軌跡的表（元素為堆棧的堆棧），給每一個記錄集一張表顯然很浪費，因此我們只用一張表來記錄。但是我們對表進行刪除項目的時候，又可能會影響到上一個回溯的數據，因此我們要開發出一個新的堆棧，可以push，可以pop，而且pop之后再push不會破壞原有的東西，一直到外邊顯示指定跳到前一個狀態為止：
1 template<typename T, typename K>
2 void Push(List<T, K>& elements, int& available, int& count, const T& element)
3 {
4 if(elements.Count()==count)
5 {
6 elements.Add(element);
7 }
8 else
9 {
10 elements[count]=element;
11 }
12 T& current=elements[count];
13 current.previous=available;
14 available=count++;
15 }
16
17 template<typename T, typename K>
18 T Pop(List<T, K>& elements, int& available, int& count)
19 {
20 T& current=elements[available];
21 available=current.previous;
22 return current;
23 }
于是我們就可以對可以回溯的列表進行保存了。一開始available=-1，count=0。每次push的時候改變available和count，但是對于列表來說，0到count-1的東西都是安全的。pop的時候改變available，但是count保留不變，這個時候elements[count-1]可以通過elements[count-1].available（而不是參數的available）追溯到上一個項。這樣就把所有存在的堆棧都壓入到同一個列表里面去了，而且不同的堆棧可以通過不同的count訪問，一直到比較小的count決定push東西了，大的count對應的堆棧才會受到破壞。于是我們就用一個列表和一個count表組成了一個元素是堆棧的堆棧。
知道怎么操作之后下面的匹配代碼就很好理解了：
1 #include "RegexRich.h"
2
3 namespace vl
4 {
5 namespace regex_internal
6 {
7
8 /***********************************************************************
9 回溯輔助數據結構
10 ***********************************************************************/
11
12 class SaverBase
13 {
14 public:
15 bool available;
16 int previous;
17 };
18
19 class StateSaver
20 {
21 public:
22 enum StateStoreType
23 {
24 Positive,
25 Negative,
26 Other
27 };
28
29 const wchar_t* reading; //當前字符串位置
30 State* currentState; //當前狀態
31 int minTransition; //最小可用轉換
32 int captureCount; //有效capture數量
33 int stateSaverCount; //有效回溯狀態數量
34 int extensionSaverAvailable; //有效未封閉擴展功能數量
35 int extensionSaverCount; //所有未封閉擴展功能數量
36 StateStoreType storeType; //保存狀態的原因
37
38 bool operator==(const StateSaver& saver)
39 {
40 return
41 reading==saver.reading &&
42 currentState==saver.currentState &&
43 minTransition==saver.minTransition &&
44 captureCount==saver.captureCount;
45 }
46 };
47
48 class ExtensionSaver : public SaverBase
49 {
50 public:
51 int captureListIndex;
52 Transition* transition;
53 const wchar_t* reading;
54
55 bool operator==(const ExtensionSaver& saver)
56 {
57 return
58 captureListIndex==saver.captureListIndex &&
59 transition==saver.transition &&
60 reading==saver.reading;
61 }
62 };
63
64 template<typename T, typename K>
65 void Push(List<T, K>& elements, int& available, int& count, const T& element)
66 {
67 if(elements.Count()==count)
68 {
69 elements.Add(element);
70 }
71 else
72 {
73 elements[count]=element;
74 }
75 T& current=elements[count];
76 current.previous=available;
77 available=count++;
78 }
79
80 template<typename T, typename K>
81 T Pop(List<T, K>& elements, int& available, int& count)
82 {
83 T& current=elements[available];
84 available=current.previous;
85 return current;
86 }
87
88 template<typename T, typename K>
89 void PushNonSaver(List<T, K>& elements, int& count, const T& element)
90 {
91 if(elements.Count()==count)
92 {
93 elements.Add(element);
94 }
95 else
96 {
97 elements[count]=element;
98 }
99 count++;
100 }
101
102 template<typename T, typename K>
103 T PopNonSaver(List<T, K>& elements, int& count)
104 {
105 return elements[--count];
106 }
107 }
108
109 template<>
110 struct POD<regex_internal::StateSaver>
111 {
112 static const bool Result=true;
113 };
114
115 template<>
116 struct POD<regex_internal::ExtensionSaver>
117 {
118 static const bool Result=true;
119 };
120
121 namespace regex_internal
122 {
123 /***********************************************************************
124 CaptureRecord
125 ***********************************************************************/
126
127 bool CaptureRecord::operator==(const CaptureRecord& record)
128 {
129 return capture==record.capture && start==record.start && length==record.length;
130 }
131
132 /***********************************************************************
133 PureInterpretor
134 ***********************************************************************/
135
136 RichInterpretor::RichInterpretor(Automaton::Ref _dfa)
137 :dfa(_dfa)
138 {
139 datas=new UserData[dfa->states.Count()];
140
141 for(int i=0;i<dfa->states.Count();i++)
142 {
143 State* state=dfa->states[i].Obj();
144 int charEdges=0;
145 int nonCharEdges=0;
146 bool mustSave=false;
147 for(int j=0;j<state->transitions.Count();j++)
148 {
149 if(state->transitions[j]->type==Transition::Chars)
150 {
151 charEdges++;
152 }
153 else
154 {
155 if(state->transitions[j]->type==Transition::Negative ||
156 state->transitions[j]->type==Transition::Positive)
157 {
158 mustSave=true;
159 }
160 nonCharEdges++;
161 }
162 }
163 datas[i].NeedKeepState=mustSave || nonCharEdges>1 || (nonCharEdges!=0 && charEdges!=0);
164 state->userData=&datas[i];
165 }
166 }
167
168 RichInterpretor::~RichInterpretor()
169 {
170 delete[] datas;
171 }
172
173 bool RichInterpretor::MatchHead(const wchar_t* input, const wchar_t* start, Result& result)
174 {
175 List<StateSaver> stateSavers;
176 List<ExtensionSaver> extensionSavers;
177
178 StateSaver currentState;
179 currentState.captureCount=0;
180 currentState.currentState=dfa->startState;
181 currentState.extensionSaverAvailable=-1;
182 currentState.extensionSaverCount=0;
183 currentState.minTransition=0;
184 currentState.reading=input;
185 currentState.stateSaverCount=0;
186 currentState.storeType=StateSaver::Other;
187
188 while(!currentState.currentState->finalState)
189 {
190 bool found=false;
191 StateSaver oldState=currentState;
192 //開始遍歷轉換
193 for(int i=currentState.minTransition;i<currentState.currentState->transitions.Count();i++)
194 {
195 Transition* transition=currentState.currentState->transitions[i];
196 switch(transition->type)
197 {
198 case Transition::Chars:
199 {
200 CharRange range=transition->range;
201 found=
202 range.begin<=*currentState.reading &&
203 range.end>=*currentState.reading;
204 if(found)
205 {
206 currentState.reading++;
207 }
208 }
209 break;
210 case Transition::BeginString:
211 {
212 found=currentState.reading==start;
213 }
214 break;
215 case Transition::EndString:
216 {
217 found=*currentState.reading==L'\0';
218 }
219 break;
220 case Transition::Nop:
221 {
222 found=true;
223 }
224 break;
225 case Transition::Capture:
226 {
227 ExtensionSaver saver;
228 saver.captureListIndex=currentState.captureCount;
229 saver.reading=currentState.reading;
230 saver.transition=transition;
231 Push(extensionSavers, currentState.extensionSaverAvailable, currentState.extensionSaverCount, saver);
232
233 CaptureRecord capture;
234 capture.capture=transition->capture;
235 capture.start=currentState.reading-input;
236 capture.length=-1;
237 PushNonSaver(result.captures, currentState.captureCount, capture);
238
239 found=true;
240 }
241 break;
242 case Transition::Match:
243 {
244 int index=0;
245 for(int j=0;j<currentState.captureCount;j++)
246 {
247 CaptureRecord& capture=result.captures[j];
248 if(capture.capture==transition->capture)
249 {
250 if(capture.length!=-1 && (transition->index==-1 || transition->index==index))
251 {
252 if(wcsncmp(input+capture.start, currentState.reading, capture.length)==0)
253 {
254 currentState.reading+=capture.length;
255 found=true;
256 break;
257 }
258 }
259 if(transition->index!=-1 && index==transition->index)
260 {
261 break;
262 }
263 else
264 {
265 index++;
266 }
267 }
268 }
269 }
270 break;
271 case Transition::Positive:
272 {
273 ExtensionSaver saver;
274 saver.captureListIndex=-1;
275 saver.reading=currentState.reading;
276 saver.transition=transition;
277 Push(extensionSavers, currentState.extensionSaverAvailable, currentState.extensionSaverCount, saver);
278 //Positive的oldState一定會被push
279 oldState.storeType=StateSaver::Positive;
280 found=true;
281 }
282 break;
283 case Transition::Negative:
284 {
285 ExtensionSaver saver;
286 saver.captureListIndex=-1;
287 saver.reading=currentState.reading;
288 saver.transition=transition;
289 Push(extensionSavers, currentState.extensionSaverAvailable, currentState.extensionSaverCount, saver);
290 //Negative的oldState一定會被push
291 oldState.storeType=StateSaver::Negative;
292 found=true;
293 }
294 break;
295 case Transition::NegativeFail:
296 {
297 //只有在回溯的時候NegativeFail才會被考慮
298 }
299 break;
300 case Transition::End:
301 {
302 ExtensionSaver saver=Pop(extensionSavers, currentState.extensionSaverAvailable, currentState.extensionSaverCount);
303 switch(saver.transition->type)
304 {
305 case Transition::Capture:
306 {
307 CaptureRecord& capture=result.captures[saver.captureListIndex];
308 capture.length=(currentState.reading-input)-capture.start;
309 found=true;
310 }
311 break;
312 case Transition::Positive:
313 for(int j=currentState.stateSaverCount-1;j>=0;j--)
314 {
315 StateSaver& saver=stateSavers[j];
316 if(saver.storeType==StateSaver::Positive)
317 {
318 oldState.reading=saver.reading;
319 oldState.stateSaverCount=j;
320 currentState.reading=saver.reading;
321 currentState.stateSaverCount=j;
322 break;
323 }
324 }
325 found=true;
326 break;
327 case Transition::Negative:
328 for(int j=currentState.stateSaverCount-1;j>=0;j--)
329 {
330 StateSaver& saver=stateSavers[j];
331 if(saver.storeType==StateSaver::Negative)
332 {
333 oldState=saver;
334 oldState.storeType=StateSaver::Other;
335 currentState=saver;
336 currentState.storeType=StateSaver::Other;
337 i=currentState.minTransition-1;
338 break;
339 }
340 }
341 break;
342 }
343 }
344 break;
345 }
346 //尋找成功，在必要的時候保存當前的回溯狀態
347 if(found)
348 {
349 UserData* data=(UserData*)currentState.currentState->userData;
350 if(data->NeedKeepState)
351 {
352 oldState.minTransition=i+1;
353 PushNonSaver(stateSavers, currentState.stateSaverCount, oldState);
354 }
355 currentState.currentState=transition->target;
356 currentState.minTransition=0;
357 break;
358 }
359 }
360 if(!found)
361 {
362 //存在回溯記錄則回溯
363 if(currentState.stateSaverCount)
364 {
365 //恢復Negative失敗狀態的時候要移動到NegativeFail后面
366 currentState=PopNonSaver(stateSavers, currentState.stateSaverCount);
367 //minTransition總是被+1后保存，因此直接-1總是有效值
368 if(currentState.currentState->transitions[currentState.minTransition-1]->type==Transition::Negative)
369 {
370 //尋找NegativeFail
371 for(int i=0;i<currentState.currentState->transitions.Count();i++)
372 {
373 Transition* transition=currentState.currentState->transitions[i];
374 if(transition->type==Transition::NegativeFail)
375 {
376 //將當前狀態移動到NegativeFail后面
377 currentState.currentState=transition->target;
378 currentState.minTransition=0;
379 currentState.storeType=StateSaver::Other;
380 break;
381 }
382 }
383 }
384 }
385 else
386 {
387 break;
388 }
389 }
390 }
391
392 //判斷是否成功并且處理返回結果
393 if(currentState.currentState->finalState)
394 {
395 result.start=0;
396 result.length=currentState.reading-input;
397 for(int i=result.captures.Count()-1;i>=currentState.captureCount;i++)
398 {
399 result.captures.RemoveAt(i);
400 }
401 return true;
402 }
403 else
404 {
405 result.captures.Clear();
406 return false;
407 }
408 }
409
410 bool RichInterpretor::Match(const wchar_t* input, const wchar_t* start, Result& result)
411 {
412 const wchar_t* read=input;
413 while(*read)
414 {
415 if(MatchHead(read, start, result))
416 {
417 result.start=read-input;
418 for(int i=0;i<result.captures.Count();i++)
419 {
420 result.captures[i].start+=result.start;
421 }
422 return true;
423 }
424 read++;
425 }
426 return false;
427 }
428
429 const IReadonlyList<WString>& RichInterpretor::CaptureNames()
430 {
431 return dfa->captureNames.Wrap();
432 }
433 }
434 }
于是帶有各種擴展功能的匹配就完成了。之前還用同樣的前端開發了一個不帶擴展功能的純匹配的正則表達式引擎。因為過于簡單就不列出來了。這些算法的詳細介紹可以看
這里。
下面的工作就是寫更多的單元測試用例，最后將這兩個不同的匹配算法封裝在一起，智能地在正確的情況下選擇更快的算法。這樣正則表達式引擎的效率將會大大提高。
posted on 2009-11-14 19:13
陳梓瀚(vczh) 閱讀(2486)
評論(1) 編輯 收藏 引用 所屬分類:
VL++3.0開發紀事