bsp;  

NFA, DFA
正则表达式引擎的两种类型，NFA: Nondeterministic Finite Automata, DFA: Deterministic Finite Automaton。
NFA基于正则表达式去匹配文本（文本作为有穷字母表Σ），而DFA是基于文本去匹配正则表达式。DFA捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。而NFA是捏着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来，然后接着往下干。一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。把多吃的字符吐出部分重新匹配的过程叫做backtracking（回溯）。
.Net中可以使用(?>patterns)，禁止对这个子表达式进行回溯，即对输入字符backtracking过程中，一旦遇到这个子表达式已经匹配的字符，就停止backtracking。下面示例演示了这个效果：
 Regular Expression  Input String  Result  
 (\\w)(\\1*)(a)   aaa ffffff 999999a999   1. aaa
 2. 999999a
 
 (\\w)(?>\\1*)(a)   aaa ffffff 999999a999   只有999999a [Page]
 因为在对aaa的匹配过程中，最后一个a被\\1*匹配上，但又不允许回溯，所以在读取aaa后面的那个空格字符后，发现跟子正则式(a)不匹配
 

NFA、DFA主要对比：
1. DFA对文本串只扫描一次，速度快（时间与有穷字母表Σ的大小成线性关系），但特性少;NFA需反复扫描文本串，速度慢，但特性多。目前主要正则表达式引擎基本都是NFA，例如Perl、Java、.Net、Python、Td、Emacs，DFA的引擎有awk、egrep、lex。
2. NFA最左子正则式优先匹配，DFA是最长左子正则式优先匹配。
3. 只有NFA支持lazy、backtracking、backreference，NFA缺省使用greedy模式，NFA可能陷入递归陷阱导致性能极差。DFA只包含有穷状态，匹配过程中无法捕获子表达式（分组）的匹配结果，因此也无法支持backreference。
有另一种NFA引擎，叫做POSIX NFA引擎。传统NFA在backtracking时，只要当前位置上的最左子正则式匹配成功就停止;而POSIX NFA会继续尝试backtracking，以试图像DFA一样找到最长左子正则式。因此POSIX NFA速度更慢。
 Engine   Regular Expression   Input String   Result  
 NFA   perl|perlman   perlman book  perl 
 NFA   perlman|perl   perlman book  perlman 
 DFA   perl|perlman   perlman book   perlman   

详细的NFA、DFA定义、算法，参考编译原理。

附加说明
1. 正则表达式在发展过程中，形成了很多版本的引擎，最基本的为grep，为了使grep具备更多特性而扩展出egrep， 目前使用的大多数正则引擎都是backtracking型的NFA。不同的正则表达式引擎之间，实现上多少也都有些差别，并且开发商还可能作出特有的扩展、语法形式等。因此，这就意味着并不是同一个正则表达式就会适用于所有的环境，例如.Net中的正则表达式，就不一定能在Java、Python、Unix中工作，这在网上查找正则表达式资源时需要注意。
2. 使用传统NFA，书写正则表达式需要特别注意性能问题，否则很容易导致死循环、性能极差等情况。
 &nbs