正則表達(dá)式的原理和實(shí)踐

正則表達(dá)式學(xué)習(xí)與實(shí)踐講解人：冷榮秋引言：當(dāng)今各種文本信息急劇增長，有固定格式的、沒有固定格式的或者是在兩者之間。有時由于應(yīng)用的需要，有待對已有的數(shù)據(jù)進(jìn)行計(jì)算機(jī)軟件自動化信息提取或者人為地加工整理。面對海量的文本數(shù)據(jù)，可能要耗費(fèi)許多人寶貴的時間，夜以繼日地工作進(jìn)行整理，期間可能還會產(chǎn)生無數(shù)的人為錯誤。而機(jī)器加工的好處就是只要它能夠被正確的識別就不會產(chǎn)生誤差，且速度也快的驚人。這就是強(qiáng)大的正則表達(dá)式所表現(xiàn)出來的神奇效果，我們對一部書本厚達(dá)2000多頁的txt文本的牛津詞典進(jìn)行過加工，通過調(diào)試正則表達(dá)式代碼來達(dá)到加工的目的，工作效率得以大幅度提升。正則表達(dá)式解釋器主要有3部分組成，分別是解析、編譯與執(zhí)行。

正則表達(dá)式可以用來：驗(yàn)證字符串是否符合指定特征，比如驗(yàn)證是否是合法的郵件地址。用來查找字符串，從一個長的文本中查找符合指定特征的字符串，比查找固定字符串更加靈活方便。

用來替換，比普通的替換更強(qiáng)大。

非確定有窮自動機(jī)（NDFA）：

KenThompson利用非確定有窮自動機(jī)（NDFA）構(gòu)造了正則表達(dá)式。NDFA是一個有向圖，其每個節(jié)點(diǎn)代表一個狀態(tài)，每條邊用字母或符號（代表空字符串）標(biāo)記。自動機(jī)有一個初始狀態(tài)并可能有多個終止或接受狀態(tài)。正則表達(dá)式匹配過程中使用了NDFA，如果在NDFA中，從初始狀態(tài)到接受狀態(tài)結(jié)束的路徑上的字母能匹配文本中的每一個字符串，就表明找到了文本中的匹配。正則表達(dá)式定義如下：字母表中的所有字母均為正則表達(dá)式。若r和s是正則表達(dá)式，那么r|s、（r）、r*和rs也是正則表達(dá)式。正則表達(dá)式r|s代表正則表達(dá)式r或s。正則表達(dá)式r*（也稱作克林閉包）代表r的任意有窮序列：r，rr，rrr，……..正則表達(dá)式rs代表r和s的連接。（r）代表正則表達(dá)式r。NDFA的構(gòu)造過程:空字的構(gòu)造方法。自動機(jī)由

-轉(zhuǎn)移連接兩個節(jié)點(diǎn)而組成。單字符a的構(gòu)造方法，它與空詞的構(gòu)造方法類化，只不過轉(zhuǎn)移是使用字符來標(biāo)識，而不是空字符串。NDFA的構(gòu)造過程(續(xù)):連接節(jié)點(diǎn)的構(gòu)造法。兩個子節(jié)點(diǎn)vl和vr對應(yīng)的Thompson自動機(jī)合并，即第一個自動機(jī)和終止?fàn)顟B(tài)成為第二個自動機(jī)的初始狀態(tài)。并節(jié)點(diǎn)的構(gòu)造法：就像電路圖中的并聯(lián)一樣，必須通過兩個子節(jié)點(diǎn)對應(yīng)的自動機(jī)vl和vr中的一個。這種構(gòu)造需要-轉(zhuǎn)移，在構(gòu)造中，要添加二個狀態(tài)，一個初始狀態(tài)I，從它有二個-轉(zhuǎn)移分別到Th(vl)和Th(vr)的初始狀態(tài)；另一個是終止?fàn)顟B(tài)F，從自動機(jī)Th(vl)和Th(vr)的終止?fàn)顟B(tài)分別由-轉(zhuǎn)移到達(dá)終止?fàn)顟B(tài)F。NDFA的構(gòu)造過程(續(xù)):星節(jié)點(diǎn)的構(gòu)造法：因?yàn)楣?jié)點(diǎn)的唯一子節(jié)點(diǎn)v*可以被重復(fù)任意多次，所以需要創(chuàng)建一個從自動機(jī)Th(v*)的終止?fàn)顟B(tài)指向其初始狀態(tài)的-轉(zhuǎn)移。但是，星符號也意味著自動機(jī)Th(v*)也可能被忽略。因此，需要創(chuàng)建初始節(jié)點(diǎn)I和終結(jié)節(jié)點(diǎn)F，并用一個-轉(zhuǎn)移將他們連接起來。另外，再創(chuàng)建兩條-轉(zhuǎn)移分別用來從節(jié)點(diǎn)I指向Th(v*)的初始狀態(tài)以及從Th(v*)的終止?fàn)顟B(tài)指向F。如右圖：有限狀態(tài)機(jī)（FiniteAutomation）

狀態(tài)機(jī)是一個有一組不同狀態(tài)的集合的系統(tǒng)。有一個特殊狀態(tài)――它描述了系統(tǒng)的初始狀態(tài)。而其他的一個或多個狀態(tài)為終止?fàn)顟B(tài)；當(dāng)一個事件將我們帶到這樣的一些狀態(tài)時，狀態(tài)機(jī)將退出。狀態(tài)是與轉(zhuǎn)換相關(guān)聯(lián)的，每個轉(zhuǎn)換都標(biāo)注有輸入事件的名稱。當(dāng)事件發(fā)生時，我們將隨著相關(guān)的轉(zhuǎn)換從當(dāng)前狀態(tài)移動到新的狀態(tài)。一個有限狀態(tài)機(jī)包含一組狀態(tài)集（states）、一個起始狀態(tài)（startstate）、一組輸入符號集（alphabet）、一個映射輸入符號和當(dāng)前狀態(tài)到下一狀態(tài)的轉(zhuǎn)換函數(shù)（transitionfunction）的計(jì)算模型。當(dāng)輸入符號串，模型隨即進(jìn)入起始狀態(tài)。它要改變到新的狀態(tài)，依賴于轉(zhuǎn)換函數(shù)。

假定一個輸入符號(symbol)，可以得到2個或者2個以上的可能狀態(tài)，那么這個finiteautomaton就是不確定的，反之就是確定的。有限狀態(tài)機(jī)（FiniteAutomation）單個字符

兩個狀態(tài)的連接e1e2e?e1|e2e*e+不確定有限狀態(tài)機(jī)（NFA）

例如要匹配abab|abbb,其NFA的狀態(tài)是確定性有限狀態(tài)機(jī)（DFA）

例如要匹配abab|abbb,其DFA的狀態(tài)是NFA執(zhí)行過程：abbb字符串的匹配過程如下：

一種高效的NFA執(zhí)行過程：同步匹配兩者

利用正則表達(dá)式來掃描要匹配的字符串，又由于此時是不確定狀態(tài)機(jī)，所以利用試探與backing的方式來做匹配的。NFA是由正則來做驅(qū)動匹配的。這就像一個過程語言，控制了解析器在匹配中的try/fail。

DFA執(zhí)行過程DFA與NFA不同，由于對于相應(yīng)的輸入都有一定的狀態(tài)的遷移，所以總的來說，DFA的匹配效率要高一些。DFA是由字符串作驅(qū)動來匹配的，在每個字符串中的每個字符只被掃描一次。這種方式就是嘗試此狀態(tài)時可能的每種輸入同時進(jìn)行匹配。普通字符和元字符

：普通字符是那些表示自身的字符，例如從a到z，A到Z，0到9等；

元字符具有特殊意義，如‘.’，表示除了‘\n’外的所有字符，其他具有此功能的有

(元字符加‘\’轉(zhuǎn)義):字符類

：單個的字符可以組成字符類，其語法為用’[’與’]’組成，例如[abcA-Z79]表示可以匹配a，b，c與A到Z，7，9的字符，其中’-’為連字符，表示字符的跨度?！甞’在”[]”間也是特殊字符，表示取反其他的特殊字符如右表：

限定符（重復(fù)）

：

限定符有2種形式，分別為’*’,’+’,’?’與’{’與’}’來表示在正則中有貪婪與非貪婪之分，默認(rèn)的情況下，正則是貪婪的。非貪婪的2種方式：在原先的限定符加上’?’（/.+?/只將匹配"abdddd"中的第一個a

）；對軟件的正則匹配功能進(jìn)行設(shè)置

選擇、分組和引用

：選擇的語法就是設(shè)置’|’，如a|bc，那么要么a或bc都可以匹配，如果(a|b)c則為匹配ac或bc。如果我們在上例中設(shè)置了”()”，那么這就是分組，每個分組都可以被引用，如(a|b)c*(e|f)\1\2，\1與\2就是引用的語法，\1表示引用了(a|b)，\2表示引用(e|f)，依此類推。這里要說明的是(a|b)c*(e|f)\1\2與(a|b)c*(e|f)(a|b)(e|f)乍一看兩者等同，但實(shí)際上，前一個不可以匹配acebf，而后一個可以。究其原因就是引用處的配平必須與被引用處一致，此例中與之匹配的可以是aceac。后向引用(補(bǔ)充)：后向引用用于重復(fù)搜索前面某個分組匹配的文本。后向引用中的括號中的表達(dá)式如下表：定位符(錨)

：如果正則表達(dá)式的匹配模式為MULTILINE模式，^可匹配一行文本的行首，$可匹配一行文本的行末。當(dāng)\b被包含于字符集合中時，\b代表退格符（ASCII碼=8）。斷言：斷言用于用于查找在某些內(nèi)容(但并不包括這些內(nèi)容，如下面幾個式子中的括號中的內(nèi)容)之前或之后的東西，當(dāng)斷言為真時才會繼續(xù)進(jìn)行匹配。exp1(?=exp2)正預(yù)測先行斷言，exp1后面出現(xiàn)exp2。eg:\b\w+(?=ing\b)能匹配“I‘msingingwhileyou’redancing.”的sing和danc。exp1(?!exp2)：exp1后面不能出現(xiàn)exp2。例如：\b((?!abc)\w)+\b匹配不包含連續(xù)字符串a(chǎn)bc的單詞

(?<=exp1)exp2正回顧后行斷言，exp2前面出現(xiàn)exp1。eg:(?<=\bre)\w+\b能匹配“readingabook”的ading。(?<!exp1)exp2：exp2前面不能出現(xiàn)exp1。(?<=exp1)exp2(?=exp3)兩向斷言,exp2前面出現(xiàn)exp1且后面出現(xiàn)exp3。eg:(?<=\s)\d+(?=\s)匹配以空白間隔的數(shù)字。(?<=<(\w+)>).*(?=<\/\1>)匹配不包含屬性的簡單HTML標(biāo)簽內(nèi)里的內(nèi)容。注釋：小括號的另一種用途是通過語法(?#comment)來包含注釋。eg：2[0-4]\d(?#200-249)|25[0-5](?#250-255)|[01]?\d\d?(?#0-199)。

要包含注釋的話，最好是啟用“忽略模式里的空白符”選項(xiàng)，這樣在編寫表達(dá)式時能任意的添加空格，Tab，換行，而實(shí)際使用時這些都將被忽略。啟用這個選項(xiàng)后，在#后面到這一行結(jié)束的所有文本都將被當(dāng)成注釋忽略掉。eg:(?<= #斷言要匹配的文本的前綴<(\w+)>#查找尖括號括起來的字母或數(shù)字(即HTML/XML標(biāo)簽)) #前綴結(jié)束.*#匹配任意文本(?=#斷言要匹配的文本的后綴

<\/\1>#查找尖括號括起來的內(nèi)容：前面是一個“/”，后面是先前捕獲的標(biāo)簽)#后綴結(jié)束平衡組/遞歸匹配:有辦法能讓正則表達(dá)式匹配xx<aa<bbb><bbb>aa>yy

嗎？語法構(gòu)造：

(?'group')把捕獲的內(nèi)容命名為group,并壓入堆棧(Stack)

(?‘-group’)從堆棧上彈出最后壓入堆棧的名為group的捕獲內(nèi)容，如果堆棧本來為空，則本分組的匹配失敗(?(group)yes|no)如果堆棧上存在以名為group的捕獲內(nèi)容的話，繼續(xù)匹配yes部分的表達(dá)式，否則繼續(xù)匹配no部分(?!)零寬負(fù)向先行斷言，由于沒有后綴表達(dá)式，試圖匹配總是失敗Eg：< #最外層的左括號[^<>]* #最外層的左括號后面的不是括號的內(nèi)容(((?‘Open’<)