RegexBuddy—Better than a regular expression tutorial!

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

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

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

考虑 Perl 中的正则表达式 aa$|a(?R)a|a 或 Ruby 2.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。正则表达式引擎再次成功退出相同的递归。这一次，正则表达式中 (?R) 或 \g'0' 后面的 a 匹配字符串中的第三个 a。aaa 被发现是整体匹配。

另一方面，PCRE 除了记住它在字符串末尾匹配 aa 之外，不会记住有关递归的任何信息。PCRE 确实回溯超过递归，将到目前为止的匹配减少到字符串中的第一个 a。但这会使正则表达式中的第二个备选方案没有任何进一步的排列可尝试。因此，第二个备选方案开头的 a 也被回溯，将到目前为止的匹配减少到无。PCRE 使用第三个备选方案在字符串开头继续匹配尝试，并发现 a 匹配字符串开头的 a。在 PCRE 中，这是整体匹配。

可以通过添加原子组使 Perl 和 Ruby 中的递归成为原子操作。aa$|a(?>(?R))a|a 在 Perl 中和 aa$|a(?>\g'0')a|a 在 Ruby 中与 PCRE 中的原始正则表达式相同。

JGsoft V2 允许您选择递归是否应该为原子递归。原子递归具有更好的性能，但可能排除某些匹配项或找到不同的匹配项，如上所示。 aa$|a(?P>0)a|a 在 JGsoft V2 中是原子的。您可以记住这一点，因为这种递归语法使用尖括号，就像原子组一样。您可以使用数字或名称代替零，对编号或命名的捕获组进行原子子例程调用。JGsoft V2 中的任何其他递归语法都不是原子的。

Boost 有两种想法。整个正则表达式的递归在 Boost 中是原子的，就像在 PCRE 中一样。但 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 中的任意长度回文，我们需要一个分别匹配偶数个字符和奇数个字符的单词的正则表达式。自由间距模式使此正则表达式更容易阅读

\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 中的正则表达式。新正则表达式中的第二个备选方案永远不会尝试。