目前越來(lái)越多的網(wǎng)站、編輯器、編程語(yǔ)言都已支持一種叫“正則表達(dá)式”的字符串查找“公式”，有過(guò)編程經(jīng)驗(yàn)的同學(xué)都應(yīng)該了解正則表達(dá)式（Regular Expression 簡(jiǎn)寫(xiě)regex）是什么東西，它是一種字符串匹配的模式（pattern），更像是一種邏輯公式。 

使用正則表達(dá)式去匹配字符串Hello World 中的 Hello  
偽代碼：/Hello/, "Hello World"  
輸出：Hello 

如何寫(xiě)好一篇關(guān)于 正則表達(dá)式 的文章，我思考了一周的時(shí)間，從未有一篇文章能讓豬哥如此費(fèi)神。

因?yàn)槲矣X(jué)得正則表達(dá)式 ：難記憶、難描述、廣而深且不受重視，有人說(shuō)正則表達(dá)式既好寫(xiě)也難寫(xiě)！

1.  好寫(xiě)：無(wú)非寫(xiě)一些常用、實(shí)用的案例，說(shuō)實(shí)話你們每個(gè)人都能寫(xiě)出這種：在網(wǎng)上百度一下然后結(jié)合一點(diǎn)自己的實(shí)際經(jīng)驗(yàn)，一篇文章就出來(lái)了。
2.  難寫(xiě)：很多人都認(rèn)為正則簡(jiǎn)單，不用記，要用就百度一下。但是絕大多數(shù)人了解的只是正則的一個(gè)小面，真正的精髓卻很少關(guān)注！

豬哥希望大家能知道正則的知識(shí)點(diǎn)其實(shí)非常非常多，尤其是正則引擎執(zhí)行原理以及正則優(yōu)化，這算是正則表達(dá)式的進(jìn)階知識(shí)點(diǎn)，面試中也可能會(huì)被問(wèn)到。

一、起源與發(fā)展

我們?cè)趯W(xué)習(xí)一門(mén)技術(shù)的時(shí)候有必要了解其起源與發(fā)展過(guò)程，這對(duì)我們?nèi)ダ斫饧夹g(shù)本身有一定的幫助！

20世紀(jì)40年代：正則表達(dá)式最初的想法來(lái)自兩位神經(jīng)學(xué)家：沃爾特·皮茨與麥卡洛克，他們研究出了一種用數(shù)學(xué)方式來(lái)描述神經(jīng)網(wǎng)絡(luò)的模型。

1956年：一位名叫Stephen Kleene的數(shù)學(xué)科學(xué)家發(fā)表了一篇題目是《神經(jīng)網(wǎng)事件的表示法》的論文，利用稱(chēng)之為正則集合的數(shù)學(xué)符號(hào)來(lái)描述此模型，引入了正則表達(dá)式的概念。正則表達(dá)式被作為用來(lái)描述其稱(chēng)之為“正則集的代數(shù)”的一種表達(dá)式，因而采用了“正則表達(dá)式”這個(gè)術(shù)語(yǔ)。

1968年：C語(yǔ)言之父、UNIX之父肯·湯普森把這個(gè)“正則表達(dá)式”的理論成果用于做一些搜索算法的研究，他描述了一種正則表達(dá)式的編譯器，于是出現(xiàn)了應(yīng)該算是最早的正則表達(dá)式的編譯器qed（這也就成為后來(lái)的grep編輯器）。

Unix使用正則之后，正則表達(dá)式不斷的發(fā)展壯大，然后大規(guī)模應(yīng)用于各種領(lǐng)域，根據(jù)這些領(lǐng)域各自的條件需要，又發(fā)展出了許多版本的正則表達(dá)式，出現(xiàn)了許多的分支。我們把這些分支叫做“流派”。

1987年：Perl語(yǔ)言誕生了，它綜合了其他的語(yǔ)言，用正則表達(dá)式作為基礎(chǔ)，開(kāi)創(chuàng)了一個(gè)新的流派，Perl流派。之后很多編程語(yǔ)言如：Python、Java、Ruby、.Net、PHP等等在設(shè)計(jì)正則式支持的時(shí)候都參考Perl正則表達(dá)式。

到這里我們也就知道為什么眾多編程語(yǔ)言的正則表達(dá)式基本一樣，因?yàn)樗麄兌紟煆腜erl。

注：Perl語(yǔ)言是一種擅長(zhǎng)處理文本的語(yǔ)言，但因晦澀語(yǔ)法和古怪符號(hào)不利于理解和記憶導(dǎo)致很多開(kāi)發(fā)者并不喜歡。

二、語(yǔ)法

完整的正則表達(dá)式由兩種字符構(gòu)成：特殊字符（元字符）和普通字符。

ps：元字符表示正則表達(dá)式功能的最小單位，如 * ^ $ \d 等等

關(guān)于語(yǔ)法部分豬哥并不想過(guò)多的講解，給大家做一個(gè)詳細(xì)的歸納整理，供大家日后快速查找吧！

如果想系統(tǒng)學(xué)習(xí)正則表達(dá)式的語(yǔ)法部分，豬哥推薦 菜鳥(niǎo)教程： https://www.runoob.com/regexp/regexp-tutorial.html

三、匹配原理

匹配原理是豬哥想要重點(diǎn)講解的部分，也希望同學(xué)們可以認(rèn)真了解這部分的內(nèi)容。

很多人覺(jué)得開(kāi)車(chē)沒(méi)必要了解車(chē)的構(gòu)造原理，但是我們學(xué)編程的還真的需要了解原理。

因?yàn)榱私庠?，你才能調(diào)優(yōu)，這往往也是初級(jí)工程師與中高級(jí)工程師之間的差別點(diǎn)之一！

1.執(zhí)行過(guò)程

正則表達(dá)式的執(zhí)行，是由正則表達(dá)引擎編譯執(zhí)行的，大致的執(zhí)行流程豬哥也畫(huà)了個(gè)流程圖給大家看看。

這里給大家提一點(diǎn)就是：預(yù)編譯（pre-use compile）

豬哥建議大家在生產(chǎn)環(huán)境中使用預(yù)編譯功能，為什么呢？

以Python語(yǔ)言內(nèi)置re模塊舉例：

1.  通過(guò)re.compile(pattern)預(yù)編譯返回Pattern對(duì)象，在后面代碼中可以直接引用。
2.  通過(guò)re.match(pattern, text)即用編譯，雖然也會(huì)有緩存Pattern對(duì)象，但是每次使用都需要去緩存中取出，比預(yù)編譯多一步取操作。

豬哥也通過(guò)實(shí)際測(cè)試來(lái) 驗(yàn)證預(yù)編譯 確實(shí)比 即用編譯 要快！ 

pattern = r'http:\/\/(?:.?\w+)+'  
text = '<a href="http://www.xxx.com">xxx.com</a>' 

2.引擎（重點(diǎn)）

既然正則表達(dá)式由執(zhí)行引擎執(zhí)行，那我們就來(lái)講講正則表達(dá)式的引擎吧，這一塊是重點(diǎn)，希望大家仔細(xì)看看，弄懂了理解了才行！

正則引擎主要可以分為基本不同的兩大類(lèi)：

1.  DFA (Deterministic finite automaton) 確定型有窮自動(dòng)機(jī)
2.  NFA (Non-deterministic finite automaton) 非確定型有窮自動(dòng)機(jī)

ps：當(dāng)然還有一種引擎為：POSIX NFA，這是根據(jù)NFA引擎出的規(guī)范版本，但因?yàn)槭褂幂^少所以我們這里也就不重點(diǎn)講解。

這里需要和大家解釋下何為確定型、有窮、自動(dòng)機(jī)這幾個(gè)名詞：

1.  確定型與非確定型：假設(shè)有一個(gè)字符串（text=abc）需要匹配，在沒(méi)有編寫(xiě)正則表達(dá)式的前提下，就直接可以確定字符匹配順序的就是確定型，不能確定字符匹配順序的則為非確定型。
2.  有窮：有窮即表示有限的意思，這里表示有限次數(shù)內(nèi)能得到結(jié)果。
3.  自動(dòng)機(jī)：自動(dòng)機(jī)便是自動(dòng)完成，在我們?cè)O(shè)置好匹配規(guī)則后由引擎自動(dòng)完成，不需要人為干預(yù)！

根據(jù)上面的解釋我們可得知DFA引擎 和 NFA引擎 的一個(gè)很大區(qū)別就是：在沒(méi)有編寫(xiě)正則表達(dá)式的前提下，是否能確定字符執(zhí)行順序！

DFA引擎執(zhí)行原理：

為了大家能很清楚的理解DFA引擎執(zhí)行原理，豬哥制作了一個(gè)簡(jiǎn)易的動(dòng)態(tài)執(zhí)行過(guò)程圖給大家看看

根據(jù)上面的動(dòng)圖我們可以得出DFA引擎的一些特點(diǎn)：

1.  文本主導(dǎo)：按照文本的順序執(zhí)行，這也就能說(shuō)明為什么DFA引擎是確定型(deterministic)了，穩(wěn)定！
2.  記錄當(dāng)前有效的所有可能：我們看到當(dāng)執(zhí)行到(d|b)時(shí)，同時(shí)比較表達(dá)式中的d和b，所以會(huì)需要更多的內(nèi)存。
3.  每個(gè)字符只檢查一次：這提高了執(zhí)行效率，而且速度與正則表達(dá)式無(wú)關(guān)。
4.  不能使用反向引用等功能：因?yàn)槊總€(gè)字符只檢查一次，文本零寬度（位置）只記錄當(dāng)前比較值，所以不能使用反向引用、環(huán)視等一些功能！

NFA引擎執(zhí)行原理：

豬哥同樣畫(huà)了一個(gè)簡(jiǎn)易的NFA引擎執(zhí)行過(guò)程圖方便大家理解

根據(jù)上面的動(dòng)圖我們可以得出NFA引擎的一些特點(diǎn)：

1.  文表達(dá)式主導(dǎo)：按照表達(dá)式的一部分執(zhí)行，如果不匹配換其他部分繼續(xù)匹配，直到表達(dá)式匹配完成。
2.  會(huì)記錄某個(gè)位置：我們看到當(dāng)執(zhí)行到(d|b)時(shí)，NFA引擎會(huì)記錄字符的位置（零寬度），然后選擇其中一個(gè)先匹配。
3.  單個(gè)字符可能檢查多次：我們看到當(dāng)執(zhí)行到(d|b)時(shí)，比較d后發(fā)現(xiàn)不匹配，于是NFA引擎換表達(dá)式的另一個(gè)分支b，同時(shí)文本位置回退，重新匹配字符'b'。這也是NFA引擎是非確定型的原因，同時(shí)帶來(lái)另一個(gè)問(wèn)題效率可能沒(méi)有DFA引擎高。

      4.  可實(shí)現(xiàn)反向引用等功能：因?yàn)榫哂谢赝诉@一步，所以可以很容易的實(shí)現(xiàn)反向引用、環(huán)視等一些功能！

兩種引擎比較

關(guān)于這兩種引擎的總結(jié)，豬哥引用《精通正則表達(dá)式》書(shū)本中的一句話來(lái)概括：

DFA（電動(dòng)機(jī)） 和NFA（汽油機(jī)） 都有很長(zhǎng)的歷史，不過(guò)，正如汽油機(jī)一樣，NFA 的歷史更長(zhǎng)一些。也有些系統(tǒng)采用了混合引擎，它們會(huì)根據(jù)任務(wù)的不同選擇合適的引擎（甚至對(duì)同一表達(dá)式中的不同部分采用不同的引擎，以求得功能與速度之間的最佳平衡）。        ——《精通正則表達(dá)式》

3.回溯（重點(diǎn)）

作為絕大多數(shù)編程語(yǔ)言都選擇的引擎——NFA (非確定型有窮自動(dòng)機(jī)) 引擎，我們當(dāng)然要再詳細(xì)了解一下它的精髓——回溯。

動(dòng)圖中，我們可以看到當(dāng)某個(gè)正則分支匹配不成功之后，文本的位置需要回退，然后換另一個(gè)分支匹配，而回退這步專(zhuān)業(yè)術(shù)語(yǔ)就叫：回溯。

回溯的原理類(lèi)似我們走迷宮時(shí)走過(guò)的路設(shè)置一個(gè)標(biāo)志物，如果不對(duì)則原路返回，換另一條路。

回溯機(jī)制不但需要重新計(jì)算正則表達(dá)式和文本的對(duì)應(yīng)位置，也需要維護(hù)括號(hào)內(nèi)的子表達(dá)式所匹配文本的狀態(tài)（b匹配成功），保存到內(nèi)存中以數(shù)字編號(hào)的組中，這就叫捕獲組。

保存括號(hào)內(nèi)的匹配結(jié)果之后，我們?cè)诤竺娴恼齽t表達(dá)式中就可以使用，這就是我們所說(shuō)的反向引用，在上面的案例中只有一個(gè)捕獲，所以$1=b。

回溯陷阱：講到回溯必須提到回溯陷阱，它導(dǎo)致的結(jié)果就是機(jī)器CPU使用率爆滿(超100%)，機(jī)器就卡死了。

舉個(gè)例子：text=aaaaa，pattern=/^(a*)b$/，匹配過(guò)程大致是

1.  (a*)：匹配到了文本中的aaaaa
2.  匹配正則中的b，但是失敗，因?yàn)?a*)已經(jīng)把text都吃了
3.  這時(shí)候引擎會(huì)要求(a*)吐出最后一個(gè)字符(a)，但是無(wú)法匹配b
4.  第二次是吐出倒數(shù)第二個(gè)字符(還是a)，依然無(wú)法匹配
5.  就這樣引擎會(huì)要求(a*)逐個(gè)將吃進(jìn)去的字符都吐出來(lái)
6.  但是到最后都無(wú)法匹配b

這里的重點(diǎn)就在于 引擎會(huì)要求*匹配的東西一點(diǎn)一點(diǎn)吐回，我們假設(shè)如果文本長(zhǎng)度為幾萬(wàn)，那引擎就要回溯幾萬(wàn)次，這對(duì)機(jī)器的CPU來(lái)說(shuō)簡(jiǎn)直是災(zāi)難。

有些復(fù)雜的正則表達(dá)式可能有多個(gè)部分都要回溯，那回溯次數(shù)就是指數(shù)型。如果文本長(zhǎng)度為500，一個(gè)表達(dá)式有兩部分都要回溯，那次數(shù)可能是500^2=25萬(wàn)次，這誰(shuí)受得了！

關(guān)于更多更詳細(xì)的回溯介紹，推薦大家可以閱讀《精通正則表達(dá)式》這本書(shū)！

四、優(yōu)化

編寫(xiě)巧妙的正則表達(dá)式不僅僅是一種技能，而且還是一種藝術(shù)。

上面我們了解到，絕大多數(shù)的編程語(yǔ)言都采用的是NFA引擎，而NFA引擎的特點(diǎn)是：功能強(qiáng)大、但有回溯機(jī)制所以效率慢。所以我們需要學(xué)習(xí)一些NFA引擎的一些優(yōu)化技巧，以減少引擎回溯次數(shù)以及更直接的匹配到結(jié)果！

針對(duì)NFA引擎的可優(yōu)化的點(diǎn)其實(shí)挺多的，為了方便大家記憶，豬哥也畫(huà)幅結(jié)構(gòu)圖歸納一下，方便大家收藏細(xì)看。

在面試過(guò)程中也許會(huì)被問(wèn)到關(guān)于正則的優(yōu)化，大家記住幾點(diǎn)就可以。

五、推薦

上面我們講解了關(guān)于正則表達(dá)式的誕生和發(fā)展、引擎、優(yōu)化等知識(shí)，但是關(guān)于正則表達(dá)式的知識(shí)點(diǎn)遠(yuǎn)遠(yuǎn)不止這些，所以最后豬哥推薦一些好的學(xué)習(xí)資料，大家有空可以了解學(xué)習(xí)下。

1.書(shū)

推薦正則表達(dá)式的書(shū)，那必然是《精通正則表達(dá)式》 ，目前這本書(shū)已經(jīng)出了第三版，豆瓣評(píng)分8.9。

內(nèi)容雖然稍有啰嗦，但是對(duì)于正則新手很友好，唯一不足是Python案例少。

2.博客

入門(mén)：菜鳥(niǎo)教程：https://www.runoob.com/regexp/regexp-tutorial.html

深入：某不知名大佬：https://blog.csdn.net/lxcnn

3.在線測(cè)試工具

https://regex101.com/，這個(gè)網(wǎng)站可以選擇不同編程語(yǔ)言的正則支持，有語(yǔ)義分析、匹配測(cè)試、參考列表等，非常實(shí)用。

4.常用案例

一些簡(jiǎn)單常用的小案例匯總，菜鳥(niǎo)教程：http://c.runoob.com/front-end/854

最后祝愿大家都能搞定正則表達(dá)式，處理文本可以得心應(yīng)手！