引言
本文将逐步讨论
些正则表达式
使用话题
本文为本站基础篇的后扩展
在阅读本文的前建议先阅读正则表达式参考文档文1. 表达式递归匹配
有时候我们需要用正则表达式来分析个计算式中括号配对情况比如使用表达式 "\( [^)]* \)" 或者 "\( .*? \)" 可以匹配对小括号但是如果括号内还嵌有层括号话如 "( ( ) )"则这种写法将不能够匹配正确得到结果是 "( ( )" 类似情况还有 HTML 中支持嵌套标签如 "<font> </font>" 等本节将要讨论是想办法把有嵌套成对括号或者成对标签匹配出来匹配未知层次
嵌套:有
正则表达式引擎专门针对这种嵌套提供了支持并且在栈空间允许情况下能够支持任意未知层次嵌套:比如 PerlPHPGRETA 等在 PHP 和 GRETA 中表达式中使用 "(?R)" 来表示嵌套部分匹配嵌套了未知层次
"小括号对" 表达式写法如下:"\( ([^
] | (?R))* \)"[Perl 和 PHP
举例代码]匹配有限层次
嵌套:对于不支持嵌套
正则表达式引擎只能通过定办法来匹配有限层次嵌套思路如下:第
步写个不能支持嵌套表达式:"\( [^]* \)""<font>((?!</?font>).)*</font>"这两个表达式在匹配有嵌套文本时只匹配最内层第 2步
写个可匹配嵌套层表达式:"\( ([^] | \( [^]* \))* \)"这个表达式在匹配嵌套层数大于时只能匹配最里面两层同时这个表达式也能匹配没有嵌套文本或者嵌套最里层匹配嵌套
层 "<font>" 标签表达式为:"<font>((?!</?font>).|(<font>((?!</?font>).)*</font>))*</font>"这个表达式在匹配 "<font>" 嵌套层数大于文本时只匹配最里面两层第 3步
找到匹配嵌套(n)层表达式 和 嵌套(n-1)层表达式的间关系比如能够匹配嵌套(n)层表达式为:[标记头] ( [匹配 [标记头] 和 [标记尾] 的外
表达式] | [匹配 n-1 层表达式] )* [标记尾]回头来看前面编写
“可匹配嵌套层”表达式:\( ( [^
]
|
\(([^])*\)
)*
\) <font> ( (?!</?font>). | (<font>((?!</?font>).)*</font>) )* </font>
PHP 和 GRETA
简便的处在于匹配嵌套(n-1)层表达式用 (?R) 表示: \( ( [^
]
|
(?R)
)*
\) 第 4步
依此类推可以编写出匹配有限(n)层表达式这种方式写出来表达式虽然看上去很长但是这种表达式经过编译后匹配效率仍然是很高2. 非贪婪匹配效率
可能有不少人和我样有过这样经历:当我们要匹配类似 "<td>内容</td>" 或者 "[b]加粗[/b]" 这样文本时我们根据正向预搜索功能写出这样表达式:"<td>([^<]|<(?!/td>))*</td>" 或者 "<td>((?!</td>).)*</td>"当发现非贪婪匹配的时
恍然大悟同样功能表达式可以写得如此简单:"<td>.*?</td>"顿时间如获至宝凡是按边界匹配地方尽量使用简捷非贪婪匹配 ".*?"特别是对于复杂表达式来说采用非贪婪匹配 ".*?" 写出来表达式确是简练了许多然而
当个表达式中有多个非贪婪匹配时或者多个未知匹配次数表达式时这个表达式将可能存在效率上陷阱有时候匹配速度慢得莫名奇妙甚至开始怀疑正则表达式是否实用效率陷阱
产生:在本站基础文章里
对非贪婪匹配描述中说到:“如果少匹配就会导致整个表达式匹配失败时候和贪婪模式类似非贪婪模式会最小限度再匹配些以使整个表达式匹配成功” 具体
匹配过程是这样:- "非贪婪部分" 先匹配最少次数然后尝试匹配 "右侧表达式"
- 如果右侧表达式匹配成功则整个表达式匹配结束如果右侧表达式匹配失败则 "非贪婪部分" 将增加匹配次然后再尝试匹配 "右侧表达式"
- 如果右侧表达式又匹配失败则 "非贪婪部分" 将再增加匹配次再尝试匹配 "右侧表达式"
- 依此类推最后得到结果是 "非贪婪部分" 以尽可能少匹配次数使整个表达式匹配成功或者最终仍然匹配失败
个表达式中有多个非贪婪匹配以表达式 "d(\w+?)d(\w+?)z" 为例对于第个括号中 "\w+?" 来说右边 "d(\w+?)z" 属于它 "右侧表达式"对于第 2个括号中 "\w+?" 来说右边 "z" 属于它 "右侧表达式"当 "z" 匹配失败时
第 2个 "\w+?" 会 "增加匹配次"再尝试匹配 "z"如果第 2个 "\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>" 效率是完全相同情况 2:如果
个表达式中有多个未知匹配次数表达式应防止进行不必要尝试匹配比如
对表达式 "<script language='(.*?)'>(.*?)</script>" 来说如果前面部分表达式在遇到 "<script language='vbscript'>" 时匹配成功后而后边 "(.*?)</script>" 却匹配失败将导致第个 ".*?" 增加匹配次数再尝试而对于表达式真正目让第个 ".*?" 增加匹配成“vbscript'>”是不对因此这种尝试是不必要尝试因此
对依靠边界来识别表达式不要让未知匹配次数部分跨过它边界前面表达式中第个 ".*?" 应该改写成 "[^']*"后边那个 ".*?" 右边再没有未知匹配次数表达式因此这个非贪婪匹配没有效率陷阱于是这个匹配脚本块表达式应该写成:"<script language='([^']*)'>(.*?)</script>" 更好
最新评论