正則文法介紹
要了解正規表達式的原理，需要先了解一些計算機語言文法的基礎知識。
一個文法可以用一個四元來定義，G = {Vt，Vn，S，P}
其中Vt是一個非空有限的符号集合，它的每個元素成為終結符号。Vn也是一個非空有限的符号集合，它的每個元素稱為非終結符号，并且Vt∩Vn=Φ。S∈Vn，稱為文法G的開始符号。P是一個非空有限集合，它的元素稱為産生式。所謂産生式，其形式為α→β，α稱為産生式的左部，β稱為産生式的右部，符号“→”表示“定義為”，并且α、β∈(Vt∪Vn)*，α≠ε，即α、β是由終結符和非終結符組成的符号串。開始符S必須至少在某一産生式的左部出現一次。
文法可推導的語言标記為L(G)。
著名語言學家Chomsky(喬姆斯基)根據對産生式所施加的限制的不同，把文法分成四種類型，即0型、1型、2型和3型。
- 0型文法要求至少含有一個非終結符，基本沒有什麼限制，一個非常重要的理論結果是：0型文法的能力相當于圖靈機
- 1型文法也叫上下文有關文法，對應于線性有界自動機，要求每個産生式α→β，都有|β|>=|α|，|β|指長度；
- 2型文法也叫上下文無關文法，對應于下推自動機，要求在1型文法的基礎上，再滿足：每一個α→β都有α是非終結符;
- 3型文法也叫正則文法，它對應于有限狀态自動機。它是在2型文法的基礎上滿足：A→α|αB（右線性）或A→α|Bα（左線性)。
正規表達式就是最後一種，正則文法，的一種表達形式，以整個字母表作為終結符集合Vt。
假設有一個文法的産生式是{S->Sa; S->b;}，那麼對應的正規表達式為
ba*
。
是以正規表達式，正則文法，有限狀态自動機這個三個概念雖然指不同的東西，但是具備内在的等價性。
正規表達式是正則文法，限制多于上下文無關文法，而我們使用的程式設計語言文法都是上下文無關文法，是以試圖通過正規表達式去處理代碼(比如語言翻譯、代碼生成)的努力極可能歸于徒勞。不過，把代碼當做純文字，然後在處理過程中使用正規表達式，仍然能大大提高效率。
正規表達式的基礎運算符
正規表達式包含很多的元字元來表達規則，不過本文不是要介紹如何使用正規表達式，關于正規表達式規則最好的參考書是《精通正規表達式》。
實際上，正規表達式核心的運算符隻有以下幾種：
| 名稱 | 示例 | 備注 |
| 或運算 | r|s | 比對的語言是L(r)和L(s)的并集 |
| 連接配接運算 | rs | 比對的語言是L(r)和L(s)連接配接 |
| Kleene運算 | r* | |
| 括号 | (r) | 比對的語言與L(r)一緻 |
kleene運算符優先級最高，且是左結合的，連接配接第二，或運算優先級最低。
運算定律:
| r|s = s|r | | 運算滿足交換律 |
| r|s|t = r|(s|t) | | 滿足結合律 |
| r(st) | 連接配接可以結合 |
| r(s|t) = rs|rt | 連接配接對|可以配置設定 |
| ℇr = rℇ = r | ℇ是連接配接的機關元 |
| r* = (r|ℇ)\* | 閉包中一定包含ℇ |
| r** = r* | *具有幂等性 |
擴充運算符使得正規表達式更具表達力，下面僅舉幾個例子：
| 擴充運算符 | 等價形式 |
| + | r+ = rr* = r*r |
| ？ | r? = r | ℇ |
| 字元類 | [a1a2…an] = a1|a2|…|an；如果是連續的字元類，可以寫成[a1-an] |
進階特性：
正規表達式具備很多進階特性，比如捕獲、環視、固化分組等等，這些特性是為了提高正規表達式的實用價值被設計出來的，不屬于正則文法的範疇。
NFA和DFA
前面說過，正則文法對應于有限狀态自動機，又分确定型有限狀态自動機(DFA)和非确定型有限狀态自動機(NFA)，這兩種狀态機的能力是一樣的，都能識别正則語言。正規表達式的識别引擎，都是基于DFA或NFA構造的。關于狀态機的基礎理論，這裡就不描述了，隻要稍微有點印象，就不妨礙繼續閱讀。
-
NFA
一個字母可以标記離開狀态的多條邊，并且ℇ 也可以标記一條邊；這說明NFA的比對過程面臨很多的岔路，需要做出選擇，一旦某條岔路失敗，就需要回朔。
下圖是正規表達式(a|b)*abb對應的NFA，它相當直覺，基本可以從正規表達式直接轉換而來。
-
DFA
對于每個狀态以及字母表中的每個字母，隻能有一條以該字母為标記的，離開該狀态的邊；這說明DFA的比對過程是确定的，每個字母是需要比對一次。
與上面NFA等價的DFA如下圖，相當地不直覺：
- 将NFA轉化成DFA
由于NFA和DFA的能力是一樣的，每個NFA必然可以轉化成一個等價的DFA。既然DFA對每個輸入可以到達的狀态時是确定的，那麼輸入串s在NFA中可能達到的狀态集合對應為等價DFA中某個狀态。從這個思路出發，可以構造出DFA。
- 首先NFA的初始狀态0不接受ℇ ，是以可以構造出DFA的初始狀态(0)；
- 集合(0)輸入a，在NFA中能夠到達(0，1)，于是構造出此狀态，以及從(0)到(0，1)的邊，标記為a
- 集合(0)輸入b，能到到達的還是(0)，是以構造出從(0)到自身的一條标記為b的邊
- 集合(0，1)輸入a，能能夠到達的還是(0，1)，與上一步類似
- 集合(0，1)輸入b，能夠給到達的是(0，2)，構造狀态(0，2)及相應的邊
- 集合(0，2)輸入a， 能夠到達(0，1)，沒有新狀态，添加一條邊
- 集合(0，2)輸入b，能夠給達到(0，3)，構造新狀态(0，3)
- 集合(0，3)輸入a，能夠到達(0，1)，添加一條邊即可
- 集合(0，3)輸入b，能夠給達到(0)，添加一條邊即可
- 沒有新狀态，結束
最終得到的DFA如下，(0，3)包含了NFA的終結狀态3，是以也是DFA的中介狀态，對狀态重新命名可以得到上面同樣的DFA。
-
DFA和NFA的效率差異
很容易了解，構造DFA的代價遠大于NFA，假設NFA的狀态數為K，那麼等價DFA的狀态數目理論上可達2的k次方，不過實際上幾乎不會出現這麼極端的情況，可以肯定的是構造DFA會消耗更多的時間和記憶體。
但是DFA一旦構造好了之後，執行效率就非常理想了，如果一個串的長度是n，那麼比對算法的執行複雜度是O(n);而NFA在比對過程中，存在大量的分支和回朔，假設NFA的狀态數為s，因為每輸入一個字元可能達到的狀态數做多為s，那麼比對算法的複雜度及時輸入串的長度乘以狀态數O(ns)。
正規表達式的NFA&DFA構造、轉化、簡化有一整套理論及方法，遠比上面的例子複雜，本文僅通過一個簡單的例子來說明原理。
NFA與DFA的能力差異
NFA和DFA這兩種比對算法，除了效率上的差别外，從更高的視點看，形成了兩種風格的引擎，進而對正規表達式的比對的其他方面能力造成差異。NFA被稱之為"表達式主導"引擎，而DFA被稱之為“文本主導”引擎。
NFA：表達式主導
從表達式的第一個部分開始，每次檢查一部分，同時檢查目前文本是否比對表達式的目前部分，如果是，則繼續表達式的下一部分，如此繼續，直到表達式的所有部分都能比對，即整個表達式比對成功。
我們來看表達式
to(nite|knight|night)
比對文本
...tonight...
的過程: 表達式的第一個部分是t，它會不斷重複掃描，直到在字元串中找到t，之後就檢查随後的o，如果能比對就繼續檢查下面的元素。這個例子中，下面的元素是
(nite|knight|night)
，意思是nite或者knight或者night，引擎會依次嘗試這三種可能。
整個過程，控制權在表達式的元素之間轉換，是以被稱之為“表達式主導”。“表達式主導”的特點是每個子表達式都是獨立的，不存在内在聯系。 子表達式與整個正規表達式的控制結構(多選、量詞)的層級關系控制了整個比對過程。
DFA：文本主導
DFA在讀入一個文本的時候，會記錄目前有效的所有比對的表達式位置(這些位置集合對應于DFA的一個狀态)。
以上面的比對過程為例：
- 當引擎讀入文本t時，記錄比對的位置是to(nite|knight|night)；
- 接着讀入o，比對位置to(nite|knight|night)；
- 讀入n，比對位置to(nite|knight|night)，兩個位置，knight被淘汰出局；
- ...
這種方式被稱之“文本主導”是因為被掃描的字元串，控制了引擎的執行過程。
差異之一：NFA表達式影響引擎
NFA表達式主導的特性，使得通過修改正規表達式來影響引擎，是以下面三個表達式盡管能夠比對同樣的文本，但是引擎的執行過程各不相同：
- to(nite|knight|night)
- tonite|toknight|tonight
- to(k?night|nite)
但是對于DFA來說，沒有任何差別。
差異之二：DFA能保證最長比對
對于包含或選項的表達式，NFA在成功比對一個選項之後可能報告比對成功，此時并不知道後面的選項是否也會成功，是否包含一個更長的比對。
假設使用
one(self)?(selfsufficient)?
來比對
oneselfsufficient
，NFA首先比對one，然後比對self，此時發現
selfsufficient
無法比對剩餘子串，但是這個子表達式不是必須的，是以可以立即傳回成功，此時比對的串為
oneself
實際上NFA引擎的比對結果與具體實作有關，而DFA必然會成功比對
oneselfsufficient
差異之三：NFA支援更多功能
NFA能夠支援“捕獲group”，“環視”，“占有優先量詞”，“固話分組”等進階功能，這些功能都基于“子表達式獨立進行比對”這一特點。 而DFA無法記錄比對曆史與子表達式之間的關系，因而也無法實作這些功能。
可見NFA引擎具備更大的實用價值，因而，我們在程式設計語言裡面使用的正規表達式庫都是基于NFA的。java的Pattern就是基于NFA的，Pattern.compile()方法顯然就是在構造NFA狀态圖。
參考資料
- 《精通正規表達式》
- 《編譯原理龍書第二版》
------------------越是喧嚣的世界，越需要甯靜的思考------------------
合抱之木，生于毫末；九層之台，起于壘土；千裡之行，始于足下。
積土成山，風雨興焉；積水成淵，蛟龍生焉；積善成德，而神明自得，聖心備焉。故不積跬步，無以至千裡；不積小流，無以成江海。骐骥一躍，不能十步；驽馬十駕，功在不舍。锲而舍之，朽木不折；锲而不舍，金石可镂。蚓無爪牙之利，筋骨之強，上食埃土，下飲黃泉，用心一也。蟹六跪而二螯，非蛇鳝之穴無可寄托者，用心躁也。