深入入門正則表達式（java） - 1 - 入門基礎
?
深入入門正則表達式（java） - 2 - 基本實例
深入入門正則表達式（java） - 3 - 正則在java中的使用
深入入門正則表達式（java） - 匹配原理 - 1 - 引擎分類與普適原則
深入入門正則表達式（java） - 匹配原理 - 2 - 回溯
?
?
本節第一部分主要介紹正則引擎的分類， 由于java屬于NFA，所以只重點介紹此類。其余類型簡要或不做介紹。
分類的內容全部來自《精通正則表達式》v3
?
| 引擎類型 | 程序 |
| DFA | awk（大多數版本）、egrep（大多數版本）、flex、lex、MySQL、Procmail |
| 傳統NFA | GNU Emacs、Java、grep（大多數版本）、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（非確定型有窮自動機）：表達式主導
正則：“to(nite|knight|night)”
目標文本：“tonight”
正則表達式從“t”開始，每次檢查一部分（由引擎查看表達式的一部分），同時檢查當前文本是否匹配表達式的當前部分。如果是，則繼續表達式的下一部分，直到表達式的所有部分都能匹配。
此例中第一個元素是“t”，它會重復嘗試，在目標字符串中找到“t”為止，然后檢查“o”，過程與此一致。然后是“(nite|knight|night)”部分，表達式會一次嘗試， 直到宣告匹配成功或失敗才會停止。 表達式中的控制權在不同元素之間轉換，所以作者稱其為“表達式主導”
所以正則：“nfa|nfa not”，目標字符串：“nfa not”中，也只是匹配“nfa”而已，而不會完整的匹配。
?
DFA （確定型有窮自動機） ：文本主導
DFA引擎在掃描字符串時，會記錄“當前有效”的所有匹配可能。
還是最初的例子，引擎移動到“t”時，它會在當前處理匹配可能中添加一個潛在的可能
接下來掃描的每個字符，都會更新當前的可能匹配序列。繼續掃描兩個字符之后的情況如上圖。分支“knight”被排除。
書中作者稱其問文本主導，是因為掃描每個字符的時候都對引擎進行了控制
?
?
測試引擎類型
1.如果支持忽略優先量詞，那么基本就是傳統NFA。DFA不支持忽略優先量詞，POSIX NFA中也沒有意義。
2.DFA不支持捕獲型括號和回溯。在這兩種混合類型的引擎中，如果沒有使用捕獲型括號，就會使用DFA
ps：在RegexBuddy中似乎只有傳統NFA，起碼做1的驗證時結果是這樣的，所以DFA和混合型引擎在這就不做驗證了，本文也主要針對java，所以這里指著重介紹和java相關內容
?
?
?
兩條普適原則 （來自 《精通正則表達式》 v3） ：
1.優先匹配最左面（最靠開頭）的匹配結果
注意：此原則并沒有規定優先匹配結果的長度，而只是規定在所有可能的匹配結果中，優先選擇最左邊的（可能有）。
作者關于此原則的解釋：匹配先從需要查找的字符串的起始位置嘗試匹配。這里的“嘗試匹配”的意思是：在當前位置測試整個正則表達式能匹配的每個可 能。如果在當前位置測試了所有的可能之后找不到匹配結果，就需要從字符的第二個字符之前的位置開始重新嘗試……只有在嘗試過所有的起始位置（直到字符串的 最后一個字符）都找不到匹配結果的情況下，才會報告失敗。
下面給出一個例子：
目標字符串“This is a cat.”
我想匹配字符“is”，我的正則為“is”
結果如下（圖1）：
這里找到了兩個結果，根據原則1，最先找到的是“this”中的“is”，而并沒有找到“is”這個單詞。這也很容易理解。下面我們看看RegexBuddy中debug的過程
這里怎么會有這么多字符，目標字符串實際只有13個字符，那么多出來的那些都是哪來的呢？
我覺得，RegexBuddy是把字符與字符之間的位置也算為一個character。再來看看圖1
我之所以把每一個字符都裝在表格里，就是讓大家看的清楚。這里，每一個豎線（其實是不存在的）也作為一個character，我覺得這樣是有道理的，比如零寬斷言，它的匹配就是在某一個豎線的位置。我們不妨用“^”測試一下，看看debug的結果。
?
當正則以“字符串起始位置錨點”開頭，引擎就會知道如果能匹配，那么肯定是從字符串開頭，所以不需要做更多的嘗試。
ps：這和RegexBuddy上面的debug結果似乎是矛盾的。確實是這樣，不知道是不是其一個bug，起碼v3.5.4是這樣的
RegexBuddy暫時是不支持字符組的集合操作的，不知這算功能缺失還是算個bug
?
?
2.標準的量詞（*，+，?，{m,n}）是匹配優先的
目標字符串：“copyright 2003”
正則：“.*”，那么匹配的結果為全部字符
正則：“.*[0-9]*”，這個時候，由于量詞是匹配優先的，所以“.*”會匹配整個字符串，而后面的“[0-9]*”怎什么也匹配不到
，這并不影響最終結果，因為“*”表示0個也可以，我們可以添加一組括號來驗證這個結果，如下圖顯示的一樣
我們現在將正則改成這樣：“.*[0-9]+”，這時候“.*”也會先把字符串全部匹配，之后是“[0-9]+”這個部分，發現它要求至少匹配到一 個數字才行，所以它會強迫“.*”吐出它之前匹配到的內容給自己使用，當“.*”吐出字符“3”之后，“[0-9]+”成功匹配，至此匹配結束，不再進行 其他嘗試。
我們來debug看看這一過程：
書中作者總結為：先來先服務。我覺得，也就是說，多個匹配優先量詞時，如果目標字符串“不能無法同時滿足其需求”，那么寫在前面的量詞會得到盡量多的字符，后面的量詞會像“類似”忽略優先量詞一樣進行匹配 - 給點就行。
?
?
?
?
轉貼請保留以下鏈接
本人blog地址
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
