C# 詞法分析器（三）：正則表達式與有限自動機

前言

正則表達式是描述詞素模式的標準工具。雖無法表達所有模式（如等量 a/b 字符串），但能高效覆蓋詞法分析所需模式類型。

一、正則表達式定義與擴展

基於 Kleene 定義，採用類似 Flex 的擴展語法，風格貼近 .NET Regex。支援字符類、Unicode 類別、量詞、選擇、連接、錨點（行首/行尾/向前看）、文件結尾 <<EOF>> 等。注意差異：不支援 POSIX 字符類、$ 匹配行尾而非單純字符、字符集相減用 C# 風格、向前看中 $ 為字面義。

二、正則表達式的類結構表示

使用 8 個類表示任意正則：

• Regex 基類
• CharClassExp：字符類（單字符）
• LiteralExp：原義文本（多字符）
• RepeatExp：重複 {m,n}
• AlternationExp：選擇 |
• ConcatenationExp：連接
• AnchorExp：錨點（僅最外層）
• EndOfFileExp：文件結尾

解析器 RegexParser 將字符串（如 "abc[0-9]+"）轉換為語法樹。

三、有限自動機識別語言

3.1 NFA 匹配

NFA 允許 ε 轉移與非確定轉移。匹配時維護狀態集合，讀入字符後計算新集合。示例：(a|b)*baa 的 NFA 匹配 "ababaa" 過程展示狀態集合變化。

3.2 DFA 匹配

DFA 無 ε 轉移、轉移確定。匹配只需單狀態追蹤，時間複雜度 O(k)（k 為輸入長度），效率極高。同樣示例展示 DFA 確定性匹配過程。

3.3 為何選擇 DFA

• 匹配效率遠超 NFA
• 構造雖耗時（最壞指數狀態增長），但僅構建一次，可重複使用；Flex 甚至在代碼生成階段預構建
• 編程語言詞法極少出現最壞指數增長情況

NFA 仍具價值：DFA 由 NFA 經子集構造法得來；理解 NFA 有助於處理多規則與向前看。

下一步

下一篇將詳細介紹 NFA 表示與正則到 NFA 的轉換。