在編譯器前端,詞法分析器的任務是將字符流切分為 Token 流。這一過程的理論基石是正則表達式 → NFA → DFA → 最小化 DFA 的自動機轉換鏈。本文以實戰視角,梳理核心概念、構造算法與工程落地要點。
正則表達式由字符、連接、選擇(|)、克萊尼閉包(*)、括號組成。例如 a(a|b)*b 表示以 a 開頭、b 結尾、中間任意 a/b 組合的字符串集合。遞歸定義 讓表達式具備嵌套表達能力,便於後續構造語法樹。
特徵: 一狀態遇同一輸入可轉移至多狀態;允許 ε-轉移(無輸入自發轉移)。
Thompson 構造法: 針對基本元素(字符、ε、∅)、連接、選擇、閉包五種情況,遞歸構建 NFA 片段並連接。優點:構造簡單、線性時間;缺點:狀態數多、需回溯匹配、運行效率低。
特徵: 無 ε-轉移;任一狀態對任一輸入至多一條轉移;運行時無回溯、O(n) 匹配。
子集構造法: 以 NFA 的 ε-closure 為起始狀態,對每個字符計算可達狀態集合,構建 DFA 狀態。
直接從正則構造 DFA(Brzozowski 導數法 / Syntax Tree + First/Last/Nullable/Followpos): 避開 NFA 中間層,直接由語法樹計算 DFA,工程上更常用(如 Lex/Flex)。
採用 Hopcroft 算法 或 表填法,將無法區分的狀態合併,得到唯一的最小 DFA,減少狀態表空間,加速匹配。


掌握這條鏈路,不僅能寫出高性能詞法器,更能理解正則引擎(PCRE/RE2/Rust regex)的底層行為,避免災難性回溯(ReDoS)坑。