共计 2155 个字符，预计需要花费 6 分钟才能阅读完成。
正则表达式引擎 所使用的两种基本技术：非确定型有穷自动机（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,ergp,less,more,.NET 语言,PCRE library,Perl,PHP,Python,Ruby,sed,vi；
使用 POSIX NFA 引擎的程序主要有：mawk,Mortice Kern Systems’ utilities,GNU Emacs(使用时可以明确指定)；
也有使用 DFA/NFA 混合的引擎：GNU awk,GNU grep/egrep,Tcl。GNU grep 采取了一种简单但有效的策略。它尽可能多地使用 DFA，在需要反向引用的时候，才切换到 NFA。GNU awk 的办法也差不多 —— 在进行 “ 是否匹配 ” 的检查时，它采用 GNU grep 的 DFA 引擎，如果需要知道具体的匹配文本的内容，就采用不同的引擎。这里的 “ 不同的引擎 ” 就是 NFA，利用自己的 gensub 函数，GNU awk 能够很方便地提供捕获括号。
引擎库：
- PCRE(Perl Compatible Regular Expressions)是一个 Perl 库，包括 perl 兼容的正规表达式库。
- boost::regex
PCRE 是一个轻量级的函数库，比 Boost 之中的正则表达式库小得多。PCRE 十分易用，同时功能也很强大，性能超过了 POSIX 正则表达式库和一些经典的正则表达式库。
和 Boost 正则表达式库的比较显示，双方的性能相差无几，PCRE 在匹配简单字符串时更快，Boost 则在匹配较长字符串时胜出。PCRE 被广泛使用在许多开源软件之中，最著名的莫过于 Apache HTTP 服务器和 PHP 脚本语言、R 脚本语言，此外，正如从其名字所能看到的，PCRE 也是 perl 语言的缺省正则库。
