递归

正则表达式递归

Perl 5.10，PCRE 4.0，Ruby 2.0以及它们的更高版本均支持正则表达式递归。Perl使用语法(?R)和(?0)来表示递归（两个作用是相同的）。Ruby 2.0使用\g<0>来表示递归。从7.7版开始，PCRE支持这三种方式——(?R)、(?0)和\g<0>。早期版本仅支持Perl语法（Perl实际上是从PCRE复制的）。Delphi，PHP和R的最新版本也支持这三种语法，因为它们的正则表达式功能是基于PCRE的。JGsoft V2也支持正则表达式递归的所有语法。             

尽管Ruby 1.9没有用于正则表达式递归的任何语法，但它确实支持捕获组递归。因此，如果将整个正则表达式包装在捕获组中，则可以在Ruby 1.9中递归整个正则表达式。.NET不支持递归，但是它支持平衡组，可以使用这些平衡组代替递归来匹配平衡结构。

稍后我们将看到，Perl，PCRE和Ruby在递归过程中处理反向引用和回溯的的方式的不同。当他们复制彼此的语法时，他们没有复制彼此的行为。JGsoft V2复制了它们的语法和行为。因此，JGsoft V2具有三种执行正则表达式递归的方法，我们可以使用不同的语法来实现递归。

Boost 1.42从Perl复制了语法。但是它的实现确实有问题的。Boost 1.60试图修复递归中量词的行为，但它与其他版本仍然有很大不同，并且与早期版本的Boost不兼容。Boost 1.64最终在无限递归时不再崩溃。但是整个正则表达式的递归仍然仅尝试第一种选择。

简单递归

正则表达式a(?R)?z ，a(?0)?z 和a\g<0>?z全部匹配至少一个字母a，并且在a的后面跟完全相同数量的字母z 。由于这些正则表达式在功能上是相同的，因此我们将使用R的语法进行递归，以查看此正则表达式如何与字符串aaazzz匹配。

首先，正则标记a匹配字符串中的第一个字符a 。然后，正则表达式引擎达到(?R)。这告诉引擎在字符串的当前位置再次尝试整个正则表达式。现在，正则标记a匹配字符串中的第二个字符a 。引擎再次达到(?R)。在第二个递归上，正则标记a匹配第三个字符a 。在第三次递归中，正则标记a不能匹配字符串中的第一个字符z 。这导致(?R)失败。但是正则表达式使用量词?使(?R)为可选。因此，引擎继续正则标记z和字符串中的第一个字符z的进行匹配。 

现在，正则表达式引擎已到达正则表达式的末尾。但是，由于递归有两个层次，因此尚未找到整体匹配项。它仅找到了(?R)的匹配项。匹配成功后退出递归，引擎也达到正则标记z 。现在，它与字符串中的第二个字符z匹配。引擎仍处于第一层递归中，成功地从中退出。最后，正则标记z匹配字符串中的第三个字符z。引擎再次位于正则表达式的末尾。这次，它不在任何递归内。因此，它返回aaazzz作为整个正则表达式匹配项。

匹配平衡结构

递归的主要目的是匹配平衡结构或嵌套结构。通用正则表达式是b(?:m|(?R))*e，其中b是平衡结构开始的地方，m是可能在平衡结构中间出现的东西，e是可能在平衡结构结束时出现的东西。为了获得正确的结果，b ，m和e中的任何两个都不能匹配相同的文本。我们可以使用原子组而不是非捕获组来提高性能：b(?>m|(?R))*e。

现实中常见的用法是匹配一组平衡的括号。\((?>[^()]|(?R))*\)匹配一对括号，中间包含任意文本，也可以包括无数个括号，只要它们都正确配对即可。如果目标字符串包含不平衡的括号，则可能在不平衡的左括号之后匹配最左边成对的平衡括号。如果我们想要正则表达式在包含不平衡括号的字符串中找不到任何匹配项，则需要使用子例程调用而不是递归。如果要查找多对平衡括号对的序列作为单个匹配项，则还需要一个子例程调用。    

选择项递归

如果平衡结构中间可能出现的内容也可以单独出现而没有开头和结尾部分，则使用通用正则表达式b(?R)*e|m来匹配。同样，b ，m和e都必须互斥。\((?R)*\)|[^()]+匹配一对平衡的括号，如上一节中的正则表达式。但是它也匹配不包含任何括号的任何文本。

此正则表达式在Boost中无法正常工作。如果某个正则表达式具有不在组内的选择项，那么在Boost中递归整个正则表达式只会尝试第一个替代方法。所以在Boost中正则表达式\((?R)*\)|[^()]+匹配任意深度嵌套的任意数量的平衡括号，中间没有任何文本，或者根本不包含任何括号的任何文本。如果调整选则项的位置，[^()]+|\((?R*\)可以匹配任何不带括号的文本，或单对括号和不带括号的任何文本。在所有其他正则表达式引擎中中，这两个正则表达式可以匹配相同的内容。

Boost的解决方案是将选择项放到一个组中。(?:\((?R)*\)|[^()]+)和(?：[^()]+|\((?R)*\))在本文讨论的所有支持递归的正则表达式引擎中，都能找到相同的匹配项。