玄幻小说排行榜完本,好看的课外书,国际完美世界下载

主頁(yè) > 知識(shí)庫(kù) > 正則表達(dá)式之貪婪與非貪婪模式詳解（概述）

正則表達(dá)式之貪婪與非貪婪模式詳解（概述）

1 概述
貪婪與非貪婪模式影響的是被量詞修飾的子表達(dá)式的匹配行為，貪婪模式在整個(gè)表達(dá)式匹配成功的前提下，盡可能多的匹配，而非貪婪模式在整個(gè)表達(dá)式匹配成功的前提下，盡可能少的匹配。非貪婪模式只被部分NFA引擎所支持。

屬于貪婪模式的量詞，也叫做匹配優(yōu)先量詞，包括：

“{m,n}”、“{m,}”、“?”、“*”和“+”。

在一些使用NFA引擎的語(yǔ)言中，在匹配優(yōu)先量詞后加上“?”，即變成屬于非貪婪模式的量詞，也叫做忽略?xún)?yōu)先量詞，包括：

“{m,n}?”、“{m,}?”、“??”、“*?”和“+?”。

從正則語(yǔ)法的角度來(lái)講，被匹配優(yōu)先量詞修飾的子表達(dá)式使用的就是貪婪模式，如“(Expression)+”；被忽略?xún)?yōu)先量詞修飾的子表達(dá)式使用的就是非貪婪模式，如“(Expression)+?”。

對(duì)于貪婪模式，各種文檔的叫法基本一致，但是對(duì)于非貪婪模式，有的叫懶惰模式或惰性模式，有的叫勉強(qiáng)模式，其實(shí)叫什么無(wú)所謂，只要掌握原理和用法，能夠運(yùn)用自如也就是了。個(gè)人習(xí)慣使用貪婪與非貪婪的叫法，所以文中都會(huì)使用這種叫法進(jìn)行介紹。

2 貪婪與非貪婪模式匹配原理
對(duì)于貪婪與非貪婪模式，可以從應(yīng)用和原理兩個(gè)角度進(jìn)行理解，但如果想真正掌握，還是要從匹配原理來(lái)理解的。

先從應(yīng)用的角度，回答一下“什么是貪婪與非貪婪模式？”

2.1 從應(yīng)用角度分析貪婪與非貪婪模式
2.1.1 什么是貪婪與非貪婪模式
先看一個(gè)例子

舉例：

源字符串：aadiv>test1/div>bbdiv>test2/div>cc

正則表達(dá)式一：div>.*/div>

匹配結(jié)果一：div>test1/div>bbdiv>test2/div>

正則表達(dá)式二：div>.*?/div>

匹配結(jié)果二：div>test1/div>（這里指的是一次匹配結(jié)果，所以沒(méi)包括div>test2/div>）

根據(jù)上面的例子，從匹配行為上分析一下，什是貪婪與非貪婪模式。

正則表達(dá)式一采用的是貪婪模式，在匹配到第一個(gè)“/div>”時(shí)已經(jīng)可以使整個(gè)表達(dá)式匹配成功，但是由于采用的是貪婪模式，所以仍然要向右嘗試匹配，查看是否還有更長(zhǎng)的可以成功匹配的子串，匹配到第二個(gè)“/div>”后，向右再?zèng)]有可以成功匹配的子串，匹配結(jié)束，匹配結(jié)果為“div>test1/div>bbdiv>test2/div>”。當(dāng)然，實(shí)際的匹配過(guò)程并不是這樣的，后面的匹配原理會(huì)詳細(xì)介紹。

僅從應(yīng)用角度分析，可以這樣認(rèn)為，貪婪模式，就是在整個(gè)表達(dá)式匹配成功的前提下，盡可能多的匹配，也就是所謂的“貪婪”，通俗點(diǎn)講，就是看到想要的，有多少就撿多少，除非再也沒(méi)有想要的了。

正則表達(dá)式二采用的是非貪婪模式，在匹配到第一個(gè)“/div>”時(shí)使整個(gè)表達(dá)式匹配成功，由于采用的是非貪婪模式，所以結(jié)束匹配，不再向右嘗試，匹配結(jié)果為“div>test1/div>”。

僅從應(yīng)用角度分析，可以這樣認(rèn)為，非貪婪模式，就是在整個(gè)表達(dá)式匹配成功的前提下，盡可能少的匹配，也就是所謂的“非貪婪”，通俗點(diǎn)講，就是找到一個(gè)想要的撿起來(lái)就行了，至于還有沒(méi)有沒(méi)撿的就不管了。

2.1.2 關(guān)于前提條件的說(shuō)明
在上面從應(yīng)用角度分析貪婪與非貪婪模式時(shí)，一直提到的一個(gè)前提條件就是“整個(gè)表達(dá)式匹配成功”，為什么要強(qiáng)調(diào)這個(gè)前提，我們看下下面的例子。

正則表達(dá)式三：div>.*/div>bb

匹配結(jié)果三：div>test1/div>bb

修飾“.”的仍然是匹配優(yōu)先量詞“*”，所以這里還是貪婪模式，前面的“div>.*/div>”仍然可以匹配到“div>test1/div>bbdiv>test2/div>”，但是由于后面的“bb”無(wú)法匹配成功，這時(shí)“div>.*/div>”必須讓出已匹配的“bbdiv>test2/div>”，以使整個(gè)表達(dá)式匹配成功。這時(shí)整個(gè)表達(dá)式匹配的結(jié)果為“div>test1/div>bb”，“div>.*/div>”匹配的內(nèi)容為“div>test1/div>”?？梢钥吹剑凇罢麄€(gè)表達(dá)式匹配成功”的前提下，貪婪模式才真正的影響著子表達(dá)式的匹配行為，如果整個(gè)表達(dá)式匹配失敗，貪婪模式只會(huì)影響匹配過(guò)程，對(duì)匹配結(jié)果的影響無(wú)從談起。

非貪婪模式也存在同樣的問(wèn)題，來(lái)看下面的例子。

正則表達(dá)式四：div>.*?/div>cc

匹配結(jié)果四：div>test1/div>bbdiv>test2/div>cc

這里采用的是非貪婪模式，前面的“div>.*?/div>”仍然是匹配到“div>test1/div>”為止，此時(shí)后面的“cc”無(wú)法匹配成功，要求“div>.*?/div>”必須繼續(xù)向右嘗試匹配，直到匹配內(nèi)容為“div>test1/div>bbdiv>test2/div>”時(shí)，后面的“cc”才能匹配成功，整個(gè)表達(dá)式匹配成功，匹配的內(nèi)容為“div>test1/div>bbdiv>test2/div>cc”，其中“div>.*?/div>”匹配的內(nèi)容為“div>test1/div>bbdiv>test2/div>”?？梢钥吹剑凇罢麄€(gè)表達(dá)式匹配成功”的前提下，非貪婪模式才真正的影響著子表達(dá)式的匹配行為，如果整個(gè)表達(dá)式匹配失敗，非貪婪模式無(wú)法影響子表達(dá)式的匹配行為。

2.1.3 貪婪還是非貪婪——應(yīng)用的抉擇
通過(guò)應(yīng)用角度的分析，已基本了解了貪婪與非貪婪模式的特性，那么在實(shí)際應(yīng)用中，究竟是選擇貪婪模式，還是非貪婪模式呢，這要根據(jù)需求來(lái)確定。

對(duì)于一些簡(jiǎn)單的需求，比如源字符為“aadiv>test1/div>bb”，那么取得div標(biāo)簽，使用貪婪與非貪婪模式都可以取得想要的結(jié)果，使用哪一種或許關(guān)系不大。

但是就2.1.1中的例子來(lái)說(shuō)，實(shí)際應(yīng)用中，一般一次只需要取得一個(gè)配對(duì)出現(xiàn)的div標(biāo)簽，也就是非貪婪模式匹配到的內(nèi)容，貪婪模式所匹配到的內(nèi)容通常并不是我們所需要的。

那為什么還要有貪婪模式的存在呢，從應(yīng)用角度很難給出滿(mǎn)意的解答了，這就需要從匹配原理的角度去分析貪婪與非貪婪模式。

2.2 從匹配原理角度分析貪婪與非貪婪模式
如果想真正了解什么是貪婪模式，什么是非貪婪模式，分別在什么情況下使用，各自的效率如何，那就不能僅僅從應(yīng)用角度分析，而要充分了解貪婪與非貪婪模式的匹配原理。

2.2.1 從基本匹配原理談起
NFA引擎基本匹配原理參考：正則基礎(chǔ)之——NFA引擎匹配原理。

這里主要針對(duì)貪婪與非貪婪模式涉及到的匹配原理進(jìn)行介紹。先看一下貪婪模式簡(jiǎn)單的匹配過(guò)程。

源字符串："Regex"

正則表達(dá)式：".*"

圖2-1

注：為了能夠看清晰匹配過(guò)程，上面的空隙留得較大，實(shí)際源字符串為“”Regex””，下同。

來(lái)看一下匹配過(guò)程。首先由第一個(gè)“"”取得控制權(quán)，匹配位置0位的“"”，匹配成功，控制權(quán)交給“.*”。

“.*”取得控制權(quán)后，由于“*”是匹配優(yōu)先量詞，在可匹配可不匹配的情況下，優(yōu)先嘗試匹配。從位置1處的“R”開(kāi)始嘗試匹配，匹配成功，繼續(xù)向右匹配，匹配位置2處的“e”，匹配成功，繼續(xù)向右匹配，直到匹配到結(jié)尾的“””，匹配成功，由于此時(shí)已匹配到字符串的結(jié)尾，所以“.*”結(jié)束匹配，將控制權(quán)交給正則表達(dá)式最后的“"”。

“"”取得控制權(quán)后，由于已經(jīng)在字符串結(jié)束位置，匹配失敗，向前查找可供回溯的狀態(tài)，控制權(quán)交給“.*”，由“.*”讓出一個(gè)字符，也就是字符串結(jié)尾處的“””，再把控制權(quán)交給正則表達(dá)式最后的“"”，由“"”匹配字符串結(jié)尾處的“"”，匹配成功。

此時(shí)整個(gè)正則表達(dá)式匹配成功，其中“.*”匹配的內(nèi)容為“Regex”，匹配過(guò)程中進(jìn)行了一次回溯。

接下來(lái)看一下非貪婪模式簡(jiǎn)單的匹配過(guò)程。

源字符串："Regex"

正則表達(dá)式：".*?"

圖2-2

看一下非貪婪模式的匹配過(guò)程。首先由第一個(gè)“"”取得控制權(quán)，匹配位置0位的“"”，匹配成功，控制權(quán)交給“.*?”。

“.*?”取得控制權(quán)后，由于“*?”是忽略?xún)?yōu)先量詞，在可匹配可不匹配的情況下，優(yōu)先嘗試不匹配，由于“*”等價(jià)于“{0,}”，所以在忽略?xún)?yōu)先的情況下，可以不匹配任何內(nèi)容。從位置1處嘗試忽略匹配，也就是不匹配任何內(nèi)容，將控制權(quán)交給正則表達(dá)式最后的“””。

“"”取得控制權(quán)后，從位置1處嘗試匹配，由“"”匹配位置1處的“R”，匹配失敗，向前查找可供回溯的狀態(tài)，控制權(quán)交給“.*?”，由“.*?”吃進(jìn)一個(gè)字符，匹配位置1處的“R”，再把控制權(quán)交給正則表達(dá)式最后的“"”。

“"”取得控制權(quán)后，從位置2處嘗試匹配，由“"”匹配位置1處的“e”，匹配失敗，向前查找可供回溯的狀態(tài)，重復(fù)以上過(guò)程，直到由“.*?”匹配到“x”為止，再把控制權(quán)交給正則表達(dá)式最后的“"”。

“"”取得控制權(quán)后，從位置6處嘗試匹配，由“"”匹配字符串最后的“"”，匹配成功。

此時(shí)整個(gè)正則表達(dá)式匹配成功，其中“.*?”匹配的內(nèi)容為“Regex”，匹配過(guò)程中進(jìn)行了五次回溯。

2.2.2 貪婪還是非貪婪——匹配效率的抉擇
通過(guò)匹配原理的分析，可以看到，在匹配成功的情況下，貪婪模式進(jìn)行了更少的回溯，而回溯的過(guò)程，需要進(jìn)行控制權(quán)的交接，讓出已匹配內(nèi)容或匹配未匹配內(nèi)容，并重新嘗試匹配，在很大程度上降低匹配效率，所以貪婪模式與非貪婪模式相比，存在匹配效率上的優(yōu)勢(shì)。

但2.2.1中的例子，僅僅是一個(gè)簡(jiǎn)單的應(yīng)用，讀者看到這里時(shí)，是否會(huì)存在這樣的疑問(wèn)，貪婪模式就一定比非貪婪模式匹配效率高嗎？答案是否定的。

舉例：

需求：取得兩個(gè)“"”中的子串，其中不能再包含“"”。

正則表達(dá)式一：".*"

正則表達(dá)式二：".*?"

情況一：當(dāng)貪婪模式匹配到更多不需要的內(nèi)容時(shí)，可能存在比非貪婪模式更多的回溯。比如源字符串為“The word "Regex" means regular expression.”。

情況二：貪婪模式無(wú)法滿(mǎn)足需求。比如源字符串為“The phrase "regular expression" is called "Regex" for short.”。

對(duì)于情況一，正則表達(dá)式一采用的貪婪模式，“.*”會(huì)一直匹配到字符串結(jié)束位置，控制權(quán)交給最后的“””，匹配不成功后，再進(jìn)行回溯，由于多匹配的內(nèi)容“means regular expression.”遠(yuǎn)遠(yuǎn)超過(guò)需匹配內(nèi)容本身，所以采用正則表達(dá)式一時(shí)，匹配效率會(huì)比使用正則表達(dá)式二的非貪婪模式低。

對(duì)于情況二，正則表達(dá)式一匹配到的是“"regular expression" is called "Regex"”，連需求都不滿(mǎn)足，自然也談不上什么匹配效率的高低了。

以上兩種情況是普遍存在的，那么是不是為了滿(mǎn)足需求，又兼顧效率，就只能使用非貪婪模式了呢？當(dāng)然不是，根據(jù)實(shí)際情況，變更匹配優(yōu)先量詞修飾的子表達(dá)式，不但可以滿(mǎn)足需求，還可以提高匹配效率。

源字符串："Regex"

給出正則表達(dá)式三："[^"]*"

看一下正則表達(dá)式三的匹配過(guò)程。

圖2-3

首先由第一個(gè)“"”取得控制權(quán)，匹配位置0位的“"”，匹配成功，控制權(quán)交給“[^"]*”。

“[^"]*”取得控制權(quán)后，由于“*”是匹配優(yōu)先量詞，在可匹配可不匹配的情況下，優(yōu)先嘗試匹配。從位置1處的“R”開(kāi)始嘗試匹配，匹配成功，繼續(xù)向右匹配，匹配位置2處的“e”，匹配成功，繼續(xù)向右匹配，直到匹配到“x”，匹配成功，再匹配結(jié)尾的“””時(shí)，匹配失敗，將控制權(quán)交給正則表達(dá)式最后的“"”。

“””取得控制權(quán)后，匹配字符串結(jié)尾處的“””，匹配成功。

此時(shí)整個(gè)正則表達(dá)式匹配成功，其中“[^"]*”匹配的內(nèi)容為“Regex”，匹配過(guò)程中沒(méi)有進(jìn)行回溯。

將量詞修飾的子表達(dá)式由范圍較大的“.”，換成了排除型字符組“[^"]”，使用的仍是貪婪模式，很完美的解決了需求和效率問(wèn)題。當(dāng)然，由于這一匹配過(guò)程沒(méi)有進(jìn)行回溯，所以也不需要記錄回溯狀態(tài)，這樣就可以使用固化分組，對(duì)正則做進(jìn)一步的優(yōu)化。

給出正則表達(dá)式四："(?>[^"]*)"

固化分組并不是所有語(yǔ)言都支持的，如.NET支持，而Java就不支持，但是在Java中卻可以使用更簡(jiǎn)單的占有優(yōu)先量詞來(lái)代替："[^"]*+"。

3 貪婪還是非貪婪模式——再談匹配效率
一般來(lái)說(shuō)，貪婪與非貪婪模式，如果量詞修飾的子表達(dá)式相同，比如“.*”和“.*?”，它們的應(yīng)用場(chǎng)景通常是不同的，所以效率上一般不具有可比性。

而對(duì)于改變量詞修飾的子表達(dá)式，以滿(mǎn)足需求時(shí)，比如把“.*”改為“[^"]*”，由于修飾的子表達(dá)式已不同，也不具有直接的可對(duì)比性。但是在相同的子表達(dá)式，又都可以滿(mǎn)足需求的情況下，比如“[^"]*”和“[^"]*?”，貪婪模式的匹配效率通常要高些。

同時(shí)還有一個(gè)事實(shí)就是，非貪婪模式可以實(shí)現(xiàn)的，通過(guò)優(yōu)化量詞修飾的子表達(dá)式的貪婪模式都可以實(shí)現(xiàn)，而貪婪模式可以實(shí)現(xiàn)的一些優(yōu)化效果，卻未必是非貪婪模式可以實(shí)現(xiàn)的。

貪婪模式還有一點(diǎn)優(yōu)勢(shì)，就是在匹配失敗時(shí)，貪婪模式可以更快速的報(bào)告失敗，從而提升匹配效率。下面將全面考察貪婪與非貪婪模式的匹配效率。

3.1 效率提升——演進(jìn)過(guò)程
在了解了貪婪與非貪婪模式的匹配基本原理之后，我們?cè)賮?lái)重新看一下正則效率提升的演進(jìn)過(guò)程。

需求：取得兩個(gè)“"”中的子串，其中不能再包含“"”。

源字符串：The phrase "regular expression" is called "Regex" for short.

正則表達(dá)式一：".*"

正則表達(dá)式一匹配的內(nèi)容為“"regular expression" is called "Regex"”，不符合要求。

提出正則表達(dá)式二：".*?"

首先“"”取得控制權(quán)，由位置0位開(kāi)始嘗試匹配，直到位置11處匹配成功，控制權(quán)交給“.*?”，匹配過(guò)程同2.2.1中非貪婪模式的匹配過(guò)程。“.*?”匹配的內(nèi)容為“Regex”，匹配過(guò)程中進(jìn)行了四次回溯。

如何消除回溯帶來(lái)的匹配效率的損失，就是使用更小范圍的子表達(dá)式，采用貪婪模式，提出正則表達(dá)式三："[^"]*"

首先“"”取得控制權(quán)，由位置0位開(kāi)始嘗試匹配，直到位置11處匹配成功，控制權(quán)交給“[^"]*”，匹配過(guò)程同2.2.2節(jié)中非貪婪模式的匹配過(guò)程?！癧^"]*”匹配的內(nèi)容為“Regex”，匹配過(guò)程中沒(méi)有進(jìn)行回溯。

3.2 效率提升——更快的報(bào)告失敗
以上討論的是匹配成功的演進(jìn)過(guò)程，而對(duì)于一個(gè)正則表達(dá)式，在匹配失敗的情況下，如果能夠以最快的速度報(bào)告匹配失敗，也會(huì)提升匹配效率，這或許是我們?cè)O(shè)計(jì)正則過(guò)程中最容易忽略的。而在源字符串?dāng)?shù)據(jù)量非常大，或正則表達(dá)式比較復(fù)雜的情況下，是否能夠快速報(bào)告匹配失敗，將對(duì)匹配效率產(chǎn)生直接的影響。

下面將構(gòu)建匹配失敗的正則表達(dá)式，對(duì)匹配過(guò)程進(jìn)行分析。

以下匹配過(guò)程分析中，源字符串統(tǒng)一為：The phrase "regular expression" is called "Regex" for short.

3.2.1 非貪婪模式匹配失敗過(guò)程分析

圖3-1

構(gòu)建匹配失敗的非貪婪模式的正則表達(dá)式：".*?"@

由于最后的“@”的存在，這個(gè)正則表達(dá)式最后一定是匹配失敗的，那么看一下匹配過(guò)程。

首先由“"”取得控制權(quán)，由位置0處開(kāi)始嘗試匹配，匹配失敗，直到圖中標(biāo)示的A處匹配成功，控制權(quán)交給“.*?”。

“.*?”取得控制權(quán)后，由A后面的位置開(kāi)始嘗試匹配，由于是非貪婪模式，首先忽略匹配，將控制權(quán)交給“"”，同時(shí)記錄一下回溯狀態(tài)?！?”取得控制權(quán)后，由A后面的位置開(kāi)始嘗試匹配，匹配字符“r”失敗，查找可供回溯的狀態(tài)，將控制權(quán)交給“.*?”，由“.*?”匹配字符“r”。重復(fù)以上過(guò)程，直到“.*?”匹配了B處前面的字符“n”，“"”匹配了B處的字符“””，將控制權(quán)交給“@”。由“@”匹配接下來(lái)的空格“ ”，匹配失敗，查找可供回溯的狀態(tài)，控制權(quán)交給“.*?”，由“.*?”匹配空格。繼續(xù)重復(fù)以上匹配過(guò)程，直到由“.*?”匹配到字符串結(jié)束位置，將控制權(quán)交給“"”。由于已經(jīng)是字符串結(jié)束位置，匹配失敗，報(bào)告整個(gè)表達(dá)式在位置11處匹配失敗，一輪匹配嘗試結(jié)束。

正則引擎?zhèn)鲃?dòng)裝置使正則向前傳動(dòng)，進(jìn)入下一輪嘗試。后續(xù)匹配過(guò)程與第一輪嘗試匹配過(guò)程基本類(lèi)似，可以參考圖3-1。

從匹配過(guò)程中可以看到，非貪婪模式的匹配失敗過(guò)程，幾乎每一步都伴隨著回溯過(guò)程，對(duì)匹配效率的影響是很大的。

3.2.2 貪婪模式匹配失敗過(guò)程分析——大范圍子表達(dá)式

圖3-2

PS：以上分析過(guò)程圖示參考了《精通正則表達(dá)式》一書(shū)相關(guān)章節(jié)圖示。

構(gòu)建匹配失敗的貪婪模式的正則表達(dá)式：".*"@

其中量詞修飾的子表達(dá)式為匹配范圍較大的“.”，由于最后的“@”的存在，這個(gè)正則表達(dá)式最后也是一定匹配失敗的，看一下匹配過(guò)程。

首先由“"”取得控制權(quán)，由位置0處開(kāi)始嘗試匹配，匹配失敗，直到圖中標(biāo)示的A處匹配成功，控制權(quán)交給“.*”。

“.*”取得控制權(quán)后，由A后面的位置開(kāi)始嘗試匹配，由于是貪婪模式，優(yōu)化嘗試匹配，一直匹配到字符串的結(jié)束位置，將控制權(quán)交給“"”?！?”取得控制權(quán)后，由于已經(jīng)是字符串的結(jié)束位置，匹配失敗，查找可供回溯的狀態(tài)，將控制權(quán)交給“.*”，由“.*”讓出已匹配字符“.”。重復(fù)以上過(guò)程，直到后面“"”匹配了C處后面的字符“””，將控制權(quán)交給“@”。由“@”匹配接下來(lái)D處的空格“ ”，匹配失敗，查找可供回溯的狀態(tài)，控制權(quán)交給“.*”，由“.*”讓出已匹配文本。繼續(xù)重復(fù)以上匹配過(guò)程，直到由“.*”讓出所有已匹配的文本到I處，將控制權(quán)交給“"”?！?”匹配失敗，由于已經(jīng)沒(méi)有可供回溯的狀態(tài)，報(bào)告整個(gè)表達(dá)式在位置11處匹配失敗，一輪匹配嘗試結(jié)束。

正則引擎?zhèn)鲃?dòng)裝置使正則向前傳動(dòng)，進(jìn)入下一輪嘗試。后續(xù)匹配過(guò)程與第一輪嘗試匹配過(guò)程基本類(lèi)似，可以參考圖3-2。

從匹配過(guò)程中可以看到，大范圍子表達(dá)式貪婪模式的匹配失敗過(guò)程，從總體上看，與非貪婪模式?jīng)]有什么區(qū)別，最終進(jìn)行的回溯次數(shù)與非貪婪模式基本一致，對(duì)匹配效率的影響仍然很大。

3.2.3 貪婪模式匹配失敗過(guò)程分析——改進(jìn)的子表達(dá)式

圖3-3

構(gòu)建匹配失敗的貪婪模式的正則表達(dá)式："[^"]*"@

其中量詞修飾的子表達(dá)式，改為匹配范圍較小的排除型字符組“[^"]”，由于最后的“@”的存在，這個(gè)正則表達(dá)式最后也是一定匹配失敗的，看一下匹配過(guò)程。

首先由“"”取得控制權(quán)，由位置0處開(kāi)始嘗試匹配，匹配失敗，直到圖中標(biāo)示的A處匹配成功，控制權(quán)交給“[^"]*”。

“[^"]*”取得控制權(quán)后，由A后面的位置開(kāi)始嘗試匹配，由于是貪婪模式，優(yōu)先嘗試匹配，一直匹配到B處，將控制權(quán)交給“"”?！?”匹配接下來(lái)的的字符“"”，匹配成功，將控制權(quán)交給“@”。由“@”匹配接下來(lái)的空格“ ”，匹配失敗，查找可供回溯的狀態(tài)，控制權(quán)交給“[^"]*”，由“[^"]*”讓出已匹配文本。繼續(xù)重復(fù)以上匹配過(guò)程，直到由“[^"]*”讓出所有已匹配的文本到C處，將控制權(quán)交給“"”?！?”匹配失敗，由于已經(jīng)沒(méi)有可供回溯的狀態(tài)，報(bào)告整個(gè)表達(dá)式在位置11處匹配失敗，一輪匹配嘗試結(jié)束。

正則引擎?zhèn)鲃?dòng)裝置使正則向前傳動(dòng)，進(jìn)入下一輪嘗試。后續(xù)匹配過(guò)程與第一輪嘗試匹配過(guò)程基本類(lèi)似，可以參考圖3-3。

從匹配過(guò)程中可以看到，使用了排除型字符組的貪婪模式的匹配失敗過(guò)程，從總體上看，大量減少了每輪回溯的次數(shù)，可以有效的提升匹配效率。

3.2.4 貪婪模式匹配失敗過(guò)程分析——固化分組
通過(guò)3.2.3節(jié)的分析可以知道，由于“[^"]*”使用了排除型字符組，那么圖3-3中，在A和B之間被匹配到的字符，就一定不會(huì)是字符“"”，所以B到C之間回溯過(guò)程就是多余的，也就是說(shuō)在這之間的可供回溯的狀態(tài)完全可以不記錄。.NET中可以使用固化分組，Java中可以使用占有優(yōu)先量詞來(lái)實(shí)現(xiàn)這一效果。

圖3-4

首先由“"”取得控制權(quán)，由位置0處開(kāi)始嘗試匹配，匹配失敗，直到圖中標(biāo)示的A處匹配成功，控制權(quán)交給“(?>[^"]*)”。

“(?>[^"]*)”取得控制權(quán)后，由A后面的位置開(kāi)始嘗試匹配，由于是貪婪模式，優(yōu)先嘗試匹配，一直匹配到B處，將控制權(quán)交給“"”，在這一匹配過(guò)程中，不記錄任何可供回溯的狀態(tài)?！?”匹配接下來(lái)的字符“””，匹配成功，將控制權(quán)交給“@”。由“@”匹配接下來(lái)的空格“ ”，匹配失敗，查找可供回溯的狀態(tài)，由于已經(jīng)沒(méi)有可供回溯的狀態(tài)，報(bào)告整個(gè)表達(dá)式在位置11處匹配失敗，一輪匹配嘗試結(jié)束。

正則引擎?zhèn)鲃?dòng)裝置使正則向前傳動(dòng)，進(jìn)入下一輪嘗試。后續(xù)匹配過(guò)程與第一輪嘗試匹配過(guò)程基本類(lèi)似，可以參考圖3-4。

從匹配過(guò)程中可以看到，使用了固化分組的貪婪模式的匹配失敗過(guò)程，沒(méi)有涉及到回溯，可以最大限度的提升匹配效率。

3.3 非貪婪模式向貪婪模式的轉(zhuǎn)換
使用匹配范圍較大的子表達(dá)式時(shí)，貪婪模式與非貪婪模式匹配到的內(nèi)容會(huì)有所不同，但是通過(guò)優(yōu)化子表達(dá)式，非貪婪模式可以實(shí)現(xiàn)的匹配，貪婪模式都可以實(shí)現(xiàn)。

比如在實(shí)際應(yīng)用中，匹配img標(biāo)簽的內(nèi)容。

舉例：

需求：取得img標(biāo)簽中的圖片地址，src=后固定為“””

源字符串：img class="test" src="/img/logo.gif" title="測(cè)試" />

正則表達(dá)式一：img\b.*?src="(.*?)".*?>

匹配結(jié)果中，捕獲組1的內(nèi)容即為圖片地址?？梢钥吹?，這個(gè)例子中使用的都是非貪婪模式，而根據(jù)上面章節(jié)的分析，后面兩個(gè)非貪婪模式都可以使用排除型字符組，將非貪婪模式轉(zhuǎn)換為貪婪模式。

正則表達(dá)式二：img\b.*?src="([^"]*)"[^>]*>

注：“src="…"”和標(biāo)簽結(jié)束標(biāo)記符“>”之間的屬性中，也可能出現(xiàn)字符“>”，但那是極端情況，這里不予討論。

后兩處非貪婪模式，可以通過(guò)排除型字符組轉(zhuǎn)換為貪婪模式，提高匹配效率，而“src=”前的非貪婪模式，由于要排除的是一個(gè)字符序列“src=”，而不是單獨(dú)的某一個(gè)或幾個(gè)字符，所以不能使用排除型字符組。當(dāng)然也不是沒(méi)有辦法，可以使用順序環(huán)視來(lái)達(dá)到這一效果。

正則表達(dá)式三：img\b(?:(?!src=).)*src="([^"]*)"[^>]*>

“(?!src=).”表示這樣一個(gè)字符，從它開(kāi)始，右側(cè)不能是字符序列“src=”，而“(?:(?!src=).)*”就表示符合上面規(guī)則的字符，有0個(gè)或無(wú)限多個(gè)。這樣就達(dá)到排除字符序列的目的，實(shí)現(xiàn)的效果同排除型字符組一樣，只不過(guò)排除型字符組排除的是一個(gè)或多個(gè)字符，而這種環(huán)視結(jié)構(gòu)排除的是一個(gè)或多個(gè)有序的字符序列。

但是以順序環(huán)視的方式排除字符序列，由于在匹配每一個(gè)字符時(shí)，都要進(jìn)行較多的判斷，所以相對(duì)于非貪婪模式，是提升效率還是降低效率，要根據(jù)實(shí)際情況進(jìn)行分析。對(duì)于簡(jiǎn)單的正則表達(dá)式，或是簡(jiǎn)單的源字符串，一般來(lái)說(shuō)是非貪婪模式效率高些，而對(duì)于數(shù)量較大源字符串，或是復(fù)雜的正則表達(dá)式，一般來(lái)說(shuō)是貪婪模式效率高些。

比如上面取得img標(biāo)簽中的圖片地址需求，基本上用正則表達(dá)二就可以了；對(duì)于復(fù)雜的應(yīng)用，如平衡組中，就需要使用結(jié)合環(huán)視的貪婪模式了。

以匹配嵌套div標(biāo)簽的平衡組為例：

Regex reg = new Regex(@"(?isx) #匹配模式，忽略大小寫(xiě)，“.”匹配任意字符

div[^>]*> #開(kāi)始標(biāo)記“div...>”

(?> #分組構(gòu)造，用來(lái)限定量詞“*”修飾范圍

div[^>]*> (?Open>) #命名捕獲組，遇到開(kāi)始標(biāo)記，入棧，Open計(jì)數(shù)加1

| #分支結(jié)構(gòu)

/div> (?-Open>) #狹義平衡組，遇到結(jié)束標(biāo)記，出棧，Open計(jì)數(shù)減1

| #分支結(jié)構(gòu)

(?:(?!/?div\b).)* #右側(cè)不為開(kāi)始或結(jié)束標(biāo)記的任意字符

)* #以上子串出現(xiàn)0次或任意多次

(?(Open)(?!)) #判斷是否還有'OPEN'，有則說(shuō)明不配對(duì)，什么都不匹配

/div> #結(jié)束標(biāo)記“/div>”

");

“(?:(?!/?div\b).)*”這里使用的就是結(jié)合環(huán)視的貪婪模式，雖然每匹一個(gè)字符都要做很多判斷，但這種判斷是基于字符的，速度很快，而如果這里使用非貪婪模式，那么每次要做的就是分支結(jié)構(gòu)“|”的判斷了，而分支結(jié)構(gòu)是非常影響匹配效率的，其代價(jià)遠(yuǎn)遠(yuǎn)高于對(duì)確定字符的判斷。而另外一個(gè)原因，就是貪婪模式可以結(jié)合固化分組來(lái)提升效率，而對(duì)非貪婪模式使用固化分組卻是沒(méi)有意義的。

4 貪婪與非貪婪——最后的回顧
4.1 一個(gè)例子的匹配原理回顧
再回過(guò)頭來(lái)看一下2.1.1節(jié)例子中正則，前面從應(yīng)用角度進(jìn)行了分析，但討論過(guò)匹配原理后會(huì)發(fā)現(xiàn)，匹配過(guò)程并不是那么簡(jiǎn)單的，下面從匹配原理角度分析的匹配過(guò)程。

圖4-1

首先由“”取得控制權(quán)，由位置0位開(kāi)始嘗試匹配，匹配字符“a”，匹配失敗，第一輪匹配結(jié)束。第二輪匹配從位置1開(kāi)始嘗試匹配，同樣匹配失敗。第三輪從位置3開(kāi)始嘗試匹配，匹配字符“”，匹配成功，控制權(quán)交給“d”。

“d”嘗試匹配字符“d”，匹配成功，控制權(quán)交給“i”。重復(fù)以上過(guò)程，直到由“>”匹配到字符“>”，控制權(quán)交給“.*”。

“.*”屬于貪婪模式，將從B處后的字符“t”開(kāi)始，一直匹配到E處，也就是字符串結(jié)束位置，將控制權(quán)交給“”。

“”從字符串結(jié)束位置嘗試匹配，匹配失敗，向前查找可供回溯的狀態(tài)，把控制權(quán)交給“.*”，由“.*”讓出一個(gè)字符“c”，把控制權(quán)再交給“”，嘗試匹配，匹配失敗，向前查找可供回溯的狀態(tài)。一直重復(fù)以上過(guò)程，直到“.*”讓出已匹配的字符“”，實(shí)際上也就是讓出了已匹配的子串“/div>cc”為止，“”才匹配字符“”成功，控制權(quán)交給“/”。

接下來(lái)由“/”、“d”、“i”、“v”分別匹配對(duì)應(yīng)的字符成功，此時(shí)整個(gè)正則表達(dá)式匹配完畢。

4.2 貪婪與非貪婪——量詞的細(xì)節(jié)
4.2.1 區(qū)間量詞的非貪婪模式
前面提到的非貪婪模式，一直都是使用的“*?”，而沒(méi)有涉及到其它的區(qū)間量詞，對(duì)于“*?”和“+?”這樣的非貪婪模式，大多數(shù)接觸過(guò)正則表達(dá)式的人都可以理解，但是對(duì)于區(qū)間量詞的非貪婪模式，比如“{m,n}?”，要么是沒(méi)見(jiàn)過(guò)，要么是不理解，主要是這種應(yīng)用場(chǎng)景非常少，所以被忽略了。

首先需要明確的一點(diǎn)，就是量詞“{m,n}”是匹配優(yōu)先量詞，雖然它有了上限，但是在達(dá)到上限之前，能夠匹配，還是要盡可能多的匹配的。而“{m,n}?”就是對(duì)應(yīng)的忽略?xún)?yōu)先量詞了，在可匹配可不匹配的情況下，盡可能少的匹配。

接下來(lái)舉一個(gè)例子說(shuō)明這種非貪婪模式的應(yīng)用。

舉例（參考限制字符長(zhǎng)度與最小匹配）：

需求：如何限制在長(zhǎng)度為100的字符串中，從頭匹配到最先出現(xiàn)的abc

csdn.{1,100}abc 這樣寫(xiě)是最大匹配(1-100個(gè)字符串中，我需要最小的)

比如csdnfddabckjdsfjabc，匹配結(jié)果應(yīng)為：csdnfddabc

正則表達(dá)式：csdn.{1,100}?abc

或許對(duì)這個(gè)例子還有人不是很理解，但是想想，其實(shí)“*”就等價(jià)于“{0,}”，“+”就等價(jià)于“{1,}”，“*?”也就是“{0,}?”，抽象出來(lái)也就是“{m,}?”，即上限為無(wú)窮大。如果上限為一個(gè)固定值，那就是“{m,n}?”，這樣應(yīng)該也就可以理解了。

“{m}”沒(méi)有放在匹配優(yōu)先量詞中，同樣的，“{m}?”雖然被部分語(yǔ)言所支持，但是也沒(méi)有放在忽略?xún)?yōu)先量詞中，主要是因?yàn)檫@兩種量詞，實(shí)現(xiàn)的效果是一樣的，只有被修飾的子表達(dá)式匹配m次才能匹配成功，且沒(méi)有可供回溯的狀態(tài)，所以也不存在是匹配優(yōu)先還是忽略?xún)?yōu)先的問(wèn)題，也就不在本文的討論范圍內(nèi)。事實(shí)上即使討論也沒(méi)有意義的，只要知道它們的匹配行為也就是了。

4.2.2 忽略?xún)?yōu)先量詞的匹配下限
對(duì)于匹配優(yōu)先量詞的匹配下限很好理解，“?”等價(jià)于“{0,1}”，它修飾的子表達(dá)式，最少匹配0次，最多匹配1次；“*”等價(jià)于“{0,}”，它修飾的子表達(dá)式，最少匹配0次，最多匹配無(wú)窮多次；“+”等價(jià)于“{1,}”，它修飾的子表達(dá)式，最少匹配1次，最多匹配無(wú)窮多次。

對(duì)于忽略?xún)?yōu)先量詞的下限，也是容易忽略的。

“??”也是忽略?xún)?yōu)先量詞，被修飾的子表達(dá)式使用的也是非貪婪模式，“??”修飾的子表達(dá)式，最少匹配0次，最多匹配1次。在匹配過(guò)程中，遵循非貪婪模式匹配原則，先不匹配，即匹配0次，記錄回溯狀態(tài)，只有不得不匹配時(shí)，才去嘗試匹配。

“*?”修飾的子表達(dá)式，最少匹配0次，最多匹配無(wú)窮多次；“+?”修飾的子表達(dá)式，最少匹配1次，最多匹配無(wú)窮多次，“+?”雖然使用的是非貪婪模式，在匹配過(guò)程中，首先要匹配一個(gè)字符，之后才是忽略匹配的，這一點(diǎn)也需要注意。

4.3 貪婪與非貪婪模式小結(jié)
Ø 從語(yǔ)法角度看貪婪與非貪婪

被匹配優(yōu)先量詞修飾的子表達(dá)式，使用的是貪婪模式；被忽略?xún)?yōu)先量詞修飾的子表達(dá)式，使用的是非貪婪模式。

匹配優(yōu)先量詞包括：“{m,n}”、“{m,}”、“?”、“*”和“+”。

忽略?xún)?yōu)先量詞包括：“{m,n}?”、“{m,}?”、“??”、“*?”和“+?”。

Ø 從應(yīng)用角度看貪婪與非貪婪

貪婪與非貪婪模式影響的是被量詞修飾的子表達(dá)式的匹配行為，貪婪模式在整個(gè)表達(dá)式匹配成功的前提下，盡可能多的匹配；而非貪婪模式在整個(gè)表達(dá)式匹配成功的前提下，盡可能少的匹配。非貪婪模式只被部分NFA引擎所支持。

Ø 從匹配原理角度看貪婪與非貪婪

能達(dá)到同樣匹配結(jié)果的貪婪與非貪婪模式，通常是貪婪模式的匹配效率較高。

所有的非貪婪模式，都可以通過(guò)修改量詞修飾的子表達(dá)式，轉(zhuǎn)換為貪婪模式。

貪婪模式可以與固化分組結(jié)合，提升匹配效率，而非貪婪模式卻不可以。

您可能感興趣的文章:

正則表達(dá)式(regex) 貪婪模式、懶惰模式使用方法
小議正則表達(dá)式效率貪婪、非貪婪與回溯
淺談php正則表達(dá)式中的非貪婪模式匹配的使用
[正則表達(dá)式]貪婪模式與非貪婪模式
正則表達(dá)式量詞與貪婪的使用詳解

標(biāo)簽：長(zhǎng)沙銅川西安宣城重慶泰州綿陽(yáng) 無(wú)錫

巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《正則表達(dá)式之貪婪與非貪婪模式詳解（概述）》，本文關(guān)鍵詞正則,表達(dá)式,之,貪婪,與,；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題，煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們，我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無(wú)關(guān)。

濮阳杆衣贸易有限公司

正則表達(dá)式之 貪婪與非貪婪模式詳解（概述）

正則表達(dá)式之貪婪與非貪婪模式詳解（概述）