Chinaunix首页 | 论坛 | 博客
  • 博客访问: 646951
  • 博文数量: 110
  • 博客积分: 8090
  • 博客等级: 中将
  • 技术积分: 1217
  • 用 户 组: 普通用户
  • 注册时间: 2005-10-10 15:32
文章分类

全部博文(110)

文章存档

2017年(2)

2015年(1)

2014年(1)

2013年(1)

2012年(1)

2011年(1)

2008年(7)

2007年(27)

2006年(45)

2005年(24)

我的朋友

分类:

2006-06-08 16:40:15

精彩来自:  
1. 表达式的递归匹配

    有时候,我们需要用正则表达式来分析一个计算式中的括号配对情况。比如,。但是如果,则这种写法将不能够匹配正确,得到的结果是 "( ( )" 。类似情况的还有 HTML 中支持嵌套的标签如 " " 等。本节将要讨论的是,想办法把有嵌套的的成对括号或者成对标签匹配出来。

匹配未知层次的嵌套:

    有的正则表达式引擎,专门针对这种嵌套提供了支持。并且在栈空间允许的情况下,能够支持任意未知层次的嵌套:比如 Perl,PHP,GRETA 等。在 PHP 和 GRETA 中,表达式中使用 "(?R)" 来表示嵌套部分。

    匹配嵌套了未知层次的 "小括号对" 的表达式写法如下:"\(  ([^()]  |  (?R))*  \)"。

    []

匹配有限层次的嵌套:

    对于不支持嵌套的正则表达式引擎,只能通过一定的办法来匹配有限层次的嵌套。思路如下:

    第一步,写一个不能支持嵌套的表达式:"",""。 这两个表达式在匹配有嵌套的文本时,只匹配最内层。

    第二步,写一个可匹配嵌套一层的表达式:""。这个表达式在匹配嵌套层数大于一时,只能匹配最里面的两层,同时,这个表达式或者嵌套的最里层。

    匹配嵌套一层的 "" 标签,表达式为:""。这个表达式在匹配 "" 嵌套层数大于一的文本时,只匹配最里面的两层。

    第三步,找到匹配嵌套(n)层的表达式 与 嵌套(n-1)层的表达式之间的关系。比如,能够匹配嵌套(n)层的表达式为:

    [标记头]  ( [匹配 [标记头] 和 [标记尾] 之外的表达式] | [匹配 n-1 层的表达式] )*  [标记尾]

    回头来看前面编写的“可匹配嵌套一层”的表达式:

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

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


2. 非贪婪匹配的效率

    可能有不少的人和我一样,有过这样的经历:当我们要匹配类似 "内容" 或者 "[b]加粗[/b]" 这样的文本时,我们根据功能写出这样的表达式:"" 或者 ""。

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

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

效率陷阱的产生:

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

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

  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" 都不能匹配时,整个表达式才宣告匹配失败。

    其实,为了使整个表达式匹配成功,也会适当的“让出”已经匹配的字符。因此贪婪匹配也有类似的情况。当一个表达式中有较多的的表达式时,为了让整个表达式匹配成功,各个贪婪或非贪婪的表达式都要进行尝试减少或增加匹配次数,由此容易形成一个大循环的尝试,造成了很长的匹配时间。本文之所以称之为“陷阱”,因为这种效率问题往往不易察觉。

    举例:,将花费较长一段时间才能判断出匹配失败 。

效率陷阱的避免:

    避免效率陷阱的原则是:避免“多重循环”的“尝试匹配”。并不是说非贪婪匹配就是不好的,只是在运用非贪婪匹配的时候,需要注意避免过多“循环尝试”的问题。

    情况一:对于只有一个非贪婪或者贪婪匹配的表达式来说,不存在效率陷阱。也就是说,要匹配类似 " 内容 " 这样的文本,表达式 "" 和 "" 和 "" 的效率是完全相同的。

    情况二:如果一个表达式中有多个的表达式,应防止进行不必要的尝试匹配。

    比如,对表达式 "" 来说, 如果前面部分表达式在遇到 "" 却匹配失败,将导致第一个 ".*?" 增加匹配次数再尝试。而对于表达式真正目的,让第一个 ".*?" 增加匹配成“vbscript'>”是不对的,因此这种尝试是不必要的尝试。

    因此,对依靠边界来识别的表达式,不要让的部分跨过它的边界。前面的表达式中,第一个 ".*?" 应该改写成 "[^']*"。后边那个 ".*?" 的右边再没有的表达式,因此这个非贪婪匹配没有效率陷阱。于是,这个匹配脚本块的表达式,应该写成:"" 更好。

阅读(1538) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~