【philippica】正則表達式從入門到放棄

1.正則表達式

2.DFA

3.NFA

4.pumping lemma

好吧標題黨了一回,本文不是介紹正則在各種語言,平台下是怎麼用的(python, ruby,js,grep?)如果真的只是想了解正則怎麼用的，推薦這篇：正則表達式30分鐘入門教程 良心推薦

去年寫過一個基於dfa的正則表達式引擎，當然是玩具級別的實現，但也收穫實多，今天看到群里在討論正則的實現，覺得有必要在徹底忘記之前記錄一下

一般語言中實現的正則大部分是擴展正則，和我這裡想講的有點不一樣，例如形如,也就是01，0011，000111,00001111...形如這樣的字元串是不能被傳統的正則表達式匹配的，下面講pumping lemma的時候會具體證明，但能識別它的語言能被上下文無關文法描述，也就是PDA(下推自動機，DFA的基礎上加一個長度為無線的棧)接受

而這樣傳統正則無法搞定的東西卻能被擴展正則的平衡組搞定，可見，擴展正則的能力是大於傳統正則的

1.正則表達式

首先一個問題正則表達式是個啥，相信大家編譯原理的書上都有，這裡不嚴謹的介紹下，核心就是三種運算：並，連接還有kleen閉包，正則表達式的輸出是一個語言(langurage)，也就是一坨符合這個規則的字元串的集合

並和連接很好理解，假設A是一個正則表達式，B是一個正則表達式，那麼A並B就是滿足正則A的字元串或者滿足正則B的字元串，記作A|B

A連接B就是匹配完正則A的字元串後繼續匹配正則B的字元串，記作AB

正則A的kleen閉包說白了就是重複，可以重複0次或者無數次記錯A*

基本的正則表達式核心就只有這三個運算，定義完運算之後在加上括弧，正則的定義是個遞歸定義，這裡不再贅述

我們來舉個例子，假設字符集∑ = {0, 1}，那麼根據上面的記號

(0|1)* 匹配空串或者任意長度的0,1字元串

((110)*)0 匹配0或者所有形如110110110...1100，也就是110重複很多次，最後以0結尾的字元串

2.DFA（Deterministic finite automata，有限狀態自動機）

接著是DFA，一個嚴謹的DFA定義是一個五元組，但我實在不想讓我寫的總結成為教科書一樣催人入睡的文章。所以直接直觀的感受一下dfa是啥。

這就是一個DFA,它首先是一個有向圖，其中每條邊都有一個權值，是字符集∑的元素，上圖中∑ = {0 ， 1},一個DFA有且只有一個起始位置的點，在上圖用一個箭頭代表，就是最左邊的q點，可以有很多個結束位置，在圖中就是兩個圈表示，也就是q001點。

DFA接受一個字元串作為輸入，如果最後走到了結束位置，那麼就說這個dfa接受該字元串，否則不接受。

我們來看DFA具體是怎麼處理的，假設上面一個DFA,我們給它101001作為輸入，想知道該DFA是否接受這個字元串，在一開始，手指指在起始位置點q上，第一個字元是1,我們看到第一個點1的那條邊是個自環，所以留在原地不動，第二個字元是0,看到邊指向q0,我們把手指指到q0去，第三個字元是1,我們看到是一條回到q的邊，無奈我們只能把手指回到q,然後的001讓我們的手指經過了q0 q00 q001，我們發現最後停在了q001的位置，然而q001是結束狀態，因此我們說上面這個dfa接受字元串101001

仔細研究後就可以發現，這就是匹配一個01字元串是否有001這個子串的過程，慢著，這個過程為啥這麼熟悉？沒錯，我們熟知的KMP演算法，其本質上就是構造了一個dfa，KMP演算法中失配邊的概念，其實就可以類比上面DFA中往回的箭頭（可以類比但不全是，因為KMP演算法中在不匹配的情況下就一直往回匹配，而DFA對一旦不匹配的每種情況（abcd...z）其返回的點可能是不一樣的，是一步到位，而不是KMP那樣一路從失配邊跳回去，所以不能說KMP的失配邊就是DFA往回的邊或自環）

那麼AC自動機那樣的多字元串匹配呢？本質上也是用多個字元串構造了一個DFA，然後字元串在上面跑，包括trie也一樣，許多熟知的字元串類演算法用DFA的角度想都能很好的理解

3.NFA

NFA和DFA比較像，但是我們可以看到，在每一個狀態，我們接受的下一個字元，通過NFA可以到達很多個下一個狀態，例如在上圖，假設我們在q1點，我們收到一個字元1，那麼我們可以到達q1點自己或者q2點，我們不能確定下一個狀態是啥

我們在此基礎上加上一個ε邊的概念，也就是邊的權可以是字符集∑ 的元素，也可以是ε

一條從q1指向q2的邊是ε的，意味著當我們在q1時，即使沒有收到任何字元，我們也可以通過ε邊跳到q2點，帶有ε邊的NFA稱為ε-NFA

下面不加證明的給出本文最最最最精彩的結論：ε-NFA NFA DFA以及正則表達式的能力是等價的！

也就是說 不存在一個語言，能夠設計一個DFA可以接受它，而相應的沒有ε-NFA NFA以及正則表達式可以接受

如果想寫一個DFA的正則的引擎，該怎麼做呢？程序化的步驟是：

a.先寫一個parser解析正則，運算結果存成AST

b.然後轉成ε-NFA

c.轉完以後去除ε邊變成NFA

d.最後再將NFA轉成DFA

a不是本文的重點，簡單說下，可以發現我們最基本的正則其實就是|這種雙目運算加上*這種單目運算，以及括弧()，所以最簡單的做法是recursive descent, 當然這種簡單的表達式也可以用polish notation做，只是由於有單目運算所以需要hack一下，大學作業寫過polish notation單目運算的應該都知道挺麻煩的

接下來是b，我們發現parser後我們需要面對的就是三種運算：並，鏈接，kleen閉包

以並為例，假設我們此時需要計算A|B,A和B是已經遞歸下去計算好了的正則，所以A和B是兩個ε-NFA，我們需要做的是將A B兩個ε-NFA用並運算合併成一個ε-NFA，輸出給上層函數

所以首先每個ε-NFA都有一個起始位置start,我們新開一個節點，將這個節點用ε邊連到兩個ε-NFA的start點，同理新開一個結束節點，將兩個ε-NFA的所有結束點用ε邊連到這個點上，所以這個樣子如同並聯電路一般，而新開的兩個點就是作為這一層的新的起始點和終止點，我們將這個新生成的ε-NFA作為返回值返回給上層

連接呢？更簡單了，假設正則表達式是AB，我們把A的所有結束位置都通過ε邊連到B的起始節點即可！A的起始點和B的結束點作為新生成ε-NFA的起始和結束

看起來最麻煩的Kleen閉包其實最不麻煩,不是重複嘛，簡單的想法就是直接把結束狀態的點連到頭，讓它配成環(peichenghuan)，不就可以重複跑了么。

做完上面的事我們就通過正則得到一個ε-NFA了，我們接下來要去了討厭的ε邊，顯然，ε邊不會對結果有影響，因此我們遍歷每一個點，如果這個點A有向外的ε邊，那麼我們順著這條ε邊一直找出去，直到找到一條不是ε邊的邊，這可能找到一坨點，我們跳過ε邊，將點A和這些點直接連邊（比如，點A和點B用ε邊相連，B向外有4條邊，權分別是『a』,"b","c","d"，那麼消ε邊的時候，A直接跳過B，直接向B連的四個點連出『a』,"b","c","d"的四條邊即可）

這樣連完以後ε邊就沒有什麼太大用處了，所以我們可以把所有ε邊去掉，如果某個點去完ε邊後成了孤立點（度數為0），那麼我們也可以把這個點給去了

消完ε邊後，整個狀態機清爽了很多，於是我們可以做步驟4了，把NFA變成DFA，可以預料到的是，這一步的操作一定是指數級的，因為本身從NFA變成DFA，點數量的變化也是指數級的

------------------------------------未完，應該下面還想講正則，ε-NFA, NFA和DFA的互相轉化,pumping lemma，感覺還有好長，盡量不坑--------------------------------------------------------

reference :

《計算理論導引》

Pumping lemma for regular languages

推薦閱讀：