匹配基礎(chǔ)

對(duì)于正則表達(dá)式，有兩條普適原則：

• 優(yōu)先選擇最左端的匹配結(jié)果；
• 標(biāo)準(zhǔn)的匹配量詞（*、+、?和{min, max}）是優(yōu)先匹配的。

規(guī)則1：優(yōu)先選擇最左端的匹配結(jié)果

正則引擎在目標(biāo)文本的某一位置檢測(cè)整個(gè)正則表達(dá)式能匹配的每樣文本，若在所有可能的匹配嘗試失敗之后，則從當(dāng)前位置的下一位置開(kāi)始重新開(kāi)始檢查。在嘗試過(guò)所有的起始位置都不能找到匹配結(jié)果的情況下，報(bào)告匹配失敗，反之則報(bào)告匹配成功。
例如，用cat來(lái)匹配The dragging belly indicates that your cat is too fat.在非全局匹配模式（/g）下，匹配的結(jié)果是indicates中的cat，而非后來(lái)的cat。若不了解這條規(guī)則，在執(zhí)行文本替換操作時(shí)，會(huì)產(chǎn)生令人困惑的結(jié)果。

規(guī)則2：標(biāo)準(zhǔn)量詞是優(yōu)先匹配的

標(biāo)準(zhǔn)匹配量詞都是匹配優(yōu)先的，它們總是嘗試匹配盡可能多的字符，直至匹配上限。以\b\w+s\b為例，\w+完全能夠匹配regexes整個(gè)單詞，但為了表達(dá)式的余下部分能夠成功匹配，\w+被迫“交還”之前匹配的字符s，該過(guò)程被稱作回溯，將在下文講到。
當(dāng)正則表達(dá)式中存在多個(gè)標(biāo)準(zhǔn)量詞，這條規(guī)則總是優(yōu)先保證前面量詞限定的部分不受后面元素的影響。如^.*(\d+)匹配CA 95472 USA時(shí)，\d+只能匹配一個(gè)數(shù)字2。
實(shí)際上，對(duì)表達(dá)式.*而言，存在濫用情況。因?yàn)?code>.可以匹配除換行符以外的所有字符，它總是引起過(guò)多不必要的回溯。比如用^.*(\d\d)來(lái)匹配about 24 characters long，在.*匹配整個(gè)字符串之后，必須循環(huán)回溯17次，直到它釋放字符2和4來(lái)滿足余下的表達(dá)式\d\d匹配成功。

正則引擎

正則引擎主要可以分為兩大類：DFA和NFA。兩類引擎經(jīng)過(guò)多年發(fā)展，產(chǎn)生了多種不必要的變體，為規(guī)范這種現(xiàn)狀，出臺(tái)了POSIX標(biāo)準(zhǔn)。POSIX標(biāo)準(zhǔn)規(guī)定了引擎應(yīng)該支持的元字符和特性，以及使用者期望由表達(dá)式獲得的準(zhǔn)確結(jié)果。而傳統(tǒng)NFA引擎根據(jù)該標(biāo)準(zhǔn)衍生出新的引擎類型，POSIX NFA。
在主流的程序中egrep、awk、MySQL使用DFA引擎，而JAVA、grep、.Net、PHP、Python、Ruby等使用傳統(tǒng)NFA引擎。

NFA引擎

NFA（非確定型有窮自動(dòng)機(jī)）引擎是以正則表達(dá)式為主導(dǎo)的引擎。NFA引擎每次檢查表達(dá)式的一部分，同時(shí)檢查當(dāng)前文本是否匹配表達(dá)式的當(dāng)前部分（這里用部分表示需要匹配的可能是一個(gè)字符，或一個(gè)子表達(dá)式），若匹配，則繼續(xù)表達(dá)式的下一部分，直至所有部分都能匹配，即表達(dá)式匹配成功。以to(nite|knight|night)匹配文本... tonight ...為例，引擎從t開(kāi)始，在目標(biāo)文本找到t為止，然后檢查緊隨其后的字符是否能匹配o。當(dāng)碰到分支結(jié)構(gòu)時(shí)，引擎會(huì)依次選擇分支所列的多種匹配模式，直至匹配成功。
由于傳統(tǒng)NFA引擎使用的是順序結(jié)構(gòu)的多選分支，在安排分支的先后順序時(shí)需格外小心，以免寫(xiě)出無(wú)意義的多選結(jié)構(gòu)。如a((ab)*|b*)，因?yàn)榈谝粭l分支(ab)*永遠(yuǎn)不會(huì)匹配失敗，所以第二條分支毫無(wú)意義。
NFA引擎匹配的過(guò)程中，每一個(gè)子表達(dá)式都是獨(dú)立的，子表達(dá)式之間不存在內(nèi)在聯(lián)系，而只是整個(gè)表達(dá)式的各個(gè)部分。

DFA引擎

DFA（確定型有窮自動(dòng)機(jī)）引擎是以文本為主導(dǎo)的引擎。DFA引擎在掃描字符串時(shí)，會(huì)記錄當(dāng)前有效的所有匹配可能。具體到... tonight ...例子，引擎每掃描一個(gè)字符，都會(huì)更新當(dāng)前的可能匹配序列，直至引擎發(fā)現(xiàn)匹配已經(jīng)完成，則報(bào)告匹配成功。若在掃描過(guò)程中，引擎發(fā)現(xiàn)目標(biāo)文本中的某個(gè)字符會(huì)令所有處理中的匹配失效，則返回某個(gè)之前保留的完整匹配，若不存在這樣的完整匹配，則報(bào)告在當(dāng)前位置無(wú)法匹配。在多選分支結(jié)構(gòu)中，DFA引擎總是優(yōu)先匹配所有分支中匹配最多文本的那條分支。

<small>注：此處用|作為引擎當(dāng)前進(jìn)行匹配的位置，下同</small>。
值得一提，DFA引擎不支持捕獲型括號(hào)、反向引用、忽略優(yōu)先量詞這些特性。

在使用正則表達(dá)式進(jìn)行檢索文本之前，兩種引擎都會(huì)編譯表達(dá)式，得到一套內(nèi)化形式，適應(yīng)各自的匹配算法。NFA的編譯過(guò)程通常要更快一些，所需內(nèi)存也更小。而在NFA匹配過(guò)程中，目標(biāo)文本的某個(gè)字符可能會(huì)被正則表達(dá)式重復(fù)檢測(cè)，在DFA中，目標(biāo)文本中的字符至多只會(huì)被檢測(cè)一次，所以，在一般情況下，DFA是要比NFA快一些（若只是簡(jiǎn)單文本的匹配測(cè)試，兩者速度倒是相差無(wú)幾）。NFA是表達(dá)式主導(dǎo)的，能提供一些DFA不支持的功能，相對(duì)而言它具有更開(kāi)闊的施展空間。

回溯

NFA引擎最重要的性質(zhì)是，在遇到多個(gè)可能成功的可能（包括量詞、多選結(jié)構(gòu)）中進(jìn)行選擇時(shí)，它會(huì)選擇其一，并記住其它，當(dāng)匹配失敗時(shí)，引擎會(huì)回溯到之前記錄的位置繼續(xù)嘗試匹配。記錄的位置包含兩個(gè)位置信息：正則表達(dá)式中的位置，和未嘗試的分支在字符串中的位置。在NFA正則表達(dá)式中，這些記錄的位置被稱為備用狀態(tài)。
回溯機(jī)制有兩個(gè)要點(diǎn)：

1. 如果需要在“進(jìn)行嘗試”和“跳過(guò)嘗試”之間選擇，對(duì)于匹配優(yōu)先量詞，引擎會(huì)優(yōu)先選擇“進(jìn)行嘗試”，而對(duì)于忽略優(yōu)先量詞，會(huì)選擇“跳過(guò)嘗試”。
2. 距離當(dāng)前最近存儲(chǔ)的選項(xiàng)就是當(dāng)本地失敗強(qiáng)制回溯時(shí)返回的，使用的原則是LIFO。

未進(jìn)行回溯的匹配

用ab?c匹配abc：

1. 匹配a，當(dāng)前狀態(tài)為a|bc和a|b?c；
2. 記錄備用狀態(tài)a|bc和ab?|c，當(dāng)前狀態(tài)仍同1所示；
3. 匹配b，當(dāng)前狀態(tài)為ab|c和ab?|c；
4. 匹配c，匹配完成，丟棄之前保存的備用狀態(tài)。

進(jìn)行了回溯的匹配

用ab?c匹配ac：

1. 匹配a，當(dāng)前狀態(tài)為a|c和a|b?c；
2. 記錄備用狀態(tài)a|c和ab?|c；
3. 匹配b失敗，返回之前記錄的備用狀態(tài)；
4. 匹配c，匹配完成。

不成功的匹配

用ab?c匹配abd：

1. 1-3步匹配過(guò)程同例1，但在匹配c時(shí)失敗，而返回備用狀態(tài)記錄位置仍失敗，由于不存在記錄的備用狀態(tài)，本次匹配失敗，故字符串前進(jìn)，再次嘗試正則表達(dá)式。當(dāng)前狀態(tài)為a|bc和|ab?c；
2. 重新開(kāi)始的整個(gè)匹配失敗，字符串繼續(xù)前進(jìn)，直至隨后的ab|c和abc|都失敗，引擎宣告匹配失敗。

忽略優(yōu)先的匹配

用ab??c匹配abc：

1. 匹配a，當(dāng)前狀態(tài)為a|bc和a|b??c；
2. 忽略b??，記錄備用狀態(tài)a|bc和a|b??c，當(dāng)前狀態(tài)為a|bc和ab??|c；
3. c無(wú)法匹配b，回溯到狀態(tài)a|bc和a|b??c；
4. 匹配b，當(dāng)前狀態(tài)為ab|c和ab??|c；
5. 匹配c，匹配完成。

同理，每次測(cè)試*或+作用的元素之前，引擎都會(huì)保存一個(gè)狀態(tài)，若測(cè)試失敗，便回退到之前保存的狀態(tài)開(kāi)始匹配。這個(gè)過(guò)程會(huì)不斷重復(fù)，直到所有的嘗試完全失敗為止。

匹配優(yōu)先與回溯

有一種常見(jiàn)的錯(cuò)誤是，當(dāng)我們希望用".*"來(lái)檢索“雙引號(hào)之間的文本”，而在匹配The name "McDonald's" is said "makudonarudo" in Japanese.這種帶有多對(duì)雙引號(hào)的文本時(shí)，總是輸出如"McDonald's" is said "makudonarudo"這種錯(cuò)誤。這也是之前提到關(guān)于.*表達(dá)式濫用的情況之一。正確的答案是用"[^"]*"代替".*"。盡管".*?"也能達(dá)到相同的效果，但是較之[^"]*，.*?存在許多不必要的回溯，效率方面有所欠缺。
但不幸的是，對(duì)于... <B>Billions</B> and <B>Zillions</B> of ...，并不能用<B>[^</B>]*</B>匹配。字符組只能代表單個(gè)字符，而這里需要的</B>是一組字符，事實(shí)是[^</B>]和[^<>B/]并無(wú)本質(zhì)區(qū)別。此時(shí)，使用忽略優(yōu)先量詞*?就派上了用場(chǎng)。但通常情況下，忽略優(yōu)先量詞并不是排除類的完美替身。若用<B>[^</B>]*?</B>來(lái)匹配... <B>Billions and <B>Zillions</B> of ...，我并不認(rèn)為輸出的<B>Billions and <B>Zillions</B>就是用戶所期望的。在支持零寬斷言的程序中，把表達(dá)式改為<B>((?!</?B>).)*</B>，就能準(zhǔn)確匹配我們期望的內(nèi)容。因?yàn)閿嘌越沽吮磉_(dá)式主體匹配<B>和</B>之外的內(nèi)容。
無(wú)論是匹配優(yōu)先，還是忽略優(yōu)先，都是為全局匹配服務(wù)的，只要引擎報(bào)告匹配失敗，則必然嘗試了所有可能的匹配。若只存在一條可能的匹配路徑，兩種模式就都能找到這個(gè)結(jié)果，區(qū)別只在于找出這個(gè)結(jié)果的效率而已。若最后可能的匹配結(jié)果不唯一，則需要根據(jù)實(shí)際情況自行選擇。
在零寬斷言的子表達(dá)式結(jié)構(gòu)中，它會(huì)保存自己的備用狀態(tài)，進(jìn)行必要的回溯。但只要零寬斷言的匹配嘗試結(jié)束，它就不會(huì)留下任何備用狀態(tài)，所有備用狀態(tài)會(huì)在斷言成功時(shí)被放棄（斷言失敗時(shí)意味著所有可能的匹配路徑都已經(jīng)被嘗試，也就無(wú)所謂放棄）。在不支持固化分組的流派中，通常可以使用零寬斷言來(lái)模擬。比如用(?=(regex))\1來(lái)模擬(?>regex)，用^(?=(\w+))\1:來(lái)模擬(?>\w+):。

占有優(yōu)先量詞與固化分組

如果流派支持固化分組或者占有優(yōu)先量詞，我們可以選擇在某個(gè)可選元素已經(jīng)成功匹配的情況下，拋棄此元素的備用狀態(tài)來(lái)阻止回溯。

固化分組

使用固化分組，(?>expression)，的匹配和正常的匹配并無(wú)差別，但若匹配進(jìn)行到次結(jié)構(gòu)之后，那么此結(jié)構(gòu)內(nèi)的所有備用狀態(tài)都會(huì)被放棄。即，在固化分組匹配結(jié)束時(shí)，它已經(jīng)匹配的文本已經(jīng)固化為一個(gè)單元，只能作為整體而保留或放棄。放棄備用狀態(tài)可能對(duì)匹配結(jié)果毫無(wú)影響，也可能導(dǎo)致匹配失敗，或者改變匹配結(jié)果。比如\b(?>\S+)ing\b就無(wú)法匹配listening a song中的listening。
如果當(dāng)我們確定保留的備用狀態(tài)毫無(wú)作用時(shí)，那么存在可以匹配的文本時(shí)，固化分組不會(huì)有任何影響，但若不存在能夠匹配的文本，放棄這些備用狀態(tài)會(huì)讓引擎更快地得出無(wú)法匹配的結(jié)論。比如用^(?>\w+):來(lái)代替^\w+:匹配Subject，可以加快報(bào)告匹配失敗的速度。

占有優(yōu)先量詞

占有優(yōu)先量詞與匹配優(yōu)先量詞相似，只是占有優(yōu)先量詞從不交還已經(jīng)匹配的字符。占有優(yōu)先量詞不會(huì)創(chuàng)造已經(jīng)匹配字符的備用狀態(tài)。