什么是正則表達式呢？正則表達式實際上是一個主要用來描述字符串匹配的工具，當然也可以用來匹配其它的東西例如二進制數據，用在字符串方面可能是最常見的。說到這里，可能大家會聯想到如下幾個主題：
怎么排除惡意的腳本代碼？要寫一個腳本語言引擎或者編譯器，是否可以用正則表達式來完成？編譯原理？

實際上要說清楚這里面的所有問題也許已經超出了我的能力范圍了，但是我還是要寫下來，再不寫下來也許哪天我就真的忘得一干二凈了。

首先說正則表達式吧。正則表達式實際上使用的是一個不確定有窮自動機，non-deterministic finite automaton，簡稱nfa。而編譯原理一般使用的是確定有窮自動機（一般就叫有窮自動機，或者有限自動機，其他的說法還包括確定的有限狀態自動機），deterministic finite automaton，簡稱dfa。關于這幾個概念的簡單解釋，隨便goo一下有窮自動機就能夠找到一大堆，這里推薦一個。nfa和dfa有什么區別呢？最簡單的區別就是nfa對同一個字符串輸入完全有可能有多種理解方式，而dfa則只有唯一的一種理解方式。從這里我們可以簡單的理解到nfa所能夠接受的規則并不一定都能夠轉化為dfa所理解的規則。事實上區別在nfa和dfa的分析過程當中就能夠體現出來了，對于nfa來說，很可能需要探測某一種接受方式，當出現不接受的時候就可能需要退出一層，嘗試另外一種可能的接受方式。而對于dfa則不一樣，因為只可能有一種確定的理解方式，因此一旦不匹配，就不需要再做別的嘗試，而可以直截了當的說“不匹配”。因此反過來說，由于dfa只有一種理解方式，所以效率明顯應該比nfa要高。在上面的推薦的地方給出了更為簡潔的說法：nfa和dfa的唯一區別就在于狀態轉移函數不一樣。

編譯器進行詞法分析時所用到的分析公式實際上看起來應該跟正則表達式很相似，那么這個表達式應該是一個什么樣的樣子呢？實際上我們都很熟悉這樣的東西：
s -> a
a -> aa|b
b -> b
上面則三條式子就是狀態轉移函數了，或者你可以理解成推導公式。里面的sabab就是所有有可能的狀態集合，其中sab三個是非終結符，ab兩個是終結符，s是初始狀態。對于上面這樣的推導公式，可以知道這個系統只接受兩種輸入：a...a或者a...ab。為什么這里要引入a、b這樣的非終結符呢？因為很多時候我們要描述這樣一個系統的時候，會經常地遇到一些重復的可定義的部分，就比如一個到多個空格/s+，我們完全可以把這些東西直接寫出來，甚至直接用一條式子表達出來，但是這樣做就會非常的麻煩和困難。為了簡便，很多時候都會將一些重復的，或者比較冗長的，或者比較重要的部分歸納成一個非終結符。非終結符的定義也不是隨隨便便的，而是有一定的規則的，這個規則這里就不討論了。

對于編譯器來說，主要有兩種構造dfa的方式，一種是ll分析方法，另外一種是lr分析方法。這兩種都是基于輸入預測的分析方法，但是分析的方法卻大有不同，ll屬于推導的方式，lr則屬于歸納的方式。如果這么說不好記，那么就記住ll指的是從左向右輸入，從左向右推導；lr是從左向右輸入，從右向左歸納。ll比較符合人的思維方式，但是卻有一些局限性。lr則比較難理解，但是適用范圍卻比ll要廣泛一點，效率也高一點。

說了半天好像跟正則表達式搭不上邊，其實那些使一些準備知識，下面來仔細的說正則表達式。大家看上面我給的那三條推導公式，實際上如果全部用終結符來表示，那么應該是：
a*(a|b)
這就是正則表達式了。因為給整個機器定義一大堆的規則和狀態轉移函數是比較復雜和不必要的，對于一般的字符串匹配來說，因此給正則表達式的執行機構提供一個簡單的、完全用終結符描述出來的匹配字符串就足夠了。

但是這并不代表著我們也應該直接用終結符來構造整個的正則表達式，這樣做會非常復雜和痛苦的，因為一個稍微復雜一點的匹配，正則表達式就會復雜到讓你看不明白，或者看的頭痛。光是括號的配對就足夠讓你忙上半天的了，還有轉義符等其他的東西呢。因此，我們完全有必要像上面說的那樣，定義出非終結符，高效率的創造正則表達式的關鍵就在于此。然而很可惜的是正則表達式本身并沒有這樣的定義，而.net也沒有給我們提供這樣的定義接口。更可惜的是，絕大部分在那里制作正則表達式創建工具的人，根本就沒有想到這一點。拿上一次我提到的regulator來說，有analyzer把整個的表達式翻譯成英語，有snippet提供編寫的便利性，還有很好的文本編輯器，不過僅此而已。analyzer對于看懂一個正則表達式也許是有幫助的，但是它對于你想自己構造一個正則表達式沒有什么幫助。snippet是仿照c#2.0里面的先進東西，然而構造正則表達式不是寫程序，寫幾個括號尖括號等等并不是最影響效率的問題，同時正則表達式也沒有什么pattern的問題，因此實際上snippet對于構造一個正則表達式也沒有什么幫助。而那個很完美的文本編輯器更是沒有跳出用終結符來構造的框框，也不會對提高效率有什么幫助。大家可以試一下用我的正則表達式構造器就知道我所提出的概念是什么意思了。

那么構造正則表達式需要注意一些什么呢？雖然說nfa因為不確定，所以限制比dfa要少，構造起來也比較方便一點。但是不好的構造方式會引起效率低下的問題，因此要盡量：
1、避免不確定的情況發生。解決的辦法是盡可能使用(?>a|b)來代替a|b或者(?:a|b)這樣的形式。（a、b代表一個很長的正則表達式字符串）
2、盡量避免遞歸層次過高的情況。eg:
a*(b*(c|d)|b*(e|f)|b*(g|h))|a*(b*(i*(j|k)|i*(l|m)|i*(n|o))
這樣對于一個a...b...i...o 這樣的字符串將會是一件非常痛苦的事情，因為匹配的過程將會經歷：
a*b*c -> a*b* ->a*b*d -> a* -> a*b*e -> a*b* -> a*b*f -> a* -> a*b*g ->... 這樣一系列的分析->回溯的過程，才能夠到達a*b*i*o這個匹配。上述表達式最好能夠改造成：a*b*(c|d|e|f|g|h|i*(j|k|l|m|n|o)) 這種形式。如果因為需要通過“組”來歸類，那么建議你修改你的“語言格式”，或者盡量減少分組的情況，或者通過匹配之后再用程序代碼來確定實際的分類情況。
3、如果可以的話，比如你要處理的問題比較復雜，就進行簡單的分步處理，以減少表達式的復雜度。表達式越簡單，就越有可能效率高，而設計失誤的可能性也比較少。分布也不要太多，畢竟一次分析也是需要花費時間的。