正则表达式话题
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)层的表达式。这种方式写出来的表达式,虽然看上去很长,但是这种表达式经过编译后,匹配效率仍然是很高的。
2.非贪婪匹配的效率
可能有不少的人和我一样,有过这样的经历:当我们要匹配类似"<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>"的效率是完全相同的。
情况二:如果一个表达式中有多个未知匹配次数的表达式,应防止进行不必要的尝试匹配。
比如,对表达式"<scriptlanguage="(.*?)">(.*?)</script>"来说,如果前面部分表达式在遇到"<scriptlanguage="vbscript">"时匹配成功后,而后边的"(.*?)</script>"却匹配失败,将导致第一个".*?"增加匹配次数再尝试。而对于表达式真正目的,让第一个".*?"增加匹配成“
因此,对依靠边界来识别的表达式,不要让未知匹配次数的部分跨过它的边界。前面的表达式中,第一个".*?"应该改写成"[^"]*"。后边那个".*?"的右边再没有未知匹配次数的表达式,因此这个非贪婪匹配没有效率陷阱。于是,这个匹配脚本块的表达式,应该写成:"<scriptlanguage="([^"]*)">(.*?)</script>"更好。
相关文章
- 正则表达式语法-JavaScript中的正则表达式详解
- 前端表单验证常用的11个JS正则表达式
- MySQL正则表达式REGEXP使用详解
- 常用正则表达式总结详解程序员
- ABAP 正则表达式(Regular Expressions)详解编程语言
- abap中,利用正则表达式删除字符串中的字母详解编程语言
- 表达式使用rm命令操作Linux中的正则表达式(rmlinux正则)
- 使用MySQL正则表达式进行字符串提取(mysql正则提取字符串)
- Oracle10G:PL/SQL正规表达式(正则表达式)手册
- 常见的数字验证正则表达式整理
- python正则表达式修复网站文章字体不统一的解决方法
- 使用正则表达式匹配tsql注释语句
- python正则表达式re模块详细介绍
- 正则表达式提取img的src