• <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>
            隨筆 - 17  文章 - 48  trackbacks - 0
            <2014年9月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            常用鏈接

            留言簿(3)

            隨筆檔案

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜


            去年花了兩三個星期的業(yè)余時間實現(xiàn)了基于DFA的正則引擎( ),時間一晃就過去一年,工作繁忙,興趣面廣,前途未卜什么的耗費太多精力,最近兩三個月抽了點時間寫了基于NFA的正則引擎,代碼放在Github

            正則引擎常見的實現(xiàn)方法

            正則的常見實現(xiàn)方式有三種:DFA、Backtracking、NFA:

            • DFA是三種實現(xiàn)中效率最高的,不過缺點也明顯,一是DFA的構(gòu)造復雜耗時,二是DFA支持的正則語法有限。在早期正則被發(fā)明出來時,只有concatenation、alternation、Kleene star,即"ab" "a|b" "a*",DFA可以輕松搞定。隨著計算機的發(fā)展,正則像所有其它語言一樣發(fā)展出各種新的語法,很多語法在DFA中難以實現(xiàn),比如capture、backreference(capture倒是有論文描述可以在DFA中實現(xiàn))。

            • Backtracking是三種實現(xiàn)中效率最低的,功能確是最強的,它可以實現(xiàn)所有后面新加的語法,因此,大多數(shù)正則引擎實現(xiàn)都采用此方法。因為它是回溯的,所以在某些情況下會出現(xiàn)指數(shù)復雜度,這篇文章有詳細的描述。

            • NFA(Thompson NFA)有相對DFA來說的構(gòu)造簡單,并兼有接近DFA的效率,并且在面對Backtracking出現(xiàn)指數(shù)復雜度時的正則表達式保持良好的性能。

            NFA-based的實現(xiàn)

            這里描述的NFA是指Thompson NFA。Thompson NFA實現(xiàn)的核心是對于正則表達式多個可能的匹配并發(fā)的向前匹配,此過程是在模擬DFA運行。比如對于正則表達式"abab|abbb"匹配字符串"abbb":

            • Backtracking的匹配過程是取正則的第一個子表達式"abab"匹配,前兩個字符匹配成功,匹配第三個字符的時候失敗,這時引擎回溯選擇第二個子表達式"abbb"匹配,最終匹配成功。

            • Thompson NFA是同時取兩個子表達式"abab"和"abbb"匹配,前兩個字符匹配時,兩個子表達式都能匹配成功,當匹配第三個字符時,子表達式"abab"匹配失敗,因此丟棄,"abbb"匹配成功接著匹配,最終匹配成功。

            上面是一個簡單的例子,沒有出現(xiàn)"*" "+" "{m,n}"這種復雜的metacharacters,在處理這種repeat的metacharacter時Thompson NFA優(yōu)勢更加明顯。

            在實際復雜的正則表達式中,NFA構(gòu)造是必然會產(chǎn)生一堆epsilon邊,這在第二篇文章中有描述。上面描述Thompson NFA實際是在模擬DFA運行,在每個字符匹配完成之后需要跳過epsilon邊得到后面要匹配的并發(fā)的狀態(tài)集合,這樣持續(xù)的并發(fā)匹配下去,當字符串匹配完成時只要有一個達到了接受狀態(tài),就是匹配成功,若這個集合為空,那表示匹配失敗。

            在我的實現(xiàn)中,構(gòu)造了一組狀態(tài)和由這組狀態(tài)加epsilon邊集合構(gòu)造的有向圖,每個狀態(tài)有自己的狀態(tài)類型,分為兩種:

            • 一種是匹配狀態(tài)類型,即用來匹配字符的狀態(tài),若字符匹配成功,則進入下一個狀態(tài);

            • 一種是操作狀態(tài)類型,即不匹配字符的狀態(tài),在每個字符匹配結(jié)束之后若到達這些狀態(tài),則會進行相應的操作,比如repeat狀態(tài),記錄匹配計數(shù),并判斷匹配計數(shù)是否完成再決定是否進入的下面的狀態(tài)。

            repeat是一種會分化的狀態(tài),達到最小匹配次數(shù)時,可以接著往下走,也可以繼續(xù)重復匹配repeat的子正則表達式,這樣就分化成兩條線了,并且每條線都帶有自己的狀態(tài)數(shù)據(jù),因此,我的實現(xiàn)中引入的thread來表示一條匹配線,里面有狀態(tài)數(shù)據(jù)。

            Match和Search

            狀態(tài)構(gòu)造完成了之后,就要開始匹配了。匹配有兩種,一種是match,即一個正則表達式能否完整匹配一個字符串,若完整匹配則匹配成功;另一種是search,要在一個字符串中或者一塊buffer中查找每個滿足的匹配。這里就有個問題,從第一個字符開始匹配,匹配了幾個字符之后發(fā)現(xiàn)匹配失敗了怎么辦呢?回退到第二個字符重新匹配?我們知道對于普通的字符串查找,有KMP算法可以保證不回退字符(其實KMP算法的預處理就是構(gòu)造DFA),或者有Boyer-Moore算法盡量回退少的字符個數(shù)。對于正則這種復雜的匹配該怎么辦呢?從上面的Thompson NFA的描述可以知道匹配過程是多條線并發(fā)匹配,因此可以構(gòu)造一個始終產(chǎn)生一條新線的狀態(tài),若匹配在前面的線失敗被丟棄之后,后面的新線始終可以補上,這樣查找的過程就不再需要回退字符了。

            我的實現(xiàn)中,狀態(tài)構(gòu)造完成后是這樣的:

                // |-----|--------|---------------|-----|-------------|
                
            // | any | repeat | capture begin |  | capture end |
                
            // |-----|--------|---------------|-----|-------------|

            用repeat-any來產(chǎn)生新的匹配線。若在match模式下,則從第三個狀態(tài)開始匹配,不會產(chǎn)生新的匹配線,一旦匹配過程失敗了就失敗了。

            結(jié)語

            正則表達式語法一直在擴展,新的語法有些很難在DFA和NFA中實現(xiàn),而在Backtracking中的實現(xiàn)又是以犧牲性能為代價。因此有些正則表達式實現(xiàn)會結(jié)合多種實現(xiàn)方式,判斷正則表達式的類型選擇不同的引擎,比如普通字符串加上一些簡單的正則語法采用DFA引擎匹配,或者只有普通字符串的匹配可以用Boyer-Moore算法,畢竟Boyer-Moore算法在普通文本查找中要優(yōu)于KMP算法:),對于復雜的正則表達式采用Backtracking,甚至有些正則引擎使用JIT來加速。

            posted on 2014-09-15 19:04 airtrack 閱讀(3192) 評論(0)  編輯 收藏 引用
            久久精品无码一区二区WWW| 精品久久久久中文字| 久久精品国产99国产精品亚洲 | 欧美成a人片免费看久久| 久久久久女教师免费一区| 日本五月天婷久久网站| 99久久精品午夜一区二区| 久久93精品国产91久久综合| 中文成人久久久久影院免费观看| 亚洲人成网亚洲欧洲无码久久 | 久久99国产综合精品免费| 国产精品美女久久久久av爽| 久久久久亚洲AV无码观看| 久久露脸国产精品| 久久精品九九亚洲精品天堂| 伊人久久综合成人网| 欧美日韩中文字幕久久久不卡 | 国内精品久久久久久久97牛牛| 精品久久人人爽天天玩人人妻| 亚洲狠狠婷婷综合久久蜜芽| 久久精品中文字幕第23页| 国内精品人妻无码久久久影院| 一极黄色视频久久网站| 久久AAAA片一区二区| 婷婷综合久久狠狠色99h| 无码日韩人妻精品久久蜜桃| 久久综合色之久久综合| 伊人丁香狠狠色综合久久| 久久综合久久综合久久| 精品国产一区二区三区久久久狼| 久久免费看黄a级毛片| 亚洲欧美另类日本久久国产真实乱对白| 久久婷婷五月综合97色一本一本 | 久久99国产乱子伦精品免费| 久久精品国产亚洲AV蜜臀色欲| 欧美精品丝袜久久久中文字幕| 国产精品综合久久第一页| 奇米影视7777久久精品| 亚洲AV无码久久精品成人 | 国产精品九九久久精品女同亚洲欧美日韩综合区| 青青青国产精品国产精品久久久久 |