【正则表达式教程】递归中的量词

Z时代
2024-01-10
分类：综合

递归量词

在介绍递归时展示了a(?R)?z是如何匹配aaazzz 。该量词?使前面的标记为可选。换句话说，它将标记重复0到1次。在a(?R)?z中(?R)是可选的，因为后面跟着一个问号?。我们可能想知道为什么正则表达式尝试了三次递归，而不是一次尝试或根本没有尝试。

原因是在递归时，正则表达式引擎在尝试整个正则表达式时可以认为是一个全新的开始。所有量词和替代词的行为都好像递归之前的匹配过程从未发生过，除了引擎通过字符串前进。正则表达式引擎从递归退出时，无论递归匹配成功还是失败，它都会还原所有量词和选择项的状态。基本上，匹配过程将正常进行，就像递归从未发生一样，除了引擎通过字符串前进。

如果我们熟悉过程编程语言，则regex递归基本上是一个递归函数调用，而量词是该函数中的局部变量。函数的每个递归都有其自己的局部变量集，这些局部变量在堆栈的较高递归中不受影响，也不受相同局部变量的影响。除了Boost之外，递归上的量词在所有形式中都是以上面说的这种方式工作。

让我们看看a(?R){3}z|q是如何执行的（Boost除外）。最简单的匹配是q ，由正则表达式中的第二个选择项找到。

让我们看一下上面的正则表达式是如何匹配aqqqz的。正则标记a和字符a匹配之后，正则表达式引擎开始递归。正则标记a不能匹配q 。仍在递归内，引擎尝试第二种选择。q匹配q 。引擎从递归中退出并成功匹配。引擎现在注意到，量词{3}已成功重复一次。它需要再重复两次，因此引擎开始另一次递归。它再次匹配q 。在量词的第三次迭代中，第三次递归匹配q 。最后，z匹配z并找到一个整体匹配。

此正则表达式与aqqz或aqqqqz不匹配。aqqz失败是因为在量词的第三次迭代期间，递归无法匹配z 。aqqqqz失败是因为a(?R){3}已经匹配aqqq ，正则标记z不匹配第四个字符q 。

上面的正则表达式可以匹配更长的字符串，例如aqaqqqzqz 。使用此字符串，在量词的第二次迭代期间，递归匹配aqqqz 。由于每个递归分别跟踪量词，因此递归需要自己的三个连续递归来满足自己的量词{3}。这可能会导致任意长度的字符串都能匹配，例如aaaqqaqqqzzaqqqqqzqaqqaaqqqzqqzzz 。

Boost如何在递归上处理量词

Boost对量词在递归上的工作方式有自己的想法。如果递归运算符根本没有任何量词，或者如果它有*作为其量词，则在Boost中与其他正则表达式引擎的作用相同。在Boost 1.59或与Boost 1.60之前的版本以及与其他regex引擎相比更高的版本中，任何其他量词可能导致完全不同的匹配（或缺少匹配）。Boost 1.60试图修复Boost与其他引擎之间的某些差异，但仅导致了不同的不兼容行为。

在Boost 1.59和更低版本中，递归上的量词会在整个递归堆栈中同时计算迭代和递归。因此，对于正则表达式a(?R){3}z|q在Boost 1.59中可能匹配包括aaaazzzz ，aaaqzzz ，aaqqzz ，aaqzqz和aqaqzzz 。在所有这些匹配中，递归和迭代的数量总计为3。其他匹配项找不到这些匹配，因为它们在每次递归过程中都需要进行3次迭代。因此，其他正则引擎可以匹配aaqqqzaqqqzaqqqzz或aqqaqqqzz之类的东西。Boost 1.59将仅匹配这些字符串中的aqqqz 。

Boost 1.60尝试像其他正则引擎一样在每个递归级别上对量词进行迭代，但是很遗憾，做的有点失败。使递归成为可选的任何量词都可以无限重复。所以Boost1.60和更高版本中将a(?R)?z和a(?R)*z视为是相同的。

虽然这解决了a(?R)?z无法在Boost 1.59中完全匹配aaazzz 的问题，然而它还允许使用该正则表达式匹配aazazz此类字符串，这在其他正则引擎中是无法匹配的。如果量词不是可选的，则Boost 1.60仅允许它在第一次递归期间进行匹配。因此，a(?R){3}z|q只能匹配q或aqqqz 。

Boost的递归量词问题也影响递归标记的父组上的量词。它们还会影响子例程调用上的量词和包含对带有量词的组的父组的子例程调用的组上的量词。