原文鏈接http://www.softec.lu/site/RegularExpressions/RegularExpressionEngines
正則運算式引擎是正則運算式匹配演算法的基礎，其有多種不同的實作，但大多數都是基于Henry Spencer的NFA引擎，
正則引擎有兩個大分類，DFA和NFA，像Perl、Java、.Net、PHP、Python、Ruby……等大多是工具都是用了NFA引擎，少數廣泛被使用的工具如mawk使用了POSIX NFA引擎（NFA的一種變種），以高效著稱的工具采用了更為高效的DFA引擎，諸如GNU awk，GNU egrep和Tcl之類的一些工具結合了NFA / DFA兩種引擎，將兩者的優點結合在一起，
基于不同型別引擎的實作的正則運算式，主要有以下幾點差異，
- 語法
- 匹配內容
- 零寬斷言(環視) 功能
- 捕獲功能
- 性能
所有的引擎都會對文本做從左向右的最長匹配，但具體細節取決于使用了何種引擎，
傳統的NFA引擎
NFA引擎中使用的非確定有限狀態機(Nondeterministic finite automation)是一種由要匹配的運算式驅動的演算法，這使得正則運算式像一個小的編程語言一樣，可控制引擎在匹配失敗時候的行為，
正則引擎從正則運算式其實位置開始，嘗試正則運算式與文本的開頭進行匹配，如果匹配成功，都前進一個配置，否則文本一直前進到下一個字符，直到匹配， 如果正則運算式需要作出選擇（例如使用替代詞或可選的量詞），它將選擇其中之一，并記住其他選擇以及在文本中進行選擇的位置，如果在之后的處理中，匹配失敗，并且還有其他可選的路徑，則引擎將回溯做之前作出選擇的位置，并嘗試其他的選擇，如果沒有其他可用的替代方案，則匹配失敗，引擎前進到下一個字符并從頭開始匹配正則運算式，
如果引擎到達了正則運算式的末尾并且所有內容都已匹配，則引擎就會認為匹配成功，并最終放棄所有剩下的替代方法，甚至不再繼續探索，這里有很重要的一點：選擇不同路徑的順序很重要，它決定是是否能做到最長匹配，
引擎會真正按照正則運算式進行匹配，讓你選擇達到完全匹配所需的每個步驟，你必須很謹慎地告訴它，首先檢查哪種選擇才能達到您的期望，你也有機會調整正則運算式，以最大程度地減少回溯并盡早進行匹配， NFA引擎中使用的方法的一些示例也可以幫助你了解回溯是如何作業的，
POSIX NFA 引擎
POSIX NFA引擎類似于傳統NFA引擎，但是當找到成功的匹配項時，它將會記錄匹配結果，并且嘗試其他可用的替代方法以查找是否可以找到更長的最左邊的匹配， 這消除了傳統NFA引擎中不能保證最長最左匹配的問題，
以弗里德爾（Friedl）的書中的這個有趣的例子為例：用one(self)?(selfsufficient)? 去匹配oneselfsufficient，傳統的NFA將匹配 oneself，而POSIX NFA將匹配oneselfsufficient，因為(self)?有兩種選擇，匹配self或者啥都不匹配，顯然最終匹配到的更長，
DFA引擎
DFA引擎中使用的確定性有限自動機（Deterministic finite automaton）是一種由要搜索的文本驅動的演算法， 對于搜索到的文本中的每個字符，DFA引擎只會查看一次， 實際上，它相當于并行嘗試了NFA中所有可能的替代方法，并將回傳其中最長的匹配，
這種方法確實更高效，但也有很多缺點：
- 你無法控制運算式回傳匹配項的方式，無論您如何構造運算式，它始終將回傳最長最左匹配，
- 沒有回溯，因此所有重復的運算子都是貪婪的， 原子分組和所有格修飾符也是無稽之談， (更多詳細資訊，請查閱RegularExpressionsBacktracking）
- 不支持零寬斷言(環視)
- 捕獲和反向參考也不可能實作
- 正則運算式預編譯時間更長，占用更多記憶體
NFA和DFA混合引擎
由于DFA引擎速度快，但NFA引擎的功能多，因此，混合NFA / DFA引擎試圖將二者的優勢結合起來， 迄今為止唯一可用的完全混合實作是Tcl中使用的Henry Spencer引擎，它是對原始實作的完全重寫， 像GNU egrep和awk只是將兩個獨立的引擎放一起，然后根據是否使用了NFA特有的功能決定使用哪個引擎，
本文來自https://blog.csdn.net/xindoo
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/250024.html
標籤：Java
上一篇：訊息佇列之RabbitMQ