寫寫對簡單的匹配原理的理解，還是以php為主。

　　首先，正則引擎主要可分為兩大類：DFA和NFA，反正引擎見多了就不奇怪了，簡單理解就是不同的匹配方式，就好比在數(shù)組中查找數(shù)據(jù)時，有的是從頭開始順序，查找，有的從中間開始查找，所用的方式不同。相對來說NFA有更長的歷史，使用NFA的工具或者語言更多，但也有兩個引擎混合使用的。某書上舉的例子非常貼切：NFA好比汽油機，DFA好比電動機，它們都能使汽車運行但有使用不同的機理。由于NFA和DFA都發(fā)展了很多年，所以又出臺了一個被稱為POSIX的標準，它規(guī)定作為一個正則引擎應(yīng)該支持的元字符和特性，以及最終用戶想要得到的準確結(jié)果。

　　NFA，以（正則）表達式為主導(dǎo)進行匹配，DFA則以待匹配的字符串為主導(dǎo)進行匹配。php使用的是傳統(tǒng)型的NFA引擎，當然了Perl也是。無論哪種引擎，有兩個通用的原則：1. 優(yōu)先匹配最靠左端的結(jié)果；2. 標準量詞（+、?、*、{m,n}）均是匹配優(yōu)先的。

　　現(xiàn)有表達式如下，要匹配字符串'tonight'

    '/to(nite|knite|night)/'

　　NFA：以表達式為主導(dǎo)，從表達式的第一部分開始，同時檢查當前文本是否匹配，如果是，繼續(xù)到表達式的下一部分，直到表達式全部都能匹配，整個匹配成功。表達式的第一個字符時t，它將在字符串中按順序從左到右反復(fù)查找，直到找到一個t字符，如果找不到就宣告失敗，如果找到，表達式下一個字符時o，繼續(xù)在待匹配字符串中查找，開頭兩個都能匹配上，進入到由括號分組的一個選擇分支中，匹配nite、knite或者night，它依次嘗試這種三種可能。第一個分支嘗試到nig時失敗，第二個分支嘗試到表達式中第一個n時失敗，第三個分支恰好完全匹配。以正則表達主導(dǎo)的引擎，就必須檢查完表達式才能得出最終結(jié)論。

　　DFA：與NFA不同，DFA在掃描字符串時，會記錄當前有效的所有匹配可能，從最開始的t，它會在當前的匹配可能中添加一種可能，如果存在的話，一直掃描到字符串中的n時，它會記錄兩種可能，nite和night兩處的n（它是從待匹配的字符串角度看表達式），繼續(xù)掃描到i還是nite和night兩種可能，接著到g只剩下night一種可能了，當h和t匹配完成后，引擎發(fā)現(xiàn)掃描字符串已掃描結(jié)束，報告成功（貌似有點深度與廣度的意味）。

　　所以，一般情況下文本主導(dǎo)的DFA引擎要更快一些，表達式主導(dǎo)的NFA必須檢測完所有的模式，在沒有抵達模式結(jié)束之前，不知道匹配的成功與否，即使前面某個表達式匹配成功了，說不定后面繼續(xù)要對它檢測一下，這可能會浪費很多時間。而DFA以字符串為主導(dǎo)，到一個地方頂多記錄幾種可能性，目標文本中的字符最多只會檢測一次。

　　但是多選分支的順序，對于不同目標字符串的影響也很大，恰好符合的分支在前面，當然能更快找到。

　　由于NFA以表達式為主，表達式書寫的不同會產(chǎn)生很大的影響，也能讓我們更加靈活的控制它，也具有更多的可變性。這其中，對于NFA來說（本來也是以php為主），有一個重要的特性：回溯---遇到需要從兩個可能成功的匹配中選擇時，先選擇一種，并記住另外一種，以作稍后可能的需要，這種情形主要出現(xiàn)在標準量詞和多選分支（|）。

　　盜圖一張：

　　從表達式（'/".*"!/'）出發(fā)，首先找到雙引號A處，接著由于是點號匹配任意字符（默認不包括換行符，這兒不用考慮），再加上元字符*表示可以匹配多個，由于標準量詞的匹配優(yōu)先機理，它一下子來到了字符串的結(jié)尾B處，因為在這之間*可以是0個、1個或多個，也就是說，這幾種形式都是有可能匹配成功的，因此，引擎會記住這兩種狀態(tài)，即在一個位置可能匹配，也可以不匹配它，只要是*元字符經(jīng)過的地方，從M到結(jié)尾都會記錄。

　　等到結(jié)尾發(fā)現(xiàn)沒有"，于是回溯，需要說明，引擎總是回溯到最近記錄的狀態(tài)（類似棧），一個個往前回溯，直到遇到一個雙引號的地方（C），然后匹配匹配到雙引號后面（D），發(fā)現(xiàn)不是感嘆號!，失敗，再次回溯（狀態(tài)記錄不為空），到E處又找到了一個雙引號，與剛才情況相同，繼續(xù)匹配（F）發(fā)現(xiàn)沒有感嘆號，失敗，繼續(xù)回溯到G，同樣由于后邊（H）不是感嘆號，仍需要回溯，到I，這時記錄的狀態(tài)已經(jīng)沒有了，也無法繼續(xù)回溯了，第一輪匹配失敗告終，但還沒完，引擎的傳動裝置繼續(xù)從A處雙引號的下一個位置開始繼續(xù)尋找第一個符合條件的雙引號，到J，然后類似上一輪的過程繼續(xù)上演。最終也沒找到 "..."! 這樣的字符串，過程卻很曲折。

　　從上面的例子可以看出：一是 .*  這種形式的效率非常低，尤其在失敗的時候（當然平常我們那幾行代碼幾乎忽略不計），而且很容易出錯，比如用 /".*/" 匹配一對雙引號包圍的字符串來匹配 ab"cde"fgh""ijk"lmn，最終的結(jié)果是"cde"fgh""ijk"，最開始的雙引號和最末尾的雙引號中間的全部內(nèi)容；二是如果有類似 ((...)*)*、((...)+)*之類的，外面里面同時記錄不定狀態(tài)的，回溯次數(shù)呈指數(shù)級上升，甚至形成死循環(huán)，更加耗時。當然對于改進狀態(tài)的引擎提前檢測這種狀況，并報告錯誤，如同瀏覽器在自己跳轉(zhuǎn)自己的頁面那樣報錯。

 　　因此在用到量詞時，比如+，它可以匹配一個到多個，大于一個時，不是必須的，有兩種選擇狀態(tài)，可以有也可以沒有，這兩種狀態(tài)就是日后可能會在回溯中用到的狀態(tài)，稱為備用狀態(tài)，?也是如此。

　　對于匹配雙引號及之間的字符，中間不包括轉(zhuǎn)義后的雙引號的情況，我們可以使用忽略優(yōu)先，'/".*?"/' ，忽略優(yōu)先按量詞的最小限度匹配， *最小是沒有，相當于先檢測空串，沒有先匹配一個字符馬上檢測雙引號，這在一定只要檢測到右邊有一個雙引號匹配即成功結(jié)束，它匹配上圖中的 "McDonald's"也省去了很多回溯。

　　當然，對于這種需要檢測兩個字符間的其他字符，還有一種辦法，如 '/"[^"]"/'，排除型字符組，它也達到了相同的需求，但情況不總是這樣。

　　比如，匹配<b>與</b>之間的字符，使用 '/<b>[^<//b>]*<//b>/' ？注意字符組一次只能匹配一個字符，這里是匹配在<b>和</b>之間的，非<、/、b、>的任意一個字符，字符組不能把里邊的字符當一個整體，對于整體、多個字符的檢測，可以選擇環(huán)視。環(huán)視與位置相關(guān)，生來就是限定周圍的字符，一個或多個均可。這里需要否定型環(huán)視，因為我們需要的不能是</b>的字符，為了好看中間隔開。

    '/<b>(   (?!<//b>) . )*<//b>/'   // 否定型環(huán)視

　　但是上面仍能匹配"<b>abc<b>def</b>"，所以還要在其之間排除<b>，中間環(huán)視檢測</?b>，/可以有或沒有都行

    '/<b> ( (?! <//? b >) . )* <//b>/'

 　　上一篇寫到了“交還”，在回溯過程中就伴隨著交還，如上面的'/".*"!/'，因發(fā)現(xiàn)雙引號后面不是感嘆號，而不得不回溯，此時選擇另一種備用狀態(tài)---不匹配剛才匹配到的字符，進行回退，是一個明顯的交還。例子：

    $pattern_1 = '/(/w+)(/d?)/';    $pattern_2 = '/(/w+)(/d+)/';    $pattern_3 = '/(/w+)(/d*)/';    $subject = 'abc12345';    PReg_match($pattern_1, $subject, $match_1);    preg_match($pattern_2, $subject, $match_2);    preg_match($pattern_3, $subject, $match_3);    echo 'match=><pre>';    var_dump($match_1, $match_2, $match_3);

　　使用捕獲型括號，分組，引擎記住兩個括號中匹配的文本。結(jié)果如下：

　　從上到下依次為$match_1、$match_2、$match_3，由于/w與/d有公共部分，而且兩個量詞都是匹配優(yōu)先，從結(jié)果來看，前一個+量詞匹配得最多（鍵值為1的項），pattern_1中，/d?沒有匹配，pattern_2中，/d+只匹配了一個，pattern_3中，/d*沒有匹配，而它們訥的過程都類似于，先讓/w+匹配到末尾，然后引擎看剩余的模式，/d?可有可無，那就無，因為無正則匹配也是成功，不交還。/d+必須匹配一個，否則將導(dǎo)致匹配失敗，這里它會交還一個，因為它必須服從使得全局匹配的成功。對于/d*也是如此，可以不匹配，不交還。

　　假如這里的pattern是'/(/w+)(/d/d)/'，那么它就必須交還兩個數(shù)字，如果沒有交還或是帶匹配字符串中沒有，就只能報告失敗。所以有兩個規(guī)律：

　　1. 先來先服務(wù)原則，匹配優(yōu)先的量詞在前，先盡量滿足自己；

　　2. 必須服從全局匹配結(jié)果，有造成失敗的可能，引擎會強迫匹配優(yōu)先量詞交還，否則整個匹配失敗。

　　如果不交還呢？就會提前報告失敗。必須談到占有優(yōu)先量詞和固化分組，以+為例形式是 /w++、 (?>/w+)

    $pattern = '//w+:/';    $subject = 'abcdefghijk';

　　如例，我們?nèi)水斎荒芤谎劭闯鰜恚址Y(jié)尾沒有冒號肯定失敗，但是程序不會這樣，它會一輪又一輪的匹配-回溯，因為它記住了一些可選擇性的狀態(tài)，但現(xiàn)在我們已經(jīng)明確知道了這些狀態(tài)是沒用的，回溯也是白費力氣，回溯前就已經(jīng)失敗了。所以可以 /w++: 或者 (?>/w+): ，有了占有優(yōu)先或者固化分組，這些可選擇性的狀態(tài)都會被拋棄，/w+一直匹配到字符串結(jié)尾，單詞沒了，然后檢測冒號存不存在，冒號不存在，但是現(xiàn)在有沒有可供回溯的狀態(tài)，立即報告失敗，如果是幾十萬行的文本會節(jié)省很多時間。

　　需要注意的是，固話分組或是占有優(yōu)先對嵌套在里面的量詞也是有作用的，這點跟?:只分組不捕獲不同

    (?>   (/d+)+  )    // 里面的/d+的狀態(tài)也會被拋棄    (?: abc (/d/d) )   // 外層的括號不會被捕獲，但里面的括號不受影響，/1仍記錄著數(shù)字字符

 　　最后記錄下選擇分支的一個坑，例

    $pattern = '/cat/';    $subject = 'indicate big cat';

　　cat當然會匹配indicate中間的cat，因為它在前面。再看這個

    $pattern = 'fat|cat|belly|your';    $subject = 'The dragging belly indicates that your cat is too fat';

　　NFA以表達式為主導(dǎo)，從表達式的角度看字符串，因此先檢測到的是fat，結(jié)果是fat嗎？結(jié)果仍是cat！所以NFA的引擎始終優(yōu)先匹配選擇分支選擇最左端的匹配結(jié)果，哪怕它位于選擇分支的后邊。

　　這也說明，NFA引擎的正則，只要表達式中還存在可能的多選分支，正則引擎會回溯到存在尚未嘗試的多選分支的地方，這個過程不斷重復(fù)，直到完成全局匹配，如果不是這樣，上例中fat先匹配成功就已經(jīng)作為結(jié)果返回了。多選狀態(tài)不是匹配優(yōu)先，也不是忽略優(yōu)先，但是嘗試是從左到右。而對于DFA和某些POSIX NFA，匹配的不是最靠字符串左端的文本，而是選擇分支中最長的分支。

　　正則的細節(jié)太多，扯不清楚，還是得看書理解，尤其是對于正則的調(diào)校，以及某些常用的判斷技巧，比如匹配" "包圍的字符串，中間可以有/"和其他轉(zhuǎn)義序列，還是很麻煩的，推薦《精通正則表達式》，中文翻譯挺棒，讀起來也不生硬，而且還有很多技巧性的東西，比如“消除循環(huán)”是一大利器。end