編譯原理入門（三）：詞法分析器原理與 DFA 實現機制

前言

詞法分析是編譯器前端的第一道關卡，任務是將預處理後的字元流切分為**詞法單元流**，供語法分析器使用。本文深入剖析詞法分析器的工作流程、核心理論模型（DFA/NFA/正則表達式）、狀態轉移圖構建與符號表整合。

工作流程總覽

1. 讀入字元流：從原始碼檔案或緩衝區逐字元讀取。
2. 過濾空白：跳過空格、製表符、換行符、註解（視語言規定）。
3. 模式匹配：依語言詞法規則識別關鍵字、標識符、常數、運算子、界符等。
4. 建構詞法單元：<類別碼, 屬性值>，如 <ID, "main">, <NUM, 123>。
5. 輸出單元流：傳遞給語法分析器；同步更新符號表（錄入標識符屬性）。

理論基石：從文法到 DFA

詞法規則本質上是**正則語言**，可用正則表達式描述。自動化構建掃描器的標準管線：

正則表達式 → NFA (非確定有限自動機) → DFA (確定有限自動機) → 最小化 DFA → 掃描器程式碼

關鍵概念對照表

DFA 執行模擬

以簡單語言識別 ID ([a-zA-Z_][a-zA-Z0-9_]*) 和 NUM ([0-9]+) 為例：

狀態 0 (初始):
  輸入字母/_ → 狀態 1 (ID 掃描中)
  輸入數字   → 狀態 2 (NUM 掃描中)
  輸入其他   → 錯誤/單字符 Token

狀態 1:
  輸入字母/數字/_ → 狀態 1 (繼續)
  輸入其他       → 接受 ID, 退回該字元, 回狀態 0

狀態 2:
  輸入數字 → 狀態 2 (繼續)
  輸入其他 → 接受 NUM, 退回該字元, 回狀態 0

掃描器核心迴圈即為：while (state != ACCEPT) state = transition[state][input];。

工具化生成：Lex / Flex

手寫 DFA 繁瑣且易錯，工業界普遍使用 **Lex (Flex)** 自動生成：

%%
[a-zA-Z_][a-zA-Z0-9_]*  { yylval.str = strdup(yytext); return ID; }
[0-9]+                  { yylval.num = atoi(yytext); return NUM; }
"+"|"-"|"*"|"/"         { return yytext[0]; }
[ \t\n]+                { /* 忽略空白 */ }
.                       { fprintf(stderr, "Unknown char: %c\n", *yytext); }
%%

• Flex 內部完成：正則 → NFA → DFA → 最小化 → C 代碼（狀態表驅動或直接編碼）。
• 生成的 yylex() 為高效掃描器入口。

符號表整合

詞法分析階段通常負責**將標識符錄入符號表**並返回索引/指標作為屬性值：

struct Token {
    int type;        // 類別碼
    union {
        int int_val;
        double float_val;
        char *str_val;
        int symtab_idx; // 標識符指向符號表索引
    } attr;
};

後續語法/語義分析透過索引查找符號表獲取型別、作用域、儲存類別等完整資訊。

常見挑戰與對策

總結

詞法分析器是編譯器「字元流 → Token 流」的翻譯官。其核心在於**正則語言識別**，理論工具鏈「正則 → NFA → DFA → 最小化」保證了理論正確與工程高效。現代開發應善用 Flex 等生成器，專注於詞法規則定義與符號表介面設計，而非手寫狀態機。