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

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

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

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

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

KenThompson利用非確定有窮自動(dòng)機(jī)（NDFA）構(gòu)造了正則表達(dá)式。NDFA是一個(gè)有向圖，其每個(gè)節(jié)點(diǎn)代表一個(gè)狀態(tài)，每條邊用字母或符號(hào)（代表空字符串）標(biāo)記。自動(dòng)機(jī)有一個(gè)初始狀態(tài)并可能有多個(gè)終止或接受狀態(tài)。正則表達(dá)式匹配過(guò)程中使用了NDFA，如果在NDFA中，從初始狀態(tài)到接受狀態(tài)結(jié)束的路徑上的字母能匹配文本中的每一個(gè)字符串，就表明找到了文本中的匹配。正則表達(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)造過(guò)程:空字的構(gòu)造方法。自動(dòng)機(jī)由

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

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

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

兩個(gè)狀態(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í)行過(guò)程：abbb字符串的匹配過(guò)程如下：

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

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

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

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

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

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

：?jiǎn)蝹€(gè)的字符可以組成字符類，其語(yǔ)法為用’[’與’]’組成，例如[abcA-Z79]表示可以匹配a，b，c與A到Z，7，9的字符，其中’-’為連字符，表示字符的跨度。‘^’在”[]”間也是特殊字符，表示取反其他的特殊字符如右表：

限定符（重復(fù)）

：

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

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

選擇、分組和引用

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

：如果正則表達(dá)式的匹配模式為MULTILINE模式，^可匹配一行文本的行首，$可匹配一行文本的行末。當(dāng)\b被包含于字符集合中時(shí)，\b代表退格符（ASCII碼=8）。斷言：斷言用于用于查找在某些內(nèi)容(但并不包括這些內(nèi)容，如下面幾個(gè)式子中的括號(hào)中的內(nèi)容)之前或之后的東西，當(dāng)斷言為真時(shí)才會(huì)繼續(xù)進(jìn)行匹配。exp1(?=exp2)正預(yù)測(cè)先行斷言，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>)匹配不包含屬性的簡(jiǎn)單HTML標(biāo)簽內(nèi)里的內(nèi)容。注釋：小括號(hào)的另一種用途是通過(guò)語(yǔ)法(?#comment)來(lái)包含注釋。eg：2[0-4]\d(?#200-249)|25[0-5](?#250-255)|[01]?\d\d?(?#0-199)。

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

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

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

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

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