转自 --http://www.cnblogs.com/zhuimengdeyuanyuan/archive/2013/02/06/2893240.html

　　《精通正则表达式（元字符）》这篇讲解了正则表达式常用的一些简单的元字符的使用，但是如果不能理解正则表达式匹配的核心，那么你永远不能在这方面有质的突破。

　　这一篇就重点讲解正则表达式的核心——正则引擎。

　　3、正则引擎

　　正则引擎主要可以分为基本不同的两大类：一种是DFA（确定型有穷自动机），另一种是NFA（不确定型有穷自动机）。DFA和NFA都有很长的历史，不过NFA的历史更长一些。使用NFA的工具包括.NET、PHP、Ruby、Perl、Python、GNU Emacs、ed、sec、vi、grep的多数版本，甚至还有某些版本的egrep和awk。而采用DFA的工具主要有egrep、awk、lex和flex。也有一些系统采用了混合引擎，它们会根据任务的不同选择合适的引擎（甚至对同一表达式中的不同部分采用不同的引擎，以求得功能与速度之间的平衡）

　　NFA和DFA都发展了很多年了，产生了许多不必要的变体，结果，现在的情况比较复杂。POSIX标准的出台，就是为了规范这种现象，POSIX标准清楚地规定了引擎中应该支持的元字符和特性。除开表面细节不谈，DFA已经符合新的标准，但是NFA风格的结果却与此不一，所以NFA需要修改才能符合标准。这样一来，正则引擎可以粗略地分为三类：DFA；传统型NFA；POSIX NFA。

　　我们来看使用`to(nite|knight|night)`来匹配文本‘…tonight…’的一种办法。正则表达式从我们需要检查的字符串的首位（这里的位置不是指某个字符的位置，而是指两个相邻字符的中间位置）开始，每次检查一部分（由引擎查看表达式的一部分），同时检查“当前文本”（此位置后面的字符）是否匹配表达式的当前部分。如果是，则继续表达式的下一部分，如果不是，那么正则引擎向后移动一个字符的位置，继续匹配，如此继续，直到表达式的所有部分都能匹配，即整个表达式能够匹配成功。在此例子中，由于表达式的第一个元素是`t`，正则引擎将会从需要匹配的字符串的首位开始重复尝试匹配，直到在目标字符中找到‘t’为止。之后就检查紧随其后的字符是否能由`o`匹配，如果能，就检查下面的元素。下面是`nite`或者`knight`或者`night`。引擎会依次尝试这3种可能。尝试`nite`的过程与之前一样：“尝试匹配`n`，然后是`i`，然后是`t`，最后是`e`”。如果这种尝试失败，引擎就会尝试另一种可能，如此继续下去，直到匹配成功或是报告失败。表达式的控制权在不同的元素之间转换，所以我们可以称它为“表达式主导”。

　　与表达式主导的NFA不同，DFA引擎在扫描字符串时会记录“当前有效”的所有匹配可能。在此例中引擎会对‘…tonight…’进行扫描，当扫描到t时，引擎会在表达式里面的t上坐上一个标记，记录当前位置可以匹配，然后继续扫描o，同样可以匹配，继续扫描到n，发现有两个可以匹配（knight被淘汰），当扫描到g时就只剩下一个可以匹配了，当h和t匹配完成后，引擎发现匹配已经成功，报告成功。我们称这种方式为“文本主导”，因为它扫描的字符串中的每个字符都对引擎进行了控制。

　　从它们匹配的逻辑上我们不难发现：一般情况下，文本主导的DFA引擎要快一些。正则表达式主导的NFA引擎，因为需要对同样的文本尝试不同的子表达式匹配，可能会浪费时间。在NFA的匹配过程中，目标文本的某个字符可能会被正则表达式反复检测很多遍（每一个字符被检测的次数不确定，所以NFA叫做不确定型有穷自动机）。相反，DFA引擎在匹配过程中目标文本中的每个字符只会最多检查一遍（每个字符被检测的次数相对确定，所以DFA叫做确定型有穷自动机）。由于DFA取得一个结果可能有上百种途径，但是因为DFA能够同时记录它们，选择哪一个表达式并无区别，也就是说你改变写法对于效率是没有影响的。而NFA是表达式主导，改变表达式的编写方式可能会节省很多功夫。

　　所以后面我们讲解的知识都是涉及的NFA的。

　　4、回溯

　　何为回溯？先来看一个例子，我们使用`a(b|c)d`去尝试匹配字符串“cabb”，正则引擎首先处于字符'c'的前面，开始查看正则表达式，发现第一个为a，不能匹配，然后引擎移动到'c'和'a'之间的位置，继续查看表达式，发现a可以匹配，然后查看表达式的后面，发现有两条路，引擎会做好标记，选择其中一条路，加入选择区匹配b，发现字符'a'后面就是'b'，可以匹配，然偶再次查看表达式，需要匹配d，发现字符串后面是'b'，不符合条件，这条路失败，引擎会自动回到之前做选择的地方，这里就称作一次回溯。那么引擎会尝试匹配a后面的c，发现'a'后面是'b'，这条路也走不通，没有其它的路线了，然后引擎又会移动位置，现在到了'a'和'b'之间，引擎回去尝试匹配表达式的a，发现当前位置后面是'b'，无法匹配，引擎又开始向后移动位置，直到移动到最后，发现没有一次匹配成功，然后引擎才会报告失败。而如果中间又一次成功完整匹配了，引擎会自动停止（传统型NFA会停止，而POSIX NFA还会继续，把所有可能匹配完，选择其中一个），报告成功。

　　现在应该知道回溯其实就是引擎在匹配字符串的过程中出现多选的情况，当其中一种选择无法匹配时再次选择另种的过程叫做回溯。其实我们在优化正则表达式的时候就是考虑的尽量减少回溯的次数。

　　4.1回溯匹配优先和忽略优先

　　《精通正则表达式》这本书里面叫做匹配优先和忽略优先，网上有很多人叫做贪婪模式和非贪婪模式，反正都一样，叫法无所谓。

　　匹配优先量词我们已经学习了，就是?、+、*、{}这四个。匹配优先量词在匹配的时候首先会尝试匹配，如果失败后回溯才会选择忽略。比如`ab?`匹配"abb"会得到"abb"。这里当匹配成功'a'后，引擎有两个选择，一个是尝试匹配后面的b，一个是忽略后面的b，而由于是匹配优先，所以引擎会尝试匹配b，发现可以匹配，得到了"ab"，接着引擎又一次遇到了同样的问题，还是会选择先匹配，所以得到了"abb"，接着引擎发现后面没有字符了，就上报匹配成功。　　

　　忽略优先量词使用的是在?、+、*、{}后面添加?组成的，忽略优先在匹配的时候首先会尝试忽略，如果失败后回溯才会选择尝试。比如`ab??`匹配“abb”会得到‘a’而不是“ab”。当引擎匹配成功a后，由于是忽略优先，引擎首先选择不匹配b，继续查看表达式，发现表达式结束了，那么引擎就直接上报匹配成功。

　　例子1：

            var reg1=/ab?/;
            var reg2=/ab??/;
            var result1=reg1.exec("abc");
            var result2=reg2.exec("abc");
            document.write(result1+" "+result2);

　　结果：

　　例子2：

　　例子3：

var reg=/ab(?!c)/; var result1=reg.exec("abdc"); var result2=reg.exec("abcd"); document.write(result1+" "+result2);