正则表达式有关引擎
正则引擎主要可以分为两大类：一种是DFA，一种是NFA。这两种引擎都有了很久的历史(至今二十多年)，当中也由这两种引擎产生了很多变体！于是POSIX的出台产生规范了不必要变体的继续产生。这样一来，目前的主流正则引擎又分为3类：一、DFA，二、传统型NFA，三、POSIX NFA。
目前使用DFA引擎的程序主要有：awk（大多数版本）,egrep（大多数版本）,flex,lex,MySQL,Procmail等；
使用传统型NFA引擎的程序主要有：GNU Emacs,Java,grep(大多数版本),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。
举例简单说明NFA与DFA工作的区别：
非确定型有穷自动机（NFA）”也可以叫做“表达式主导”；另外一种是“确定型有穷自动机（DFA）”也可以叫做“文本主导”。
比如有字符串this is yansen’s blog，正则表达式为 /ya(msen|nsen|nsem)/ (不要在乎表达式怎么样，这里只是为了说明引擎间的工作区别)。
NFA工作方式如下，先在字符串中查找 y 然后匹配其后是否为 a ，如果是 a 则继续，查找其后是否为 m 如果不是则匹配其后是否为 n (此时淘汰msen选择支)。然后继续看其后是否依次为 s,e，接着测试是否为 n ，是 n 则匹配成功，不是则测试是否为 m 。为什么是 m ？因为 NFA 工作方式是以正则表达式为标准，反复测试字符串，这样同样一个字符串有可能被反复测试了很多次！
而DFA则不是如此，DFA会从 this 中 t 开始依次查找 y，定位到 y ，已知其后为 a ，则查看表达式是否有 a ，此处正好有 a 。然后字符串 a 后为 n ，DFA依次测试表达式，此时 msen 不符合要求淘汰。nsen 和 nsem 符合要求，然后DFA依次检查字符串，检测到sen 中的 n 时只有nsen 分支符合，则匹配成功！
由此可以看出来，两种引擎的工作方式完全不同，一个(NFA)以表达式为主导，一个(DFA)以文本为主导！一般而论，DFA引擎则搜索更快一些！但是NFA以表达式为主导，反而更容易操纵，因此一般程序员更偏爱NFA引擎！
名词“回溯”
回溯就像是在走岔路口，当遇到岔路的时候就先在每个路口做一个标记。如果走了死路，就可以照原路返回，直到遇见之前所做过的标记，标记着还未尝试过的道路。如果那条路也走不能，可以继续返回，找到下一个标记，如此重复，直到找到出路，或者直到完成所有没有尝试过的路。
一、分支和回溯
下面的例子演示了这一过程是如何处理分支的。
/h(ello|appy) hippo/.test("hellothere, happyhippo");
此正则表达式匹配“hellohippo”或“happyhippo”。测试一开始，它要查找一个h，目标字符串的第一个字母恰好就是h，它立刻就被找到了。接下来，子表达式（ello|appy）提供了两个处理选项。正则表达式选择最左边的选项（分支选择总是从左到右进行），检查ello是否匹配字符串的下一个字符。确实匹配，然后正则表达式又匹配了后面的空格。然而在这一点上它走进了死胡同，因为hippo 中的h 不能匹配字符串中的下一个字母t。此时正则表达式还不能放弃，因为它还没有尝试过所有的选择，随后它回溯到最后一个检查点（在它匹配了首字母h 之后的那个位置上）并尝试匹配第二个分支选项。但是没有成功，而且也没有更多的选项了，所以正则表达式认为从字符串的第一个字符开始匹配是不能成功的，因此它从第二个字符开始，重新进行查找。它没有找到h，所以就继续向后找，直到第14 个字母才找到，它匹配happy的那个h。然后它再次进入分支过程。这次ello未能匹配，但是回溯之后第二次分支过程中，它匹配了整个字符串“happyhippo”。匹配成功了。
二、重复与回溯
下一个例子显示了带重复量词的回溯。
var str = "<p>Para 1.</p>" +
"<img src='smiley.jpg'>" +
"<p>Para 2.</p>" +
"<div>Div.</div>";
/<p>.*<\/p>/i.test(str);
正则表达式一上来就匹配了字符串开始的三个字母<p>。然后是.*。点号匹配除换行符以外的任意字符，星号这个贪婪量词表示重复零次或多次——匹配尽量多的次数。因为目标字符串中没有换行符，它将吞噬剩下的全部字符串！不过正则表达式模板中还有更多内容需要匹配，所以正则表达式尝试匹配<。它在字符串末尾匹配不成功，所以它每次回溯一个字符，继续尝试匹配<，直到它回到</div>标签的<位置。然后它尝试匹配\/（转义反斜杠），匹配成功，然后是p，匹配不成功。正则表达式继续回溯，重复此过程，直到第二段末尾时它终于匹配了</p>。匹配返回成功，它从第一段头部一直扫描到最后一个的末尾，这可能不是你想要的结果。
你可以将正则表达式中的贪婪量词*改为懒惰（又名非贪婪）量词*?，以匹配单个段落。懒惰量词的回溯工作以相反方式进行。当正则表达式/<p>.*?<\/p>/推进到.*?时，它首先尝试全部跳过然后继续匹配<\/p>。它这么做是因为*?匹配零次或多次，但尽可能少重复，尽可能少的话那么它就可以重复零次。但是，当随后的<在字符串的这一点上匹配失败时，正则表达式回溯并尝试下一个最小的字符数：一个。它继续像这样向前回溯到第一段的末尾，在那里量词后面的<\/p>得到完全匹配。
如果目标字符串只有一个段落，你可以看到此正则表达式的贪婪版本和懒惰版本是等价的，但是他们尝试匹配的过程不同。
三、回溯失控
当一个正则表达式占用浏览器上秒，上分钟或者更长时间时，问题原因很可能是回溯失控。为说明此问题，考虑下面的正则表达式，它的目标是匹配整个HTML文件。此表达式被拆分成多行是为了适合页面显示。不像其他大多数正则表达式那样，JavaScript没有选项可使点号匹配任意字符，包括换行符，所以此例中以[\s\S]匹配任意字符。
/<html>[\s\S]*?<head>[\s\S]*?<title>[\s\S]*?<\/title>[\s\S]*?<\/head>
[\s\S]*?<body>[\s\S]*?<\/body>[\s\S]*?<\/html>/
此正则表达式匹配正常HTML字符串时工作良好，但是如果目标字符串缺少一个或多个标签时，它就会变得十分糟糕。例如</html>标签缺失，那么最后一个[\s\S]*?将扩展到字符串的末尾，因为在那里没有发现</html>标签，然后并没有放弃，正则表达式将察看此前的[\s\S]*?队列记录的回溯位置，使它们进一步扩大。正则表达式尝试扩展倒数第二个[\s\S]*?——用它匹配</body>标签，就是此前匹配过正则表达式模板<\/body>的那个标签——然后继续查找第二个</body>标签直到字符串的末尾。当所有这些步骤都失败了，倒数第三个[\s\S]*?将被扩展直至字符串的末尾，依此类推。
名词“备用状态”
对于正则表达式：不论选择那一种途径，如果它能匹配成功，而且正则表达式的余下部分也能匹配成功，此时才宣告最终匹配成功，或许你觉得我这个说的是废话。但你请看下面的，如果正则表达式中余下的部分最终匹配失败，引擎会知道需要回溯到之前作出选择的地方，选择其他的备用分支继续尝试。这样最终表达式所有的可能途径知道最终的成功或失败。回溯常和备用状态联系起来分析，那就来说一下，什么叫备用状态。
按我的理解是：大家应该都知道迷宫，走迷宫最常用的方法就是做记号，此刻我们假如用石头做记号，每当我们遇到十字路口是，我们就丢下一块石头，来标记我们所选择的路口，但我们发现不此路不通时，我们就进行回溯，回退到离我们最近的哪一个十字路口，然后重新选择我们的方向，这种方法是我们最常用的。我要说的是，正则表达式中的备用状态就是那个我们在每个十字路口的石头。其实我觉得这就算递归中的回溯，要是你理解了递归，这个应该不难理解。NFA中的LIFO(后进先出)的原则我觉就是那个迷宫此路不通的记号石头就是我们最好的LIFO例子。
名词"忽略优先量词"（*?、+?、??、{min、max}?、）
针对NFA的greedy(贪婪)原则，正则表达式有了忽略优先量词，这很大程度上解决了，很多由于greedy原则带来的麻烦和效率的问题。她只会匹配符合要求的最小的选择。如：
若用 <B>.*</B> 来匹配<B>I</B>and<B>you</B>are chinese,we are very happy to be chinese.
结果会是：<B>I</B>and<B>you</B>
但用<B>.*?</B>匹配 则结果是：<B>I</B>
名词"固化分组"：(?>)
使用固化分组，这会让引擎不记住备用状态，这又是能很好的提高正则表达式的效率。这也是优化正则表达式的常用方式。如下面的例子：
用 i.*! 来匹配 iHello! 在没有用固化分组时，是可以匹配成功的。
若用固化分组，i(?>.*)! 来匹配 iHello! 则匹配不成功，由于*是贪婪的她会一直匹配到最后，又由于固化分组了.*,她不会再吐出字符让后面的!来匹配。所以匹配失败。
参考：http://kb.cnblogs.com/page/86751/
http://www.yiiyaa.net/1292
http://ec06cumt.iteye.com/blog/556850
