C#詞法分析器之轉換DFA詳解

2020-01-24 03:23:19

字體：大中小

來源：轉載

供稿：網友

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

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

namespace Cyjb.Compiler.Lexer {
     class Dfa {
         // 在當前 DFA 中創建一個新狀態。
         DfaState NewState() {}
     }
 }

DFA 的狀態也比較簡單，必要的屬性只有兩個：符號索引和狀態轉移。

符號索引表示當前的接受狀態對應的是哪個正則表達式。不過 DFA 的一個狀態可能對應于 NFA 的多個狀態（詳見下面的子集構造法），所以 DFA 狀態的符號索引是一個數組。對于普通狀態，符號索引是空數組。

狀態轉移表示如何從當前狀態轉移到下一狀態，由于在構造 NFA 時已經劃分好了字符類，所以在 DFA 中直接使用數組記錄下不同字符類對應的轉移（DFA 中是不存在 ϵ 轉移的，而且對每個字符類有且只有一條轉移）。

在 NFA 的狀態定義中，還有一個狀態類型屬性，但是在 DFA 狀態中卻沒有這個屬性，是因為 Trailing 類型的狀態會在 DFA 匹配字符串的時候處理（會在下篇文章中說明），TrailingHead 類型的狀態會在構造 DFA 的時候與 Normal 類型的狀態合并（詳見 2.4 節）。

下面是 DfaState 類的定義：

復制代碼代碼如下:

namespace Cyjb.Compiler.Lexer {
     class DfaState {
         // 獲取包含當前狀態的 DFA。
         Dfa Dfa { get; private set; }
         // 獲取或設置當前狀態的索引。
         int Index { get; set; }
         // 獲取或設置當前狀態的符號索引。
         int[] SymbolIndex { get; set; }
         // 獲取或設置特定字符類轉移到的狀態。
         DfaState this[int charClass] { get; set; }
     }
 }

DFA 的狀態中額外定義的兩個屬性 Dfa 和 Index 同樣是為了方便狀態的使用。
二、NFA 轉換為 DFA
2.1 子集構造法

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

子集構造算法需要用到的操作有：

操作	描述
ϵ-closure(s)	能夠從 NFA 的狀態 s 開始，只通過 ϵ 轉移能夠到達的 NFA 狀態集合
ϵ-closure(T)	能夠從 T 中某個 NFA 狀態 s開始，只通過 ϵ 轉移能夠到達的 NFA 狀態集合，即 ∪s∈Tϵ-closure(s)
move(T,a)	能夠從 T 中某個狀態 s 出發，通過標號為 a 的轉移到達的 NFA 狀態集合

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

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

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

據此，可以得到以下的算法（算法中的 T[a]=U 表示在狀態 T 中的字符類 a 上存在到狀態 U 的轉移）：

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

如果某個 NFA 是終結狀態，那么所有包含它的 DFA 狀態也是終結狀態，而且 DFA 狀態的符號索引就包含 NFA 狀態對應的符號索引。一個 DFA 狀態可能對應于多個 NFA 狀態，所以上面定義 DfaState 時，符號索引是一個數組。

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

輸入：NFA 的狀態集合 
輸出：
將  的所有狀態壓入堆棧

while (堆棧非空) {
 彈出棧頂元素 
 foreach ( :  可以通過  轉移到達 ) {
  if () {
   
   將  壓入堆棧
  }
 }
}

計算的算法更加簡單，只有一個循環：

輸入：NFA 的狀態集合 
輸出：

foreach () {
 if ( 存在字符類  上的轉移，目標為 ) {
  
 }
}
2.2 子集構造法的示例
這里以上一節中從正則表達式 (a|b)*baa 構造得到的 NFA 作為示例，將它轉化為 DFA。這里的輸入字母表 /Sigma = /{a, b/}。
圖 1 正則表達式 (a|b)*baa 的 NFA
圖 2 構造 DFA 的示例
 
圖 3 最終得到的 DFA
2.3 多個首狀態的子集構造法
上一節中構造得到的 NFA 是具有多個開始狀態的（為了支持上下文和行首限定符），不過對子集構造法并不會產生影響，因為子集構造法是從開始狀態開始，沿著 NFA 的轉移不斷構造相應的 DFA 狀態，只要對多個開始狀態分別調用自己構造法就可以正確構造出多個 DFA，而且不必擔心 DFA 之間的相互影響。為了方便起見，這多個 DFA 仍然保存在一個 DFA 中，只不過還是使用起始狀態來進行區分。

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

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

View Code 
 /// <summary>
 /// 根據當前的 NFA 構造 DFA，采用子集構造法。
 /// </summary>
 /// <param name="headCnt">頭節點的個數。</param>
 internal Dfa BuildDfa(int headCnt) {
     Dfa dfa = new Dfa(charClass);
     // DFA 和 NFA 的狀態映射表，DFA 的一個狀態對應 NFA 的一個狀態集合。
     Dictionary<DfaState, HashSet<NfaState>> stateMap =
         new Dictionary<DfaState, HashSet<NfaState>>();
     // 由 NFA 狀態集合到對應的 DFA 狀態的映射表（與上表互逆）。
     Dictionary<HashSet<NfaState>, DfaState> dfaStateMap =
         new Dictionary<HashSet<NfaState>, DfaState>(SetEqualityComparer<NfaState>.Default);
     Stack<DfaState> stack = new Stack<DfaState>();
     // 添加頭節點。
     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 中的每個轉移，尋找 Move 集合。
             HashSet<NfaState> set = Move(stateSet, i);
             if (set.Count > 0) {
                 set = EpsilonClosure(set);
                 DfaState newState;
                 if (!dfaStateMap.TryGetValue(set, out newState)) {
                     // 添加新狀態.
                     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 的轉移。
                 state[i] = newState;
             }
         }
     }
     return dfa;
 }
 /// <summary>
 /// 返回指定 NFA 狀態集合的 ϵ 閉包。 
 /// </summary>
 /// <param name="states">要獲取 ϵ 閉包的 NFA 狀態集合。</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);
         // 這里只需遍歷 ϵ 轉移。
         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 狀態集合的字符類轉移集合。 
 /// </summary>
 /// <param name="states">要獲取字符類轉移集合的 NFA 狀態集合。</param>
 /// <param name="charClass">轉移使用的字符類。</param>
 /// <returns>得到的字符類轉移集合。</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;
 }

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

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

3.2 DFA 最小化的示例 
下面以圖 4(a) 為例，給出 DFA 最小化的示例。
初始的劃分包括兩個組  和 ，分別是非接受狀態組和接受狀態組。
第一次分割，在  組中，對于字符 a，狀態  都轉移到組內的狀態，而狀態  轉移到組  中，所以狀態  需要被劃分出來。對于字符 b，所有狀態都轉移到該組內的狀態，不能區分； 組中，只含有一個狀態，無需進一步劃分。這一輪 。
第二次分割，在  組中，對于字符 a，狀態  都轉移到組內的狀態，而狀態  轉移到組  中，對于字符 b 則不能區分；組  和組  同樣不做劃分。這一輪 。
第三次分割，唯一可能被分割的組 ，對于字符 a 和字符 b，都會轉移到相同的組內，所以不會被分割。因此就得到 。
最后，構造出最小化的 DFA，它有四個狀態，對應于  的四個分組。分別挑選  作為每個分組的代表，其中， 是開始狀態， 是接受狀態。將所有狀態到  的轉移都修改為到  的轉移，最后得到的 DFA 轉換表為：
DFA 狀態 a 上的轉移 b 上的轉移
A A C
C D C
D E C
E A C
最后再將狀態重新排序，得到的就是如圖 4(b) 所示的 DFA 了。

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

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

其中，CharClass 是字符類的映射表，它是長為 65536 的數組，用于將字符映射為相應的字符類；Transitions 是 DFA 的轉移表，行數等于 DFA 中的狀態數，列數為字符類的個數；SymbolIndex 則是每個狀態對應的符號索引。
當然也可以對 DFA 的轉移表和符號索引進行壓縮以節約內存，不過這個留在以后再說。