最近瞭解了下有關正則表達式回溯的內容，想想就寫下來，方便自己。 正則表達式匹配演算法是建立在正則表達式引擎的基礎上的，目前有兩種引擎：DFA(確定型有窮自動機)和NFA(不確定型有窮自動機)。這兩種引擎的區別主要在於被匹配對象不同。 DFA是用文本去匹配表達式。而NFA是用表達式去匹配文本。這個瞭解一 ...
最近瞭解了下有關正則表達式回溯的內容，想想就寫下來，方便自己。
正則表達式匹配演算法是建立在正則表達式引擎的基礎上的，目前有兩種引擎：DFA(確定型有窮自動機)和NFA(不確定型有窮自動機)。這兩種引擎的區別主要在於被匹配對象不同。
DFA是用文本去匹配表達式。而NFA是用表達式去匹配文本。這個瞭解一下就信了。目前我們用的是NFA自動機。
為什麼有時候正則表達式的使用會導致CPU飆升呢？這個與正則表達式的回溯有關。什麼就正則表達式的回溯以及為什麼會發生回溯呢？請看下麵的例子。
regex="b{1,3}ac";
text="bbac";
表達式在匹配文本的時候是一個一個的去校驗。b{1,3}表示最少出現一個b,最多3個b連續出現。這樣在我們的文本中出現了連續的兩個b,所以文本是符合這條表達式的。但是由於NFA的貪婪特性，也就是會更多的去匹配文本。表達式會用第三個b去和文本中的所處第三位置的a去匹配，結果不符合。這樣就結束了嗎？並沒有，接下來表達式會在已經匹配的三個字元中“吐”出字元a，這就是回溯。然後就從表達式中的a開始逐一匹配剩餘文本ac。直到結束。
如果想要解決這種問題，就需要改變表達式的匹配模式。表達式有三種模式：貪婪模式、懶惰模式、獨占模式。
剛剛我們所用到的是貪婪模式，儘可能多的去匹配。
而懶惰模式，儘可能少的去匹配，但仍會發生回溯。獨占模式，儘可能多的去匹配，但不回溯。
那如何將表達式改為懶惰模式呢：
regex="b{1,3}?ac";
獨立模式呢？
regex="b{1,3}+ac";這種就可以解決回溯的問題。
這些只是個人的理解，有什麼不足之處，還望指出，如果不理解的可以參考：http://www.cnblogs.com/study-everyday/p/7426862.html。希望對你有所幫助。
