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