來源：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。