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

递归匹配与非贪婪匹配

正则表达式话题
引言
本文将逐步讨论一些正则表达式的使用话题。本文为本站基础篇之后的扩展，在阅读本文之前，建议先阅读正则表达式参考文档一文。
--------------------------------------------------------------------------------
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>" 更好。
正则表达式－分组构造

分组构造使您可以捕获子表达式组并提高具有非捕获预测先行和回顾后发修饰符的正则表达式的效率。下表描述了正则表达式分组构造。
分组构造 说明
( ) 捕获匹配的子字符串（或非捕获组；有关详细信息，请参见正则表达式选项中的 ExplicitCapture 选项）。使用 () 的捕获根据左括号的顺序从 1 开始自动编号。捕获元素编号为零的第一个捕获是由整个正则表达式模式匹配的文本。
(?<name> ) 将匹配的子字符串捕获到一个组名称或编号名称中。用于 name 的字符串不能包含任何标点符号，并且不能以数字开头。可以使用单引号替代尖括号，例如 (?'name')。
(?<name1-name2> ) 平衡组定义。删除先前定义的 name2 组的定义并在 name1 组中存储先前定义的 name2 组和当前组之间的间隔。如果未定义 name2 组，则匹配将回溯。由于删除 name2 的最后一个定义会显示 na
me2 的先前定义，因此该构造允许将 name2 组的捕获堆栈用作计数器以跟踪嵌套构造（如括号）。在此构造中，name1 是可选的。可以使用单引号替代尖括号，例如 (?'name1-name2')。
(?: ) 非捕获组。
(?imnsx-imnsx: ) 应用或禁用子表达式中指

递归匹配与非贪婪匹配

定的选项。例如，(?i-s: ) 将打开不区分大小写并禁用单行模式。有关详细信息，请参见正则表达式选项。
(?= ) 零宽度正预测先行断言。仅当子表达式在此位置的右侧匹配时才继续匹配。例如，\w+(?=\d) 与后跟数字的单词匹配，而不与该数字匹配。此构造不会回溯。
(?! ) 零宽度负预测先行断言。仅当子表达式不在此位置的右侧匹配时才继续匹配。例如，\b(?!un)\w+\b 与不以 un 开头的单词匹配。
(?<= ) 零宽度正回顾后发断言。仅当子表达式在此位置的左侧匹配时才继续匹配。例如，(?<=19)99 与跟在 19 后面的 99 的实例匹配。此构造不会回溯。
(?<! ) 零宽度负回顾后发断言。仅当子表达式不在此位置的左侧匹配时才继续匹配。
(?> ) 非回溯子表达式（也称为“贪婪”子表达式）。该子表达式仅完全匹配一次，然后就不会逐段参与回溯了。（也就是说，该子表达式仅与可由该子表达式单独匹配的字符串匹配。）
命名捕获根据左括号的从左到右的顺序按顺序编号（与非命名捕获类似），但在对所有非命名捕获进行计数之后才开始对命名捕获进行编号。例如，模式 ((?<One>abc)/d+)?(?<Two>xyz)(.*) 按编号和名称产生下列捕获组。（编号为 0 的第一个捕获总是指整个模式）。
编号 名称 模式
0 0（默认名称） ((?<One>abc)/d+)?(?<Two>xyz)(.*)
1 1（默认名称） ((?<One>abc)/d+)
2 2（默认名称） (.*)
3 1 (?<One>abc)
4 2 (?<Two>xyz)
正则表达式－替换和分组
替换使用 | 字符来允许在两个或多个替换选项之间进行选择。例如，可以扩展章节标题正则表达式，以返回比章标题范围更广的匹配项。但是，这并不象您可能认为的那样简单。替换匹配 | 字符两边的尽可能最大的表达式。您可能认为，下面的表达式匹配出现在行首和行尾、后面跟一个或两个数字的 Chapter 或 Section：
/^Chapter|Section [1-9][0-9]{0,1}$/
很遗憾，上面的正则表达式要么匹配行首的单词 Chapter，要么匹配行尾的单词 Section 及跟在其后的任何数字。如果输入字符串是 Chapter 22，那么上面的表达式只匹配单词 Chapter。如果输入字符串是 Section 22，那么该表达式匹配 Section 22。
若要使正则表达式更易于控制，可以使用括号来限制替换的范围，即，确保它只应用于两个单词 Chapter 和 Section。但是，括号也用于创建子表达式，并可能捕获它们以供以后使用，这一点在有关反向引用的那一节讲述。通过在上面的正则表达式的适
当位置添加括号，就可以使该正则表达式匹配 Chapter 1 或 Section 3。
下面的正则表达式使用括号来组合 Chapter 和 Section，以便表达式正确地起作用：
/^(Chapter|Section) [1-9][0-9]{0,1}$/
虽然这些表达式正确发挥作

递归匹配与非贪婪匹配

用，但 Chapter| Section 两边的括号还会使得两个匹配单词中的任何一个被捕获以供将来使用。由于在上面的表达式中只有一组括号，因此，只有一个被捕获的“子匹配项”。可以通过使用 RegExp 对象的 $1-$9 属性来引用此子匹配项。
在上面的示例中，您只需要使用括号来组合单词 Chapter 和 Section 之间的选择。若要防止匹配被保存以备将来使用，请在括号内正则表达式模式之前放置 ?:。下面的修改提供相同的能力而不保存子匹配项：
/^(?:Chapter|Section) [1-9][0-9]{0,1}$/
除 ?: 元字符外，两个其他非捕获元字符创建被称为“预测先行”匹配的某些内容。正向预测先行使用 ?= 指定，它匹配处于括号中匹配正则表达式模式的起始点的搜索字符串。反向预测先行使用 ?! 指定，它匹配处于与正则表达式模式不匹配的字符串的起始点的搜索字符串。
例如，假设您有一个文档，该文档包含指向 Windows 3.1、Windows 95、Windows 98 和 Windows NT 的引用。再进一步假设，您需要更新该文档，将指向 Windows 95、Windows 98 和 Windows NT 的所有引用更改为 Windows 2000。下面的正则表达式（这是一个正向预测先行的示例）匹配 Windows 95、Wi
ndows 98 和 Windows NT：
/Windows(?=95 |98 |NT )/
找到一处匹配后，紧接着就在匹配的文本（不包括预测先行中的字符）之后搜索下一处匹配。例如，如果上面的表达式匹配 Windows 98，将在 Windows 之后而不是在 98 之后继续搜索。

本文来源：https://www.bwwdw.com/article/qmz4.html