引言

[b][url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%5C%28%5B%5E%29%5D%2A%5C%29&txt=2+-+%28+b+%2B+3+%29&dlt=0]使用表达式 "\( [^)]* \)" 或者 "\( .*? \)" 可以匹配一对小括号[/url]。但是如果[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%5C%28%5B%5E%29%5D*%5C%29&txt=2%20-%20%28%20b%20%2B%203%20-%20%28%20c%20-%20x%20%29%20%29&dlt=0]括号内还嵌有一层括号的话，如 "( ( ) )"[/url]，则这种写法将不能够匹配正确，得到的结果是 "( ( )" 。类似情况的还有 HTML 中支持嵌套的标签如 "<font> </font>" 等。本节将要讨论的是，想办法把有嵌套的的成对括号或者成对标签匹配出来。 [i]匹配未知层次的嵌套：[/i]     有的正则表达式引擎，专门针对这种嵌套提供了支持。并且在栈空间允许的情况下，能够支持任意未知层次的嵌套：比如 Perl，PHP，GRETA 等。在 PHP 和 GRETA 中，表达式中使用 "(?R)" 来表示嵌套部分。     匹配嵌套了未知层次的 "小括号对" 的表达式写法如下："\(  ([^()]  |  (?R))*  \)"。     [[url=http://www.nk975.com/sswater/myref/index.asp?id=18]Perl 和 PHP 的示例代码[/url]] [i]匹配有限层次的嵌套：[/i]     对于不支持嵌套的正则表达式引擎，只能通过一定的办法来匹配有限层次的嵌套。思路如下：     第一步，写一个[b]不能支持嵌套[/b]的表达式："[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%5C%28%5B%5E%28%29%5D*%5C%29&txt=2%20-%20%28%20b%20%2B%203%20-%20%28%20c%20-%20x%20%29%20%29&dlt=0]\( [^()]* \)[/url]"，"[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%3Cfont%3E%28%28%3F%21%3C/%3Ffont%3E%29.%29*%3C/font%3E&txt=aaa%20%3Cfont%3E%20%3Cbr%3E%20%3Cfont%3E%20%3Chr%3E%20%3C/font%3E%20x%20%3C/font%3E&dlt=0]<font>((?!</?font>).)*</font>[/url]"。这两个表达式在匹配有嵌套的文本时，只匹配最内层。     第二步，写一个[b]可匹配嵌套一层[/b]的表达式："[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%5C%28%28%5B%5E%28%29%5D%7C%5C%28%28%5B%5E%28%29%5D%29*%5C%29%29*%5C%29&txt=%28%202%20-%20%28%20b%20%2B%203%20-%20%28%20c%20-%20x%20%29%20%29%20%29&dlt=1]\( ([^()] | \( [^()]* \))* \)[/url]"。这个表达式在匹配嵌套层数大于一时，只能匹配最里面的两层，同时，这个表达式[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%5C%28%28%5B%5E%28%29%5D%7C%5C%28%28%5B%5E%28%29%5D%29*%5C%29%29*%5C%29&txt=2%20-%20%28%20b%20%2B%203%20%29&dlt=0]也能匹配没有嵌套的文本[/url]或者嵌套的最里层。     匹配嵌套一层的 "<font>" 标签，表达式为："[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%3Cfont%3E%28%28%3F%21%3C/%3Ffont%3E%29.%7C%28%3Cfont%3E%28%28%3F%21%3C/%3Ffont%3E%29.%29*%3C/font%3E%29%29*%3C/font%3E&txt=%3Cfont%3E%20%3Cfont%3E%20a%20%3Cfont%3E%20%3Chr%3E%20%3C/font%3E%20x%20%3C/font%3E%20%3C/font%3E&dlt=6]<font>((?!</?font>).|(<font>((?!</?font>).)*</font>))*</font>[/url]"。这个表达式在匹配 "<font>" 嵌套层数大于一的文本时，只匹配最里面的两层。     第三步，找到匹配嵌套(n)层的表达式 与 嵌套(n-1)层的表达式之间的关系。比如，能够匹配嵌套(n)层的表达式为：     [标记头]  ( [匹配 [标记头] 和 [标记尾] 之外的表达式] | [匹配 n-1 层的表达式] )*  [标记尾]     回头来看前面编写的“可匹配嵌套一层”的表达式：

	\(	(	[^()]	|	\(([^()])*\)	)*	\)
	<font>	(	(?!</?font>).	|	(<font>((?!</?font>).)*</font>)	)*	</font>
	PHP 和 GRETA 的简便之处在于，匹配嵌套(n-1)层的表达式用 (?R) 表示：
	\(	(	[^()]	|	(?R)	)*	\)

    第四步，依此类推，可以编写出匹配有限(n)层的表达式。这种方式写出来的表达式，虽然看上去很长，但是这种表达式经过编译后，匹配效率仍然是很高的。

---

[b][url=http://www.cnlei.org/blog/article.asp?id=173#forward]正向预搜索[/url][/b]功能写出这样的表达式："[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%3Ctd%3E%28%5B%5E%3C%5D%7C%3C%28%3F%21/td%3E%29%29*%3C/td%3E&txt=%u5185%u5BB91%20%3Ctd%3E%20%u5185%u5BB92%20%3C/td%3E%20%3Ctd%3E%20%u5185%u5BB93%20%3C/td%3E&dlt=0]<td>([^<]|<(?!/td>))*</td>[/url]" 或者 "[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%3Ctd%3E%28%28%3F%21%3C/td%3E%29.%29*%3C/td%3E&txt=%u5185%u5BB91%20%3Ctd%3E%20%u5185%u5BB92%20%3C/td%3E%20%3Ctd%3E%20%u5185%u5BB93%20%3C/td%3E&dlt=0]<td>((?!</td>).)*</td>[/url]"。     当发现[b][url=http://www.cnlei.org/blog/article.asp?id=173#reluctant]非贪婪匹配[/url][/b]之时，恍然大悟，同样功能的表达式可以写得如此简单："[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%3Ctd%3E.*%3F%3C/td%3E&txt=%u5185%u5BB91%20%3Ctd%3E%20%u5185%u5BB92%20%3C/td%3E%20%3Ctd%3E%20%u5185%u5BB93%20%3C/td%3E&dlt=0]<td>.*?</td>[/url]"。顿时间如获至宝，凡是按边界匹配的地方，尽量使用简捷的非贪婪匹配 ".*?"。特别是对于复杂的表达式来说，采用非贪婪匹配 ".*?" 写出来的表达式的确是简练了许多。     然而，当一个表达式中，有多个非贪婪匹配时，或者多个[b][url=http://www.cnlei.org/blog/article.asp?id=173#times]未知匹配次数[/url][/b]的表达式时，这个表达式将可能存在效率上的陷阱。有时候，匹配速度慢得莫名奇妙，甚至开始怀疑正则表达式是否实用。 [i]效率陷阱的产生：[/i]     在本站[url=http://www.cnlei.org/blog/article.asp?id=173]基础文章[/url]里，对[url=http://www.cnlei.org/blog/article.asp?id=173#reluctant]非贪婪匹配[/url]的描述中说到：“如果少匹配就会导致整个表达式匹配失败的时候，与贪婪模式类似，非贪婪模式会最小限度的再匹配一些，以使整个表达式匹配成功。”     具体的匹配过程是这样的： [list=1] [*]"非贪婪部分" 先匹配最少次数，然后尝试匹配 "右侧的表达式"。 [/*][*]如果右侧的表达式匹配成功，则整个表达式匹配结束。如果右侧表达式匹配失败，则 "非贪婪部分" 将增加匹配一次，然后再尝试匹配 "右侧的表达式"。 [/*][*]如果右侧的表达式又匹配失败，则 "非贪婪部分" 将再增加匹配一次。再尝试匹配 "右侧的表达式"。 [/*][*]依此类推，最后得到的结果是 "非贪婪部分" 以尽可能少的匹配次数，使整个表达式匹配成功。或者最终仍然匹配失败。 [/*][/list]     当一个表达式中有多个非贪婪匹配，以表达式 "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" 都不能匹配时，整个表达式才宣告匹配失败。     其实，为了使整个表达式匹配成功，[b][url=http://www.cnlei.org/blog/article.asp?id=173#reluctant]贪婪匹配[/url][/b]也会适当的“让出”已经匹配的字符。因此贪婪匹配也有类似的情况。当一个表达式中有较多的[b][url=http://www.cnlei.org/blog/article.asp?id=173#times]未知匹配次数[/url][/b]的表达式时，为了让整个表达式匹配成功，各个贪婪或非贪婪的表达式都要进行尝试减少或增加匹配次数，由此容易形成一个大循环的尝试，造成了很长的匹配时间。本文之所以称之为“陷阱”，因为这种效率问题往往不易察觉。     举例：[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=d%28%5Cw%2B%3F%29d%28%5Cw%2B%3F%29d%28%5Cw%2B%3F%29z&txt=dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd&dlt=0]"d(\w+?)d(\w+?)d(\w+?)z" 匹配 "ddddddddddd..." 时[/url]，将花费较长一段时间才能判断出匹配失败。 [i]效率陷阱的避免：[/i]     避免效率陷阱的原则是：避免“多重循环”的“尝试匹配”。并不是说非贪婪匹配就是不好的，只是在运用非贪婪匹配的时候，需要注意避免过多“循环尝试”的问题。     情况一：对于只有一个非贪婪或者贪婪匹配的表达式来说，不存在效率陷阱。也就是说，要匹配类似 "<td> 内容 </td>" 这样的文本，表达式 "[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%3Ctd%3E%28%5B%5E%3C%5D%7C%3C%28%3F%21/td%3E%29%29*%3C/td%3E&txt=%u5185%u5BB91%20%3Ctd%3E%20%u5185%u5BB92%20%3C/td%3E%20%3Ctd%3E%20%u5185%u5BB93%20%3C/td%3E&dlt=0]<td>([^<]|<(?!/td>))*</td>[/url]" 和 "[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%3Ctd%3E%28%28%3F%21%3C/td%3E%29.%29*%3C/td%3E&txt=%u5185%u5BB91%20%3Ctd%3E%20%u5185%u5BB92%20%3C/td%3E%20%3Ctd%3E%20%u5185%u5BB93%20%3C/td%3E&dlt=0]<td>((?!</td>).)*</td>[/url]" 和 "[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%3Ctd%3E.*%3F%3C/td%3E&txt=%u5185%u5BB91%20%3Ctd%3E%20%u5185%u5BB92%20%3C/td%3E%20%3Ctd%3E%20%u5185%u5BB93%20%3C/td%3E&dlt=0]<td>.*?</td>[/url]" 的效率是完全相同的。     情况二：如果一个表达式中有多个[b][url=http://www.cnlei.org/blog/article.asp?id=173#times]未知匹配次数[/url][/b]的表达式，应防止进行不必要的尝试匹配。     比如，对表达式 "[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%3Cscript%20language%3D%22%28.*%3F%29%22%3E%28.*%3F%29%3C/script%3E&txt=%3Cscript%20language%3D%22javascript%22%3E%20var%20i%3D0%3B%20%3C/script%3E&dlt=0]<script language='(.*?)'>(.*?)</script>[/url]" 来说，如果前面部分表达式在遇到 "<script language='vbscript'>" 时匹配成功后，而后边的 "(.*?)</script>" 却匹配失败，将导致第一个 ".*?" 增加匹配次数再尝试。而对于表达式真正目的，让第一个 ".*?" 增加匹配成“vbscript'>”是不对的，因此这种尝试是不必要的尝试。     因此，对依靠边界来识别的表达式，不要让[url=http://www.cnlei.org/blog/article.asp?id=173#times]未知匹配次数[/url]的部分跨过它的边界。前面的表达式中，第一个 ".*?" 应该改写成 "[^']*"。后边那个 ".*?" 的右边再没有[url=http://www.cnlei.org/blog/article.asp?id=173#times]未知匹配次数[/url]的表达式，因此这个非贪婪匹配没有效率陷阱。于是，这个匹配脚本块的表达式，应该写成："[url=http://www.cnlei.org/blog/example/regexlab/workshop.asp?pat=%3Cscript%20language%3D%22%28%5B%5E%22%5D*%29%22%3E%28.*%3F%29%3C/script%3E&txt=%3Cscript%20language%3D%22javascript%22%3E%20var%20i%3D0%3B%20%3C/script%3E&dlt=0]<script language='([^']*)'>(.*?)</script>[/url]" 更好。