寫在前面
做碼農的，應該基本都寫過正則表達式吧？匹配合法的郵箱手機號之類的都會用到正則表達式匹配。正則表達式語法非常簡單，但是功能很強大，幾乎能匹配所有格式的字符串。正則表達式幾乎是所有現代語言都有支持庫的，在所有語言裡都可以使用。功能強大，應用廣泛，是現代碼農的必備技能之一。
regex
正則表達式是啥？
正則表達式（regular expression）簡稱regex，又叫規則表達式。是一套描述字符串匹配模式的符號集。常見的如同“+”,"*","?"等，都是非常常用的符號。
正則表達式最早是一些數學研究裡用來表示某種模型的符號集，後來被Ken Thompson大神，也就是unix操作系統以及c語言之父，將這套符號表示用在了自己開發的編輯器QED裡面。隨著unix的流行，正則表達式也逐漸在unix類系統裡面應用廣泛，比如vi，grep，awk等等命令，都支持正則表達式。只不過有些命令支持得比較簡單，有些則比較完備。
Ken Thompson大神
後來隨著perl語言的流行，perl裡將正則表達式作為了一直內置的類型，而且使用起來非常簡單，對正則表達式進行了擴展，支持的功能更加強大。perl很長一段時間，都是*nix類系統下面的主流腳本語言。對正則表達式的支持，使得perl字符串處理能力非常強大，也是它流行的重要原因之一。
perl
因為perl對正則表達式的擴展十分強大，以至於後來原本IEEE組織制定了正則表達式的Posix標準之後，因為perl的擴展又分出一個perl樣式正則表達式的分支PCRE(Perl Compatible Regular Expressions)，相信大家都聽說過。事實上大部分編程語言裡的regex是PCRE，當然也有posix和PCRE都支持的，而*nix工具裡則主要是使用posix標準。PCRE同時也是一個大名鼎鼎的正則表達式庫的名字，相信關注過的同學都知道。
除了少數語法上的區別，posix和PCRE大部分語法是一致的。有些不同，像PCRE支持反向引用，posix標準裡沒確定是否支持，但是大多數實現裡都支持。
正則表達式怎麼實現的？
有人肯定好奇於這麼強大的工具到底如何實現的。其實也不難，一般是把正則表達式轉化為NFA
或DFA，然後學過編譯原理的同學肯定知道下面該如何做了，一般就是構建解析表之類的。但是也有把正則表達式作為一種微型語言，編譯成虛擬機opcode，然後通過虛擬器去執行，這樣雖然麻煩，但好處就是很容易優化，甚至通過jit轉化為機器碼執行。
下面附帶Rob Pike大神曾經寫過的一個極簡的正則表達式引擎，只支持'^','$','.','*'幾種符號，不過也能滿足不少簡單需求了，代碼不過30來行。
<code>int
match
(
char
*regexp,char
*text) {if
(regexp[0
] =='^'
)return
matchhere(regexp+1
,text);do
{if
(matchhere(regexp,text))return
1
; }while
(*text++!='\0'
);return
0
; }int
matchhere
(
char
*regexp,char
*text) {if
(regexp[0
] =='\0'
)return
1
;if
(regexp[1
] =='*'
)return
matchstar(regexp[0
],regexp+2
,text);if
(regexp[0
] =='$'
&& regexp[1
]=='\0'
)return
*text =='\0'
;if
(*text!='\0'
&& (regexp[0
]=='.'
|| regexp[0
]==*text))return
matchhere(regexp+1
,text+1
);return
0
; }int
matchstar
(
int
c,char
*regexp,char
*text) {do
{if
(matchhere(regexp,text))return
1
; }while
(*text!='\0'
&& (*text++ ==c || c=='.'
));return
0
; } /<code>
