C# 詞法分析器（四）：從正則表達式構建 NFA

前言

有了正則表達式的語法樹，下一步便是構建等價的 NFA（非確定有限狀態自動機）。NFA 易於從正則表達式遞歸構造，且有助於理解模式匹配本質。

一、NFA 的表示

採用首尾狀態表示法：每個 NFA 片段僅暴露 HeadState 和 TailState，內部結構封裝。NfaState 核心屬性：

• SymbolIndex：接受狀態的符號索引，非接受狀態為 -1
• CharClassTransition / CharClassTarget：字符類轉移（至多一條）
• EpsilonTransitions：ε 轉移列表
• StateType：Normal、TrailingHead、Trailing（支援向前看）

二、Thompson 構造法

2.1 基本規則

• 字符類：首尾狀態間添加一條字符類轉移

void BuildNfa(Nfa nfa) {
    nfa.HeadState = nfa.NewState();
    nfa.TailState = nfa.NewState();
    nfa.HeadState.Add(nfa.TailState, charClass);
}

2.2 歸納規則

1. 選擇 s|t：新增首尾狀態，分別 ε 連接 N(s) 和 N(t) 的首尾
2. 連接 st：N(s) 尾 ε 連接 N(t) 首，首尾分別為 N(s) 首、N(t) 尾
3. 重複 s{m,n}：
   • 有限上限：創建 n 個 N(s) 串聯，第 m-1 起添加 ε 到尾狀態
   • 無上限 n=∞：創建 m 個 N(s)，最後一個首尾間加 ε 循環
4. 向前看 s/t：同連接規則，但將 N(s) 尾標記為 TrailingHead，N(t) 尾標記為 Trailing，供後續 DFA 處理

2.3 示例：(a|b)*baa

逐步展示從正則到 NFA 的構造過程，直觀展示狀態與轉移的增長。

三、字符類劃分

為處理大字母表（Unicode），採用在線字符類劃分算法：每添加新轉移，檢查現有字符類是否需分裂，確保同一字符類內字符行為一致。使用 CharSet 高效實現集合運算。

HashSet GetCharClass(string charClass) {
    // 遍歷現有字符類，計算交集與差集，分裂並更新映射
    // 返回新轉移對應的字符類集合
}

四、多規則、限定符與上下文

• 多正則：新增虛擬首狀態，ε 連接各正則首狀態
• 行尾限定 $：視為預定義向前看 /\n 或 /\r?\n
• 行首限定 ^：構建兩組 NFA，行首用全集，非行首用排除行首限定的集合
• 上下文：每個上下文對應一組正則，構建獨立 NFA。共 2N 組（含行首/非行首），合併為一個擁有 2N 首狀態的 NFA，共享字符類

雖有一定內存開銷，但匹配極快，避免運行時回溯。

總結

NFA 構建完成，下一篇將介紹 NFA 到 DFA 的轉換與優化。