編譯器原理實戰：從詞法分析器生成器到 Java 版編譯器前端構建

手寫編譯器前端：基於 Allen Holub《Compiler Design in C》的 Java 移植實踐

《Compiler Design in C》（龍書/虎書之外的工程導向經典）提供了完整的 C 版詞法/語法分析器生成器代碼。本文記錄將其 **核心數據結構、狀態機構建、模板驅動代碼生成** 移植至 Java 的全過程，並輸出清晰的 **七張架構圖**，展示從字符流輸入到 DFA 生成的完整鏈路。項目已開源，可直接克隆運行。

一、學習動機與技術路線

• 經典教材偏理論，離「可運行代碼」有距離；
• 選擇 Holub 書配套代碼（C 版）為藍本，**手動移植為 Java**，強迫理解每個模塊職責；
• 採用 **模板驅動生成**：Lex 規則 → NFA → DFA → 最小化 DFA → Java 詞法分析器源碼；
• 同理 Yacc 規則 → LR(1) 分析表 → Java 語法分析器。

二、詞法分析器生成器核心架構（七圖全景）

1. 整體圖：輸入緩沖區 → 正則解析 → NFA 構建 → 子集構造法 → DFA → 最小化 → 模板渲染 → 生成 Lexer.java；
2. 輸入緩沖區：雙緩衝區、標記行列號、支持回退、EOF 處理；
3. Lex 生成器主流程：RegExp.parse() → NFAFragment → NFA.build() → DFA.subsetConstruction() → DFA.minimize() → Emitter.emit()；
4. NFA 結構：狀態節點、ε/字符邊、接受態、片段連接算法；
5. DFA 結構：狀態集合、轉移表、最小化霍普克洛夫特算法；
6. 分析器生成：模板文件（骨架 + 佔位符）+ 代碼發射器 → 可編譯 Java 文件；
7. 模板文件組織：通用骨架、動作代碼注入點、錯誤處理鉤子。

三、關鍵技術點速覽

四、項目地址與後續規劃

• 通用編譯器生成器：https://github.com/9527hello/Compiler
• C 語言子集編譯器：https://github.com/9527hello/CCompiler
• 後續：完成 LR(1) 語法分析器生成器、語義分析、中間代碼生成、寄存器分配、目標代碼發射。

五、給初學者的建議

1. 先跑通 Lex/Yacc 生成的代碼，再看生成器源碼；
2. 手寫一個簡單的正則→NFA→DFA 流程，體會「狀態機」本質；
3. 模板驅動生成比硬編碼發射更易維護、擴展目標語言；
4. 編譯器前端（詞法/語法/語義）與後端（優化/代碼生成）可獨立演進，接口穩定是關鍵。