三种正则表达式引擎类型（Python用的是NFA 匹配器）
×××××××××××××××××××

.NET Framework 正则表达式引擎 (regex) 是回溯的正则表达式匹配器，它并入了传统的非确定性有限自动机 (NFA)
引擎（例如 Perl、Python、Emacs 和 Tcl 使用的引擎）。这令其区别于更快的、但功能更有限的纯正则表达式确定性有限自动机
(DFA) 引擎，例如在 awk、egrep 或 lex 中提供的那些引擎。这也使其有别于标准化的、但较慢的 POSIX NFA。

本节概述了三种引擎类型的优缺点，并解释了 .NET Framework 引擎为什么实现传统的 NFA 匹配器。

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

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

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

程序员更为喜欢传统的 NFA 引擎的原因在于，NFA 引擎与 DFA 或 POSIX NFA 引擎相比更易于表达。尽管在最坏情况下 NFA
引擎的运行速度稍慢，但您可以通过使用降低多义性和限制回溯的模式，控制这些引擎以在线性时或多项式时状态下查找匹配。


（再次感叹MSDN文档的博大精深，如果有个PSDN并且是中文的，该有多好啊）

匹配行为
.NET Framework 正则表达式引擎 (regex) 是回溯的正则表达式匹配器，它并入了传统的非确定性有限自动机 (NFA)
引擎（例如 Perl、Python、Emacs 和 Tcl 使用的引擎）。这令其区别于更快的、但功能更有限的纯正则表达式确定性有限自动机
(DFA) 引擎，例如在 awk、egrep 或 lex 中提供的那些引擎。这也使其有别于标准化的、但较慢的 POSIX NFA。

三种正则表达式引擎类型
本节概述了三种引擎类型的优缺点，并解释了 .NET Framework 引擎为什么实现传统的 NFA 匹配器。

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

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

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

程序员更为喜欢传统的 NFA 引擎的原因在于，NFA 引擎与 DFA 或 POSIX NFA 引擎相比更易于表达。尽管在最坏情况下 NFA
引擎的运行速度稍慢，但您可以通过使用降低多义性和限制回溯的模式，控制这些引擎以在线性时或多项式时状态下查找匹配。

.NET Framework 引擎功能
在充分利用传统 NFA 引擎优点的基础上，.NET Framework
正则表达式引擎包括了一组完整的构造，让程序员能够操纵回溯引擎。这些构造可被用于更快地找到匹配，或支持特定扩展，而非其他扩展。