正則表達式及其他
2004年6月29日 16:10什么是正則表達式呢？正則表達式實(shí)際上是一個(gè)主要用來(lái)描述字符串匹配的工具，當然也可以用來(lái)匹配其它的東西例如二進(jìn)制數據，用在字符串方面可能是最常見(jiàn)的。說(shuō)到這里，可能大家會(huì )聯(lián)想到如下幾個(gè)主題：
怎么排除惡意的腳本代碼？要寫(xiě)一個(gè)腳本語(yǔ)言引擎或者編譯器，是否可以用正則表達式來(lái)完成？編譯原理？
實(shí)際上要說(shuō)清楚這里面的所有問(wèn)題也許已經(jīng)超出了我的能力范圍了，但是我還是要寫(xiě)下來(lái)，再不寫(xiě)下來(lái)也許哪天我就真的忘得一干二凈了。
首先說(shuō)正則表達式吧。正則表達式實(shí)際上使用的是一個(gè)不確定有窮自動(dòng)機，Non-deterministic finite automaton，簡(jiǎn)稱(chēng)NFA。而編譯原理一般使用的是確定有窮自動(dòng)機（一般就叫有窮自動(dòng)機，或者有限自動(dòng)機，其他的說(shuō)法還包括確定的有限狀態(tài)自動(dòng)機），Deterministic finite automaton，簡(jiǎn)稱(chēng)DFA。關(guān)于這幾個(gè)概念的簡(jiǎn)單解釋?zhuān)S便Goo一下有窮自動(dòng)機就能夠找到一大堆，這里推薦一個(gè)。NFA和DFA有什么區別呢？最簡(jiǎn)單的區別就是NFA對同一個(gè)字符串輸入完全有可能有多種理解方式，而DFA則只有唯一的一種理解方式。從這里我們可以簡(jiǎn)單的理解到NFA所能夠接受的規則并不一定都能夠轉化為DFA所理解的規則。事實(shí)上區別在NFA和DFA的分析過(guò)程當中就能夠體現出來(lái)了，對于NFA來(lái)說(shuō)，很可能需要探測某一種接受方式，當出現不接受的時(shí)候就可能需要退出一層，嘗試另外一種可能的接受方式。而對于DFA則不一樣，因為只可能有一種確定的理解方式，因此一旦不匹配，就不需要再做別的嘗試，而可以直截了當的說(shuō)“不匹配”。因此反過(guò)來(lái)說(shuō)，由于DFA只有一種理解方式，所以效率明顯應該比NFA要高。在上面的推薦的地方給出了更為簡(jiǎn)潔的說(shuō)法：NFA和DFA的唯一區別就在于狀態(tài)轉移函數不一樣。
編譯器進(jìn)行詞法分析時(shí)所用到的分析公式實(shí)際上看起來(lái)應該跟正則表達式很相似，那么這個(gè)表達式應該是一個(gè)什么樣的樣子呢？實(shí)際上我們都很熟悉這樣的東西：
S -> A
A -> aA|B
B -> b
上面則三條式子就是狀態(tài)轉移函數了，或者你可以理解成推導公式。里面的SABab就是所有有可能的狀態(tài)集合，其中SAB三個(gè)是非終結符，ab兩個(gè)是終結符，S是初始狀態(tài)。對于上面這樣的推導公式，可以知道這個(gè)系統只接受兩種輸入：a...a或者a...ab。為什么這里要引入A、B這樣的非終結符呢？因為很多時(shí)候我們要描述這樣一個(gè)系統的時(shí)候，會(huì )經(jīng)常地遇到一些重復的可定義的部分，就比如一個(gè)到多個(gè)空格\s+，我們完全可以把這些東西直接寫(xiě)出來(lái)，甚至直接用一條式子表達出來(lái)，但是這樣做就會(huì )非常的麻煩和困難。為了簡(jiǎn)便，很多時(shí)候都會(huì )將一些重復的，或者比較冗長(cháng)的，或者比較重要的部分歸納成一個(gè)非終結符。非終結符的定義也不是隨隨便便的，而是有一定的規則的，這個(gè)規則這里就不討論了。
對于編譯器來(lái)說(shuō)，主要有兩種構造DFA的方式，一種是LL分析方法，另外一種是LR分析方法。這兩種都是基于輸入預測的分析方法，但是分析的方法卻大有不同，LL屬于推導的方式，LR則屬于歸納的方式。如果這么說(shuō)不好記，那么就記住LL指的是從左向右輸入，從左向右推導；LR是從左向右輸入，從右向左歸納。LL比較符合人的思維方式，但是卻有一些局限性。LR則比較難理解，但是適用范圍卻比LL要廣泛一點(diǎn)，效率也高一點(diǎn)。
說(shuō)了半天好像跟正則表達式搭不上邊，其實(shí)那些使一些準備知識，下面來(lái)仔細的說(shuō)正則表達式。大家看上面我給的那三條推導公式，實(shí)際上如果全部用終結符來(lái)表示，那么應該是：
a*(a|b)
這就是正則表達式了。因為給整個(gè)機器定義一大堆的規則和狀態(tài)轉移函數是比較復雜和不必要的，對于一般的字符串匹配來(lái)說(shuō)，因此給正則表達式的執行機構提供一個(gè)簡(jiǎn)單的、完全用終結符描述出來(lái)的匹配字符串就足夠了。
但是這并不代表著(zhù)我們也應該直接用終結符來(lái)構造整個(gè)的正則表達式，這樣做會(huì )非常復雜和痛苦的，因為一個(gè)稍微復雜一點(diǎn)的匹配，正則表達式就會(huì )復雜到讓你看不明白，或者看的頭痛。光是括號的配對就足夠讓你忙上半天的了，還有轉義符等其他的東西呢。因此，我們完全有必要像上面說(shuō)的那樣，定義出非終結符，高效率的創(chuàng )造正則表達式的關(guān)鍵就在于此。然而很可惜的是正則表達式本身并沒(méi)有這樣的定義，而.NET也沒(méi)有給我們提供這樣的定義接口。更可惜的是，絕大部分在那里制作正則表達式創(chuàng )建工具的人，根本就沒(méi)有想到這一點(diǎn)。拿上一次我提到的Regulator來(lái)說(shuō)，有Analyzer把整個(gè)的表達式翻譯成英語(yǔ)，有Snippet提供編寫(xiě)的便利性，還有很好的文本編輯器，不過(guò)僅此而已。Analyzer對于看懂一個(gè)正則表達式也許是有幫助的，但是它對于你想自己構造一個(gè)正則表達式?jīng)]有什么幫助。Snippet是仿照C#2.0里面的先進(jìn)東西，然而構造正則表達式不是寫(xiě)程序，寫(xiě)幾個(gè)括號尖括號等等并不是最影響效率的問(wèn)題，同時(shí)正則表達式也沒(méi)有什么Pattern的問(wèn)題，因此實(shí)際上Snippet對于構造一個(gè)正則表達式也沒(méi)有什么幫助。而那個(gè)很完美的文本編輯器更是沒(méi)有跳出用終結符來(lái)構造的框框，也不會(huì )對提高效率有什么幫助。大家可以試一下用我的正則表達式構造器就知道我所提出的概念是什么意思了。
那么構造正則表達式需要注意一些什么呢？雖然說(shuō)NFA因為不確定，所以限制比DFA要少，構造起來(lái)也比較方便一點(diǎn)。但是不好的構造方式會(huì )引起效率低下的問(wèn)題，因此要盡量：
1、避免不確定的情況發(fā)生。解決的辦法是盡可能使用(?>A|B)來(lái)代替A|B或者(?:A|B)這樣的形式。（A、B代表一個(gè)很長(cháng)的正則表達式字符串）
2、盡量避免遞歸層次過(guò)高的情況。eg:
a*(b*(c|d)|b*(e|f)|b*(g|h))|a*(b*(i*(j|k)|i*(l|m)|i*(n|o))
這樣對于一個(gè)a...b...i...o 這樣的字符串將會(huì )是一件非常痛苦的事情，因為匹配的過(guò)程將會(huì )經(jīng)歷：
a*b*c -> a*b* ->a*b*d -> a* -> a*b*e -> a*b* -> a*b*f -> a* -> a*b*g ->... 這樣一系列的分析->回溯的過(guò)程，才能夠到達a*b*i*o這個(gè)匹配。上述表達式最好能夠改造成：a*b*(c|d|e|f|g|h|i*(j|k|l|m|n|o)) 這種形式。如果因為需要通過(guò)“組”來(lái)歸類(lèi)，那么建議你修改你的“語(yǔ)言格式”，或者盡量減少分組的情況，或者通過(guò)匹配之后再用程序代碼來(lái)確定實(shí)際的分類(lèi)情況。
3、如果可以的話(huà)，比如你要處理的問(wèn)題比較復雜，就進(jìn)行簡(jiǎn)單的分步處理，以減少表達式的復雜度。表達式越簡(jiǎn)單，就越有可能效率高，而設計失誤的可能性也比較少。分布也不要太多，畢竟一次分析也是需要花費時(shí)間的。
