Regex-Directed Versus Text-Directed

DFA和NFA反映了将正则表达式在应用算法上的根本差异。我把对应汽油机的NFA称为“表达式主导（regex-directed）”引擎，而对应电动机的DFA称为“文本主导（text-directed）”引擎。

NFA引擎：表达式主导

NFA Engine:Regex-Directed

我们来看用「to（nite|knight|night）」匹配文本‘…tonight…’的一种办法。正则表达式从「t」开始，每次检查一部分（由引擎查看表达式的一部分），同时检查“当前文本（current text）”是否匹配表达式的当前部分。如果是，则继续表达式的下一部分，如此继续，直到表达式的所有部分都能匹配，即整个表达式能够匹配成功。

在「to（nite|knight|night）」的例子中，第一个元素是「t」，它将会重复尝试，直到在目标字符串中找到‘t’为止。之后，就检查紧随其后的字符是否能由「o」匹配，如果能，就检查下面的元素。在本例中，“下面的元素”指「（nite|knight|night）」它的真正含义是“「nite」或者「knight」或者「night」”。引擎会依次尝试这 3 种可能。我们（具有高级神经网络的人类）能够发现，如果待匹配的字符串是 tonight，第三个选择能够匹配。不论神经学起源（☞85）如何，表达式主导的引擎必须完全测试，才能得出结论。

尝试「nite」的过程与之前一样：“尝试匹配「n」，然后是「i」，然后是「t」，最后是「e」。”如果这种尝试失败——就像本例，引擎会尝试另一种可能，如此继续下去，直到匹配成功或是报告失败。表达式中的控制权在不同的元素之间转换，所以我称它为“表达式主导”。

NFA引擎在操作上的优点

实质上，在表达式主导的匹配过程中，每一个子表达式都是独立的。这不同于反向引用，子表达式之间不存在内在联系，而只是整个正则表达式的各个部分。在子表达式与正则表达式的控制结构（多选分支、括号以及匹配量词）的层级关系（layout）控制了整个匹配过程。

因为NFA引擎是正则表达式主导的，驾驶员（也就是编写表达式的人）有充足的机会来实现他/她期望的结果（第5章和第6章将会告诉读者，如何正确高效地实现目标）。现在看起来，这点还有些模糊，但过一段就会变清晰。

DFA引擎：文本主导

DFA Engine:Text-Directed

与表达式主导的NFA不同，DFA引擎在扫描字符串时，会记录“当前有效（currently in the works）”的所有匹配可能。具体到 tonight的例子，引擎移动到 t时，它会在当前处理的匹配可能中添加一个潜在的可能：

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

有效的可能匹配变为两个（knight被淘汰出局）。扫描到g时，就只剩下一个可能匹配了。当h和t匹配完成后，引擎发现匹配已经完成，报告成功。

我称这种方式为“文本主导”，是因为它扫描的字符串中的每个字符都对引擎进行了控制。在本例中，某个未完成的匹配也许是任意多个（只要可行）匹配的开始。不合适的匹配可能在扫描后继文字时会被去除。在某些情况下，“处理中的未终结匹配（partial match in progress）”可能就是一个完整的匹配。例如正则表达式「to（…）？」，括号内的部分并不是必须出现的，但考虑到匹配优先的性质，引擎仍然会尝试匹配括号内的部分。匹配过程中，在尝试括号内的部分时，完整匹配（‘to’）已经保留下来，以应付括号中的内容无法匹配的情况。

如果引擎发现，文本中出现的某个字符会令所有处理中的匹配可能失效，就会返回某个之前保留的完整匹配。如果不存在这样的完整匹配，则要报告在当前位置无法匹配。

第一想法：比较NFA与DFA

First Thoughts:NFA and DFA in Comparison

如果读者根据上面介绍的知识比较NFA和DFA，可能会得出结论：一般情况下，文本主导的DFA引擎要快一些。正则表达式主导的NFA引擎，因为需要对同样的文本尝试不同的子表达式匹配，可能会浪费时间（就好像上面例子中的3个分支）。

这个结论是对的。在NFA的匹配过程中，目标文本中的某个字符可能会被正则表达式中的不同部分重复检测（甚至有可能被同一部分反复检测）。即使某个字表达式能够匹配，为了检查表达式中剩下的部分，找到匹配，它也可能需要再一次应用（甚至可能反复多次）。单独的子表达式可能匹配成功，也可能失败，但是，直到抵达正则表达式的末尾之前，我们都无法确知全局匹配成功与否（也就是说“不到最后关头不能分胜负（It’s not over until the fat lady sings）”，但这句话又不符合本段的语境）。相反，DFA引擎则是 确定型的（deterministic）——目标文本中的每个字符只会检查（最多）一遍。对于一个已经匹配的字符，你无法知道它是否属于最终匹配（它可能属于最终会失败的匹配），但因为引擎同时记录了所有可能的匹配，这个字符只需要检测一次，如此而已。

正则表达式引擎所使用的两种基本技术，都对应有正式的名字：非确定型有穷自动机（NFA）和确定型有穷自动机（DFA）。这两个名字实在是太饶舌，所以我坚持只用 DFA 和 NFA。下文中不会出现它们的全称了（注4）。

用户需要面对的结果

因为NFA具有表达式主导的特性，引擎的匹配原理就非常重要。我已经说过，通过改变表达式的编写方式，用户可以对表达式进行多方面的控制。拿 tonight的例子来说，如果改变表达式的编写方式，可能会节省很多工夫，比如下面这3种方式：

●「to(ni(ght|te)|knight)」

●「tonite|toknight|tonight」

●「to(k?night|nite)」

给出任意文本，这 3 个表达式都可以捕获相同的结果，但是它们以不同的方式控制引擎。现在，我们还无法分辨这3者的优劣，不过接下来会看到。

DFA的情况相反——引擎会同时记录所有的匹配选择，因为这3个表达式最终能够捕获的文本相同，在写法上的差异并无意义。取得一个结果可能有上百种途径，但因为DFA能够同时记录它们（有点神奇，待稍后详述），选择哪一个表达式并无区别。对纯粹的 DFA 来说，即使「abc」和「 [aa-a]（b|b{1}|b）c」看来相差巨大，但其实是一样的。

如果要描述DFA，我能想到的特征有：

●DFA匹配很迅速。

●DFA匹配很一致。

●谈论DFA匹配很恼人。

最终我会展开这3点。

因为NFA是表达式主导的，谈论它是件很有意思的事情。NFA为创造性思维提供了丰富的施展空间。调校好一个表达式能带来许多收益，调校不好则会带来严重后果。这就好比发动机的熄火和点不着火，他们并不只是汽油发动机的专利。为了彻底弄明白这个问题，我们来看NFA最重要的部分：回溯（backtracking）。