所有格量词

所有格量词

关于 重复运算符 或 量词 的一节说明了贪婪和懒惰重复之间的区别。贪婪和懒惰决定了正则表达式引擎尝试正则表达式模式的可能排列的顺序。贪婪的量词首先尝试尽可能多地重复标记，然后随着引擎回溯以寻找整体匹配，逐渐放弃匹配。惰性量词首先根据需要重复标记几次，然后随着引擎在正则表达式中回溯以找到整体匹配项而逐渐扩展匹配项。  

由于贪婪和懒惰会更改尝试排列的顺序，因此它们可以更改整个正则表达式匹配。但是，它们不会改变以下事实：如果找不到匹配项，则正则表达式引擎将回溯以尝试正则表达式的所有可能排列。

所有格量词是防止正则表达式引擎尝试所有排列的一种方法。考虑到性能的问题，这个还是很有用的。毕竟有时候现实情况中我们是可以提前知道一些信息的。可以减少不必要的回溯是优化性能的一个很好的方式。我们可以使用所有格量词来消除某些匹配项。

在本教程中讨论的regex风格中，所有格量词均由JGsoft，Java和PCRE支持。包括与基于PCRE的语言PHP，Delphi，和R 。Ruby从Ruby 1.9开始支持所有格量词，Perl从Perl 5.10开始支持，而Boost从Boost 1.42开始支持。            

所有格量词的工作方式

像贪婪的量词一样，所有格量词将标记重复的次数越多越好。但是与贪婪的量词不同，它不会因为引擎回溯而放弃匹配。使用所有格量词，要么是全部匹配，要么是全部不匹配。我们可以通过在其后面加上一个额外的+来使量词具有所有格。*是贪婪的，*?是懒惰的，而*+是所有格。++ ，?+和{n,m}+也都是所有格。

让我们看看如果尝试将"[^"]*+"与"abc"匹配，会发生什么情况。"匹配双引号字符" 。[^"]匹配由星号重复的a，b和c 。最后的token"匹配最后的字符双引号" ，我们找到了整个匹配项。在这种情况下，无论我们使用贪婪量词还是所有格量词，最终结果都是相同的。不过，所有格量词性能有所提高，因为所有格量词不必记住任何回溯位置。

在正则表达式失败的情况下，性能提高可能非常重要。如果目标字符串为"abc （无引号），则上述匹配过程以相同的方式发生，第二个”匹配失败。使用所有格量词时，没有回溯的步骤。正则表达式没有任何替代或非占位符，它们可以放弃部分匹配项以尝试对正则表达式进行不同的排列。因此，当第二个“失败时，匹配尝试将立即失败。

如果我们使用"[^"]*"有一个贪婪的量词来代替，引擎就会回溯。之后，正则"在字符串的结尾匹配失败，[^"]*将放弃此次匹配，开始回溯，此时[^"]*匹配ab。则"将无法匹配c 。引擎继续回溯，[^"]*回溯到刚好匹配a，"又不匹配b 。最后，[^"]*回溯以匹配零个字符，然而"匹配字符a还是失败。仅在这一点上，所有回溯位置都已用尽，引擎才放弃匹配尝试。从本质上讲，此正则表达式执行的不必要的步骤与不匹配的开头引号后面包含的字符一样多。

什么时候所有格量词很重要

所有格量词的主要实际好处是可以加快正则表达式的速度。特别是，所有格量词使我们的正则表达式可以更快地失败，避免不必要的回溯。在上面的示例中，当结束引号不匹配时，我们知道正则表达式不可能跳过引号。因此，无需回溯并宣告匹配失败。我们通过使量词所有格来使正则表达式引擎意识到这一点。实际上，某些引擎（包括JGsoft引擎）在编译正则表达式时会检测到[^"]*和"是互斥的，并自动使星号*成为所有格量词。

现在，像使用单个量词的正则表达式一样进行线性回溯的速度非常快。我们不太可能会注意到速度差异。但是，当我们嵌套量词时，所有格可以节省我们的时间。嵌套量词意味着我们在一个组中有一个或多个重复的标记，并且该组也被重复。那时灾难性的回溯就会经常抬起它那丑陋的头。在这种情况下，我们将依靠所有格量词或者原子分组来节省时间。

所有格量词可以更改匹配结果

使用所有格量词可以更改匹配尝试的结果。由于没有完成回溯，因此不会使用所有格量词找到需要贪婪的量词进行回溯的匹配。例如，".*"匹配"abc"x中的"abc" ，但是".*+"根本不匹配此字符串。

在两个正则表达式中，首个"匹配字符串中的首个" 。然后，重复的点.与字符串abc"x的其余部分匹配。第二个"则在字符串的末尾不匹配。

现在，两个正则表达式的路径有所不同。所有格星号都想要这一切。没有回溯完成。由于"失败，将没有任何排列尝试，并且总的匹配尝试失败。贪婪的.*虽然最初会抢占所有内容，但愿意回溯。它将一次回溯一个字符。回溯到abc" ，"无法与x匹配。回溯到abc ，token " 匹配字符" 。找到一个整体匹配项"abc" 。

从本质上讲，这里的需要注意的是，在使用所有格量词时，我们需要确保将要应用所有格量词的所有内容都不能与应遵循的所有格匹配。上例中的问题是点.也与右引号匹配。这阻止了我们使用所有格量词。上一节中否定的字符类[^”]不能与右引号匹配，因此我们可以使其具有所有格。

使用原子分组而不是所有格量词

从技术上讲，所有格量词在单原子修饰符周围放置原子组的符号很方便。支持所有格量词的正则表达式都支持原子分组。但是，并非所有支持原子分组的正则表达式都支持所有格量词。使用这些正则引擎，我们可以使用原子组获得完全相同的结果。  

基本上，用(?>X*)代替X*+。重要的是要注意，X和所有格量化符+都在原子组内。即使X是一个组，我们仍然需要在其周围放置一个额外的原子组以实现相同的效果。(?:a|b)*+等效于(?>(?:a|b)*)但不等于(?>a|b)*。后者是有效的正则表达式，但是当用作较大的正则表达式的一部分时，它不会具有相同的效果。

为了说明这个问题，我们来看(?:a|b)*+b和(?>(?:a|b)*)b均不匹配b 。a|b匹配b 。星号*是满足的，并且它的所有格或原子组的事实将使星号忘记其所有回溯位置。正则表达式中的第二个b没有剩余要匹配的内容，所以总体匹配尝试失败。

在正则表达式(?>a|b)*b中，原子组强迫该选择项放弃其回溯位置。这意味着，如果a匹配，则如果正则表达式的其余部分失败，它将不会再次尝试b 。由于星号不在组中，因此它是正常的贪婪。当第二个b失败时，贪婪的星号将回溯到第零次迭代。然后，第二个token b匹配目标字符串中的b。

当将别人使用所有格量词编写的正则表达式转换为不具有所有格量词的正则表达式时，这种区别尤为重要。