不同正则库使用的引擎以及自动机DFA/NFA

正则表达式引擎分成两类，一类称为DFA（确定性有穷自动机）Deterministic Finite Automation，另一类称为NFA（非确定性有穷自动机）。两类引擎要顺利工作，都必须有一个正则式和一个文本串，一个捏在手里，一个吃下去。DFA捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。而NFA是捏着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来：“某年某月某日在某处匹配上了！”，然后接着往下干。一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。

DFA与NFA机制上的不同带来5个影响：

1. DFA对于文本串里的每一个字符只需扫描一次，比较快，但特性较少；NFA要翻来覆去吃字符、吐字符，速度慢，但是特性丰富，所以反而应用广泛，当今主要的正则表达式引擎，如Perl、Ruby、Python的re模块、Java和.NET的regex库，都是NFA的。

2. 只有NFA才支持lazy和backreference等特性；

3. NFA急于邀功请赏，所以最左子正则式优先匹配成功，因此偶尔会错过最佳匹配结果；DFA则是“最长的左子正则式优先匹配成功”。

4. NFA缺省采用greedy量词；

5. NFA可能会陷入递归调用的陷阱而表现得性能极差。

正则表达式引擎所使用的两种基本技术：非确定型有穷自动机（NFA）和确定型有穷自动机（DFA）。

NFA是基于表达式的（Regex-Directed），去匹对相配文档（文档作为有穷字母表Σ），而DFA是基于文本的（Text-Directed），去匹对相配正则表达式。

目前的主流正则引擎又分为3类：一、DFA，二、传统型NFA，三、POSIX NFA。

DFA：

DFA 引擎在线性时状态下执行，因为它们不要求回溯（并因此它们永远不测试相同的字符两次）。DFA 引擎还可以确保匹配最长的可能的字符串。但是，因为 DFA 引擎只包含有限的状态，所以它不能匹配具有反向引用的模式；并且因为它不构造显示扩展，所以它不可以捕获子表达式。

NFA：

传统的 NFA 引擎运行所谓的“贪婪的”匹配回溯算法，以指定顺序测试正则表达式的所有可能的扩展并接受第一个匹配项。因为传统的 NFA 构造正则表达式的特定扩展以获得成功的匹配，所以它可以捕获子表达式匹配和匹配的反向引用。？但是，因为传统的 NFA 回溯，所以它可以访问完全相同的状态多次（如果通过不同的路径到达该状态）。因此，在最坏情况下，它的执行速度可能非常慢。因为传统的 NFA 接受它找到的第一个匹配，所以它还可能会导致其他（可能更长）匹配未被发现。

NFA最重要的部分：回溯（backtracking）。回溯就像是在道路的每个分岔口留下一小堆面包屑。如果走了死路，就可以照原路返回，直到遇见面包屑标示的尚未尝试过的道路。如果那条路也走不通，你可以继续返回，找到下一堆面包屑，如此重复，直到找到出路，或者走完所有没有尝试过的路。

POSIX NFA：

POSIX NFA 引擎与传统的 NFA 引擎类似，不同的一点在于：在它们可以确保已找到了可能的最长的匹配之前，它们将继续回溯。因此，POSIX NFA 引擎的速度慢于传统的 NFA 引擎；并且在使用 POSIX NFA 时，您恐怕不会愿意在更改回溯搜索的顺序的情况下来支持较短的匹配搜索，而非较长的匹配搜索。

DFA与NFA对比：

1. DFA对于文本串里的每一个字符只需扫描一次，比较快，但特性较少；

   NFA要翻来覆去吃字符、吐字符，速度慢，但是特性丰富，所以反而应用广泛。

   当今主要的正则表达式引擎，如Perl、Ruby、Python的re模块、Java和.NET的regex库，都是NFA的。

2. 只有NFA支持lazy、backtracking、backreference，NFA缺省应用greedy模式，NFA可能会陷入递归险境导致性能极差。

    DFA只包含有穷状态，匹对相配过程中无法捕获子表达式（分组）的匹对相配结果，因此也无法支持backreference。

    DFA不能支持捕获括号和反向引用。

    POSIX NFA会继续尝试backtracking，以试图像DFA相同找到最长左子正则式。因此POSIX NFA速度更慢。 

3. NFA是最左子式匹配，而DFA是最长左子式匹配。

4. NFA的编译过程通常要快一些，需要的内存也更少一些。

    对于“正常”情况下的简单文本匹配测试，两种引擎的速度差不多。

    一般来说，DFA的速度与正则表达式无关，而NFA中两者直接相关。

5. 对正则表达式依赖性较量强的操作系统（大量应用正则做搜索匹对相配），最好完全把握NFA->DFA算法，充分理解所应用的正则表达式引擎的思想和特性。--- 使用AC多模匹配算法来进行转换？参见snort软件。

目前正则引擎支持的语言种类：

引擎类型	程序
DFA	awk(大多数版本)、egrep（大多数版本）、flex、lex、MySQL、Procmail
传统型 NFA	GNU Emacs、Java、grep（大多数版本）、less、more、.NET语言、PCRE library、Perl、PHP（所有三套正则库）、Python、Ruby、set（大多数版本）、vi
POSIX NFA	mawk、Mortice Lern System's utilities、GUN Emacs（明确指定时使用）
DFA/NFA混合	GNU awk、 GNU grep/egrep、 Tcl

简单地说，DFA 自动机的时间复杂度是线性的，更加稳定，但是功能有限。而 NFA 的时间复杂度比较不稳定，有时候很好，有时候不怎么好，好不好取决于你写的正则表达式。但是胜在 NFA 的功能更加强大，所以包括 Java 、.NET、Perl、Python、Ruby、PHP 等语言都使用了 NFA 去实现其正则表达式。

使用NFA可能导致CPU 使用率高，关键原因就是： NFA 自动机，这种正则表达式引擎在进行字符匹配时会发生回溯（backtracking）。而一旦发生回溯，那其消耗的时间就会变得很长，有可能是几分钟，也有可能是几个小时，时间长短取决于回溯的次数和复杂度。

C/C++语言常用的正则库GNU Regex Library（glibc）使用DFA/NFA混合，而PCRE则使用传统型的NFA，两则在性能上会有一些区别。