From: www.regexlab.com

引言

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

1. 表達式的遞歸匹配

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

匹配未知層次的嵌套：

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

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

    [Perl 和 PHP 的示例代碼]

匹配有限層次的嵌套：

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

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

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

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

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

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

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

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

2. 非貪婪匹配的效率

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

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

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

效率陷阱的產生：

    在本站基礎文章里，對非貪婪匹配的描述中說到：“如果少匹配就會導致整個表達式匹配失敗的時候，與貪婪模式類似，非貪婪模式會最小限度的再匹配一些，以使整個表達式匹配成功。”

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

1. “非貪婪部分” 先匹配最少次數，然后嘗試匹配 “右側的表達式”。
2. 如果右側的表達式匹配成功，則整個表達式匹配結束。如果右側表達式匹配失敗，則 “非貪婪部分” 將增加匹配一次，然后再嘗試匹配 “右側的表達式”。
3. 如果右側的表達式又匹配失敗，則 “非貪婪部分” 將再增加匹配一次。再嘗試匹配 “右側的表達式”。
4. 依此類推，最后得到的結果是 “非貪婪部分” 以盡可能少的匹配次數，使整個表達式匹配成功。或者最終仍然匹配失敗。

    當一個表達式中有多個非貪婪匹配，以表達式 “d(w+?)d(w+?)z” 為例，對于第一個括號中的 “w+?” 來說，右邊的 “d(w+?)z” 屬于它的 “右側的表達式”，對于第二個括號中的 “w+?” 來說，右邊的 “z” 屬于它的 “右側的表達式”。

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

    其實，為了使整個表達式匹配成功，貪婪匹配也會適當的“讓出”已經匹配的字符。因此貪婪匹配也有類似的情況。當一個表達式中有較多的未知匹配次數的表達式時，為了讓整個表達式匹配成功，各個貪婪或非貪婪的表達式都要進行嘗試減少或增加匹配次數，由此容易形成一個大循環的嘗試，造成了很長的匹配時間。本文之所以稱之為“陷阱”，因為這種效率問題往往不易察覺。

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

效率陷阱的避免：

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

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

    情況二：如果一個表達式中有多個未知匹配次數的表達式，應防止進行不必要的嘗試匹配。

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

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