正则表达式的使用话题

【 tulaoshi.com - Web开发 】

本文将逐步讨论一些正则表达式的使用话题。本文为本站基础篇之后的扩展，在阅读本文之前，建议先阅读正则表达式参考文档一文。

有时候，我们需要用正则表达式来分析一个计算式中的括号配对情况。比如，使用表达式 "( [^)]* )" 或者 "( .*？ )" 可以匹配一对小括号。但是如果括号内还嵌有一层括号的话，如 "( ( ) )"，则这种写法将不能够匹配正确，得到的结果是 "( ( )" 。类似情况的还有 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)层的表达式。这种方式写出来的表达式，虽然看上去很长，但是这种表达式经过编译后，匹配效率仍然是很高的。

可能有不少的人和我一样，有过这样的经历：当我们要匹配类似 "td内容/td" 或者 "[b]加粗[/b]" 这样的文本时，我们根据正向预搜索功能写出这样的表达式："td([^]|(？!/td))*/td" 或者 "td((？!/td).)*/td"。

当发现非贪婪匹配之时，恍然大悟，同样功能的表达式可以写得如此简单："td.*？/td"。顿时间如获至宝，凡是按边界匹配的地方，尽量使用简捷的非贪婪匹配 ".*？"。特别是对于复杂的表达式来说，采用非贪婪匹配 ".*？" 写出来的表达式的确是简练了许多。

然而，当一个表达式中，有多个非贪婪匹配时，或者多个未知匹配次数的表达式时，这个表达式将可能存在效率上的陷阱。有时候，匹配速度慢得莫名奇妙，甚至开始怀疑正则表达式是否实用。

效率陷阱的产生：

在本站基础文章里，对非贪婪匹配的描述中说到：如果少匹配就会导致整个表达式匹配失败的时候，与贪婪模式类似，非贪婪模式会最小限度的再匹配一些，以使整个表达式匹配成功。

具体的匹配过程是这样的：

当一个表达式中有多个非贪婪匹配，以表达式 "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" 更好。