From: www.regexlab.com

引言

    本文將逐步討論一些正則表達(dá)式的使用話題。本文為本站基礎(chǔ)篇之后的擴(kuò)展，在閱讀本文之前，建議先閱讀正則表達(dá)式參考文檔一文。

1. 表達(dá)式的遞歸匹配

    有時(shí)候，我們需要用正則表達(dá)式來分析一個(gè)計(jì)算式中的括號(hào)配對(duì)情況。比如，使用表達(dá)式 “( [^)]* )” 或者 “( .*? )” 可以匹配一對(duì)小括號(hào)。但是如果括號(hào)內(nèi)還嵌有一層括號(hào)的話，如 “( ( ) )”，則這種寫法將不能夠匹配正確，得到的結(jié)果是 “( ( )” 。類似情況的還有 HTML 中支持嵌套的標(biāo)簽如 “<font> </font>” 等。本節(jié)將要討論的是，想辦法把有嵌套的的成對(duì)括號(hào)或者成對(duì)標(biāo)簽匹配出來。

匹配未知層次的嵌套：

    有的正則表達(dá)式引擎，專門針對(duì)這種嵌套提供了支持。并且在?？臻g允許的情況下，能夠支持任意未知層次的嵌套：比如 Perl，PHP，GRETA 等。在 PHP 和 GRETA 中，表達(dá)式中使用 “(?R)” 來表示嵌套部分。

    匹配嵌套了未知層次的 “小括號(hào)對(duì)” 的表達(dá)式寫法如下：”(  ([^()]  |  (?R))*  )”。

    [Perl 和 PHP 的示例代碼]

匹配有限層次的嵌套：

    對(duì)于不支持嵌套的正則表達(dá)式引擎，只能通過一定的辦法來匹配有限層次的嵌套。思路如下：

    第一步，寫一個(gè)不能支持嵌套的表達(dá)式：”( [^()]* )”，”<font>((?!</?font>).)*</font>”。這兩個(gè)表達(dá)式在匹配有嵌套的文本時(shí)，只匹配最內(nèi)層。

    第二步，寫一個(gè)可匹配嵌套一層的表達(dá)式：”( ([^()] | ( [^()]* ))* )”。這個(gè)表達(dá)式在匹配嵌套層數(shù)大于一時(shí)，只能匹配最里面的兩層，同時(shí)，這個(gè)表達(dá)式也能匹配沒有嵌套的文本或者嵌套的最里層。

    匹配嵌套一層的 “<font>” 標(biāo)簽，表達(dá)式為：”<font>((?!</?font>).|(<font>((?!</?font>).)*</font>))*</font>”。這個(gè)表達(dá)式在匹配 “<font>” 嵌套層數(shù)大于一的文本時(shí)，只匹配最里面的兩層。

    第三步，找到匹配嵌套(n)層的表達(dá)式 與 嵌套(n-1)層的表達(dá)式之間的關(guān)系。比如，能夠匹配嵌套(n)層的表達(dá)式為：

    [標(biāo)記頭]  ( [匹配 [標(biāo)記頭] 和 [標(biāo)記尾] 之外的表達(dá)式] | [匹配 n-1 層的表達(dá)式] )*  [標(biāo)記尾]

    回頭來看前面編寫的“可匹配嵌套一層”的表達(dá)式：

    第四步，依此類推，可以編寫出匹配有限(n)層的表達(dá)式。這種方式寫出來的表達(dá)式，雖然看上去很長(zhǎng)，但是這種表達(dá)式經(jīng)過編譯后，匹配效率仍然是很高的。

2. 非貪婪匹配的效率

    可能有不少的人和我一樣，有過這樣的經(jīng)歷：當(dāng)我們要匹配類似 “<td>內(nèi)容</td>” 或者 “[b]加粗[/b]” 這樣的文本時(shí)，我們根據(jù)正向預(yù)搜索功能寫出這樣的表達(dá)式：”<td>([^<]|<(?!/td>))*</td>” 或者 “<td>((?!</td>).)*</td>”。

    當(dāng)發(fā)現(xiàn)非貪婪匹配之時(shí)，恍然大悟，同樣功能的表達(dá)式可以寫得如此簡(jiǎn)單：”<td>.*?</td>”。頓時(shí)間如獲至寶，凡是按邊界匹配的地方，盡量使用簡(jiǎn)捷的非貪婪匹配 “.*?”。特別是對(duì)于復(fù)雜的表達(dá)式來說，采用非貪婪匹配 “.*?” 寫出來的表達(dá)式的確是簡(jiǎn)練了許多。

    然而，當(dāng)一個(gè)表達(dá)式中，有多個(gè)非貪婪匹配時(shí)，或者多個(gè)未知匹配次數(shù)的表達(dá)式時(shí)，這個(gè)表達(dá)式將可能存在效率上的陷阱。有時(shí)候，匹配速度慢得莫名奇妙，甚至開始懷疑正則表達(dá)式是否實(shí)用。

效率陷阱的產(chǎn)生：

    在本站基礎(chǔ)文章里，對(duì)非貪婪匹配的描述中說到：“如果少匹配就會(huì)導(dǎo)致整個(gè)表達(dá)式匹配失敗的時(shí)候，與貪婪模式類似，非貪婪模式會(huì)最小限度的再匹配一些，以使整個(gè)表達(dá)式匹配成功?！?

    具體的匹配過程是這樣的：

1. “非貪婪部分” 先匹配最少次數(shù)，然后嘗試匹配 “右側(cè)的表達(dá)式”。
2. 如果右側(cè)的表達(dá)式匹配成功，則整個(gè)表達(dá)式匹配結(jié)束。如果右側(cè)表達(dá)式匹配失敗，則 “非貪婪部分” 將增加匹配一次，然后再嘗試匹配 “右側(cè)的表達(dá)式”。
3. 如果右側(cè)的表達(dá)式又匹配失敗，則 “非貪婪部分” 將再增加匹配一次。再嘗試匹配 “右側(cè)的表達(dá)式”。
4. 依此類推，最后得到的結(jié)果是 “非貪婪部分” 以盡可能少的匹配次數(shù)，使整個(gè)表達(dá)式匹配成功?；蛘咦罱K仍然匹配失敗。

    當(dāng)一個(gè)表達(dá)式中有多個(gè)非貪婪匹配，以表達(dá)式 “d(w+?)d(w+?)z” 為例，對(duì)于第一個(gè)括號(hào)中的 “w+?” 來說，右邊的 “d(w+?)z” 屬于它的 “右側(cè)的表達(dá)式”，對(duì)于第二個(gè)括號(hào)中的 “w+?” 來說，右邊的 “z” 屬于它的 “右側(cè)的表達(dá)式”。

    當(dāng) “z” 匹配失敗時(shí)，第二個(gè) “w+?” 會(huì) “增加匹配一次”，再嘗試匹配 “z”。如果第二個(gè) “w+?” 無論怎樣 “增加匹配次數(shù)”，直至整篇文本結(jié)束，”z” 都不能匹配，那么表示 “d(w+?)z” 匹配失敗，也就是說第一個(gè) “w+?” 的 “右側(cè)” 匹配失敗。此時(shí)，第一個(gè) “w+?” 會(huì)增加匹配一次，然后再進(jìn)行 “d(w+?)z” 的匹配。循環(huán)前面所講的過程，直至第一個(gè) “w+?” 無論怎么 “增加匹配次數(shù)”，后邊的 “d(w+?)z” 都不能匹配時(shí)，整個(gè)表達(dá)式才宣告匹配失敗。

    其實(shí)，為了使整個(gè)表達(dá)式匹配成功，貪婪匹配也會(huì)適當(dāng)?shù)摹白尦觥币呀?jīng)匹配的字符。因此貪婪匹配也有類似的情況。當(dāng)一個(gè)表達(dá)式中有較多的未知匹配次數(shù)的表達(dá)式時(shí)，為了讓整個(gè)表達(dá)式匹配成功，各個(gè)貪婪或非貪婪的表達(dá)式都要進(jìn)行嘗試減少或增加匹配次數(shù)，由此容易形成一個(gè)大循環(huán)的嘗試，造成了很長(zhǎng)的匹配時(shí)間。本文之所以稱之為“陷阱”，因?yàn)檫@種效率問題往往不易察覺。

    舉例：”d(w+?)d(w+?)d(w+?)z” 匹配 “ddddddddddd…” 時(shí)，將花費(fèi)較長(zhǎng)一段時(shí)間才能判斷出匹配失敗。

效率陷阱的避免：

    避免效率陷阱的原則是：避免“多重循環(huán)”的“嘗試匹配”。并不是說非貪婪匹配就是不好的，只是在運(yùn)用非貪婪匹配的時(shí)候，需要注意避免過多“循環(huán)嘗試”的問題。

    情況一：對(duì)于只有一個(gè)非貪婪或者貪婪匹配的表達(dá)式來說，不存在效率陷阱。也就是說，要匹配類似 “<td> 內(nèi)容 </td>” 這樣的文本，表達(dá)式 “<td>([^<]|<(?!/td>))*</td>” 和 “<td>((?!</td>).)*</td>” 和 “<td>.*?</td>” 的效率是完全相同的。

    情況二：如果一個(gè)表達(dá)式中有多個(gè)未知匹配次數(shù)的表達(dá)式，應(yīng)防止進(jìn)行不必要的嘗試匹配。

    比如，對(duì)表達(dá)式 “<script language='(.*?)’>(.*?)</script>” 來說，如果前面部分表達(dá)式在遇到 “<script language=’vbscript’>” 時(shí)匹配成功后，而后邊的 “(.*?)</script>” 卻匹配失敗，將導(dǎo)致第一個(gè) “.*?” 增加匹配次數(shù)再嘗試。而對(duì)于表達(dá)式真正目的，讓第一個(gè) “.*?” 增加匹配成“vbscript’>”是不對(duì)的，因此這種嘗試是不必要的嘗試。

    因此，對(duì)依靠邊界來識(shí)別的表達(dá)式，不要讓未知匹配次數(shù)的部分跨過它的邊界。前面的表達(dá)式中，第一個(gè) “.*?” 應(yīng)該改寫成 “[^’]*”。后邊那個(gè) “.*?” 的右邊再?zèng)]有未知匹配次數(shù)的表達(dá)式，因此這個(gè)非貪婪匹配沒有效率陷阱。于是，這個(gè)匹配腳本塊的表達(dá)式，應(yīng)該寫成：”<script language='([^’]*)’>(.*?)</script>” 更好。