在上一篇文章中，已經(jīng)得到了與正則表達(dá)式等價的 NFA，本篇文章會說明如何從 NFA 轉(zhuǎn)換為 DFA，以及對 DFA 和字符類進(jìn)行化簡。
 一、DFA 的表示

DFA 的表示與 NFA 比較類似，不過要簡單的多，只需要一個添加新狀態(tài)的方法即可。Dfa 類的代碼如下所示：

符號索引表示當(dāng)前的接受狀態(tài)對應(yīng)的是哪個正則表達(dá)式。不過 DFA 的一個狀態(tài)可能對應(yīng)于 NFA 的多個狀態(tài)（詳見下面的子集構(gòu)造法），所以 DFA 狀態(tài)的符號索引是一個數(shù)組。對于普通狀態(tài)，符號索引是空數(shù)組。

狀態(tài)轉(zhuǎn)移表示如何從當(dāng)前狀態(tài)轉(zhuǎn)移到下一狀態(tài)，由于在構(gòu)造 NFA 時已經(jīng)劃分好了字符類，所以在 DFA 中直接使用數(shù)組記錄下不同字符類對應(yīng)的轉(zhuǎn)移（DFA 中是不存在 ϵ 轉(zhuǎn)移的，而且對每個字符類有且只有一條轉(zhuǎn)移）。

在 NFA 的狀態(tài)定義中，還有一個狀態(tài)類型屬性，但是在 DFA 狀態(tài)中卻沒有這個屬性，是因?yàn)?Trailing 類型的狀態(tài)會在 DFA 匹配字符串的時候處理（會在下篇文章中說明），TrailingHead 類型的狀態(tài)會在構(gòu)造 DFA 的時候與 Normal 類型的狀態(tài)合并（詳見 2.4 節(jié)）。

下面是 DfaState 類的定義：

將 NFA 轉(zhuǎn)換為 DFA，采用的是子集構(gòu)造（subset construction）算法。該算法的過程與《C# 詞法分析器（三）正則表達(dá)式》的 3.1 節(jié)中提到的 NFA 匹配過程比較相似。在 NFA 的匹配過程中，使用的都是 NFA 的一個狀態(tài)集合，那么子集構(gòu)造法就是用 DFA 的一個狀態(tài)來對應(yīng) NFA 的一個狀態(tài)集合，即 DFA 讀入輸入字符串 a1a2⋯an 之后到達(dá)的狀態(tài)，就對應(yīng)于 NFA 讀入同樣的字符串 a1a2⋯an 之后到達(dá)的狀態(tài)的集合。

子集構(gòu)造算法需要用到的操作有：

我們需要找到的是當(dāng)一個 NFA N 讀入了某個輸入串后，可能位于的所有狀態(tài)集合。

首先，在讀入第一個字符之前，N 可以位于 ϵ-closure(s0) 中的任何狀態(tài)，其中 s0 是 N 的開始狀態(tài)。那么，此時 ϵ-closure(s0) 就表示 DFA 的開始狀態(tài)。

假設(shè) N 在讀入輸入串 x 之后可以位于集合 T 中的狀態(tài)上，下一個輸入字符是 a，那么 N 可以立即移動到 move(T,a) 中的任何狀態(tài)，并且還可以通過 ϵ 轉(zhuǎn)移來移動到 ϵ-closure(move(T,a)) 中的任何狀態(tài)上。這樣的每個不同的 ϵ-closure(move(T,a)) 就表示了一個 DFA 的狀態(tài)。如果這個說明難以理解，可以參考后面給出的示例。

據(jù)此，可以得到以下的算法（算法中的 T[a]=U 表示在狀態(tài) T 中的字符類 a 上存在到狀態(tài) U 的轉(zhuǎn)移）：

輸入：一個 NFA N
輸出：與 NFA 等價的 DFA D
一開始，ϵ-closure(s0) 是 D 中的唯一狀態(tài)，且未被標(biāo)記
while (在 D 中存在未被標(biāo)記的狀態(tài) T) {
 為 T 加上標(biāo)記
 foreach (每個字符類 a) {
  U=ϵ-closure(move(T,a))
  if (U 不在 D 中) {
   將 U 加入 D 中，且未被標(biāo)記
  }
  T[a]=U
 }
}

如果某個 NFA 是終結(jié)狀態(tài)，那么所有包含它的 DFA 狀態(tài)也是終結(jié)狀態(tài)，而且 DFA 狀態(tài)的符號索引就包含 NFA 狀態(tài)對應(yīng)的符號索引。一個 DFA 狀態(tài)可能對應(yīng)于多個 NFA 狀態(tài)，所以上面定義 DfaState 時，符號索引是一個數(shù)組。

計算 ϵ-closure(T) 的過程就是從一個狀態(tài)集合開始的簡單圖搜索過程，使用 DFS 即可實(shí)現(xiàn)，具體的算法如下（ϵ-closure(s) 的算法也同理，等價于 /epsilon /text{-} closure(/{s/})）：

輸入：NFA 的狀態(tài)集合 T
輸出：/epsilon /text{-} closure(T)
將 T 的所有狀態(tài)壓入堆棧
/epsilon /text{-} closure(T) = T
while (堆棧非空) {
 彈出棧頂元素 t
 foreach (u : t 可以通過 /epsilon 轉(zhuǎn)移到達(dá) u) {
  if (u /notin /epsilon /text{-} closure(T)) {
   /epsilon /text{-} closure(T) = /epsilon /text{-} closure(T) /cup /left/{ u /right/}
   將 u 壓入堆棧
  }
 }
}

計算 move(T,a) 的算法更加簡單，只有一個循環(huán)：

輸入：NFA 的狀態(tài)集合 T
輸出：move(T,a)
move(T,a) = /emptyset
foreach (u /in T) {
 if (u 存在字符類 a 上的轉(zhuǎn)移，目標(biāo)為 t) {
  move(T,a) = move(T,a) /cup /left/{ t /right/}
 }
}
2.2 子集構(gòu)造法的示例
這里以上一節(jié)中從正則表達(dá)式 (a|b)*baa 構(gòu)造得到的 NFA 作為示例，將它轉(zhuǎn)化為 DFA。這里的輸入字母表 /Sigma = /{a, b/}。
圖 1 正則表達(dá)式 (a|b)*baa 的 NFA
圖 2 構(gòu)造 DFA 的示例
 
圖 3 最終得到的 DFA
2.3 多個首狀態(tài)的子集構(gòu)造法
上一節(jié)中構(gòu)造得到的 NFA 是具有多個開始狀態(tài)的（為了支持上下文和行首限定符），不過對子集構(gòu)造法并不會產(chǎn)生影響，因?yàn)樽蛹瘶?gòu)造法是從開始狀態(tài)開始，沿著 NFA 的轉(zhuǎn)移不斷構(gòu)造相應(yīng)的 DFA 狀態(tài)，只要對多個開始狀態(tài)分別調(diào)用自己構(gòu)造法就可以正確構(gòu)造出多個 DFA，而且不必?fù)?dān)心 DFA 之間的相互影響。為了方便起見，這多個 DFA 仍然保存在一個 DFA 中，只不過還是使用起始狀態(tài)來進(jìn)行區(qū)分。

2.4 DFA 狀態(tài)的符號索引
一個 DFA 狀態(tài)對應(yīng) NFA 的一個狀態(tài)集合，那么直接將這多個 NFA 狀態(tài)的符號索引全都拿來就可以了。不過前面說到， TrailingHead 類型的 NFA 狀態(tài)會在構(gòu)造 DFA 的時候與 Normal 類型的 NFA 狀態(tài)合并，這個合并指的就是符號索引的合并。
這個合并的方法也很簡單，Normal 類型的狀態(tài)直接將符號索引拿來，TrailingHead 類型的狀態(tài)，則將 int.MaxValue - SymbolIndex 的值作為 DFA 狀態(tài)的符號索引，這樣兩種類型的狀態(tài)就可以區(qū)分出來（由于定義的符號數(shù)不會太多，所以不必?fù)?dān)心出現(xiàn)重復(fù)或者負(fù)值）。
最后，再對 DFA 狀態(tài)的符號索引從小到大進(jìn)行排序。這樣就會使 Normal 類型狀態(tài)的符號索引總是排在 TrailingHead 類型狀態(tài)的符號索引的前面，在后面進(jìn)行詞法分析時能夠更容易處理，效率也會有略微的提升。

2.5 子集構(gòu)造法的實(shí)現(xiàn)
子集構(gòu)造法的 C# 實(shí)現(xiàn)與上面給出的偽代碼基本一致，不過這里有個問題需要解決，就是如何高效的從 NFA 的狀態(tài)集合得到相應(yīng)的 DFA 狀態(tài)。由于 NFA 狀態(tài)集合是采用 HashSet<NfaState> 來保存的，所以我直接利用 Dictionary<HashSet<NfaState>, DfaState> 來解決這個問題，這里需要采用自定義的弱哈希函數(shù)，使得集合對應(yīng)的哈希值只與集合中的元素相關(guān)，而與元素順序無關(guān)。
下面就是定義在 Nfa 類中的方法：
復(fù)制代碼 代碼如下:

View Code 
 /// <summary>
 /// 根據(jù)當(dāng)前的 NFA 構(gòu)造 DFA，采用子集構(gòu)造法。
 /// </summary>
 /// <param name="headCnt">頭節(jié)點(diǎn)的個數(shù)。</param>
 internal Dfa BuildDfa(int headCnt) {
     Dfa dfa = new Dfa(charClass);
     // DFA 和 NFA 的狀態(tài)映射表，DFA 的一個狀態(tài)對應(yīng) NFA 的一個狀態(tài)集合。
     Dictionary<DfaState, HashSet<NfaState>> stateMap =
         new Dictionary<DfaState, HashSet<NfaState>>();
     // 由 NFA 狀態(tài)集合到對應(yīng)的 DFA 狀態(tài)的映射表（與上表互逆）。
     Dictionary<HashSet<NfaState>, DfaState> dfaStateMap =
         new Dictionary<HashSet<NfaState>, DfaState>(SetEqualityComparer<NfaState>.Default);
     Stack<DfaState> stack = new Stack<DfaState>();
     // 添加頭節(jié)點(diǎn)。
     for (int i = 0; i < headCnt; i++) {
         DfaState head = dfa.NewState();
         head.SymbolIndex = new int[0];
         HashSet<NfaState> headStates = EpsilonClosure(Enumerable.Repeat(this[i], 1));
         stateMap.Add(head, headStates);
         dfaStateMap.Add(headStates, head);
         stack.Push(head);
     }
     int charClassCnt = charClass.Count;
     while (stack.Count > 0) {
         DfaState state = stack.Pop();
         HashSet<NfaState> stateSet = stateMap[state];
         // 遍歷字符類。
         for (int i = 0; i < charClassCnt; i++) {
             // 對于 NFA 中的每個轉(zhuǎn)移，尋找 Move 集合。
             HashSet<NfaState> set = Move(stateSet, i);
             if (set.Count > 0) {
                 set = EpsilonClosure(set);
                 DfaState newState;
                 if (!dfaStateMap.TryGetValue(set, out newState)) {
                     // 添加新狀態(tài).
                     newState = dfa.NewState();
                     stateMap.Add(newState, set);
                     dfaStateMap.Add(set, newState);
                     stack.Push(newState);
                     // 合并符號索引。
                     newState.SymbolIndex = set.Where(s => s.SymbolIndex != Symbol.None)
                         .Select(s => {
                             if (s.StateType == NfaStateType.TrailingHead) {
                                 return int.MaxValue - s.SymbolIndex;
                             } else {
                                 return s.SymbolIndex;
                             }
                         }).OrderBy(idx => idx).ToArray();
                 }
                 // 添加 DFA 的轉(zhuǎn)移。
                 state[i] = newState;
             }
         }
     }
     return dfa;
 }
 /// <summary>
 /// 返回指定 NFA 狀態(tài)集合的 ϵ 閉包。 
 /// </summary>
 /// <param name="states">要獲取 ϵ 閉包的 NFA 狀態(tài)集合。</param>
 /// <returns>得到的 ϵ 閉包。</returns>
 private static HashSet<NfaState> EpsilonClosure(IEnumerable<NfaState> states) {
     HashSet<NfaState> set = new HashSet<NfaState>();
     Stack<NfaState> stack = new Stack<NfaState>(states);
     while (stack.Count > 0) {
         NfaState state = stack.Pop();
         set.Add(state);
         // 這里只需遍歷 ϵ 轉(zhuǎn)移。
         int cnt = state.EpsilonTransitions.Count;
         for (int i = 0; i < cnt; i++) {
             NfaState target = state.EpsilonTransitions[i];
             if (set.Add(target)) {
                 stack.Push(target);
             }
         }
     }
     return set;
 }
 /// <summary>
 /// 返回指定 NFA 狀態(tài)集合的字符類轉(zhuǎn)移集合。 
 /// </summary>
 /// <param name="states">要獲取字符類轉(zhuǎn)移集合的 NFA 狀態(tài)集合。</param>
 /// <param name="charClass">轉(zhuǎn)移使用的字符類。</param>
 /// <returns>得到的字符類轉(zhuǎn)移集合。</returns>
 private static HashSet<NfaState> Move(IEnumerable<NfaState> states, int charClass) {
     HashSet<NfaState> set = new HashSet<NfaState>();
     foreach (NfaState state in states) {
         if (state.CharClassTransition != null && state.CharClassTransition.Contains(charClass)) {
             set.Add(state.CharClassTarget);
         }
     }
     return set;
 }

在這個實(shí)現(xiàn)中，將 DFA 的起始狀態(tài)的符號索引設(shè)為了空數(shù)組，這樣會使得空字符串 $/epsilon$ 不會被匹配（其它匹配不會受到影響），即 DFA 至少會匹配一個字符。這樣的做法在詞法分析中是有意義的，因?yàn)樵~素不能是空字符串。

2.6 DFA 中的死狀態(tài) 
嚴(yán)格說來，由以上的算法得到的 DFA 可能并不是一個 DFA，因?yàn)?DFA 要求每個狀態(tài)在每個字符類上有且只有一個轉(zhuǎn)移。而上面的算法生成的 DFA，在某些字符類上可能并沒有的轉(zhuǎn)移，因?yàn)樵谒惴ㄖ校绻@個轉(zhuǎn)移對應(yīng)的 NFA 狀態(tài)集合是空集，則無視這個轉(zhuǎn)移。如果是嚴(yán)格的 DFA 的話，這時應(yīng)該添加一個到死狀態(tài) $/emptyset$ 的轉(zhuǎn)移(死狀態(tài)在所有字符類上的轉(zhuǎn)移都到達(dá)其自身)。
但是在詞法分析中，需要知道什么時候已經(jīng)不存在被這個 DFA 接受的可能性了，這樣才能夠知道是否已經(jīng)匹配到了正確的詞素。因此，在詞法分析中，到達(dá)死狀態(tài)的轉(zhuǎn)移將被消除，如果沒有找到某個輸入符號上的轉(zhuǎn)換，就認(rèn)為這時候已經(jīng)匹配到了正確的詞素（最后一個終結(jié)狀態(tài)對應(yīng)的詞素）。
三、DFA 的化簡3.1 DFA 最小化 
上面雖然構(gòu)造出了一個可用的 DFA，但它可能并不是最優(yōu)的，例如下面的兩個等價的 DFA，識別的都是正則表達(dá)式 (a|b)*baa，但具有不同的狀態(tài)數(shù)。
圖 4 兩個等價的 DFA
顯然，狀態(tài)數(shù)越少的 DFA，匹配時的效率越高，所以需要使用一些算法，來將 DFA 的狀態(tài)數(shù)最小化，即 DFA 的化簡。
化簡 DFA 的思想是尋找等價狀態(tài)――它們都（不）是接受狀態(tài)，而且對于任意的輸入，總是轉(zhuǎn)移到等價的狀態(tài)。找到所有等價的狀態(tài)后，就可以將它們合并為一個狀態(tài)，實(shí)現(xiàn) DFA 狀態(tài)數(shù)的最小化。
尋找等價狀態(tài)一般有兩種方法：分割法和合并法。
分割法是先將所有接受狀態(tài)和所有非接受狀態(tài)看作兩個等價狀態(tài)集合，然后從里面分割出不等價的狀態(tài)子集，直到剩下的所有等價狀態(tài)集合都不可再分。合并法是先將所有狀態(tài)看作不等價的，然后從里面找到兩個（或多個）等價的狀態(tài)，并合并為一個狀態(tài)。 
兩種方法都可以實(shí)現(xiàn) DFA 的化簡，但是合并法比較復(fù)雜，因此這里我使用分割法來對 DFA 進(jìn)行化簡。
DFA 最小化的算法如下：
輸入：一個 DFA $D$
輸出：與 $D$ 等價的最簡 DFA $D'$
構(gòu)造 $D$ 的初始劃分 $/Pi$，初始劃分包含兩個組：接受狀態(tài)組和非接受狀態(tài)組
while (true) {
 foreach (組 $G /in /Pi$) {
  將 $G$ 劃分為更小的組，使得兩個狀態(tài) $s$ 和 $t$ 在同一組中當(dāng)且僅當(dāng)對于所有輸入符號，$s$ 和 $t$ 的轉(zhuǎn)移都到達(dá) $/Pi$ 中的同一組
 }
 將新劃分的組保存到 $/Pi _{new}$ 中
 if ($/Pi_{new} /ne /Pi$) {
  $/Pi = /Pi_{new}$
 } else {
  $/Pi _{final} = /Pi$
  break;
 }
}
在 $/Pi _{final}$ 中的每個組中都選取一個狀態(tài)作為該組的代表，這些代表就構(gòu)成了 $D'$ 的狀態(tài)。
$D'$ 的開始狀態(tài)是包含了 $D$ 的開始狀態(tài)的組的代表。 
$D'$ 的接受狀態(tài)是包含了 $D$ 的接受狀態(tài)的組的代表。
令 $s$ 是 $/Pi_{final}$ 中某個組 $G$ 中的狀態(tài)（不是代表），那么將 $D'$ 中到 $s$ 的轉(zhuǎn)移，都更改為到 $G$ 的代表的轉(zhuǎn)移。
因?yàn)榻邮軤顟B(tài)和非接受狀態(tài)在最開始就被劃分開了，所以不會存在某個組即包含接受狀態(tài)，又包含非接受狀態(tài)。
在實(shí)際的實(shí)現(xiàn)中，需要注意的是由于一個 DFA 狀態(tài)可能對應(yīng)多個不同的終結(jié)符，因此在劃分初始狀態(tài)時，對應(yīng)的終結(jié)符不同的終結(jié)狀態(tài)也要被劃分到不同的組中。

3.2 DFA 最小化的示例 
下面以圖 4(a) 為例，給出 DFA 最小化的示例。
初始的劃分包括兩個組 /{A, B, C, D/} 和 /{E/}，分別是非接受狀態(tài)組和接受狀態(tài)組。
第一次分割，在 /{A, B, C, D/} 組中，對于字符 a，狀態(tài) A, B, C 都轉(zhuǎn)移到組內(nèi)的狀態(tài)，而狀態(tài) D 轉(zhuǎn)移到組 /{E/} 中，所以狀態(tài) D 需要被劃分出來。對于字符 b，所有狀態(tài)都轉(zhuǎn)移到該組內(nèi)的狀態(tài)，不能區(qū)分；/{E/} 組中，只含有一個狀態(tài)，無需進(jìn)一步劃分。這一輪 /Pi _{new} = /left/{ /{A, B, C/}, /{D/}, /{E/} /right/}。
第二次分割，在 /{A, B, C/} 組中，對于字符 a，狀態(tài) A, B 都轉(zhuǎn)移到組內(nèi)的狀態(tài)，而狀態(tài) C 轉(zhuǎn)移到組 /{D/} 中，對于字符 b 則不能區(qū)分；組 /{D/} 和組 /{E/} 同樣不做劃分。這一輪 /Pi_{new} = /left/{/{A, B/}, /{C/}, /{D/}, /{E/} /right/}。
第三次分割，唯一可能被分割的組 /{A, B/}，對于字符 a 和字符 b，都會轉(zhuǎn)移到相同的組內(nèi)，所以不會被分割。因此就得到 /Pi_{final} = /left/{ /{A, B/}, /{C/}, /{D/}, /{E/} /right/}。
最后，構(gòu)造出最小化的 DFA，它有四個狀態(tài)，對應(yīng)于 /Pi_{final} 的四個分組。分別挑選 A, C, D, E 作為每個分組的代表，其中，A 是開始狀態(tài)，E 是接受狀態(tài)。將所有狀態(tài)到 B 的轉(zhuǎn)移都修改為到 A 的轉(zhuǎn)移，最后得到的 DFA 轉(zhuǎn)換表為：
DFA 狀態(tài)
a 上的轉(zhuǎn)移
b 上的轉(zhuǎn)移
A
A
C
C
D
C
D
E
C
E
A
C
最后再將狀態(tài)重新排序，得到的就是如圖 4(b) 所示的 DFA 了。

3.3 字符類最小化 
在 DFA 最小化之后，還要將字符類也最小化，因?yàn)?DFA 的最小化過程會合并等價狀態(tài)，這時可能會使得某些字符類變得等價，如圖 5 所示。
圖 5 等價的字符類
等價字符類的尋找比等價狀態(tài)更簡單些，先將化簡后的 DFA 用表格的形式寫出來，以圖 5 中的 DFA 為例：
DFA 狀態(tài)
a 上的轉(zhuǎn)移
b 上的轉(zhuǎn)移
c 上的轉(zhuǎn)移
A
B
B
/emptyset
B
B
B
C
C
/emptyset
/emptyset
/emptyset
表格中的第一列是 DFA 的狀態(tài)，后面的三列分別代表不同字符類上的轉(zhuǎn)移。表格的第二行到第四行分別對應(yīng)著 A、B、C 三個狀態(tài)的轉(zhuǎn)移。那么，如果在這個表格中某兩列完全相同，那么對應(yīng)的字符類就是等價的。
化簡 DFA 和字符類的實(shí)現(xiàn)代碼比較多，這里就不貼了，請參見 Dfa 類。
最后化簡得到的 DFA，一般是用轉(zhuǎn)移表的形式保存（即上面的表格形式），使用下面三個數(shù)組就可以完整表示出 DFA 了。
復(fù)制代碼 代碼如下:

int[] CharClass;
int[,] Transitions;
int[][] SymbolIndex;

其中，CharClass 是字符類的映射表，它是長為 65536 的數(shù)組，用于將字符映射為相應(yīng)的字符類；Transitions 是 DFA 的轉(zhuǎn)移表，行數(shù)等于 DFA 中的狀態(tài)數(shù)，列數(shù)為字符類的個數(shù)；SymbolIndex 則是每個狀態(tài)對應(yīng)的符號索引。
當(dāng)然也可以對 DFA 的轉(zhuǎn)移表和符號索引進(jìn)行壓縮以節(jié)約內(nèi)存，不過這個留在以后再說。