比起DFA汗贫，NFA看起來足夠“麻煩”：它的狀態(tài)是不確定的，這有點像走迷宮耿战，越走岔路口越多蛋叼，最后不會迷路嗎？
不過剂陡，NFA的正則引擎自有辦法：如果有多個可能的狀態(tài)狈涮，它們會在選擇時記錄下這些狀態(tài)備用，然后才選擇其中某個狀態(tài)嘗試鸭栖；如果之后遇到死路歌馍，則退回去，選擇最近一次記錄的且未嘗試過的狀態(tài)晕鹊；如果又遇到死路松却，再選擇最近一次記錄的且未嘗試過的狀態(tài)...
這有點像在分岔路口留下標記——如果我們在遇到的每個分岔路口都留下標記暴浦，即使前頭是死路，也可以根據(jù)標記返回晓锻，而不會迷路歌焦。
為了說明NFA的匹配過程，來看看第2章舉過的雙引號字符串匹配的例子砚哆，所用的正則表達式為".*",字符串為"quoted string"独撇，匹配過程如圖所示：
[圖片上傳失敗...(image-f3c454-1545311212332)]
從圖中可以看出，在匹配的過程中躁锁，.*曾經(jīng)匹配了quoted string"纷铣，但是為了表達式中最后一個"的匹配，.*不得不“交還”最后的"灿里，這種“嘗試失敗-重新選擇”的過程关炼，就是回溯（backtracking）。
回溯只屬于NFA引擎匣吊。從之前地原理圖中可以看到，NFA匹配時寸潦，正則引擎并不準確知道當前的狀態(tài)色鸳，只能在所有狀態(tài)不確定的地方將各種狀態(tài)都保存下載（現(xiàn)在已經(jīng)匹配了哪些字符，進行到字符串中的哪個位置见转，正則表達式中的哪個位置）命雀，逐一嘗試，發(fā)現(xiàn)此路不通斩箫，則退回來吏砂，選擇最近保存的其臺狀態(tài)嘗試...如此進行下去，直到達到最終狀態(tài)乘客；或者所有可能狀態(tài)都嘗試完畢狐血，仍不能達到最終狀態(tài)。
看到這里就不難明白為什么不推薦使用.*了易核，因為.幾乎能匹配任何字符串匈织，而*又表示“匹配優(yōu)先”，所以正則引擎再處理.*后的其他元素之前牡直，會讓.*“吞掉”幾乎整個字符串缀匕。仍然是上面的正則表達式，只是字符串變?yōu)?code>"quoted" string碰逸，回溯的次數(shù)大大增加了乡小，如果在結尾的"之后還有很長的文本，則回溯的次數(shù)還可能大大增加饵史，匹配過程如圖所示：
[圖片上傳失敗...(image-2e92e0-1545311212332)]
為避免這類問題满钟，最好的辦法是準確表達意圖胜榔，比如規(guī)定雙引號字符串內部不允許出現(xiàn)雙引號字符，就要將表達式改為"[^"]*"零远；當然也可以換用忽略優(yōu)先量詞苗分，將表達式改為".?*"。不過總的經(jīng)驗是牵辣，除非確實必要摔癣，否則盡量不要使用.*。
要注意的不僅僅有.*纬向，還有更糟的情況择浊，比如(...*)*之類的表達式，這時候回溯的次數(shù)會呈指數(shù)級增長逾条，卻不會對匹配有任何影響琢岩，所以絕對應該避免。
在實際引用中师脂，不僅要注意自己寫的正則表達式担孔，還要防范外界對惡意程序，它們刻意使用會造成大量回溯的表達式吃警，將計算機的資源消耗殆盡糕篇，這種攻擊有一個專門的名詞，叫做正則表達式拒絕服務攻擊（regular expression denial of service）酌心。
