2.15 避免失控重复
问题描述
使用一个正则表达式来匹配一个完整的HTML文件，并检查其中的html、head、title和body标签是否进行了正确嵌套。当HTML文件中不拥有正确标签的时候，该正则表达式必须能够高效地宣布匹配失败。
解决方案
<html>(?>.*?<head>)(?>.*?<title>)(?>.*?</title>)
(?>.*?</head>)(?>.*?<body[^>]*>)(?>.*?</body>).*?</html>
正则选项：不区分大小写、点号匹配换行符
正则流派：.NET、Java、PCRE、Perl、Ruby
JavaScript和Python不支持固化分组。因此在这两种正则流派中无法消除不必要的回溯。当使用JavaScript或者Python编程时，可以通过对这些标签一一进行字面文本查找来解决这个问题，在找到一个标签之后，再在剩余的目标文本中查找下一个标签。
讨论
从下面这个最原始的解答入手，对这个问题的正确解答会更加容易理解：
<html>.*?<head>.*?<title>.*?</title>↵
.*?</head>.*?<body[^>]*>.*?</body>.*?</html>
正则选项：不区分大小写、点号匹配换行符
正则流派：.NET、Java、JavaScript、PCRE、Perl、Python、Ruby
如果你在一个规范正确的HTML文件上测试这个正则表达式，它会完全正常地运行。‹.*?›会略过所有的内容，因为我们打开了“点号匹配换行符”的选项。懒惰的星号量词会确保这个正则表达式一次只会前进一个字符，每次都会检查是否匹配到了下一个标签。实例2.4和实例2.13中已经讲解过这一切。
但是，如果这个正则表达式需要处理并不包含所有这些HTML标签的目标文本，你就遇到麻烦了。最坏的情形是当</html>缺失的时候。
设想，正则引擎已经匹配了所有前面的标签，现在正在忙着处理最后‹.?›的匹配。因为‹</html>›永远无法匹配，所以‹.?›会一直匹配到文件的结尾。现在它无法匹配更多字符，所以宣布匹配失败。
但是这还不是故事的结束。另外6个‹.?›都记住了一个回溯位置，因此会允许它们进一步扩展。当最后一个‹.?›匹配失败的时候，它前面的那个会进行扩展，逐步匹配到< /body >。该标签之前被正则表达式中的字面量‹</body>›匹配。这个‹.?›会一直扩展到文件的结尾，在它之前所有的‹.?›惰性点号量词也同样会这样做。只有当第一个到达了文件末尾的时候，正则引擎才会宣布匹配失败。
这个正则表达式拥有最坏情形的复杂度1FFO(n7)，也就是目标文本长度的7次方。其中包含7个惰性点号量词，每一个都可能尝试匹配到文件的结尾。如果文件的大小增加一倍，正则表达式就可能需要增加128倍的处理步骤才能计算出它无法匹配。
我们把这种情形称作灾难性回溯（catastrophic backtracking）。由于出现了太多的回溯，正则表达式会无休止的匹配下去或者让你的应用程序崩溃。一些正则表达式实现会比较聪明，可能会及早退出这种失控的匹配尝试，但是即使在这种情况下，正则表达式也还是会严重影响程序的性能。
灾难回溯是一种被称作组合爆炸（combinatorial explosion）的现象的一种实例，其中几种正交条件交织起来，不得不尝试所有的组合。你也可以说正则表达式是不同重复操作符的笛卡尔乘积。
解决方案是使用固化分组来避免不必要的回溯。在‹< /body >›匹配成功之后，第6个‹.*?›就没有必要进行扩展。如果‹< /html >›匹配失败的话，那么扩展第6个惰性点号也不可能神奇地变出一个html终止标签。
要想使一个量词化的正则表达式记号在紧随其后的分界符匹配之后停止扩展，就需要把正则表达式的量词部分与分界符一起放到一个固化分组中：‹(?>.? body >)›。这样正则引擎就会在找到‹ body >›之后丢弃‹.? body >›所有的匹配位置。如果‹ html >›随后匹配失败的话，因为正则引擎已经忘记了‹.*? body >›的回溯位置，所以不会进行任何扩展。
如果我们对正则表达式中所有其他的‹.*?›都做同样的操作，那么它们就都不会再继续扩展。虽然在正则表达式中还是存在7个惰性点号，但是它们永远也不会产生交叉。这样就会把正则表达式的复杂度降低到O(n)，它与目标文本的长度之间是线性关系。而正则表达式的效率不可能比这更高了。
变体
如果你确实想知道灾难性回溯如何执行，那么可以在xxxxxxxxxx之上测试一下‹(x+x+)+y›。如果它很快就会失败，那么在目标文本中再添加一个x。重复这个过程，直到正则表达式要花费很长的时间来完成匹配或者你的应用程序因此崩溃。除非你使用的是Perl，否则并不需要添加太多的x字符就会出问题。
在本书中讨论的所有正则流派中，只有Perl有能力检测过分复杂的正则表达式，并且它会终止匹配尝试，而不会造成程序崩溃。
这个正则表达式的复杂度是O(2n)。当‹y›匹配失败的时候，正则引擎会尝试所有可能的排列组合，重复每个‹x+›以及包含它们的分组。例如，在尝试的过程后期，会出现一个这样的排列：‹x+›匹配xxx，第二个‹x+›匹配x，然后接着这个分组会被重复3次，其中每个‹x+›匹配x。如果存在10个x字符的话，就会存在1024种组合。如果把这个数量加到32，那么我们就会要处理超过40亿种组合，这肯定会让任何一种正则引擎耗尽内存，除非它包含一个安全开关，能够自己放弃，并且宣布你的正则表达式过于复杂。
该例中，这个没有多大意义的正则表达式可以很容易被重写为‹xx+y›，这样它就可以在线性时间内找到完全一样的匹配。在实践中，对于更加复杂的正则表达式可能就不会找到这样显而易见的解决方案了。
本质上来说，必须要小心某个正则表达式的两个或者更多个部分会匹配相同文本的情形。在这些情形中，可能会需要固化分组来确保正则引擎不会去尝试所有的方式以把目标文本根据正则表达式的这两个部分进行分割。在测试你的正则表达式时，应该总要使用包含部分可以匹配，但是又不能整体被正则表达式匹配的（较长）测试目标文本。