递归中的回溯

递归和子例程调用可能是或不是原子的

本教程前面的章节介绍了正则表达式递归和正则表达式子例程。在本章节中，“递归”一词是指整个正则表达式的递归，捕获组的递归以及对捕获组的子例程调用。   

如果递归后剩余的正则表达式失败，则Perl和Ruby会返回递归。他们根据需要尝试递归的所有排列，以使正则表达式的其余部分匹配。PCRE将递归视为原子。PCRE通常在递归过程中回溯，但是一旦递归匹配，即使正则表达式的其余部分不匹配，它也不会尝试对递归进行任何进一步的排列。结果是Perl和Ruby可能找到PCRE找不到的正则表达式匹配项，或者Perl和Ruby可能找到不同的匹配项。      

考虑Perl中的正则表达式aa$|a(?R)a|a或和其相同的Ruby2.0中的aa$|a\g'0'a|a。PCRE支持这两种语法。让我们看看当aaa是目标字符串时，Perl，Ruby和PCRE如何使用此正则表达式进行匹配的。       第一个选择项aa$失败，因为无法在字符串的第二个和第三个a之间使锚匹配。在字符串的开头尝试第二种选择，a匹配a 。现在，正则表达式引擎进入第一个递归。         

在递归内，第一个选择项匹配字符串中的第二个和第三个a 。正则表达式引擎退出成功的递归。但现在，(?R)或\g'0'后面的a匹配失败，因为正则表达式引擎已经达到了字符串的结尾。因此，正则表达式引擎必须回溯。这是PCRE不同于Perl或Ruby的行为。        

Perl和Ruby可以记录在递归中，正则表达式与第二种选择匹配，并且有三种可能的选择。Perl和Ruby回溯到递归中。递归内的第二个选择项被回溯，从而将匹配减少到字符串中的第一个a 。现在尝试第三种选择项。a匹配字符串中的第二个a 。regex引擎再次从同一递归中成功退出。此时，(?R)或\g'0'后面的a正与第三个字符a匹配。 找到aaa作为整体匹配项。                  

另一方面，PCRE除了在字符串末尾匹配aa之外，此次递归什么都没有记录。PCRE不回溯递归去减少到现在位置匹配到的a。但这在正则表达式中留下了第二种选择，而无需尝试任何其他选择。因此，第二种选择开始时的a也被回溯，从而使匹配到现在没有任何结果。PCRE继续从该字符串的开头尝试第三种选择，a匹配字符串最开始的a。在PCRE中，这是整体匹配。            

我们可以通过添加原子组来使Perl和Ruby原子递归。在Perl中aa$|a(?>(?R))a|a。在Ruby中aa$|a(?>\g'0')a|a。这两者和PCRE中的最初的正则表达式是一样的。

通过JGsoft V2，我们可以选择是否应使用原子递归。原子递归可以提供更好的性能，但是可以排除某些匹配项或找到不同的匹配项，如上所述。aa$|a(?P>0)a|a在JGsoft V2中是原子的。我们可以记住这一点，因为这种递归语法与原子组一样使用尖括号。我们可以使用数字或名称（而不是零）来对已编号或已命名的捕获组进行原子子例程调用。在JGsoft V2中，递归的任何其他语法都不是原子的。   

Boost有两种方式。就像PCRE中一样，在Boost中，整个正则表达式的递归是原子的。但是Boost将回退到子例程调用和捕获组（如Perl）的递归中。因此，我们可以通过将整个正则表达式封装到捕获组中然后调用它从而在Boost中进行非原子递归。 

PCRE2最初的行为类似于PCRE，将所有递归和子例程调用视为原子调用。PCRE2 10.30改变了这一点，它试图向Perl靠拢，但最终却走向了Boost。PCRE2 10.30将像Perl一样回溯到子例程调用和捕获组的递归。但是PCRE2仍然无法回溯到整个正则表达式的递归。在以下示例中，“PCRE”仅表示原始PCRE。对于PCRE2 10.22及更低版本，请遵循PCRE示例。对于PCRE2 10.30及更高版本，请遵循Perl示例。 

Perl和Ruby中任意长度的回文

在递归和捕获组的主题中介绍了一个正则表达式，以匹配长度为奇数个字符的回文。解决方案似乎微不足道。

\b(?'word'(?'letter'[a-z])(?&word)\k'letter'|[a-z]?)\b

在Perl中有作用。量词?使与回文中间的字母匹配的[a-z]为可选。在Ruby中，我们可以使用

\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\b

向解决方案中添加相同的量词指定反向引用的递归级别。在PCRE中，Perl的解决方案仍然匹配奇数回文，但不匹配偶数回文。

让我们看看这些正则表达式如何匹配或不匹配deed。PCRE与Perl和Ruby一样，与原始正则表达式相同。组“letter”与d匹配。在三个连续的递归中，组捕获e ，e和d 。第四次递归失败，因为没有剩余的字符要匹配。在第三次递归中，第一个备选方案被回溯，第二个备选方案在字符串末尾匹配d 。引擎成功匹配后退出第三次递归。在第二次递归中，反向引用失败，因为字符串中没有剩余字符。       

这里的行为有所不同。Perl和Ruby回溯到第三次递归并回溯了量词?，这使得第二种选择是可选的。在第三次递归中，第二个选择放弃在字符串末尾匹配的d 。引擎再次退出第三次递归，这次成功进行了零长度匹配。回到第二次递归中，反向引用仍然失败，因为该组为第二次递归存储了e ，但字符串中的下一个字符是d 。因此，第一个选择被回溯，第二个选择与字符串中的第二个e匹配。成功退出第二次递归。

在第一次递归中，反向引用再次失败。该组为第一个递归存储了e ，但字符串中的下一个字符是d 。同样，Perl和Ruby返回第二个递归以尝试第二种选择找到零长度匹配的排列。再次返回第一次递归，现在反向引用与字符串中的第二个e匹配。引擎成功完成了第一次递归。返回整体匹配尝试，后向引用将匹配字符串中的最后一个d 。单词边界成功，并且找到了整体匹配项。

但是，PCRE不会回溯到第三次递归。当它在第二次递归回溯到第一个选择项时，它会在第三次递归上回溯。现在，第二个递归中的第二个替代项与字符串中的第二个e匹配。成功退出第二次递归。    

在第一次递归中，反向引用再次失败。该组为第一个递归存储了e ，但字符串中的下一个字符是d 。同样，PCRE不会回退到第二个递归中，但是在第一个递归中使第一个选择项时会立即失败。现在，第一次递归中的第二个替代项与字符串中的第一个e匹配。PCRE成功退出第一次递归。回到整个匹配尝试中，反向引用失败，因为该组在递归之前捕获了d ，并且下一个字符是字符串中的第二个e 。再次回溯，整个正则表达式匹配项中的第二个替代项现在与字符串中的第一个d匹配。然后单词边界失败。PCRE未找到任何匹配项。

PCRE中任意长度的回文

为了匹配PCRE中任意长度的回文，我们需要一个正则表达式来分别匹配偶数个字符和奇数个字符的单词。Free-Spacing模式使此正则表达式更易于阅读：

\b(?'word'
  (?'oddword' (?'oddletter' [a-z])(?P>oddword)  \k'oddletter' |[a-z])
| (?'evenword'(?'evenletter'[a-z])(?P>evenword)?\k'evenletter')
)\b

 基本上，这是原始正则表达式的两个副本，并带有选择项。第一种选择是将“word”和“letter”组重命名为“ oddword”和“ oddletter”。第二种选择是将“word”和“letter”组重命名为“evenword”和“ evenletter”。现在，量词?使调用(?P>evenword)成为可选项，而不是|[a-z]。一个新的组“word”将“oddword”和“ evenword”这两个组结合在一起，因此单词边界仍然适用于整个正则表达式。   

此正则表达式中的第一个选择项“oddword”以与“递归和捕获组”章节中讨论的正则表达式完全相同的方式与类似于radar的奇数回文匹配。从未尝试过新正则表达式中的第二种选择。    

当字符串是如deed的偶数长度的回文时，新的正则表达式将首先尝试第一个选择项的所有排列。仅在第一个选择项找不到匹配项后，才尝试第二个选择项“evenword”。 

第二种选择以与原始正则表达式相同的方式开始。组“evenletter”匹配d 。在三个连续的递归中，组捕获e ，e和d 。第四次递归失败，因为没有剩余的字符要匹配。回到第三次递归中，正则表达式引擎注意到递归调用(?P>evenword)?是可选的。继续进行向后引用\k’evenletter’。反向引用失败，因为字符串中没有剩余的字符。由于递归没有其他尝试，因此回溯。“ evenletter”组必须放弃其最近的匹配，并且PCRE从失败的第三次递归退出。       

在第二次递归中，反向引用失败，因为捕获组在该递归过程中匹配了e ，但字符串中的下一个字符是d 。组放弃了另一个匹配，PCRE从第二次递归失败退出。   

在第一次递归中，反向引用成功。该组在该递归过程中与字符串中的第一个e相匹配，而反向引用与第二个e相匹配。PCRE的第一次递归成功退出。  

回到整体匹配尝试中，反向引用再次成功。在整体匹配尝试期间，组与字符串开头的d匹配，而反向引用与最后的d匹配。退出“ evenword”和“word”组，单词边界在字符串的末尾匹配。deed是整个匹配项。