Start Your Engines!

现在我们来看看，引擎的类比能为我们提供多大帮助。引擎的价值在于，有了它，你不需要花多少气力就能从一个地方移动到另一个地方。驾驶员只需要放松或者听听音乐，发动机会完成余下的事情。它的主要任务就是驱动车轮，而驾驶员没必要关心它是如何工作的。是这样吗？

两类引擎

Two Kinds of Engines

设想一下驾驶电动汽车的情形？电动汽车已经诞生很久了，但它们不像汽油发动机驱动的汽车那样普及，因为电动汽车还不够成熟。如果你有辆电动汽车，请记住别给它加油。如果你的汽车采用汽油发动机，请务必远离烟火。电动机几乎总是“能够运行”，汽油机则需要多加保养。更换火花塞、空气过滤器，或者换用不同品牌的汽油，有可能大大提升发动机的效率。当然，也可能降低汽油机的性能，或者导致发动机罢工。不同引擎的工作原理也有不同，但目的都是驱动车轮。不过，如果你想开车去某个地方，还得把好方向盘，当然，这是题外话。

新的标准

New Standards

让我们看看添加一条新规范：加利福尼亚州的尾气排放标准（注 1）。一些发动机达到了加州的严格排放标准，一些则没有。这两类发动机并没有本质的不同，只是按标准划分为两类。这些标准规定了发动机尾气排放的成分，而并没有规定发动机应该怎样做才能达标。所以，现在我们可以把之前的两分法变为四分法：符合标准的电动机、不符合标准的电动机、符合标准的汽油机和不符合标准的汽油机。

回到原来的话题，我敢打赌，电动机不需要做多少改动就可以达标——标准只是“规定”尾气的成分，而电动机几乎没有尾气。相反，汽油机要达标可能就需要大的修改和更新。使用汽油发动机的驾驶员尤其需要注意汽油的型号——如果加错了油，他们就惹上大麻烦了。

标准的作用

更严格的排放标准是个好玩意儿，但驾驶员也需要考虑更多，同时更加小心（至少对汽油车来说如此）。不过坦白说，新标准对大多数人没有什么影响，因为其他州不会施行加州的标准。

所以你知道，四种类型的发动机其实可以分为三类：两类是汽油机，一类是电动机。虽然它们都是驱动车轮的，但你明白了其中的差异。你不知道的是，这堆复杂的玩意与正则表达式有什么关系！其实这里面的关系远比你能想象的要复杂。

正则引擎的分类

Regex Engine Types

正则引擎主要可以分为基本不同的两大类：一种是DFA（相当于之前说的电动机），另一种是NFA（相当于前面的汽油机）。我们很快就会知道DFA和NFA的具体含义，但是现在读者只需要知道这两个名字，就像“Bill”和“Ted”，“汽油机”和“电动机”一样。

DFA 和NFA 都有很长的历史，不过，正如汽油机一样，NFA 的历史更长一些。使用NFA的工具包括.NET、PHP、Ruby、Perl、Python、GNU Emacs、ed、sec、vi、grep的多数版本，甚至还有某些版本的egrep和awk。而采用DFA的工具主要有egrep、awk、lex和flex。也有些系统采用了混合引擎，它们会根据任务的不同选择合适的引擎（甚至对同一表达式中的不同部分采用不同的引擎，以求得功能与速度之间的最佳平衡）。表4-1列出了少量常用的工具及其大多数版本使用的引擎。如果你最喜欢的工具没有名列其中，可以参考下一页的“测试引擎的类型”来找到答案。

表4-1：部分程序及其所使用的正则引擎

第3章已经讲过，NFA和DFA都发展了二十多年，产生了许多不必要的变体，结果，现在的情况比较复杂。POSIX标准的出台，就是为了规范这种现象，POSIX标准不但清楚地规定了前一章中提到的引擎应该支持的元字符和特性，还明确规定了使用者期望由表达式获得的准确结果。除开表面细节不谈，DFA（也就是电动机）显然已经符合新的标准，但是NFA风格的结果却与此不一，所以NFA需要修改才能符合标准。这样一来，正则引擎可以粗略地分为3类：

●DFA（符合或不符合POSIX标准的都属此类）。

●传统型NFA。

●POSIX NFA.

这里提到的POSIX是匹配意义上的，也就是说，POSIX标准规定的某个正则表达式的应有行为（本章稍后部分将讨论）；而不是指POSIX标准引入的匹配特性。许多程序支持这些特性，但结果与POSIX规范不完全一致。

老式（功能极少的）程序，比如egrep、awk、lex之类，一般都是使用DFA引擎（电动机），所以，新的标准只是肯定了既有的情况，而没有大的改变。但是也存在一些汽油机版本的此类程序，如果它们需要达到POSIX标准，就需要做些修改。通过了加州排放标准测试（POSIX NFA）的汽油机能够产生符合标准的结果，但是这些必要的修改会增加保养的难度。以前，错位的火花塞也能应付着使用，但现在根本就点不着火。以前还能“凑合”的汽油，现在会弄得发动机砰砰乱响。不过，一旦掌握其中的门道，发动机就能平稳安静地运转了。

几句题外话

From the Department of Redundancy Department

现在，我请读者回过头去，重新思考关于引擎的故事。其中的每句话都涉及某些与正则表达式相关的事实。读第二遍会引起许多思考。尤其是，为什么说电动机（DFA引擎）只是“能够运行”。什么影响了汽油机（NFA）？使用NFA引擎时，应该如何调整才能获得期望的结果？通过（排放）测试的POSIX DFA有什么特别之处？现实中“熄火的引擎”又是什么？

测试引擎的类型

Testing the Engine Type

工具所采用的引擎的类型，决定了引擎能够支持的特性以及这些特性的用途。所以，通常情况下，我们只需要几个测试用的表达式，就能判断出程序所使用的引擎类型（毕竟，如果你不能分辨引擎的类型，这种分类就没有意义）。现在，我并不期望读者理解下面的这些测试原理，我只是提供一些测试表达式，即使读者最喜欢使用的软件没有出现在表4-1之内，也可以判断出引擎的类型，继续阅读本章的其他内容。

是否传统型NFA

传统型NFA是使用最广泛的引擎，而且它很容易识别。首先，看看忽略优先量词（☞141）是否得到支持？如果是，基本就能确定这是传统型 NFA。我们将要看到，忽略优先量词是DFA不支持的，在POSIX NFA中也没有意义。为了确认这一点，只需要简单地用正则表达式「nfa|nfa·not」来匹配字符串‘nfa·not’，如果只有‘nfa’匹配了，这就是传统型NFA。如果整个‘nfa not’都能匹配，则此引擎要么是POSIX NFA，要么是DFA。

DFA还是POSIX NFA

某些情况下，DFA 与 POSIX NFA 的区别是很明显的。DFA 不支持捕获型括号（capturing parentheses）和回溯（backreferences），这一点有助于判断，不过，也存在同时使用两种引擎的混合系统，在这种系统中，如果没有使用捕获型括号，就会使用DFA。

下面这个简单的测试能说明很多问题，用「X（.+）+X」来匹配形如‘=XX======================’的字符串，例如使用egrep命令：

echo=XX=========================================|egrep\'X(.+)+X\'

如果执行需要花很长时间，就是NFA（如果上一项测试显示这不是传统型NFA，那么它肯定是POSIX NFA）。如果时间很短，就是DFA，或者是支持某些高级优化的NFA。如果显示堆栈超溢（stack overflow），或者超时退出，那么它是NFA引擎。