840
技海無涯：正則表達式相關的知識和技術(2)——算法
轉換算法
為了讓正則表達式最終能夠被機器識別，並且能夠用其來匹配目標字符串，必須首先將正則表達式轉換為NFA或者DFA（後麵介紹）兩種等價的自動機，一般的轉換過程如下：
正則表達式—①—>NFA—②—>DFA。
當然也可以直接這樣轉換，當然這個算法複雜度更高：
正則表達式—③—>DFA。
上麵的每個過程對應一個算法，下麵我們分別簡單的介紹三種算法。
①正則表達式——>NFA：Thompson 算法
算法本身是比較簡單的，算法的關鍵如下：每個字符都構造一個NFA，然後用epsilon變化將每個NFA連接起來。
具體的算法描述請參考《編譯原理（龍書）》第一版的3.7.1章節。
②NFA—②—>DFA：子集構造算法
這個算法稍微複雜一些，算法關鍵如下：
1）區分狀態和狀態集：DFA中的狀態，實際上對應NFA中的多個狀態，也就是一個NFA狀態集；這也是算法為什麼叫子集算法的原因，因為DFA中的每一個狀態實際上都是NFA狀態集的一個子集。
2）二次轉換：對於已經構造的DFA狀態（NFA狀態集），拿字符集循環驗證狀態集中的狀態能否轉換到其它狀態，有二次轉換：（1）首先看原有狀態集中哪些狀態包含指定字符的轉換，（2）一旦轉換成功，則這些轉換後的狀態後續所有能夠經過一個或者多個epsilon轉換到達的狀態都要包含進來；。
③正則表達式——>DFA。
這個算法沒有明確的名稱，但其中用到了語法樹的概念，因此我暫且稱其為“語法樹構造法”。
算法太複雜，我還沒有時間來仔細研究，因此就不能詳細介紹了：）有需要的大俠可以參考《編譯原理（龍書）》第一版3.9.2章節。
④Shunting-yard算法
在介紹表達式的時候提到了中綴表達式、後綴表達式，將中綴表達式轉換為後綴表達式的算法就是Shunting-yard算法。
詳情請參考：https://en.wikipedia.org/wiki/Shunting_yard_algorithm
========================未完待續==================================
最後更新：2017-04-02 00:06:48