这一章的内容是有关于正则表达式的匹配原理中一个很重要的内容：回溯。前面的内容基本已经包含了正则表达式的所有常用的内容（针对于NFA引擎）。这一章的目的是想在基础上更深入一点点，写一点关于匹配原理的内容。所以这章的内容会有些稍难。在讲回溯之前，我们先来看看正则表达式的引擎分类。

正则表达式引擎

   在汽车中，引擎的作用是驱动汽车前进的。而在正则表达式中，引擎的作用同样是驱动正则表达式前进的。不同的引擎对相同的表达式能输出同样的结果，但是它们驱动的过程不同，效率也不同，不同引擎支持的功能也不同。至于为什么会几类引擎，这是在正则表达式的发展中衍生出来的。

   这里用《精通正则表达式》中的比喻来讲解引擎的分类。汽车已经诞生很久了，之前的小汽车一直使用的是汽油发动机。后来北京市出台了尾气排放标准，这时候，有一些汽油发动机就不能满足这个排放标准了。而另一些汽油发动机依然能满足这个新的尾气排放标准。它们在本质上并没有不同，都还是汽油发动机。只是按照这个北京市的新标准被分为了两类。然后后来，电动发动机被发明了，它们更稳定，更快，也能满足这个排放标准，但是它们不普及。这个北京市出台的新标准很好，很棒。但是它只能针对北京市，其它地方的汽车它管不了。所以这个新的标准对大多数的车并没有影响。最终的结果就是传统的汽油机依然被大多数的车使用，标准汽油机和电动机只有少部分车在使用。

   现在出现了三种发动机：传统汽油机、标准汽油机、电动机。它们对应的正则表达式引擎就是：传统型NFA、POSIX NFA、DFA。

   在这不对引擎进行过多的描述，我们只需要知道，现在使用的正则表达式工具，绝大多数用的引擎还是传统型NFA就够了。

回溯

   回溯是NFA引擎最重要的性质。在正则表达式遇到需要在两个可能成功的表达式中进行选择，它会先选择其一，同时记住另一个，以备稍候可能的需要。需要做出选择的情形包括量词和多选结构。举个例子：

   正则表达式：(abc|xyz)

   上面这个多选结构的意思就是在可以匹配【abc】或者【xyz】中的一个，即两个都有可能匹配成功。那么假设它要匹配的文本是【xyz】。匹配时，引擎会首先选择abc来进行匹配。在进行匹配之前，引擎会记住还有一个备用状态也可能匹配成功。正则表达式【abc】匹配失败以后，引擎就会进行回溯，文本部分回到【xyz】开头的位置，正则部分开始用【xyz】对文本进行匹配，匹配以后能匹配成功，匹配的文本是【abc】。

   《精通正则表达式》中用了一个经典的现实世界的例子来描述备用状态和回溯。回溯就像在走迷宫，走到岔路的时候就选择要走的分岔口，然后在另一个分岔口留下一小堆面包屑。往前走，如果遇到岔路，就进行选择，在另一条岔路口留下一小堆面包屑。如果走进岔路以后发现是条死路，就回头。找到最后一次放面包屑的岔路口路，进行另一条路的尝试，如此循环，直到所有的可能性都尝试过。有可能中途能走出迷宫（匹配成功），有可能尝试完所有的路都无法走出迷宫（匹配失败）

   回溯的情形就和上面这个草图一样。举个例子的话就是这样：

   正则表达式：ab?c

   上面这个正则，假设要匹配的文本是【ac】，正则a首先匹配字符【a】，然后b?这进行选择，匹配还是不匹配？由于该处的量词是匹配优先的，就要进行匹配，然后在另一条路（不匹配b的情形）留下一个备用状态。之后匹配失败b?无法匹配字符【c】，引擎进行回溯，回溯到备用状态，进行不匹配正则b?的情形。这时候由于不匹配正则b，直接进行正则c的匹配。可以与字符【c】想匹配。所以此匹配成功，匹配结果为【ac】

正则表达（五）——引擎、回溯