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-1 层的表达式] )* [标记尾]
回头来看前面编写的“可匹配嵌套一层”的表达式:
|
\( |
( |
[^()] |
| |
\(([^()])*\) |
)* |
\) |
<font> |
( |
(?!</?font>). |
| |
(<font>((?!</?font>).)*</font>) |
)* |
</font> |
|
|
|
|
|
|
|
PHP 和 GRETA 的简便之处在于,匹配嵌套(n-1)层的表达式用 (?R) 表示: |
\( |
( |
[^()] |
| |
(?R) |
)* |
\) |
第四步,依此类推,可以编写出匹配有限(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>" 的效率是完全相同的。
情况二:如果一个表达式中有多个未知匹配次数的表达式,应防止进行不必要的尝试匹配。
比如,对表达式 "<script language='(.*?)'>(.*?)</script>" 来说, 如果前面部分表达式在遇到 "<script language='vbscript'>" 时匹配成功后,而后边的 "(.*?)</script>" 却匹配失败,将导致第一个 ".*?" 增加匹配次数再尝试。而对于表达式真正目的,让第一个 ".*?" 增加匹配成“vbscript'>”是不对的,因此这种尝试是不必要的尝试。
因此,对依靠边界来识别的表达式,不要让未知匹配次数的部分跨过它的边界。前面的表达式中,第一个 ".*?" 应该改写成 "[^']*"。后边那个 ".*?" 的右边再没有未知匹配次数的表达式,因此这个非贪婪匹配没有效率陷阱。于是,这个匹配脚本块的表达式,应该写成:"<script language='([^']*)'>(.*?)</script>" 更好。
分享到:
相关推荐
1. 表达式的递归匹配 有时候,我们需要用正则表达式来分析一个计算式中的括号配对情况。比如,使用表达式 "\( [^)]* \)" 或者 "\( .*? \)" 可以匹配一对小括号。但是如果括号内还嵌有一层括号的话 ,如 "( ( ) )...
函数以递归方式在路径中搜索与通配符表达式(例如“ images *。*”)或正则表达式(例如“ images [0-9]。* \。*”)匹配的文件名。 该函数返回与给定模式匹配的每个文件的完整路径的元胞数组。
javascript 验证url的正则表达式. 经典正则表达式. 正则表达式--递归匹配与非贪婪匹配
主要介绍了C#正则表达式的递归匹配分析,针对C#程序的正则匹配方法,很有实用价值,需要的朋友可以参考下
代码如下:–由父项递归下级 with cte(id,parentid,text) as (–父项 select id,parentid,text from treeview where parentid = 450 union all –递归结果集中的下级 select t.id,t.parentid,t.text from treeview as...
原理: 对每一个非终结符(分别代表一个语法单位)按其产生方式结构构造相应的语法子程序,以完成非终结符号所对应的语法单位的分析和识别任务。其中终结符号产生匹配命令...因为文法可以递归,相应子程序也是递归的。
t-regex :使用树正则表达式的匹配器和语法t-regex定义了一系列组合器,以在任何Haskell数据类型上表达树正则表达式。 此外,通过使用一些组合器(以及一些模板Haskell),它定义了一种很好的语法,用于使用该树正则...
一般来说,递归的正则表达式用来匹配任意嵌套层次的结构或左右对称的结构。例如匹配: ((((())))) (hello (world) good (boy) bye) <p>hello world <strong>hello world</strong> abc.def.ghij...stu.vwx.yz ...
boost库的regex正则表达式实现文件递归模糊匹配搜索
好东西 都是好东西咧 里面包括 C#中的常用正则表达式总结 javascript 验证url的正则表达式 JavaScript中的正则表达式学习1-2 JS与正则式强化训练作业 ...正则表达式--递归匹配与非贪婪匹配 正则式测试工具 等等等等
主要介绍了JavaScript正则表达式校验与递归函数实际应用,需要的朋友可以参考下
目录 一、 本文目标 3 二、 如何使用本教程 3 三、 正则表达式到底是什么东西? 3 四、 入门 4 ...十九、 平衡组/递归匹配 18 二十、 还有些什么东西没提到 20 二十一、 网上的资源及本文参考文献 21
支持命名分组,条件表达式,递归表达式等多种高级特性。(1.2版本新特点) 与 GRETA、boost 相比,DEELX 独到之处: 完全使用模版库编写,支持 char, wchar_t, int 等以及其他基类型版本。 全部代码位于一个...
1. 本文目标 2. 如何使用本教程 3. 正则表达式到底是什么东西?...19. 平衡组/递归匹配 20. 还有些什么东西没提到 21. 联系作者 22. 最后,来点广告…… 23. 网上的资源及本文参考文献 24. 更新纪录
IF(G2,(10-(G3-G2)*2)*G1,11*G1))就不行了,因为有很多的逗号和其他符号干扰,所以研究了一个正则表达式解决了这个问题,可以是任意复杂的IF表达式,如果需要进一步的匹配子判断式,则可以用自己擅长的语言做递归,...
什么时候会用到递归正则表达式呢? 当然是待匹配的字串中递归地出现某种模式时(貌似废话). 最经典的例子, 就是递归正则处理嵌套括号的问题了. 例子如下. 假设你的文本中包含了正确配对的嵌套括号. 括号的深度可以是...
学习正则表达式快速入门的法宝。 语言深入浅出,举例实用、典型。 1、本文目标 2、如何使用本教程 ...19、平衡组/递归匹配 20、还有些什么东西没提到 21、联系作者 22、网上的资源及本文参考文献 23、更新纪录
则表达式工具 Match Tracer 是...支持高级正则语法,例如递归匹配等。 可以保存文本片段,例如表达式或者其他文本,也可以跟任意其他编辑器之前相互拖动。 可以保存当前表达式为一个‘快照’,使您可以放心改写表达式。