原文链接http://www.softec.lu/site/RegularExpressions/RegularExpressionEngines

正则表达式引擎是正则表达式匹配算法的根底。其有多种不同的实现，但大多数都是基于Henry Spencer的NFA引擎。

正则引擎有两个大分类，DFA和NFA，像Perl、Java、.Net、PHP、Python、Ruby……等大多是工具都是用了NFA引擎。多数宽泛被应用的工具如mawk应用了POSIX NFA引擎（NFA的一种变种）。以高效著称的工具采纳了更为高效的DFA引擎。诸如GNU awk，GNU egrep和Tcl之类的一些工具联合了NFA / DFA两种引擎，将两者的长处联合在一起。

基于不同类型引擎的实现的正则表达式，次要有以下几点差别。

  • 语法
  • 匹配内容
  • 零宽断言(环视) 性能
  • 捕捉性能
  • 性能

所有的引擎都会对文本做从左向右的最长匹配，但具体细节取决于应用了何种引擎。

传统的NFA引擎

NFA引擎中应用的非确定无限状态机(Nondeterministic finite automation)是一种由要匹配的表达式驱动的算法。这使得正则表达式像一个小的编程语言一样，可管制引擎在匹配失败时候的行为。

正则引擎从正则表达式其实地位开始，尝试正则表达式与文本的结尾进行匹配，如果匹配胜利，都后退一个配置，否则文本始终后退到下一个字符，直到匹配。 如果正则表达式须要作出抉择（例如应用代替词或可选的量词），它将抉择其中之一，并记住其余抉择以及在文本中进行抉择的地位。如果在之后的解决中，匹配失败，并且还有其余可选的门路，则引擎将回溯做之前作出抉择的地位，并尝试其余的抉择。如果没有其余可用的代替计划，则匹配失败，引擎后退到下一个字符并从头开始匹配正则表达式。

如果引擎达到了正则表达式的开端并且所有内容都已匹配，则引擎就会认为匹配胜利，并最终放弃所有剩下的代替办法，甚至不再持续摸索。这里有很重要的一点：抉择不同门路的程序很重要，它决定是是否能做到最长匹配。

引擎会真正依照正则表达式进行匹配，让你抉择达到齐全匹配所需的每个步骤。你必须很审慎地通知它，首先查看哪种抉择能力达到您的冀望。你也有机会调整正则表达式，以最大水平地缩小回溯并尽早进行匹配。 NFA引擎中应用的办法的一些示例也能够帮忙你理解回溯是如何工作的。

POSIX NFA 引擎

POSIX NFA引擎相似于传统NFA引擎，然而当找到胜利的匹配项时，它将会记录匹配后果，并且尝试其余可用的代替办法以查找是否能够找到更长的最右边的匹配。 这打消了传统NFA引擎中不能保障最长最左匹配的问题。

以弗里德尔（Friedl）的书中的这个乏味的例子为例：用one(self)?(selfsufficient)? 去匹配oneselfsufficient，传统的NFA将匹配 oneself，而POSIX NFA将匹配oneselfsufficient，因为(self)?有两种抉择，匹配self或者啥都不匹配，显然最终匹配到的更长。

DFA引擎

DFA引擎中应用的确定性无限自动机（Deterministic finite automaton）是一种由要搜寻的文本驱动的算法。 对于搜寻到的文本中的每个字符，DFA引擎只会查看一次。 实际上，它相当于并行尝试了NFA中所有可能的代替办法，并将返回其中最长的匹配。

这种办法的确更高效，但也有很多毛病：

  • 你无法控制表达式返回匹配项的形式，无论您如何结构表达式，它始终将返回最长最左匹配。
  • 没有回溯，因而所有反复的运算符都是贪心的。 原子分组和所有格修饰符也是无稽之谈。 (更多详细信息，请查阅RegularExpressionsBacktracking）
  • 不反对零宽断言(环视)
  • 捕捉和反向援用也不可能实现
  • 正则表达式预编译工夫更长，占用更多内存

NFA和DFA混合引擎

因为DFA引擎速度快，但NFA引擎的性能多，因而，混合NFA / DFA引擎试图将二者的劣势联合起来。 迄今为止惟一可用的齐全混合实现是Tcl中应用的Henry Spencer引擎，它是对原始实现的齐全重写。 像GNU egrep和awk只是将两个独立的引擎放一起，而后依据是否应用了NFA特有的性能决定应用哪个引擎。