寫在前面

從源代碼到可執(zhí)行文件要經(jīng)歷幾個過程：

1. 詞法分析
2. 語法分析
3. 語義分析
4. 中間代碼生成
5. 代碼優(yōu)化

詞法分析有點像中文分詞，是將輸入結(jié)構(gòu)化的第一步：從字符串序列變?yōu)?strong>詞法單元序列，它的輸出將作為語法分析的輸入。在詞法單元中主要涉及到的概念有：

1. DFA：有窮確定狀態(tài)機。
2. NFA：有窮不確定狀態(tài)機。

確定和不確定的區(qū)別在于：當(dāng)遇到字符的時候狀態(tài)的變化是不是確定的，下面是一個NFA的例子：

NFA

對于這樣一個狀態(tài)機可以構(gòu)造出一個轉(zhuǎn)換表如下：

對于DFA來說每個狀態(tài)上的轉(zhuǎn)換都是確定的，那么其對應(yīng)的代碼的樣子如下：

s = s0;
c = nextChar();
while(c != eof){
    s = move(s, c); // 根據(jù)狀態(tài)轉(zhuǎn)換表
    c = nextChar();
}
return s in F ? "yes" : "no";

從代碼上來看DFA要比NFA簡單不少，那么下面接著來看。

從NFA到DFA

既然DFA看起來要比NFA用起來簡單很多，那么如果能將NFA轉(zhuǎn)換為DFA的話問題不就變簡單了？

子集構(gòu)造法是一種比較簡單、直觀的轉(zhuǎn)化方法，既然在NFA中狀態(tài)1根據(jù)字符a可以到狀態(tài)1，也可以到狀態(tài)2，那么如果將狀態(tài){1,2}合并看做一個節(jié)點，那得到結(jié)果不就是DFA了~

從NFA到DFA

在實際操作的時候需要用到三個集合：

1. ε-closure(s)：從NFA中狀態(tài)s開始只通過ε得到的狀態(tài)的集合。
2. ε-closure(T)：從T中的某個狀態(tài)s開始只通過ε得到的狀態(tài)的集合。
3. move(T, a)：從T中某個狀態(tài)s開始通過a得到的狀態(tài)集合。

在NFA上構(gòu)造完成三個集合之后，那么可以通過如下流程進行轉(zhuǎn)換：

// 在最開始Dstatus中只有ε-closure(s0)一種狀態(tài)，并未未加標(biāo)記
while(在Dstatus中有一個未標(biāo)記的狀態(tài)T){
    給T加上標(biāo)記；
    for(每個輸入符號a) {
        U = ε-closure(move(T, a));
        if(U 不在Dstates中)
            將U加入到Dstatus中// 不加標(biāo)記
        Dtran[T, a] = U;// 轉(zhuǎn)換表
    }
}

在實際上DFA和NFA的狀態(tài)數(shù)都是差不多的，但是理論上轉(zhuǎn)換后的DFA可能是原本的NFA狀態(tài)數(shù)的指數(shù)級，(a|b)*a(a|b)^(n-1)就是這樣一個例子：

DFA狀態(tài)數(shù)為NFA的指數(shù)倍

從正則到NFA

很多的詞法分析器都是用正則來描述規(guī)則，一般正則基本上能搞定所有的需求，而且足夠簡單。但是在識別輸入的字符序列的時候需要用到自動機，那么就需要從正則到NFA or DFA的轉(zhuǎn)換。對于正則的每種行為都有對應(yīng)的NFA中的轉(zhuǎn)換可以代替：

1. r=s|t：通過ε實現(xiàn)。
2. r=st：將s的接受狀態(tài)和t的初始狀態(tài)進行合并。
3. r=s*：將s的接受狀態(tài)和初始狀態(tài)相連，從而達到循環(huán)的效果。

達到的效果如下：

從正則到NFA

對于(a|b)*a這樣的正則按照上面的方法得到的NFA如下：

(a|b)*a對應(yīng)的NFA

有了這種方法，根據(jù)正則的AST就能很容易遞歸生成NFA。

從正則到DFA

DFA是比較簡單的，那么在解析正則的一個思路是正則->NFA->DFA，但是這樣做比較麻煩，我們肯定是希望能夠直接轉(zhuǎn)換。這里需要四個集合：

1. nullable(n)：節(jié)點n的子表達式中包含空字符串。
2. firstpos(n)：節(jié)點n為根的子表達式中某個串的第一個符號的位置的集合。
3. lastpos(n)：節(jié)點n為根的子表達式中某個串的末一個符號的位置的集合。
4. followpos(p)：如果L((r)#)中的某個串x=a1..an，使得我們在解釋為什么x屬于L((r)#)時，可以將x中的某個ai和AST中的位置p匹配，且位置ai+1和位置q匹配，那么q在該集合中。

這樣看起來比較難理解，來看一個例子：

集合例子

那么對于框中的根節(jié)點來說：

1. nullable(n)：false。
2. firstpos(n)：{1,2,3}。
3. lastpos(n)：{3}。
4. followpos(1)：{1,2,3}。

這些集合可以遞歸得到，比如較為麻煩的followpos的計算方法如下：

1. 如果n是一個cat節(jié)點，其左右子節(jié)點分別為c1、c2，那么對于lastpos(c1)中的每個位置i，firstpos(c2)中的所有位置都在followpos(i)中。
2. 如果n是一個star節(jié)點，并且i是lastpos(n)中的一個位置，那么firstpos(n)中所有的位置都在followpos(i)中。

其中關(guān)鍵的followpos其實就是NFA中的狀態(tài)轉(zhuǎn)換，那么下面的正則到DFA的過程就很容易理解了：

// 構(gòu)造D的狀態(tài)集Dstates和D的轉(zhuǎn)換函數(shù)Dtran。
初始化Dstates，使之只包含未標(biāo)記狀態(tài)firstpos(n0)，其中n0是(r)#的抽象語法樹的根節(jié)點
while(Dstates中存在未標(biāo)記狀態(tài)S){
    標(biāo)記S；
    for(每個輸入符號a){
        令U為S中和a對應(yīng)的所有位置p的followpos(p)的并集；
        if(U不在Dstates中)
            將U作為未標(biāo)記的狀態(tài)加入到Dstates中；
        Dtran[S,a] = U;
    }
}

在實際中DFA確實有優(yōu)勢，但是還有進一步優(yōu)化的空間，接著往下看。

DFA狀態(tài)最小化

在DFA中有一些狀態(tài)是的等價的，等價的意思就是沒有區(qū)別的，那有區(qū)別的意義在于：

從狀態(tài)s、t出發(fā)，沿著標(biāo)號為x的路徑到達兩個狀態(tài)，分別為接受狀態(tài)和非接受狀態(tài)。

下面是一個簡單的最小化的例子：

狀態(tài)最小化

那么最小化呢？上面的這個定義太抽象了，如果直接找路徑的話估計會累死的。想到每條路徑都是由字符一點一點拼接成的，那么對應(yīng)的方法也就比較容易能想到了：

1. 將所有狀態(tài)根據(jù)接受、非接受分成兩組。
2. 遍歷分組、字符，如果同一組內(nèi)的狀態(tài)根據(jù)該字符到達了不同的組，那么繼續(xù)將當(dāng)前的組進行分割。
3. 重復(fù)執(zhí)行2，直到?jīng)]有變化。
4. 每個組中選擇一個代表狀態(tài)，重新構(gòu)造DFA，最小化完成。

最后給出一個結(jié)論：任何一個正則表達式都有唯一的狀態(tài)數(shù)最少的DFA。