正则表达式之回溯

    同样是上面的例子“文本主导”在扫描字符串时，会记录当前有效的所有匹配可。当引擎移动到t时，它会在当前处理的匹配可能中添加一个潜在的可能：

接下来扫描的每个字符，都会更新当前的可能匹配序列。继续扫描两个字符以后的情况是：

有效的可能匹配变为两个（knight被淘汰出局）。扫描到g时，就只剩下一个可能匹配了。当h和t匹配完成后，引擎发现匹配已经完成，报告成功。“文本主导”是因为它扫描的字符串中的每个字符都对引擎进行了控制。

    如果想要弄明白“表达式主导”是如何工作的，那就要看一下我们今天的主题“回溯（backtracking）”。回溯就像是在走岔路口，当遇到岔路的时候就先在每个路口做一个标记。如果走了死路，就可以照原路返回，直到遇见之前所做过的标记，标记着还未尝试过的道路。如果那条路也走不能，可以继续返回，找到下一个标记，如此重复，直到找到出路，或者直到完成所有没有尝试过的路。

    在许多情况下，正则引擎必须在两个（或更多）选项中做出选择。当遇到/……x?……/时，引擎必须是否尝试匹配X。对于/……X+……/的情况，毫无疑问，X至少尝试匹配一次――因为加号要求必须匹配至少一次。第一个X匹配之后，此要求已经满足，需要决定是否尝试下一个X。如果决定进行，还要决定是否匹配第三个X，第四个X，如此继续。每次选择，其实就是做一个标记，用于提示此处还有另一个可能的选择，保留起来以备用。在回溯的过程中要考虑两个要点：哪个分支应当首先选择？回溯的时候使用的是哪个（或者是哪些个）之前保存的分支？

    第一个问题是按下面这条重要原则来选择的：

        如果需要在“进行尝试”和“路过尝试”之间选择，对于匹配优先量词，引擎会优先选择“进行尝试”，而对于忽略优先量词，会选择“路过尝试”。

    第二个问题是按以下这条原则：

        距离当前最近储存的选项就是当本地失败强制回溯时返回的。使用的原则是LIFO（last in first out，后进先出）。

    我们先来看几个在道路中做标记的例子：

        1、未进行回溯的匹配

            用[ab?c]来匹配“abc”。[a]匹配之后，匹配的当前状态如下：

            现在轮到[b?]了，正则引擎需要决定：是需要尝试[b]呢，还是跳过？因为[？]是匹配优先的，它会尝试匹配。但是，为了确保在这个尝试最终失败之后能够恢复，引擎会把：

            最终的[c]也能成功匹配，所以整个匹配完成。备用状态不再需要了，所以不再保存它们。

        2、进行了回溯的匹配

            下面要匹配的文本是“ac”，在尝试[b]之前，一切都与之前的过程相同。显然，这次[b]无法匹配。也就是说，对[……？]进行尝试的路走不通了。因为有一个备用状态，这个“局部匹配失败”产工会导致整体匹配失败。引擎会进行回溯，也就是说，把“当前状态”切换为最近保存的状态。

            在[b]尝试之前保存的尚未尝试的选项。这时候，[c]可以匹配c，所以整个匹配宣告完成。

        3、不成功的匹配

            现在要匹配的文本是“abx”。在尝试[b]以前，因为存在问号，保存了这个备用状态：

            [b]能够匹配，但这条路往下却走不通了，因为[c]无法匹配x。于是引擎会回溯到之前的状态，“交还”b给[c]来匹配。显然，这次测试也失败了。如果还有其他保存的状态，回溯会继续进行，但是此时不存在其他状态，在字符串中当前位置开始的整个匹配也就宣告失败。

    目前对正则表达式的回溯只能理解这么多，以后我再慢慢补充吧！