隨筆檔案

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

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

• DFA是三種實現(xiàn)中效率最高的，不過缺點也明顯，一是DFA的構(gòu)造復(fù)雜耗時，二是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ù)復(fù)雜度，這篇文章有詳細(xì)的描述。

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

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

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

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

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

在實際復(fù)雜的正則表達(dá)式中，NFA構(gòu)造是必然會產(chǎn)生一堆epsilon邊，這在第二篇文章中有描述。上面描述Thompson NFA實際是在模擬DFA運行，在每個字符匹配完成之后需要跳過epsilon邊得到后面要匹配的并發(fā)的狀態(tài)集合，這樣持續(xù)的并發(fā)匹配下去，當(dāng)字符串匹配完成時只要有一個達(dá)到了接受狀態(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é)束之后若到達(dá)這些狀態(tài)，則會進行相應(yīng)的操作，比如repeat狀態(tài)，記錄匹配計數(shù)，并判斷匹配計數(shù)是否完成再決定是否進入的下面的狀態(tài)。

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

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

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

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

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