青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆-341  評(píng)論-2670  文章-0  trackbacks-0
    DFA與捕獲和預(yù)查結(jié)合起來(lái)的話很麻煩,不能用一張表來(lái)迭代,而是要用回溯,然后在回溯的時(shí)候記下?tīng)顟B(tài)。至此正則表達(dá)式的所有算法都完成了,接下來(lái)是詳細(xì)介紹。

    每一個(gè)回溯的記錄都需要一張帶有所有捕獲軌跡的表(元素為堆棧的堆棧),給每一個(gè)記錄集一張表顯然很浪費(fèi),因此我們只用一張表來(lái)記錄。但是我們對(duì)表進(jìn)行刪除項(xiàng)目的時(shí)候,又可能會(huì)影響到上一個(gè)回溯的數(shù)據(jù),因此我們要開發(fā)出一個(gè)新的堆棧,可以push,可以pop,而且pop之后再push不會(huì)破壞原有的東西,一直到外邊顯示指定跳到前一個(gè)狀態(tài)為止:
 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         }

    于是我們就可以對(duì)可以回溯的列表進(jìn)行保存了。一開始available=-1,count=0。每次push的時(shí)候改變available和count,但是對(duì)于列表來(lái)說(shuō),0到count-1的東西都是安全的。pop的時(shí)候改變available,但是count保留不變,這個(gè)時(shí)候elements[count-1]可以通過(guò)elements[count-1].available(而不是參數(shù)的available)追溯到上一個(gè)項(xiàng)。這樣就把所有存在的堆棧都?jí)喝氲酵粋€(gè)列表里面去了,而且不同的堆棧可以通過(guò)不同的count訪問(wèn),一直到比較小的count決定push東西了,大的count對(duì)應(yīng)的堆棧才會(huì)受到破壞。于是我們就用一個(gè)列表和一個(gè)count表組成了一個(gè)元素是堆棧的堆棧。

    知道怎么操作之后下面的匹配代碼就很好理解了:
  1 #include "RegexRich.h"
  2 
  3 namespace vl
  4 {
  5     namespace regex_internal
  6     {
  7 
  8 /***********************************************************************
  9 回溯輔助數(shù)據(jù)結(jié)構(gòu)
 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;                    //當(dāng)前字符串位置
 30             State*                currentState;                //當(dāng)前狀態(tài)
 31             int                    minTransition;                //最小可用轉(zhuǎn)換
 32             int                    captureCount;                //有效capture數(shù)量
 33             int                    stateSaverCount;            //有效回溯狀態(tài)數(shù)量
 34             int                    extensionSaverAvailable;    //有效未封閉擴(kuò)展功能數(shù)量
 35             int                    extensionSaverCount;        //所有未封閉擴(kuò)展功能數(shù)量
 36             StateStoreType        storeType;                    //保存狀態(tài)的原因
 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                 //開始遍歷轉(zhuǎn)換
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一定會(huì)被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一定會(huì)被push
291                             oldState.storeType=StateSaver::Negative;
292                             found=true;
293                         }
294                         break;
295                     case Transition::NegativeFail:
296                         {
297                             //只有在回溯的時(shí)候NegativeFail才會(huì)被考慮
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                     //尋找成功,在必要的時(shí)候保存當(dāng)前的回溯狀態(tài)
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                         //恢復(fù)Negative失敗狀態(tài)的時(shí)候要移動(dòng)到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                                     //將當(dāng)前狀態(tài)移動(dòng)到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             //判斷是否成功并且處理返回結(jié)果
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 }

    于是帶有各種擴(kuò)展功能的匹配就完成了。之前還用同樣的前端開發(fā)了一個(gè)不帶擴(kuò)展功能的純匹配的正則表達(dá)式引擎。因?yàn)檫^(guò)于簡(jiǎn)單就不列出來(lái)了。這些算法的詳細(xì)介紹可以看這里

    下面的工作就是寫更多的單元測(cè)試用例,最后將這兩個(gè)不同的匹配算法封裝在一起,智能地在正確的情況下選擇更快的算法。這樣正則表達(dá)式引擎的效率將會(huì)大大提高。
posted on 2009-11-14 19:13 陳梓瀚(vczh) 閱讀(2484) 評(píng)論(1)  編輯 收藏 引用 所屬分類: VL++3.0開發(fā)紀(jì)事

評(píng)論:
# re: Vczh Library++3.0之正則表達(dá)式引擎(DFA與捕獲、預(yù)查結(jié)合的匹配)[未登錄](méi) 2009-11-19 01:52 | megax
有沒(méi)有測(cè)試過(guò)你的正則的效率?和delex比怎么樣?  回復(fù)  更多評(píng)論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美一区二区大片| 国产综合精品| 亚洲美女精品成人在线视频| 久热精品视频| 久久天天躁狠狠躁夜夜av| 韩国福利一区| 欧美黄在线观看| 欧美日韩国产页| 欧美一级网站| 久久婷婷国产综合国色天香| 亚洲精选在线| 中日韩高清电影网| 国内视频一区| 日韩视频一区二区三区在线播放 | 欧美专区中文字幕| 久久久www| 国产精品久久久久999| 久久久久久久一区二区| 最近中文字幕日韩精品 | 欧美在线观看你懂的| 伊人色综合久久天天| 亚洲精品一区二区三区99| 国产精品视频网址| 久久免费国产精品| 欧美巨乳在线观看| 久久久亚洲一区| 欧美精品在线观看播放| 欧美一级久久久久久久大片| 葵司免费一区二区三区四区五区| 一区二区三区久久网| 性欧美在线看片a免费观看| 亚洲精品免费观看| 欧美一区观看| 亚洲欧美中日韩| 欧美大片一区二区| 另类酷文…触手系列精品集v1小说| 欧美日韩精品久久久| 久久人人精品| 国产麻豆91精品| 一区二区欧美国产| 亚洲精品影视| 久久躁狠狠躁夜夜爽| 久久久精品国产免大香伊| 欧美天堂亚洲电影院在线观看 | 亚洲精品一区在线| 久久久夜精品| 久久米奇亚洲| 国产一区二区三区免费不卡| 一区二区三区视频免费在线观看| 亚洲国产一区二区三区a毛片 | 午夜精品福利在线| 亚洲欧美电影在线观看| 欧美理论在线| 亚洲国产综合91精品麻豆| 国产精品久久久久免费a∨大胸| 亚洲国产精品精华液2区45| 国产一区二区三区在线观看视频 | 国产精品永久免费在线| 亚洲精品中文字| 亚洲精品一区在线观看香蕉| 久久久久久久久蜜桃| 亚洲综合色婷婷| 国产精品成人午夜| 亚洲少妇一区| 欧美亚洲自偷自偷| 国产精品尤物| 欧美在线短视频| 久久久国产精品一区二区中文 | 久久久999精品视频| 欧美一区二区三区四区在线观看地址 | 久久久九九九九| 国产在线欧美| 久久久久国产成人精品亚洲午夜| 久久精品国产亚洲5555| 国产亚洲高清视频| 欧美亚洲一区二区在线| 久久久久国产一区二区| 国模一区二区三区| 久久夜色精品国产亚洲aⅴ| 模特精品在线| 中文精品视频| 国产欧美精品一区| 久久在线免费观看| 亚洲狼人精品一区二区三区| 中文成人激情娱乐网| 国产欧美日本| 久久人人看视频| 亚洲精品欧美日韩专区| 亚洲欧美久久久久一区二区三区| 国产精品视频一二| 久久久久天天天天| 亚洲精品欧美专区| 久久久久久黄| 99精品福利视频| 国产精品亚洲综合一区在线观看 | 久久精品亚洲热| 亚洲国产婷婷| 久久成人人人人精品欧| 亚洲国产精品123| 国产精品久久综合| 免费不卡视频| 亚洲欧美日韩国产综合| 亚洲成人自拍视频| 久久激情视频| 一本色道久久综合狠狠躁的推荐| 国产精品一区=区| 欧美激情91| 久久久久久尹人网香蕉| 中文av字幕一区| 亚洲国产一区二区精品专区| 欧美一区二区三区在线观看| 日韩午夜电影| 亚洲国产精品视频一区| 国产午夜精品视频| 欧美涩涩视频| 欧美国产日韩一区二区三区| 欧美在线你懂的| 宅男噜噜噜66国产日韩在线观看| 欧美福利视频| 久久综合色8888| 午夜精品视频| 一本一本a久久| 亚洲免费久久| 亚洲精品一区二区三区在线观看| 国产一区二区三区免费不卡| 国产精品美女久久久久久久 | 欧美成人免费在线观看| 欧美一区二区在线免费观看 | 老司机午夜免费精品视频| 在线视频一区二区| 亚洲精品一区二区在线| 亚洲福利电影| 欧美国产精品人人做人人爱| 久久天天综合| 麻豆国产va免费精品高清在线| 欧美一区二区免费| 午夜精品久久久久久久久| 亚洲一区二区三区四区五区黄| 亚洲精选一区| 中国成人亚色综合网站| 亚洲午夜精品久久| 亚洲综合精品四区| 午夜在线a亚洲v天堂网2018| 亚洲欧美久久久| 欧美一级在线亚洲天堂| 欧美在线999| 久久综合九色99| 欧美电影在线| 亚洲精品久久久久久一区二区| 亚洲人成在线观看| 一区二区三区久久网| 亚洲免费人成在线视频观看| 欧美在线视屏 | 99re国产精品| 亚洲一区二区三区涩| 欧美一区91| 免费观看久久久4p| 欧美日韩一区二区三区在线观看免| 欧美日韩综合视频| 国产欧美日韩另类一区| 狠狠色丁香久久婷婷综合_中| 在线观看日韩av| 一区二区久久久久| 欧美在线看片a免费观看| 久久五月天婷婷| 亚洲欧洲一区二区在线播放 | 你懂的亚洲视频| 亚洲久色影视| 久久精精品视频| 欧美久久在线| 国产一区二区在线观看免费播放| 亚洲国产精品悠悠久久琪琪| 在线亚洲精品福利网址导航| 午夜宅男欧美| 亚洲国产日韩欧美在线动漫| 亚洲中无吗在线| 美女视频黄 久久| 国产精品午夜国产小视频| 亚洲国产另类精品专区| 午夜精品久久久久久久| 欧美91福利在线观看| 亚洲图片激情小说| 欧美成人午夜激情在线| 国产欧美亚洲日本| 99re这里只有精品6| 久久久免费观看视频| 在线午夜精品自拍| 欧美 日韩 国产精品免费观看| 国产精品系列在线| 亚洲三级视频| 美女主播精品视频一二三四| 亚洲视频免费看| 欧美精品在线看| 在线看国产日韩| 久久蜜桃资源一区二区老牛| 一区二区三区回区在观看免费视频| 久久人人九九| 国语自产精品视频在线看抢先版结局| 中文精品视频| 日韩视频在线免费|