正则表达式--递归匹配与非贪婪匹配

正则表达式--递归匹配与非贪婪匹配  
 

　　
　　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>"。 顿时间如获至宝，凡是按边界匹配的地方，尽量使用简捷的非贪婪匹配".*?"。特别是对于复杂的表达式来说，采用非贪婪匹配 ".*?" 写出来的表达式的确是简练了许多。
　　然而，当一个表达式中，有多个非贪婪匹配时，或者多个未知匹配次数的表达式时，这个表达式将可能存在效率上的陷阱。有时候，匹配速度慢得莫名奇妙，甚至开始怀疑正则表达式是否实用。