隨筆檔案

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

正則的常見實現方式有三種：DFA、Backtracking、NFA：

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

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

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

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

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

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

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

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

在我的實現中，構造了一組狀態和由這組狀態加epsilon邊集合構造的有向圖，每個狀態有自己的狀態類型，分為兩種：

• 一種是匹配狀態類型，即用來匹配字符的狀態，若字符匹配成功，則進入下一個狀態；

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

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

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

我的實現中，狀態構造完成后是這樣的：

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

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