C# 詞法分析器（五）：NFA 轉 DFA 與最小化

前言

上一篇已從正則表達式構建出 NFA（非確定有限狀態自動機），本文將詳細說明如何將 NFA 轉換為等價的 DFA（確定有限狀態自動機），並對 DFA 與字符類進行化簡優化。

一、DFA 的表示

DFA 結構較 NFA 簡單，僅需狀態集合與轉移表。DfaState 核心屬性：

• SymbolIndex：接受狀態對應的符號索引數組（一個 DFA 狀態可對應多個 NFA 狀態）
• Transitions：字符類到目標狀態的映射（DFA 每字符類僅有一條轉移）

無需狀態類型屬性，因 Trailing 型狀態在匹配時處理，TrailingHead 型在構造時與 Normal 合併。

二、NFA 轉 DFA：子集構造法

2.1 算法原理

子集構造法核心思想：DFA 的一個狀態對應 NFA 的一個狀態集合。關鍵操作：

• ε-closure(T)：從狀態集合 T 出發，沿 ε 轉移可達的所有狀態
• move(T, a)：從 T 沿字符類 a 的轉移可達的狀態集合

算法流程：

1. 初始狀態 = ε-closure({s0})，加入 DFA，標記為未處理
2. 而 DFA 中存在未處理狀態 T：
   • 標記 T 為已處理
   • 對每個字符類 a：U = ε-closure(move(T, a))；若 U 不在 DFA 中則加入；設置 T[a] = U
3. 若 NFA 狀態為終結狀態，包含它的 DFA 狀態也為終結狀態，符號索引合併所有對應 NFA 狀態的索引

2.2 示例：(a|b)*baa

以正則 (a|b)*baa 為例，展示從 NFA 到 DFA 的構造過程，最終得到極小 DFA。

2.3 多首狀態處理

為支援上下文與行首限定，NFA 擁有多個開始狀態。子集構造法對每個首狀態分別執行，生成多個 DFA 但共享字符類，統一存儲於一個 DFA 結構中，以首狀態區分。

2.4 符號索引合併與排序

TrailingHead 型 NFA 狀態的符號索引轉換為 int.MaxValue - SymbolIndex，與 Normal 型索引區分。最後對 DFA 狀態的符號索引升序排序，使 Normal 索引在前，提升匹配效率。

2.5 C# 實現要點

使用 Dictionary<HashSet<NfaState>, DfaState> 配合自定義弱哈希（忽略元素順序）高效映射狀態集合。核心方法 BuildDfa、EpsilonClosure、Move 直接對應偽代碼。起始狀態符號索引設為空數組，避免匹配空串（詞素不可為空）。

2.6 死狀態處理

嚴格 DFA 需死狀態，但詞法分析中消除死狀態轉移：若無對應字符類轉移，視為匹配結束，採用最後接受狀態對應的詞素。

三、DFA 化簡

3.1 DFA 最小化（Hopcroft 算法思想）

將狀態劃分為接受/非接受兩組，反覆按字符類轉移目標組劃分，直到無法再分。示例將 5 狀態 DFA 最小化為 4 狀態。

3.2 字符類最小化

DFA 最小化後，部分字符類可能變得等價。將化簡後 DFA 以表格形式列出，若兩列轉移完全相同，則對應字符類等價，可合併。

3.3 最終表示

化簡後的 DFA 以三個數組保存：

int[] CharClass;      // 字符 -> 字符類映射 (65536 長度)
int[,] Transitions;   // 狀態轉移表 [狀態數, 字符類數]
int[][] SymbolIndex;  // 每狀態的符號索引數組

可進一步壓縮轉移表節省內存，留待後續優化。

下一步

下一篇將介紹如何基於此 DFA 構建詞法分析器。