2.14 消除不必要的回溯
问题描述
上一个实例解释了贪心和懒惰量词之间的区别，以及它们是如何进行回溯的。在有些情形下，这种回溯是不必要的。
‹bd+b›使用了一个贪心量词，而‹bd+?b›使用的是懒惰量词。它们都会匹配相同的内容：一个整数。如果给它们同样的目标文本，它们都会找到完全一样的匹配。在这里所做的任何回溯都是不必要的。试着改写这个正则表达式，明确地消除所有回溯，使正则表达式更加高效。
解决方案
\b\d++\b
正则选项：无
正则流派：Java、PCRE、Perl 5.10、Ruby 1.9
最容易的解决方案是使用一个占有量词。但是只有最新的几种正则流派中才支持它。
\b(?>\d+)\b
正则选项：无
正则流派：.NET、Java、PCRE、Perl、Ruby
一个固化分组（atomic group）可以提供完全一样的功能，但是需要使用稍微难懂点的语法。对固化分组的支持相比占有量词来说更为广泛。
JavaScript和Python都不支持占有量词或固化分组。因此在这两种正则流派中无法消除不必要的回溯。
讨论
占有量词（possessive quantifier）与贪心量词是类似的：它也会试图去重复尽可能多的次数。它们的区别是占有量词永远不会回退，即使回退是能够匹配正则表达式后面部分的唯一手段时，也不会这样去做。占有量词也不会记录任何可能的回溯位置。
在量词之后添加加号，来得到对应的占有量词。例如，‹*+›、‹++›、‹?+›和‹{7,42}+›都是占有量词。
在Java 4或者更新版本中，也就是从Java中包含了java.util.regex包的第一个发布起，就提供了对占有量词的支持。本书中介绍的PCRE的所有版本（版本4～7）都支持占有量词。Perl从5.10版本也开始支持它们。经典的Ruby正则表达式不支持占有量词，但是Oniguruma引擎，也就是Ruby 1.9中使用的默认引擎是支持占有量词的。
包含贪心量词的固化分组与占有量词会产生完全相同的效果。当正则引擎退出固化分组的时候，量词会记住所有的回溯位置，并且分组中的其他选择分支都会被丢弃。所使用的语法是‹(?>⋯)›，其中‹⋯›可以是任意正则表达式。固化分组本质上是非捕获分组，加上拒绝回溯的功能。这里的问号不是量词；而是固化分组的起始括号就是由三个字符‹(?>›组成。
把正则表达式‹bd++b›（占有版本）应用到123abc 456的时候，‹b›会匹配目标文本的开始，‹d++›则会匹配123。到目前为止，这和‹bd+b›（贪心版本）所做的并没有区别。但是接着第二个‹b›会在3和a之间匹配失败。
占有量词不会保存任何回溯位置。既然在这个正则表达式中不存在其他量词或者选择分支，因此在第二个单词边界匹配失败的时候，就没有其他选择可以尝试了。正则引擎会立即宣布从1开始的匹配失败。
正则引擎还会在字符串中的下一个字符位置尝试匹配该正则表达式，使用占有量词并不会改变这一点。如果这一正则表达式必须匹配整个目标文本，就需要使用定位符，这在实例2.5中已经讲解过。最终，正则引擎会从4开始的位置尝试匹配该正则表达式，并且找到匹配456。
使用贪心量词的区别是当在第一次匹配第二个‹b›的尝试失败之后，贪心量词会开始回溯。正则引擎接着会（没必要地）在2和3之间，以及1和2之间测试‹b›。
使用固化分组的匹配过程本质上是一样的。如果把正则表达式‹b(?>d+)b›（占有版本）应用到123abc 456之上，在目标文本的开始处会匹配单词边界。接着正则引擎会进入固化分组，‹d+›会匹配123。现在引擎退出固化分组。在这一点上，由‹d+›所记住的回溯位置都被丢弃了。当第二个‹b›匹配失败的时候，正则引擎没有其他选择，只能离开，因此会导致这次匹配尝试立即失败。与占有量词的版本一样，最终456会被找到。
我们描述占有量词不会去记住回溯位置，而固化分组则会把回溯位置丢弃。这样会更容易理解匹配过程，但是读者也不要太在意这里的区别，因为很可能在你所使用的正则流派中根本不存在这样的区别。在许多流派中，‹x++›仅仅是‹(?>x+)›语法上的简写，而二者的实现则完全是一模一样的。至于引擎是从来没有记住回溯位置，还是说它稍后会把这些位置丢弃，对于匹配尝试的最后结果来说是根本无关紧要的。
占有量词和固化分组的不同之处是占有量词只应用于单个正则表达式记号，而固化分组则可以把一个完整正则表达式包起来。
‹w++d++›和‹(?>w+d+)›是完全不一样的。‹w++d++›与‹(?>w+)(?>d+)›则是一样的，二者都无法匹配abc123。‹w++›可以完整匹配abc123。然后，正则引擎会在目标文本的结尾处试图匹配‹d++›。因为现在并不存在任何可以匹配的多余字符，所以‹d++›会匹配失败。因为没有保存任何回溯位置，匹配尝试失败。
‹(?>w+d+)›在同一个固化分组中拥有两个贪心量词。在这个固化分组中，回溯会正常发生。回溯的位置只有当引擎退出整个分组的时候才会被丢弃。当目标文本是abc123的时候，‹w+›会匹配abc123。贪心量词则会记住回溯的位置。当‹d+›匹配失败的时候，‹w+›会主动放弃一个字符。这样‹d+›就可以匹配3。现在，引擎会退出这个固化分组，并且丢弃掉为‹w+›和‹d+›记住的所有回溯位置。因为此时正则表达式已经到达了结尾，所以没有其他任务要完成。结果是找到了整体匹配。
如果还没有到达结尾，如‹(?>w+d+)d+›，我们就会遇到与‹w++d++›一样的情形。在目标文本的结尾处，不存在任何内容可以匹配第二个‹d+›。因为这时回溯位置已经被丢弃了，所以正则引擎只能宣布匹配失败。
占有量词和固化分组所做的不仅仅是优化正则表达式。它们也会通过排除可以利用回溯完成的匹配，而改变一个正则表达式最终找到的匹配。
本实例展示了如何使用占有量词和固化分组来进行一些较小的优化，而这些优化在性能测试中甚至可能不会表现出任何区别。下一个实例会讲解固化分组如何制造更加显著的不同。