正则基础之 NFA引擎匹配原理
?來源：http://www.jb51.net/article/19332.htm
?
1 為什么要了解引擎匹配原理
一個個音符雜亂無章的組合在一起，彈奏出的或許就是噪音，同樣的音符經過作曲家的手，就可以譜出非常動聽的樂曲，一個演奏者同樣可以照著樂譜奏出動聽的樂曲，但他/她或許不知道該如何去改變音符的組合，使得樂曲更動聽。
作為正則 的使用者也一樣，不懂正則 引擎原理的情況下，同樣可以寫出滿足需求的正則 ，但是不知道原理，卻很難寫出高效且沒有隱患的正則 。所以對于經常使用正則 ，或是有興趣深入學習正則 的人，還是有必要了解一下正則 引擎的匹配原理的。
2 正則 表達式引擎
正則 引擎大體上可分為不同的兩類：DFA和NFA，而NFA又基本上可以分為傳統型NFA和POSIX NFA。
DFA Deterministic finite automaton 確定型有窮自動機
NFA Non-deterministic finite automaton 非確定型有窮自動機
Traditional NFA
POSIX NFA
DFA引擎因為不需要回溯，所以匹配快速，但不支持捕獲組，所以也就不支持反向引用和$number這種引用方式，目前使用DFA引擎的語言和工具主要有awk、egrep 和 lex。
POSIX NFA主要指符合POSIX標準的NFA引擎，它的特點主要是提供longest-leftmost匹配，也就是在找到最左側最長匹配之前，它將繼續回溯。同DFA一樣，非貪婪模式或者說忽略優先量詞對于POSIX NFA同樣是沒有意義的。
大多數語言和工具使用的是傳統型的NFA引擎，它有一些DFA不支持的特性：
捕獲組、反向引用和$number引用方式；
環視(Lookaround，(?<=…)、(?<!…)、(?=…)、(?!…))，或者有的有文章叫做預搜索；
忽略優化量詞（??、*?、+?、{m,n}?、{m,}?），或者有的文章叫做非貪婪模式；
占有優先量詞（?+、*+、++、{m,n}+、{m,}+，目前僅Java和PCRE支持），固化分組(?>…)。
引擎間的區別不是本文的重點，僅做簡要的介紹，有興趣的可參考相關文獻。
3 預備知識
3.1 字符串組成
對于字符串“abc ”而言，包括三個字符和四個位置。
3.2 占有字符和零寬度
正則 表達式匹配過程中，如果子表達式匹配到的是字符內容，而非位置，并被保存到最終的匹配結果中，那么就認為這個子表達式是占有字符的；如果子表達式匹配的僅僅是位置，或者匹配的內容并不保存到最終的匹配結果中，那么就認為這個子表達式是零寬度的。
占有字符是互斥的，零寬度是非互斥的。也就是一個字符，同一時間只能由一個子表達式匹配，而一個位置，卻可以同時由多個零寬度的子表達式匹配。
3.3 控制權和傳動
正則 的匹配過程，通常情況下都是由一個子表達式（可能為一個普通字符、元字符或元字符序列組成）取得控制權，從字符串的某一位置開始嘗試匹配，一個子表達式開始嘗試匹配的位置，是從前一子表達匹配成功的結束位置開始的。如正則 表達式：
( 子表達式一)(子表達式二)
假設(子表達式一) 為零寬度表達式，由于它匹配開始和結束的位置是同一個，如位置0，那么(子表達式二) 是從位置0開始嘗試匹配的。
假設(子表達式一) 為占有字符的表達式，由于它匹配開始和結束的位置不是同一個，如匹配成功開始于位置0，結束于位置2，那么(子表達式二) 是從位置2開始嘗試匹配的。
而對于整個表達式來說，通常是由字符串位置0開始嘗試匹配的。如果在位置0開始的嘗試，匹配到字符串某一位置時整個表達式匹配失敗，那么引擎會使正則 向前傳動，整個表達式從位置1開始重新嘗試匹配，依此類推，直到報告匹配成功或嘗試到最后一個位置后報告匹配失敗。
4 正則 表達式簡單匹本過程
4.1 基礎匹配過程
?
源字符串：abc
正則 表達式：abc
匹配過程：
首先由字符“a ”取得控制權，從位置0開始匹配，由“a ”來匹配“a ”，匹配成功，控制權交給字符“b ”；由于“a ”已被“a ”匹配，所以“b ”從位置1開始嘗試匹配，由“b ”來匹配“b ”，匹配成功，控制權交給“c ”；由“c ”來匹配“c ”，匹配成功。
此時正則 表達式匹配完成，報告匹配成功。匹配結果為“abc ”，開始位置為0，結束位置為3。
?
4.2 含有匹配優先量詞的匹配過程——匹配成功（一）
源字符串：abc
正則 表達式：ab?c
量詞“? ”屬于匹配優先量詞，在可匹配可不匹配時，會先選擇嘗試匹配，只有這種選擇會使整個表達式無法匹配成功時，才會嘗試讓出匹配到的內容。這里的量詞“? ”是用來修飾字符“b ”的，所以“b? ”是一個整體。
匹配過程：
首先由字符“a ”取得控制權，從位置0開始匹配，由“a ”來匹配“a ”，匹配成功，控制權交給字符“b? ”；由于“? ”是匹配優先量詞，所以會先嘗試進行匹配，由“b? ”來匹配“b ”，匹配成功，控制權交給“c ”，同時記錄一個備選狀態；由“c ”來匹配“c ”，匹配成功。記錄的備選狀態丟棄。
此時正則 表達式匹配完成，報告匹配成功。匹配結果為“abc ”，開始位置為0，結束位置為3。
4.3 含有匹配優先量詞的匹配過程——匹配成功（二）
源字符串：ac
正則 表達式：ab?c
匹配過程：
首先由字符“a ”取得控制權，從位置0開始匹配，由“a ”來匹配“a ”，匹配成功，控制權交給字符“b? ”；先嘗試進行匹配，由“b? ”來匹配“c ”，同時記錄一個備選狀態，匹配失敗，此時進行回溯，找到備選狀態，“b? ”忽略匹配，讓出控制權，把控制權交給“c ”；由“c ”來匹配“c ”，匹配成功。
此時正則 表達式匹配完成，報告匹配成功。匹配結果為“ac ”，開始位置為0，結束位置為2。其中“b? ”不匹配任何內容。
4.4 含有匹配優先量詞的匹配過程——匹配失敗
源字符串：abd
正則 表達式：ab?c
匹配過程：
首先由字符“a ”取得控制權，從位置0開始匹配，由“a ”來匹配“a ”，匹配成功，控制權交給字符“b? ”；先嘗試進行匹配，由“b? ”來匹配“b ”，同時記錄一個備選狀態，匹配成功，控制權交給“c ”；由“c ”來匹配“d ”，匹配失敗，此時進行回溯，找到記錄的備選狀態，“b? ”忽略匹配，即“b? ”不匹配“b ”，讓出控制權，把控制權交給“c ”；由“c ”來匹配“b ”，匹配失敗。此時第一輪匹配嘗試失敗。
正則 引擎使正則 向前傳動，由位置1開始嘗試匹配，由“a ”來匹配“b ”，匹配失敗，沒有備選狀態，第二輪匹配嘗試失敗。
繼續向前傳動，直到在位置3嘗試匹配失敗，匹配結束。此時報告整個表達式匹配失敗。
4.5 含有忽略優先量詞的匹配過程——匹配成功
源字符串：abc
正則 表達式：ab??c
量詞“?? ”屬于忽略優先量詞，在可匹配可不匹配時，會先選擇不匹配，只有這種選擇會使整個表達式無法匹配成功時，才會嘗試進行匹配。這里的量詞“?? ”是用來修飾字符“b ”的，所以“b?? ”是一個整體。
匹配過程：
首先由字符“a ”取得控制權，從位置0開始匹配，由“a ”來匹配“a ”，匹配成功，控制權交給字符“b?? ”；先嘗試忽略匹配，即“b?? ”不進行匹配，同時記錄一個備選狀態，控制權交給“c ”；由“c ”來匹配“b ”，匹配失敗，此時進行回溯，找到記錄的備選狀態，“b?? ”嘗試匹配，即“b?? ”來匹配“b ”，匹配成功，把控制權交給“c ”；由“c ”來匹配“c ”，匹配成功。
此時正則 表達式匹配完成，報告匹配成功。匹配結果為“abc ”，開始位置為0，結束位置為3。其中“b?? ”匹配字符“b ”。
4.6 零寬度匹配過程
源字符串：a12
正則 表達式：^ (?=[a-z]) [a-z0-9]+ $
元字符“^ ”和“$ ”匹配的只是位置，順序環視“(?=[a-z]) ”只進行匹配，并不占有字符，也不將匹配的內容保存到最終的匹配結果，所以都是零寬度的。
這個正則 的意義就是匹配由字母和數字組成的，第一個字符是字母的字符串。
匹配過程：
首先由元字符“^ ”取得控制權，從位置0開始匹配，“^ ”匹配的就是開始位置“位置0 ”，匹配成功，控制權交給順序環視“(?=[a-z]) ”；
“(?=[a-z]) ”要求它所在位置右側必須是字母才能匹配成功，零寬度的子表達式之間是不互斥的，即同一個位置可以同時由多個零寬度子表達式匹配，所以它也是從位置0嘗試進行匹配，位置0的右側是字符“a ”，符合要求，匹配成功，控制權交給“[a-z0-9]+ ”；
因為“(?=[a-z]) ”只進行匹配，并不將匹配到的內容保存到最后結果，并且“(?=[a-z]) ”匹配成功的位置是位置0，所以“[a-z0-9]+ ”也是從位置0開始嘗試匹配的，“[a-z0-9]+ ”首先嘗試匹配“a ”，匹配成功，繼續嘗試匹配，可以成功匹配接下來的“1 ”和“2 ”，此時已經匹配到位置3，位置3的右側已沒有字符，這時會把控制權交給“$ ”；
元字符“$ ”從位置3開始嘗試匹配，它匹配的是結束位置，也就是“位置3 ”，匹配成功。
此時正則 表達式匹配完成，報告匹配成功。匹配結果為“a12 ”，開始位置為0，結束位置為3。其中“^ ”匹配位置0，“(?=[a-z]) ”匹配位置0，“[a-z0-9]+ ”匹配字符串“a12 ”，“$ ”匹配位置3。
總結
以上是生活随笔為你收集整理的正则基础之 NFA引擎匹配原理的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 标签的使用
- 下一篇： JS实现刷新iframe的方法