正則表達式引擎及其分類

作者: Yansen 發布時間: 2010-12-30 11:07 閱讀: 7588 次推薦: 2 [收藏]

　　正則引擎主要可以分為兩大類：一種是DFA，一種是NFA。這兩種引擎都有了很久的歷史(至今二十多年)，當中也由這兩種引擎產生了很多變體！于是POSIX的出臺產生規范了不必要變體的繼續產生。這樣一來，目前的主流正則引擎又分為3類：一、DFA，二、傳統型NFA，三、POSIX NFA。

　　DFA 引擎在線性時狀態下執行，因為它們不要求回溯（并因此它們永遠不測試相同的字符兩次）。DFA 引擎還可以確保匹配最長的可能的字符串。但是，因為 DFA 引擎只包含有限的狀態，所以它不能匹配具有反向引用的模式；并且因為它不構造顯示擴展，所以它不可以捕獲子表達式。

　　傳統的 NFA 引擎運行所謂的“貪婪的”匹配回溯算法，以指定順序測試正則表達式的所有可能的擴展并接受第一個匹配項。因為傳統的 NFA 構造正則表達式的特定擴展以獲得成功的匹配，所以它可以捕獲子表達式匹配和匹配的反向引用。但是，因為傳統的 NFA 回溯，所以它可以訪問完全相同的狀態多次（如果通過不同的路徑到達該狀態）。因此，在最壞情況下，它的執行速度可能非常慢。因為傳統的 NFA 接受它找到的第一個匹配，所以它還可能會導致其他（可能更長）匹配未被發現。

　　POSIX NFA 引擎與傳統的 NFA 引擎類似，不同的一點在于：在它們可以確保已找到了可能的最長的匹配之前，它們將繼續回溯。因此，POSIX NFA 引擎的速度慢于傳統的 NFA 引擎；并且在使用 POSIX NFA 時，您恐怕不會愿意在更改回溯搜索的順序的情況下來支持較短的匹配搜索，而非較長的匹配搜索。

　　目前使用DFA引擎的程序主要有：awk,egrep,flex,lex,MySQL,Procmail等；
　　使用傳統型NFA引擎的程序主要有：GNU Emacs,Java,ergp,less,more,.NET語言,PCRE library,Perl,PHP,Python,Ruby,sed,vi；
　　使用POSIX NFA引擎的程序主要有：mawk,Mortice Kern Systems’ utilities,GNU Emacs(使用時可以明確指定)；
　　也有使用DFA/NFA混合的引擎：GNU awk,GNU grep/egrep,Tcl。

　　舉例簡單說明NFA與DFA工作的區別：

　　比如有字符串this is yansen’s blog，正則表達式為 /ya(msen|nsen|nsem)/ (不要在乎表達式怎么樣，這里只是為了說明引擎間的工作區別)。

　　NFA工作方式如下，先在字符串中查找 y 然后匹配其后是否為 a ，如果是 a 則繼續，查找其后是否為 m 如果不是則匹配其后是否為 n (此時淘汰msen選擇支)。然后繼續看其后是否依次為 s,e，接著測試是否為 n ，是 n 則匹配成功，不是則測試是否為 m 。為什么是 m ？因為 NFA 工作方式是以正則表達式為標準，反復測試字符串，這樣同樣一個字符串有可能被反復測試了很多次！

　　而DFA則不是如此，DFA會從 this 中 t 開始依次查找 y，定位到 y ，已知其后為 a ，則查看表達式是否有 a ，此處正好有 a 。然后字符串 a 后為 n ，DFA依次測試表達式，此時 msen 不符合要求淘汰。nsen 和 nsem 符合要求，然后DFA依次檢查字符串，檢測到sen 中的 n 時只有nsen 分支符合，則匹配成功！