正則表達(dá)式話題

熱門標(biāo)簽：湖南企業(yè)智能外呼系統(tǒng)供應(yīng)商 高德地圖標(biāo)注短信簽約 百音電話機(jī)器人 電銷機(jī)器人公司簡(jiǎn)介 福州工作銷售電話機(jī)器人 RO地圖標(biāo)注app 錫林郭勒盟地圖標(biāo)注位置 自制電銷機(jī)器人 知名的電話機(jī)器人

From: www.regexlab.com

引言

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

---

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

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

匹配未知層次的嵌套：

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

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

    [Perl 和 PHP 的示例代碼]

匹配有限層次的嵌套：

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

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

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

    匹配嵌套一層的 "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)記尾]

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

	\(	(	[^()]	|	\(([^()])*\)	)*	\)
	font>	(	(?!/?font>).	|	(font>((?!/?font>).)*/font>)	)*	/font>
	PHP 和 GRETA 的簡(jiǎn)便之處在于，匹配嵌套(n-1)層的表達(dá)式用 (?R) 表示：
	\(	(	[^()]	|	(?R)	)*	\)

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

---

2. 非貪婪匹配的效率

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

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

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

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

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

    具體的匹配過(guò)程是這樣的：

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+?" 來(lái)說(shuō)，右邊的 "d(\w+?)z" 屬于它的 "右側(cè)的表達(dá)式"，對(duì)于第二個(gè)括號(hào)中的 "\w+?" 來(lái)說(shuō)，右邊的 "z" 屬于它的 "右側(cè)的表達(dá)式"。

    當(dāng) "z" 匹配失敗時(shí)，第二個(gè) "\w+?" 會(huì) "增加匹配一次"，再嘗試匹配 "z"。如果第二個(gè) "\w+?" 無(wú)論怎樣 "增加匹配次數(shù)"，直至整篇文本結(jié)束，"z" 都不能匹配，那么表示 "d(\w+?)z" 匹配失敗，也就是說(shuō)第一個(gè) "\w+?" 的 "右側(cè)" 匹配失敗。此時(shí)，第一個(gè) "\w+?" 會(huì)增加匹配一次，然后再進(jìn)行 "d(\w+?)z" 的匹配。循環(huán)前面所講的過(guò)程，直至第一個(gè) "\w+?" 無(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)檫@種效率問(wèn)題往往不易察覺(jué)。

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

效率陷阱的避免：

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

    情況一：對(duì)于只有一個(gè)非貪婪或者貪婪匹配的表達(dá)式來(lái)說(shuō)，不存在效率陷阱。也就是說(shuō)，要匹配類似 "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>" 來(lái)說(shuō)，如果前面部分表達(dá)式在遇到 "script language='vbscript'>" 時(shí)匹配成功后，而后邊的 "(.*?)/script>" 卻匹配失敗，將導(dǎo)致第一個(gè) ".*?" 增加匹配次數(shù)再嘗試。而對(duì)于表達(dá)式真正目的，讓第一個(gè) ".*?" 增加匹配成“vbscript'>”是不對(duì)的，因此這種嘗試是不必要的嘗試。

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