????首先說一下正則表達式的本質(zhì)，顧名思義，正則表達式是一種表達式，同算術(shù)表達式一樣是有基本單元（因子）加上運算符構(gòu)成的一種運算系統(tǒng)。

????算數(shù)表達式的因子是 數(shù)，而正則表達式的因子是 字符。算術(shù)表達式的基本四則運算是 +，-，*，/；而正則表達式的基本運算是 （連接），|（并），*（閉包）。由于連接省略了運算符，不太方便表示，所以以下用?○ 表示連接。

????算術(shù)表達式的結(jié)果是一個數(shù)，而正則表達式的結(jié)果是一個字符串。

抽象語法樹

????我們用抽象語法樹來描述一個正則表達式，以便能夠直觀地看到該正則表達式的結(jié)構(gòu)。關(guān)于抽象語法樹的知識，需要的話可以另說。

????簡單的說，抽象語法樹就是用 因子 作為葉子節(jié)點，而用運算符作為內(nèi)部節(jié)點來連接葉子節(jié)點的一種樹。

????比如，(a|b)*abb的抽象語法樹為：

????上圖中的數(shù)字是給字符的編號。該圖應(yīng)該不難看懂，看不懂的可以提出來，篇幅所限，就不多說了。

算法的推導(dǎo)

????要構(gòu)造DFA，則我們必須知道：

（1）開始時可以出現(xiàn)哪些符號，由于符號是有重復(fù)的，如上圖中的a，而且上圖中的a是不等價的，所以只能給它們賦予不同的編號來加以區(qū)分，我們也使用編號的集和來表示DFA的一個狀態(tài)；

（2）接下來可以出現(xiàn)哪些編號；

（3）接下來的接下來可以出現(xiàn)哪些編號；

（4）接下來的接下來的接下來可以出現(xiàn)哪些編號......

（5）最后可以出現(xiàn)哪些編號。

OK，知道了這些，實際上就知道了DFA的所有狀態(tài)，DFA的狀態(tài)對應(yīng)一個編號集和，以下統(tǒng)稱?狀態(tài)。

計算過程

????開始狀態(tài)就是抽象語法的根節(jié)點的開始編號集和，結(jié)束狀態(tài)就是根節(jié)點的結(jié)束編號集和，而中間狀態(tài)則是緊跟著某個狀態(tài)的編號集和。

????這些信息只需要一次對抽象語法樹的遍歷就可以求出來了。

????以下稱開始編號集為firstpos集，結(jié)束編號集為lastpos集，用nullable來表示一個節(jié)點是否可空，可空的意思就是會產(chǎn)生空串，比如正則表達式? a? 就是可空的，它可以什么都不匹配。還有一個集和是followpos集，它是編號的后跟編號的集和，比如 正則表達式 ab，由于b緊跟在a后面，所以b的編號在 followpos(a) 中。

????以下是計算過程。

對于任意節(jié)點 n：

（1）如果它是 編號為 i 的葉子節(jié)點，那么

nullable(n) = false,?

firstpos(n) = {i},

lastpos(n) = {i} ；

（2）如果它是一個 并節(jié)點，也就是 n = n1 | n2，那么

nullable(n) = nullable(n1) || nullable(n2)，

firstpos(n) = firstpos(n1) ∪ firstpos(n2)，

lastpos(n) = lastpos(n1) ∪ lastpos(n2)；

（3）如果它是一個 連接節(jié)點，也就是 n = n1 n2，那么

nullable(n) = nullable(n1) && nullable(n2)，

firstpos(n) = nullable(n1) ? firstpos(n1) ∪ firstpos(n2) : firstpos(n1)，

lastpos(n) = nullable(n2) ??lastpos(n1) ∪ lastpos(n2) : lastpos(n2)；

（3）如果它是一個?閉包節(jié)點，也就是 n = n1 *，那么

nullable(n) = true，

firstpos(n) =?firstpos(n1)，

lastpos(n) =?lastpos(n1)。

????最后是followpos的計算，這個很簡單，只有兩種情況會使一個編號在另一個編號后面：

（1）如果n是一個連接節(jié)點，也就是 n = n1 n2，則

所有 p ∈ lastpos(n1)，有 followpos(p) = followpos(p) ∪ firstpos(n2)；

（2）如果n是一個閉包節(jié)點，也就是 n = n1 *，則

所有 p ∈ lastpos(n1)，有 followpos(p) = followpos(p) ∪ firstpos(n1)。

????

????值得指出的是，我們需要的只有 抽象語法樹的根節(jié)點的 firstpos集 以及 所有編號的follopos集，其他的都是可以舍去的臨時信息。

????舉例分析，上圖中，只有 * 節(jié)點是可空的；其他信息如下圖，節(jié)點左邊紅色的信息是它的firstpos集，右邊藍色的信息是它的lastpos集：

????它們的followpos集是：

編號????????????????????????????followpos

1?????????????????????????????????{1, 2, 3}

2?????????????????????????????????{1, 2, 3}

3????????????????????????????????{4}

4????????????????????????????????{5}

5????????????????????????????????Φ

構(gòu)造DFA

????我們使用一個狀態(tài)集Dstates來保存所有的狀態(tài)（也就是編號集），使用一個表Dtran來表示轉(zhuǎn)換，算法如下：

（1）初始化Dstates，使之只包含未標記的狀態(tài) firstpos(n0)，n0是抽象語法的根節(jié)點，未標記就是未處理過該狀態(tài)的轉(zhuǎn)換；

（2）

while(Dstates中存在未標記的狀態(tài)S)

{

????標記S;

????for(每個輸入符號a)

????{

????????求出 編號集U = S中所有與a對應(yīng)的編號的followpos集的并集；

????????if( U 不在 Dstates中)

????????????將U作為未標記的狀態(tài)加入到Dstates中；

??????? Dtran[S, a] = U;

????}

}

舉例

????上述例子中的開始編號集為 {1，2，3}，對應(yīng)的DFA的開始狀態(tài) 0 ，首先將其加入到Dstates中。

????接下來，由于它未標記，所以取出它，并分析它的轉(zhuǎn)換，S = {1，2，3}；

????標記S；

????對于符號a，S中有編號1，3和a對應(yīng)，并且followpos(1) = {1, 2, 3}, followpos(3) = {4}，則

S在a上的轉(zhuǎn)換 U = followpos(1) ∪ followpos(3) = {1, 2, 3, 4}；

????U不在Dstates中，故將U加入Dstates，因此U就是1號狀態(tài)了。

????設(shè)置 Dstran[S, a] = U，也就是 Dstran[0, a] = 1。

????對于符號b，S中有編號2與其對應(yīng)，并且followpos(2) = {1, ,2 3}，則S在b上的轉(zhuǎn)換 U = {1, 2, 3}，U已經(jīng)在Dstates中了，所以不需要加入了，只需要設(shè)置 Dtran[S, b] = U，也就是

Dtran[0, b] = 0 就行了。

????依次類推可以得出DFA轉(zhuǎn)換表為：

狀態(tài)????????a????????b????????其他

0???????????? 1????????0

1???????????? 1????????2

2?????????????1????????3

3???????????? 1????????0???????? 接受

其他說明

????（1）抽象語法樹是給人看的，實際上并不需要構(gòu)造出來就可以求出所需的各種集和；

????（2）可以給正則表達式連接上一個結(jié)束符來表示接受，比如說連接上一個 #，則所有在#上有轉(zhuǎn)換的狀態(tài)都是接受狀態(tài)；

????（3）參考 《編譯原理》第二版（龍書）109頁到114頁；

????（3）還請支持一下，非常感謝！