一. 傳說中的正則表達式

無論你和計算機沾不沾邊，“正則表達式”這個詞多多少少都會聽過，而越是不了解，就越感覺這個詞逼格很高。“正則”是什么東西？聽上去挺洋氣的，正看上去像正規(guī)，然后則呢...打則必死。

第一次碰見這玩意兒的時候還是當(dāng)初學(xué)RMXP的時候(也是個上古的東西了)。想當(dāng)年連程序都沒寫過就去學(xué)Ruby，而那翻譯也鬼才把成員變量翻譯成“實變量”(至少也應(yīng)該是實例變量啊)，搞了半天都不知道這到底是個什么鬼，為什么前面要加個at。在教程的結(jié)尾，寫著“附錄”“正則表達式”，深深地吸引著年幼的我。

點進去。

從頭到尾是各種類字符通配符的列表。

這是個啥？！

二. 正則表達式&正規(guī)式

如果你學(xué)過編譯原理那一定聽說過正規(guī)式卻又沒聽說過正則表達式...趕緊去學(xué)！學(xué)會前不要說自己是CS的XD。

這兩者概念上似乎有微秒的不同但是本質(zhì)卻是一樣的。個人認為，可以把正則表達式看為一種正規(guī)式，給定一個模式與一個字符串就可以查找字符串內(nèi)模式出現(xiàn)的地方。而討論這些，就不得不討論狀態(tài)機。

三. 狀態(tài)機

狀態(tài)機是現(xiàn)實事物運行規(guī)則抽象而成的一個數(shù)學(xué)模型。簡單而言，就是用一些存儲空間來表示當(dāng)前的狀態(tài)，然后每一次根據(jù)外部的數(shù)據(jù)或者情況改自己的狀態(tài)?！禝CS》里面舉了兩個例子，一個是籃球比賽的記分牌，還有一個是轉(zhuǎn)盤密碼鎖。你都可以把所有可能的狀態(tài)列舉出來，然后根據(jù)不同的情況(進球了，或者扭入了一個密碼)來變更整個系統(tǒng)的狀態(tài)。狀態(tài)機這個模型可以在很多地方使用，包括對一個模式的匹配，最直接的辦法就是使用狀態(tài)機。

四. NFA&DFA

假設(shè)現(xiàn)在已經(jīng)有了一個模式，人肉去做匹配，最簡單的就是一個一個看，和普通的字符串匹配有點相似。比如，要匹配ab或者ac，假設(shè)沒有優(yōu)化，0號狀態(tài)就是初始狀態(tài)，1號狀態(tài)為0狀態(tài)下讀入a，2號為1號讀b;3號為0號讀a，4號為3號讀c。這個樣子，在0號狀態(tài)計算機并不知道走哪條分支，只能隨便走一個，等匹配到后面發(fā)現(xiàn)錯了，就需要回溯，這就是NFA。

NFA比較直接，但是也比較簡陋，需要回溯的話在匹配中會消耗大量資源，但是可以轉(zhuǎn)成DFA(雖然也要不少資源算、轉(zhuǎn))。DFA就直接，每一步到下一個狀態(tài)都是確定的。做法很簡單，將NFA每個狀態(tài)下每種輸入會得到怎樣的結(jié)果全部計算一遍。第一步當(dāng)然是初始狀態(tài)A0，把不經(jīng)過任何字符或者經(jīng)過epsilon(空字符)能到達的狀態(tài)全部寫出來，然后計算經(jīng)過所有字符后能到達的狀態(tài)A1 A2...An，然后再把所有的狀態(tài)作輸入，再經(jīng)過一個字符，得到B(A1)1 B(A1)2...B(An)m。本質(zhì)上則是提前把所有可能的回溯全部做了。

五. More about 正則表達式

(其實是在水字數(shù))

很多要搜索的地方支持正則表達式搜索，當(dāng)你對你要搜的東西比較印象比較模糊的時候可以用，會非常方便，比如VS，比如everything。當(dāng)然，也可以用來處理爬蟲爬回來的數(shù)據(jù)。有的時候，是真的為了快速匹配一些模式，所以要記下一些常用的通配符。

^ 匹配字符串開頭

$ 匹配字符串結(jié)尾

上面兩個很重要，比如你想匹配文件名的話寫 .*\.pdf$ 專門指定要以.pdf結(jié)尾，而f后面啥也不能接，就可以用$，同理^表示要從開頭開始匹配。

.

匹配任意字符，使用頻率Max，就連上面那個那么簡單的例子都跳脫不了這個符號

* 前面的字符/模式重復(fù)任意次(或者零次)

+ 前面的字符/模式重復(fù)任意次(一次及以上)

還是見第一個例子， .* 就表示任意字符重復(fù)任意次。注意，如果在這兩個符號后面加上 ? 表示是惰性匹配，只要滿足條件就匹配中，否則系統(tǒng)會嘗試匹配盡可能長的串。

aaaaa與表達式 a+? 和 a+ 第一個只會匹配a，而第二個會匹配aaaaa

? 前面的字符/模式可有可無

do(es)? 匹配do或者does

[a-zA-Z] 匹配一個任意大小寫字母

中括號表示匹配里面列舉的任意一個字符

[^a-zA-Z] 與上面相反，匹配一個字母以外的字符

^放在前面表示匹配列舉以外的

(?<=pattern)

(?=pattern)

一個前肯一個后肯。

(?<=Hello)hi(?=Bye)

匹配前有Hello后有Bye的hi

\ 萬能的轉(zhuǎn)義

當(dāng)你感覺你用的字符可能不代表它本身的含義的時候，加上這個。