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

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

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

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

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

下面是 DfaState 類的定義：

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

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

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

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

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

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

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

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

計(jì)算 ϵ-closure(T) 的過程就是從一個(gè)狀態(tài)集合開始的簡單圖搜索過程，使用 DFS 即可實(shí)現(xiàn)，具體的算法如下（ϵ-closure(s) 的算法也同理，等價(jià)于 \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 壓入堆棧
  }
 }
}

計(jì)算 move(T,a) 的算法更加簡單，只有一個(gè)循環(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 多個(gè)首狀態(tài)的子集構(gòu)造法
上一節(jié)中構(gòu)造得到的 NFA 是具有多個(gè)開始狀態(tài)的（為了支持上下文和行首限定符），不過對子集構(gòu)造法并不會產(chǎn)生影響，因?yàn)樽蛹瘶?gòu)造法是從開始狀態(tài)開始，沿著 NFA 的轉(zhuǎn)移不斷構(gòu)造相應(yīng)的 DFA 狀態(tài)，只要對多個(gè)開始狀態(tài)分別調(diào)用自己構(gòu)造法就可以正確構(gòu)造出多個(gè) DFA，而且不必?fù)?dān)心 DFA 之間的相互影響。為了方便起見，這多個(gè) DFA 仍然保存在一個(gè) DFA 中，只不過還是使用起始狀態(tài)來進(jìn)行區(qū)分。

2.4 DFA 狀態(tài)的符號索引
一個(gè) DFA 狀態(tài)對應(yīng) NFA 的一個(gè)狀態(tài)集合，那么直接將這多個(gè) NFA 狀態(tài)的符號索引全都拿來就可以了。不過前面說到， TrailingHead 類型的 NFA 狀態(tài)會在構(gòu)造 DFA 的時(shí)候與 Normal 類型的 NFA 狀態(tài)合并，這個(gè)合并指的就是符號索引的合并。
這個(gè)合并的方法也很簡單，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)行詞法分析時(shí)能夠更容易處理，效率也會有略微的提升。

2.5 子集構(gòu)造法的實(shí)現(xiàn)
子集構(gòu)造法的 C# 實(shí)現(xiàn)與上面給出的偽代碼基本一致，不過這里有個(gè)問題需要解決，就是如何高效的從 NFA 的狀態(tài)集合得到相應(yīng)的 DFA 狀態(tài)。由于 NFA 狀態(tài)集合是采用 HashSet<NfaState> 來保存的，所以我直接利用 Dictionary<HashSet<NfaState>, DfaState> 來解決這個(gè)問題，這里需要采用自定義的弱哈希函數(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)的個(gè)數(shù)。</param>
 internal Dfa BuildDfa(int headCnt) {
     Dfa dfa = new Dfa(charClass);
     // DFA 和 NFA 的狀態(tài)映射表，DFA 的一個(gè)狀態(tài)對應(yīng) NFA 的一個(gè)狀態(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 中的每個(gè)轉(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;
 }

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

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

3.2 DFA 最小化的示例 
下面以圖 4(a) 為例，給出 DFA 最小化的示例。
初始的劃分包括兩個(gè)組 \{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\} 組中，只含有一個(gè)狀態(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，它有四個(gè)狀態(tài)，對應(yīng)于 \Pi_{final} 的四個(gè)分組。分別挑選 A, C, D, E 作為每個(gè)分組的代表，其中，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 的最小化過程會合并等價(jià)狀態(tài)，這時(shí)可能會使得某些字符類變得等價(jià)，如圖 5 所示。
圖 5 等價(jià)的字符類
等價(jià)字符類的尋找比等價(jià)狀態(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 三個(gè)狀態(tài)的轉(zhuǎn)移。那么，如果在這個(gè)表格中某兩列完全相同，那么對應(yīng)的字符類就是等價(jià)的。
化簡 DFA 和字符類的實(shí)現(xiàn)代碼比較多，這里就不貼了，請參見 Dfa 類。
最后化簡得到的 DFA，一般是用轉(zhuǎn)移表的形式保存（即上面的表格形式），使用下面三個(gè)數(shù)組就可以完整表示出 DFA 了。
復(fù)制代碼 代碼如下:

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

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

最新評論