正規表達式的正則引擎分為很多種，最常用的引擎類型有perl，tcl, python,.net,ruby,php,java.util.regex等，建構正規表達式的方式決定了某個正規表達式[b]能否[/b]比對一個特定字元串，在[b]何處[/b]比對，以及比對[b]成功或報告失敗[/b]的[b]速度[/b]。
[color=red][b]正則引擎主要可以分為不同的兩大類：一種是DFA(文本主導引擎，确定型有窮自動機),另一種是NFA(表達式主導，非确定型有窮自動機)。[/b][/color]兩者都有很長的曆史，使用NFA的工具包括java,.net,ruby,perl,python,vi,grep的多數版本，甚至還有某些版本的egrep和awk。而采用DFA的工具主要有egrep，awk，lex和flex。也有些系統采用了混合引擎，他們會根據任務的不同選擇合适的引擎。後面會慢慢引入這兩種引擎。
[b]4.1 比對的基礎[/b]
在了解不同引擎的差異之前，我們先看看他們的相似之處。
本篇會介紹比對執行的實際流程。理想的情況是，所有的而知識都能歸納為幾條容易記憶的簡單規則，使用者不需要了解這些規則包含的原理。很不幸，事實并非如此。[b]隻有兩條普适[/b]的原則，其他都要根據實際的引擎和模式等來綜合确定：
[b]1. 優先選擇[color=red]最左端[/color]的比對結果。
2. 标準的比對量詞是[color=red]比對優先[/color]的。[/b]
[b]4.1.1 規則1：優先選擇最左端的比對結果[/b]
根據這條規則，起始位置最靠左的比對結果總是優先于其他可能的比對結果。這條規則并沒有規定優先的比對結果長度，實際上可能有多個比對結果起始位置都在最左端。是以後面會讨論優先選擇哪種。
這條規則的由來是：比對[color=red][b]（1）[/b][/color]先從要查找的字元串的[color=red][b]起始位置嘗試比對[/b][/color]。在這裡，“嘗試比對”的意思是，在目前位置測試整個正規表達式能比對的每樣文本。如果在目前位置測試了[b]所有的可能[/b]（因為可能會有多選項或量詞）之後不能找到比對結果，[color=red][b]（2）[/b][/color]就需要從字元串的[b]第二個字元[/b]之前的位置開始重新嘗試。在找到比對結果以前必須在所有的位置重複此過程。隻有在嘗試過所有的位置都不能找到比對結果的情況下，才會報告“比對失敗”。說完這些，是不是感覺有點眼熟？編譯原理裡的詞法分析，文法分析是不是也這樣？後面再說到回溯，那就更相像了。
是以，如果要用”ORA”來比對FLOAT,從該字元串左邊開始第一輪嘗試會失敗，ORA不能比對FLO，第二輪也會失敗，ORA不能比對LOA，第三輪的嘗試能夠成功，是以引擎會停下來，報告比對結果。
[b]4.2 引擎的構造[/b]
所有的額引擎都是由不同的零部件組合而成的，[b]正則引擎中的零件分為：文字字元，量詞，字元組，括号等等[/b]，就是前面介紹過的那些。這些零件的組合方式決定了引擎的特性。首先，讓我們來看看這些零件：
[b]文字文本，例如a, 我們…[/b]
對于非元字元的文字字元，嘗試比對時需要考慮就是”這個字元與目前嘗試的字元相同嗎？”。如果一個正規表達式隻包含純文字，例如”usa”，那麼正則引擎會将其視為一個’u’，接着一個’s’，接着一個’a’。如果進行不區分大小寫的比對時，每個字元就分别比對其大小寫形式。
[b]字元組，點号，Unicode屬性及其他[/b]
通常情況下,字元組，點号，Unicode屬性及其他的比對是比較簡單的:無論字元組的長度是多少，它都隻能比對一個字元。
點号可以很友善地表示複雜的字元組，它幾乎能比對所有字元，是以他的作用也很簡單，其他的簡便方式還包括”\w”,”\W”和”\d”等。
[b]捕獲型括号[/b]
用于捕獲文本的括号（而不是用于分組的括号）不會影響比對的過程。
[b]錨點（^, (?<=\d)）[/b]
錨點可以分為兩大類：簡單錨點（^,$,\b…）和複雜錨點（順序環視，逆序環視等）。
[b]說明：[/b]
在講解DFA和NFA之前，不得不指出，捕獲括号，忽略優先量詞都隻對NFA起作用，對DFA不起作用。這是由他們的工作方式決定的，有些工具是混合兩種正則引擎的。
[b]4.2.1 規則2:标準量詞是比對優先的[/b]
标準比對量詞(?,+,*以及{min,max})都是比對優先的。這些比對[b]總是希望最長的比對[/b]。如果最終結果并非該表達式的所有可能中最長的，原因肯定是比對字元過多導緻比對失敗的。舉例，用”\b\w+s\b”來比對”regexes”,”\w+”完全能比對整個單詞，但如果比對整個單詞，”regexes”的最後一個”s”就不能被正規表達式比對了，為了完成比對，”\w+”必須比對”regexe”,把最後的”s”留出來。後面我們會知道，這不是‘留’出來的，而是‘吐’出來的，也就是回退。
[b]過度的比對優先[/b]
現在讓我們回頭看看”盡可能多的比對”的比對優先量詞。比較下”^Subject: ”和
”^Subject: (.*)”，後者多加了一個”(.*)”，但對比對結果不會有影響，隻要前者能比對，後者一定能比對。那後者多加的有什麼用呢？因為星号是比對優先的，是以我們可以添加”(.*)”來作為反向引用，擷取”^Subject: “之後的内容儲存起來。
再來看看”^.*([0-9][0-9])”，它能夠比對一行字元的最後兩位數字，如果有的話，将他們儲存在變量裡（perl裡可以通過$1引用）。比對過程如下：[color=red][b]（1）[/b][/color]”^”比對字元串的開始位置，[color=red][b]（2）[/b][/color]然後”.*”盡可能多的比對，會比對到整行文本。[color=red][b]（3）[/b][/color]然後”[0-9][0-9]”是必須比對的，在嘗試比對行末的位置時會失敗，這樣他會通知”.*”:“嗨，你占有的太多了，交出一些字元來吧，這樣我可能能比對”。比對優先元件首先會盡可能多的比對字元，但為了整個表達式的比對，他們通常需要釋放一些字元。釋放總是一個一個的釋放，可能會釋放多次。當然，釋放也是有底線的，就是釋放後剩下的至少是自己的下限，比如加号至少要給自己留一個字元。仍然不能滿足要求就會報告此次比對失敗。
[b]先來先服務[/b]
前面的例子貌似已經明白了，[color=red][b]事實應該還不夠明白[/b][/color]。看下”^.*[0-9][b]+[/b]”來比對一行的最後兩個數字，期望比對的不止是最後兩位數字，而是整個數。那比對”copyright 2003.”捕獲型括号裡比對到的結果是什麼呢？
“^.*”會比對完整個表達式。然後”[0-9]+”需要至少比對一個數字，這時候會告訴星号交還一個字些字元。星号不願意還是要交還最後一個點号。此時[0-9]+還是無法比對，還要讓星号繼續交還，這次又交還一個3，[0-9]+此時可以比對了。這時交還的動作就結束了，[0-9]+的下限已經滿足了，星号不會再仁慈的交還字元。因為有個原則：先來先服務。先滿足前面的比對優先字元。
[b]深入細節[/b]
交還的動作是如何發生的呢？這其實就是引擎類型決定的：是DFA還是NFA。
[b]4.3 表達式主導和文本主導[/b]
DFA和NFA反映了将正規表達式在應用算法上的根本差異。NFA稱為“表達式主導(regex-directed)”引擎，DFA稱為“文本主導(text-directed)”引擎。
[b]4.3.1 NFA引擎：表達式主導[/b]
我們來看用”to(nite|knight|night)”比對文本”…tonight…”的一種辦法。正規表達式從”t”開始，每次檢查一部分（由引擎檢視表達式的一部分），同時檢查”目前文本(current text)”是否比對表達式的目前部分。如果是，則繼續表達式的下一部分，如此繼續，直到表達式的所有部分都能比對，即整個表達式能夠比對成功。
在”to(nite|knight|night)”的例子中，[b]（1）[/b]第一個元素是’t’,它将重複嘗試，直到在目标字元串中找到’t’為止。[color=red][b]（2）[/b][/color]之後就檢查緊随其後的字元是否能由’o’比對。[color=red][b]（3）[/b][/color]如果能就檢查下面的元素，在本例中，下面的元素指”(nite|knight|night)”,它的真正含義是”nite”或”knight”或者”night”。引擎會一次嘗試這3種可能。表達式主導的引擎必須完全測試，才能得出結論。
NFA引擎在操作上的優點
實質上，在表達式主導的比對過程中，每一個子表達式都是獨立的。這不同于反向引用，子表達式之間不存在内在聯系，隻是整個正規表達式的各個部分。在子表達式與正規表達式的控制結構(多選分支，括号以及比對量詞)的層級關系控制了整個比對過程。熟知NFA的比對原理後，正規表達式的作者可以精确控制比對過程。
[b]4.3.2 DFA引擎：文本主導[/b]
與表達式主導的NFA不同，DFA引擎在掃描字元串時，會[b]記錄”目前有效(currently in the works)”的所有比對可能[/b]。具體到tonight的例子，引擎移到”t”時，會在目前處理的比對可能中添加一個潛在的可能。
[img]http://dl2.iteye.com/upload/attachment/0095/0573/bd8f8607-d5b2-3370-aad3-61ecd5f76aa1.bmp[/img]
有效的可能比對變為兩個(knight被淘汰出局)。掃描到g時，就隻剩下一個可能比對了。當h和t比對完成後，引擎發現比對已經完成，報告成功。
這種方式成為[b]”文本主導”[/b]，是因為它掃描的字元串中的每個字元都對引擎進行了控制。例如”to(…)?”，括号内的部分并不是必須出現的，但考慮到比對優先的性質，引擎仍然會嘗試比對括号内的部分。比對過程中，在嘗試括号内的部分時，完整比對”to”已經保留下來，以因對括号中的内容無法比對的情況。如果引擎發現，文本中出現的某個字元會令所有進行中的比對可能失效，就會傳回某個之前保留的完整比對。如果不存在這樣的完整比對，則要報告在目前位置無法比對。
[b]4.3.3 比較NFA與DFA[/b]
根據上面介紹的知識比較NFA和DFA，可能會得出結論：[b]一般情況下，文本主導的DFA引擎要快一些，正規表達式主導的NFA引擎因為需要對同樣的文本嘗試不同的子表達式比對，可能會浪費時間（就像上面例子中的3個分支）。[/b]
這個結論是對的。在NFA的比對過程中，目标文本中的某個字元可能會被正規表達式中的不同部分重複檢測，甚至有可能被同一部分反複檢測。即使某個子表達式能夠比對，為了檢查表達式中剩下的部分，找到比對，它也可能需要再一次應用（甚至可能反複多次）。單獨的子表達式可能成功也可能失敗，但是，直到抵達正規表達式的末尾之前，我們都無法确知全局比對成功與否。相反，DFA引擎則是确定型的，目标文本中的每個字元隻會檢查一遍（最多一遍，可能剩下的不需要檢查了）。
正規表達式引擎所使用的兩種基本技術，都對應有正式的名字：[b]非确定型有窮自動機(NFA)和确定型有窮自動機（DFA）。[/b]
[b]使用者需要面對的結果[/b]
因為NFA具有表達式主導的特性，引擎的比對原理就非常重要。通過改變表達式的編寫方式，使用者可以對表達式進行多方面的控制（java.util.regex就是NFA）。拿tonight的例子來說，如果改變表達式的編寫方式，可能會節省很多功夫，比如下面3種方式：
1）“to(ni(ght|te)|knight)”
2）“tonite|toknight|tonight”
3）“to(k?night|nite)”
給出任意文本，這3個表達式都可以捕獲相同的結果，但是他們以不同的方式控制引擎。後面我們還會看到這3種寫法的優劣。
DFA情況相反，引擎會同時記錄所有的比對選擇，因為這3個表達式最終能捕獲的文本相同，在寫法上的差異并無意義，因為DFA能同時記錄他們所有的比對可能位置，是以選擇哪個并無差別。如果要描述DFA，能想到的特征有：
1）比對很迅速
2）比對很一緻
3）談論DFA比對很惱人…
因為NFA是表達式主導的，NFA為創造性思維提供了豐富的施展空間。調校好一個表達式能帶來許多收益，調校不好則會帶來嚴重後果。為了徹底弄明白這個問題，我們來看NFA最重要的部分：回溯(back tracking)。
[b]4.4 回溯[/b]
NFA引擎最重要的性質是，它會[b]依次[/b]處理各個子表達式或組成元素，遇到需要在兩個可能成功的可能中進行選擇的時候，它會選擇其一，同時記住另一個，以備稍後可能的需要。
[color=red][b]需要做出選擇的情形包括量詞（決定是否嘗試另一次比對）和多選結構（決定選擇哪個多選分支，留下哪個稍後嘗試）。[/b][/color]
不論選擇哪一種途徑，如果他能比對成功，而且正規表達式的餘下部分也成功了，比對即告完成。如果正規表達式餘下部分最終比對失敗，引擎會知道需要回溯到之前作出選擇的地方，選擇其他的備用分支繼續嘗試。這樣，引擎會嘗試表達式的所有可能途徑（或者說是比對完成之前需要的所有途徑）。
[b]一個簡單的例子[/b]
現在來看個完整的例子，用先前的”to(nite|knight|night)”比對字元串”hot tonic tonight!”。第一個元素”t”從字元串的最左端開始嘗試，因為無法比對文本的’h’，是以從第二個位置開始嘗試，同樣也失敗，然後第三個，這時候’t’能夠比對，接下來的’o’無法比對空格，至此，本輪嘗試也失敗。
繼續下去，從… tonic…的’t’開始，to比對成功後，剩下的3個多選分支都成為可能，引擎選取其中之一進行嘗試，然後留下其他的選擇作為備用。我們假定引擎首先選擇的是”nite”，這個表達式被分解為’n’+’i’+’t’+’e’，在正則進行到”toni”比對後比對’c’的時候失敗，但這種失敗并不意味着整個表達式比對失敗，現在就會回到上一次選擇的地方，嘗試其他多選分支。假設引擎這次選擇了”knight”，那麼馬上就會遭遇失敗，因為子表達式的’k’不能比對文本的’n’，這次選擇也失敗。現在隻剩下最後的選項”night”，仍然會失敗。
[color=red][b]這時，比對會回退到正則的最開始，接着從比對文本的下一個字元開始上面的過程，直到比對到… tonight![/b][/color]，這一次，多選分支”night”終于比對到字元串的結尾部分，于是整個比對成功。
[b]4.4.1 回溯的兩個要點[/b]
回溯機制的基本原理并不難了解，但是有些細節對實際應用很重要。他們時，面對衆多選擇時，哪個分支應當首先選擇？回溯進行時，應該選取哪個儲存的狀态？
下面的原則能解答這些問題，[b]原則1：[/b]
如果需要在”進行嘗試”和“跳過嘗試“之間選擇，對于比對優先量詞，引擎會優先”進行嘗試”，而對于忽略優先量詞，會選擇“跳過嘗試”。
回溯前可能多次儲存了備用分支，就像走路時路過了很多岔路口，那回溯的時候使用的是之前儲存的哪個分支？[b]原則2：[/b]
距離目前最近儲存的選項就是當本地失敗強制回溯時傳回的，使用的原則是LIFO(last in first out，後進先出)。也就是傳回到離自己最近的那個備用路徑。
在一個多選分支面前要選擇哪個呢？[b]原則3：[/b]
選擇離自己最近的分支，也就是按照列出的順序，從左到右選擇。
[b]4.4.2 備用狀态[/b]
用NFA正規表達式的術語來說，那些備選路徑的位置相當于”備用狀态， saved state”。他們用來标記：[b]在需要的時候，比對可以從這裡重新開始嘗試。他們儲存了兩個位置：正規表達式中的位置和未嘗試的分支在字元串中的位置（相當于cpu執行指令時要儲存下一條指令，這裡未嘗試的位置就是失敗時下一次要比對的位置）。[/b]
總之，NFA是以正規表達式來驅動比對和回溯的，下面舉例再次說明如何儲存備用狀态和回溯的：
1.未進行回溯的比對
[img]http://dl2.iteye.com/upload/attachment/0095/0575/16c73306-3563-3a2a-ada5-3ca312ff9348.bmp[/img]
2.進行了回溯的比對
[img]http://dl2.iteye.com/upload/attachment/0095/0577/2d5aefff-2b2c-391c-b88c-60eada44796e.bmp[/img]
3.不成功的比對
[img]http://dl2.iteye.com/upload/attachment/0095/0585/974191c5-73e8-3fa4-9053-81ee6f53cb1d.bmp[/img]
[img]http://dl2.iteye.com/upload/attachment/0095/0583/b8489919-d05c-3bcc-83fe-5ed3059365d1.bmp[/img]
4.忽略優先的比對
[img]http://dl2.iteye.com/upload/attachment/0095/0581/c0f51636-bab2-3dd8-a930-ed5680f7f3ff.bmp[/img]
[b]4.4.3 回溯與比對優先[/b]
如果工具使用的是NFA正規表達式主導的[b]回溯引擎[/b]，了解正規表達式的回溯原理就成了高效完成任務的關鍵。前面看到”?”的比對優先和”??”的忽略優先是如何工作的，現在來看看星号和加号。
[b]星号，加号及其回溯[/b]
如果認為”x*”基本等同于”x?x?x?x?x?...”那麼情況與之前沒有大的差别。每次測試星号作用的元素之前，引擎都會儲存一個狀态，這樣，如果測試失敗，還能夠從儲存的狀态開始比對。[b]這個過程不斷重複，直到包含星号的嘗試完全失敗為止。[/b]
是以，如果用”[0-9]+”來比對”a 1234 num”, 正則的”[0-9]”遇到‘4’之後的空格無法比對，而此時加号能偶回溯的位置對應了4個儲存的狀态：
[img]http://dl2.iteye.com/upload/attachment/0095/0629/cbe19c8a-7bad-3e2c-8592-723e506ead52.bmp[/img]
也就是說，在每個位置，”[0-9]”的嘗試都代表一種可能。在”[0-9]”遇到空格比對失敗時，引擎回溯到最近儲存的狀态。
[b]需要注意的是[/b]：
[color=red]第一，回溯機制不但需要重新計算正規表達式和文本的對應位置，也需要維護括号内的子表達式所比對文本的狀态。不但需要同時維護反向引用的狀态，也會影響比對的效率。
第二，由星号（或其他任何比對優先量詞）限定的部分不受後面元素影響，而隻是比對盡可能多的内容。[/color]
[b] 4.5 關于比對優先和回溯的更多内容[/b]
NFA和DFA都具備許多比對優先相關的特性（DFA不支援忽略優先，是以隻需要關注比對優先）。
NFA的比對優先很值得一談，因為NFA是表達式主導的，是以比對優先的特性能産生許多神奇的結果。除了忽略優先，NFA還提供了其他許多特性，比如環視，條件判斷，反向引用以及固化分組。最重要的是NFA能讓使用者直接操控比對的過程，如果運用得當，這會帶來很大的友善，但也可能帶來某些性能問題（下一篇會讨論正則的性能）。
[b]4.5.1 比對優先的問題[/b]
前面我們看到，”.*”經常會比對到一行文本的末尾。這是因為”.*”比對時隻從自身出發，比對盡可能多的内容，隻有在全局比對需要的情況下才會”被迫”交還一些字元。
有些時候問題很嚴重。舉例，如果我們要比對雙引号裡的文本該怎麼做？使用”.*”嗎？比如要比對的文本是：
the name “MCDonald’s ” is said “makudonarudo” in Japanese.
最開始的雙引号比對之後，”.*”能比對任何字元，是以它會一直比對到字元串的末尾。為了讓最後的雙引号能比對，”.*”[b]不斷交還字元，直到滿足位置[/b]，最後，這個正則比對到的内容是：
”McDonald’s” is said “makudonarudo”
這顯然不是我們期望的結果。那麼我們如果能夠隻取得”McDonald’s”呢？關鍵的問題在于要認識到，我們希望比對的[b]不是雙引号之間的“任何文本”，而是“除雙引号之外的任何文本”[/b]。如果用”[^"]*”來取代”.*”（也就是”[^"]*”）就不會出現上面的問題。事實上，可能還有一種出乎意料的問題，因為在大多數流派中”[^"]”能夠比對換行符，而點号則不能。是以更精确的表達是”[^"\n]*”。
這種用法仍然有限制，也就是說當需要排除的[b]不是單個字元[/b]時，這樣就不能做到，比如提取<B>和</B>之間的字元。下面還會介紹其他更通用的方法。
[b]4.5.2 使用忽略優先量詞[/b]
上面的問題之是以出現，是因為标準量詞是比對優先的。某些NFA支援忽略優先的量詞，*?就是*對應的忽略優先量詞。我們用”<B>.*?</B>”就可以提取一對<B>标簽裡的内容。是以我們知道了，星号之類的比對優先量詞有時候的确友善，但有時候也會帶來大麻煩。這時候，忽略優先的量詞就能派上用場了。但忽略優先量詞也有局限性，比如我們用剛才的”<B>.*?</B>”來比對：
…<B>Billions and <B>Zillions</B> of suns…
這時候比對到的結果就是<B>Billions and <B>Zillions</B>，這也不是我們希望的結果。
這個例子也說明了，通常情況下，忽略優先量詞并不是排除類的完美替身。
如果支援排除環視，我們就能得到與排除型字元組相當的結果。比如”(?!<B>)”,隻有當<B>不在字元串中的目前位置時才能成功。是以，把正則改為：”<B>((?!<B>).)*?</B>”就能準确的比對我們期望的内容。分開講解：
[img]http://dl2.iteye.com/upload/attachment/0095/0579/e0d5c99f-821f-3bd8-90df-6d79cd130223.bmp[/img]
現在，環視功能會禁止正規表達式的主體比對<B>和</B>之外的内容，這也是我們之前試圖用忽略優先量詞解決的問題，是以現在可以不用忽略優先功能了。這個表達式還有能夠改進的地方，後面分析效率的時候還會看到它。
[b]4.5.3 比對優先和忽略優先都期望獲得比對[/b]
再回顧下前面的例子，因為浮點數的顯示問題，”1.625”或”3.00”有時候會變成”1.62500000002828”或”3.00000000028822”,為了解決這個問題，我們使用：
$price =~ s/(\.\d\d[1-9]?)\d*/$1/;
來儲存$price小數點後面兩到三位小數。”\.\d\d”比對最開始兩位數字，而”[1-9]?”用來比對可能出現的不等于零的第三個小數。
到現在一切正常，但是，如果$price的資料本身就是規範的格式，如$price = 27.625，結果就是我們使用.625替換了.625，相當于白費功夫。結果雖然是我們需要的，但是否存在更有效的辦法隻進行必要的替換，如果本身複合格式就不替換了呢？我們會想，如果最後的\d*能比對到數字，那應該就能達到目的，把最後的”\d*”換成”\d+”：
$price =~ s/(\.\d\d[1-9]?)\d+/$1/;
對于1.635000000002828這樣的複雜數字，仍然有效。但如果對9.43這樣的數字，末尾的”\d+”無法比對，就不會替換。但這樣仍然達不到要求，試想如果數字是27.625，結果會怎樣，對了，它會被替換成27.62。這已經不是效率的問題了，結果是錯的。
那再改進，把”[1-9]?”改為忽略優先的”[1-9]??”,得到的結果是一樣的，忽略優先并不能解決這個問題。
[b]4.5.4 比對優先，忽略優先和回溯的要旨[/b]
[b]無論是比對優先，還是忽略優先，都是為全局比對服務的，在這一點上他們沒有差別。[/b]如果全局比對需要，無論是比對優先還是忽略優先，在遇到“本地比對失敗”時，引擎都會回歸到備用狀态，然後嘗試未嘗試的路徑。隻要引擎報告了失敗，它就已經嘗試了所有的可能。
測試路徑的先後順序，在比對優先和忽略優先的情況下是不同的，但是隻有在測試完所有可能的路徑之後，才會最終報告比對失敗。
最後，如果[b]隻有一條[/b]可能的路徑，那兩者都能找到結果，隻是嘗試路徑的次序不同，并[b]不會影響比對的結果[/b]，隻是需要嘗試的次數，這是關于效率的問題。如果存在[b]不隻一種可能[/b]的結果，那比對優先會傳回最長的結果，而忽略優先會比對最短的結果。
[b]4.6占有優先量詞和固化分組[/b]
仍然考慮”.625”的例子，我們知道，如果比對能夠進行到”(\.\d\d[1-9]\d+)”的”(\.\d\d[1-9]”之後，我們就不希望進行回溯，繼續向前比對如果成功就成功，失敗就失敗，就能滿足我們的要求。
那麼，如果我們能避免這些備用狀态，[1-9]?的比對就不會交還，就是我們需要的。但是，如果比對”.5000”，此時[1-9]不能比對，就确實需要回溯，放棄[1-9]，讓之後的\d+能比對需要删除的數字。聽起來，這是兩種相反的要求，一會要回溯，一會不要回溯。但我們[b]真正需要的是隻有在某個可選元素已經比對成功的情況下才抛棄此元素的“忽略”狀态[/b]。也就是說如果”[1-9]”能夠比對成功該，就放棄備用狀态，不再回溯，如果比對失敗就允許回溯。
這需要的正是固化分組(?>…)或者占有優先量詞[1-9]?+。
[b]4.6.1 用(?>…)實作固化分組[/b]
具體來說，[b]使用”(?>…)”的比對與正常的比對并無差别，但是如果比對進行到此結構之後，[color=red]也就是進行到閉括号之後，那麼此結構體中的所有備用狀态都會被放棄[/color][/b]。也就是說，固化分組比對結束時，它已經比對的文本固化為一個單元，隻能作為整體而保留或放棄。括号内的子表達式中未嘗試過的備用狀态都不複存在了，多以回溯永遠也不能選擇其中的狀态。
是以，我們用”(\.\d\d(?>[1-9]?))\d+”。固化分組内，量詞能正常工作。完全能符合我們的需要，類似6.135，3.12不會被替換，其餘情況正常工作。
[b]4.6.2 固化分組的要旨[/b]
前面說過，比對優先和忽略優先都不會影響需要檢測路徑的本身，而隻會影響檢測的順序。如果不能比對，無論是按照比對優先還是忽略優先的順序，每條路徑都會被測試。然而，固化分組與他們截然不同，因為固化分組會放棄某些可能的路徑。根據具體情況不同，放棄備用狀态可能會導緻不同的結果：
1）毫無影響：如果在使用備用狀态之前能完成比對，固化分組就不會影響比對。
2）導緻比對失敗：放棄備用狀态可能意味着，本來有可能成功的比對現在不可能成功了。
3）改變比對結果：在某些情況下，放棄備用狀态可能得到不同的比對結果。
4）加快報告比對失敗的速度：如果不能找到比對對象，放棄備用狀态可能讓正則引擎更快地比對失敗。
我們将在後面看到，固化分組非常有價值，也是最常用的提高效率的技巧。
[b]4.6.3 占有優先量詞，?+, *+, ++, {min, max}+[/b]
占有優先量詞與比對優先量詞很相似，隻是他們[b]從來不交還已經比對的字元[/b]。隻要已經比對，也會放棄備用狀态。
你也許會想，占有優先量詞和固化分組關系非常緊密。像”\w++”與”(?>\w+)”的比對結果完全相同，隻是寫起來更加友善。使用占有優先量詞，”^(?>\w+):”可以寫作”^\w++:”。
請務必區分”(?>M)+”和”(?>M+)”，前者放棄’M’建立的備用狀态，但單字元’M’不會創造任何狀态，是以這樣做沒有意義；而後者”M+”創造備用狀态，這樣做才有意義。”(?>M+)”又等價于”M++”。
[b]4.7 環視中的回溯[/b]
初看時并不容易認識到，環視與固化分組和占有優先量詞有緊密的聯系。環視分為4種：肯定性和否定性的順序環視和逆序環視，他們隻是簡單測試，其中表達式能否在目前位置的後面（順序環視）或前面（逆序環視）。
深入點看，在NFA的世界中包含了備用狀态和回溯，環視是怎麼實作的？環視結構中的子表達式有自己的世界。它也會儲存備用狀态，進行必要的回溯。如果整個子表達式能夠成功比對，結果如何呢？肯定型環視會認為自己比對成功；而否定環視會認為比對失敗。在任何一種情況下，因為關注的隻是比對存在與否，此比對嘗試所在的世界，包括在嘗試中創造的所有的備用狀态，都會被放棄。如果環視中的子表達式無法比對，結果如何呢？因為它隻應用到自己的世界中，是以回溯時隻能選擇目前環視結構中的備用狀态。
是以我們知道，隻要環視結構的比對嘗試結束，他就不會留下任何備用狀态。這裡用到的就是固化分組和占有優先量詞。
作為替換，如果正則流派不支援固化分組，可以使用肯定環視來模拟固化分組。
[b]4.8 DFA,NFA和POSIX[/b]
最左最長規則：POSIX标準規定，如果在字元串中的某個位置存在多個可能的比對，應當傳回的是最長的比對。因為在所有同樣從最左邊開始的可能的比對文本中它是最長的，是以叫”最左最長”比對。
[b]4.9 速度和效率[/b]
如果傳統型NFA的效率是我們應當關注的問題，那麼POSIX NFA的效率更值得關注，因為它需要進行更多的回溯。POSIX NFA需要嘗試正規表達式的所有變體。正規表達式寫的糟糕的話，比對的效率就會很低。
[b]4.9.1 DFA的效率[/b]
文本主導的DFA巧妙地避免了回溯造成的效率問題。DFA同時記錄了所有可能的比對，這樣來提高速度。
DFA引擎需要更多的時間和記憶體。它第一次遇見正規表達式時，在作出任何嘗試之前就會用比NFA詳細的多的辦法來分析這個正規表達式。開始嘗試比對之前它已經内建了一張路線圖。描述“遇到這個字元就該選擇這個或那個可能的比對”，字元串中的每個字元都會按照這張路線圖來比對。
有時候，構造這張路線圖可能需要相當的事件和記憶體，不過隻要建立了針對特定正規表達式的路線圖，結果就可以應用到任意長度的文本。
[b]4.9.2 NFA和DFA的比較[/b]
[b]1.DFA和NFA：在預編譯階段的差別[/b]
在使用正規表達式搜尋之前，兩種引擎都會編譯表達式，得到一套内化形式，适應各自的比對算法。NFA的編譯過程通常要快一些，需要的記憶體也少一些。傳統型NFA和POSIX NFA之間并沒有實質的差别。
[b]2.DFA與NFA:比對速度的差别[/b]
對于“正常”情況下的簡單文本比對測試，兩種引擎的速度差不多。一般來說，DFA的速度與正規表達式無關，而NFA中兩者直接相關。(讓我突然覺得這有點像oracle中的優化器RBO和CBO模式分别與sql語句的關系。)
傳統的NFA在報告無法比對以前，必須嘗試正規表達式的所有變體。這也是為什麼後面我們要單獨讨論提高NFA表達式的比對速度技巧。傳統型NFA如果能找到一個比對，肯定會停止比對。而POSIX NFA必須嘗試正規表達式的所有變體，確定獲得最長的比對文本。是以，對POSIX NFA的效率問題更為重要。
DFA不需要做太多的優化，因為它的比對速度很快。
[b]4.DFA和NFA:比對結果的差别[/b]
DFA傳回最左邊的最長的比對文本。傳統型NFA可能傳回同樣的結果，當然也可能傳回别的文本。針對某一型具體的引擎，同樣的正規表達式，同樣的文本，總是得到同樣的結果，在這個意義上說，它不是随機的。
[b]5.DFA與NFA:能力的差異[/b]
NFA引擎能提供DFA不支援的功能，例如：
1)捕獲由括号内的子表達式比對的文本。
2)環視，以及其他複雜的零長度确認。
3)非比對優先的量詞，以及有序的多選結構。
4)占有優先量詞和固化分組。
![IBM Power程式設計馬拉松——以“碼”會友，把手言歡！[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)