1.歷史：

引用
正則表達(dá)式萌芽于1940年代的神經(jīng)生理學(xué)研究，由著名數(shù)學(xué)家Stephen Kleene第一個(gè)正式描述。具體地說(shuō)，Kleene歸納了前述的神經(jīng)生理學(xué)研究，在一篇題為《正則集代數(shù)》的論文中定義了“正則集”，并在其上定義了一個(gè)代數(shù)系統(tǒng)，并且引入了一種記號(hào)系統(tǒng)來(lái)描述正則集，這種記號(hào)系統(tǒng)被他稱為“正則表達(dá)式”。在理論數(shù)學(xué)的圈子里被研究了幾十年之后，1968年，后來(lái)發(fā)明了UNIX系統(tǒng)的Ken Thompson第一個(gè)把正則表達(dá)式用于計(jì)算機(jī)領(lǐng)域，開(kāi)發(fā)了qed和grep兩個(gè)實(shí)用文本處理工具，取得了巨大成功。在此后十幾年里，一大批一流計(jì)算機(jī)科學(xué)家和黑客對(duì)正則表達(dá)式進(jìn)行了密集的研究和實(shí)踐。在1980年代早期，UNIX運(yùn)動(dòng)的兩個(gè)中心貝爾實(shí)驗(yàn)室和加州大學(xué)伯克利分校分別圍繞grep工具對(duì)正則表達(dá)式引擎進(jìn)行了研究和實(shí)現(xiàn)。與之同時(shí)，編譯器“龍書(shū)”的作者Alfred Aho開(kāi)發(fā)了Egrep工具，大大擴(kuò)展和增強(qiáng)了正則表達(dá)式的功能。此后，他又與《C程序設(shè)計(jì)語(yǔ)言》的作者Brian Kernighan等三人一起發(fā)明了流行的awk文本編輯語(yǔ)言。到了1986年，正則表達(dá)式迎來(lái)了一次飛躍。先是C語(yǔ)言頂級(jí)黑客Henry Spencer以源代碼形式發(fā)布了一個(gè)用C語(yǔ)言寫(xiě)成的正則表達(dá)式程序庫(kù)（當(dāng)時(shí)還不叫open source），從而把正則表達(dá)式的奧妙帶入尋常百姓家，然后是技術(shù)怪杰Larry Wall橫空出世，發(fā)布了Perl語(yǔ)言的第一個(gè)版本。自那以后，Perl一直是正則表達(dá)式的旗手，可以說(shuō)，今天正則表達(dá)式的標(biāo)準(zhǔn)和地位是由Perl塑造的。Perl 5.x發(fā)布以后，正則表達(dá)式進(jìn)入了穩(wěn)定成熟期，其強(qiáng)大能力已經(jīng)征服了幾乎所有主流語(yǔ)言平臺(tái)，成為每個(gè)專業(yè)開(kāi)發(fā)者都必須掌握的基本工具。

2.DFA和NFA

引用理解DFA和NFA
正則表達(dá)式引擎分成兩類，一類稱為DFA（確定性有窮自動(dòng)機(jī)），另一類稱為NFA（非確定性有窮自動(dòng)機(jī)）。兩類引擎要順利工作，都必須有一個(gè)正則式和一個(gè)文本串，一個(gè)捏在手里，一個(gè)吃下去。DFA捏著文本串去比較正則式，看到一個(gè)子正則式，就把可能的匹配串全標(biāo)注出來(lái)，然后再看正則式的下一個(gè)部分，根據(jù)新的匹配結(jié)果更新標(biāo)注。而NFA是捏著正則式去比文本，吃掉一個(gè)字符，就把它跟正則式比較，匹配就記下來(lái)：“某年某月某日在某處匹配上了！”，然后接著往下干。一旦不匹配，就把剛吃的這個(gè)字符吐出來(lái)，一個(gè)個(gè)的吐，直到回到上一次匹配的地方。
DFA與NFA機(jī)制上的不同帶來(lái)5個(gè)影響：
1. DFA對(duì)于文本串里的每一個(gè)字符只需掃描一次，比較快，但特性較少；NFA要翻來(lái)覆去吃字符、吐字符，速度慢，但是特性豐富，所以反而應(yīng)用廣泛，當(dāng)今主要的正則表達(dá)式引擎，如Perl、Ruby、Python的re模塊、Java和.NET的regex庫(kù)，都是NFA的。
2. 只有NFA才支持lazy和backreference等特性；
3. NFA急于邀功請(qǐng)賞，所以最左子正則式優(yōu)先匹配成功，因此偶爾會(huì)錯(cuò)過(guò)最佳匹配結(jié)果；DFA則是“最長(zhǎng)的左子正則式優(yōu)先匹配成功”。
4. NFA缺省采用greedy量詞（見(jiàn)item 4）；
5. NFA可能會(huì)陷入遞歸調(diào)用的陷阱而表現(xiàn)得性能極差。

我這里舉一個(gè)例子來(lái)說(shuō)明第3個(gè)影響。

例如用正則式/perl|perlman/來(lái)匹配文本 ‘perlman book’。如果是NFA，則以正則式為導(dǎo)向，手里捏著正則式，眼睛看著文本，一個(gè)字符一個(gè)字符的吃，吃完 ‘perl’ 以后，跟第一個(gè)子正則式/perl/已經(jīng)匹配上了，于是記錄在案，往下再看，吃進(jìn)一個(gè) ‘m’，這下糟了，跟子式/perl/不匹配了，于是把m吐出來(lái)，向上匯報(bào)說(shuō)成功匹配 ‘perl’，不再關(guān)心其他，也不嘗試后面那個(gè)子正則式/perlman/，自然也就看不到那個(gè)更好的答案了。

如果是DFA，它是以文本為導(dǎo)向，手里捏著文本，眼睛看著正則式，一口一口的吃。吃到/p/，就在手里的 ‘p’ 上打一個(gè)鉤，記上一筆，說(shuō)這個(gè)字符已經(jīng)匹配上了，然后往下吃。當(dāng)看到 /perl/ 之后，DFA不會(huì)停，會(huì)嘗試再吃一口。這時(shí)候，第一個(gè)子正則式已經(jīng)山窮水盡了，沒(méi)得吃了，于是就甩掉它，去吃第二個(gè)子正則式的/m/。這一吃好了，因?yàn)橛制ヅ渖狭?，于是接著往下吃。直到把正則式吃完，心滿意足往上報(bào)告說(shuō)成功匹配了 ‘perlman’。

由此可知，要讓NFA正確工作，應(yīng)該使用 /perlman|perl/ 模式。

通過(guò)以上例子，可以理解為什么NFA是最左子式匹配，而DFA是最長(zhǎng)左子式匹配。實(shí)際上，如果仔細(xì)分析，關(guān)于NFA和DFA的不同之處，都可以找出道理。而明白這些道理，對(duì)于有效應(yīng)用正則表達(dá)式是非常有意義的。

寫(xiě)道正則表達(dá)式的形式定義故意非常精簡(jiǎn)，避免定義多余的量詞 ? 和 +，它們可以被表達(dá)為: a+ = aa* 和 a? = (a|ε)。有時(shí)增加補(bǔ)算子 ~ ；~R 指示在 Σ* 上的不在 R 中的所有字符串的集合。補(bǔ)算子是多余的，因?yàn)樗褂闷渌阕觼?lái)表達(dá)(盡管計(jì)算這種表示的過(guò)程是復(fù)雜的，而結(jié)果可能指數(shù)性的增大)。
這種意義上的正則表達(dá)式可以表達(dá)正則語(yǔ)言，精確的是可被有限狀態(tài)自動(dòng)機(jī)接受的語(yǔ)言類。但是在簡(jiǎn)潔性上有重要區(qū)別。某類正則語(yǔ)言只能用大小指數(shù)增長(zhǎng)的自動(dòng)機(jī)來(lái)描述，而要求的正則表達(dá)式的長(zhǎng)度只線性的增長(zhǎng)。正則表達(dá)式對(duì)應(yīng)于喬姆斯基層級(jí)的類型-3文法。在另一方面，在正則表達(dá)式和不導(dǎo)致這種大小上的爆炸的非確定有限狀態(tài)自動(dòng)機(jī)(NFA)之間有簡(jiǎn)單的映射；為此 NFA 經(jīng)常被用作正則表達(dá)式的替代表示。
我們還要在這種形式化中研究表達(dá)力。如下面例子所展示的，不同的正則表達(dá)式可以表達(dá)同樣的語(yǔ)言: 這種形式化中存在著冗余。
有可能對(duì)兩個(gè)給定正則表達(dá)式寫(xiě)一個(gè)算法來(lái)判定它們所描述的語(yǔ)言是否本質(zhì)上相等，簡(jiǎn)約每個(gè)表達(dá)式到極小確定有限自動(dòng)機(jī)，確定它們是否同構(gòu)（等價(jià)）。
這種冗余可以消減到什么程度? 我們可以找到仍有完全表達(dá)力的正則表達(dá)式的有趣的子集嗎? Kleene 星號(hào)和并集明顯是需要的，但是我們或許可以限制它們的使用。這提出了一個(gè)令人驚奇的困難問(wèn)題。因?yàn)檎齽t表達(dá)式如此簡(jiǎn)單，沒(méi)有辦法在語(yǔ)法上把它重寫(xiě)成某種規(guī)范形式。過(guò)去公理化的缺乏導(dǎo)致了星號(hào)高度問(wèn)題。最近 Dexter Kozen 用克萊尼代數(shù)公理化了正則表達(dá)式。
很多現(xiàn)實(shí)世界的“正則表達(dá)式”引擎實(shí)現(xiàn)了不能用正則表達(dá)式代數(shù)表達(dá)的特征。

目前正則引擎支持的語(yǔ)言種類：

引擎類型程序DFAawk(大多數(shù)版本)、egrep（大多數(shù)版本）、flex、lex、MySQL、Procmail傳統(tǒng)型 NFAGNU Emacs、Java、grep（大多數(shù)版本）、less、more、.NET語(yǔ)言、PCRE library、Perl、PHP（所有三套正則庫(kù)）、Python、Ruby、set（大多數(shù)版本）、viPOSIX NFAmawk、Mortice Lern System's utilities、GUN Emacs（明確指定時(shí)使用）DFA/NFA混合GNU awk、 GNU grep/egrep、 Tcl?