手寫 Java 編譯器系列（一）：Thompson 構造法之輸入文本預處理與宏展開

專案目標

將文本格式正則表達式轉換為鏈表式 NFA（非確定性有限自動機）。首階段任務：輸入文本預處理，核心難點在於宏定義遞歸展開。

輸入格式範例

D [0-9]                          // 宏定義
A [a-z]                          // 宏定義
AD {D}|{A}                       // 宏引用其他宏
{AD}\.{AD}+                      // 正則表達式主體

預處理後應轉為：

([0-9]|[a-z])\.([0-9]|[a-z])+

架構設計：兩大核心類

1. MacroHandler：宏定義解析與儲存

• 使用 Map macroMap 儲存「宏名 → 宏體」
• 同名宏後定義覆蓋前定義
• 解析邏輯：跳過空白 → 讀取宏名(直到空白) → 跳過空白 → 讀取宏體(直到換行/空白) → 存入 Map
• 提供 expandMacro(name) 介面，供正則處理器呼叫

2. RegularExpressionHandler：正則文本宏展開

• 逐字符讀取正則文本
• 遇到 { 且不在雙引號內 → 判定為宏引用
• 提取大括號內宏名 → 呼叫 macroHandler.expandMacro(name) → 替換
• 替換後內容若仍含 {} → 遞歸展開，直到無宏引用
• 錯誤處理：單邊大括號、宏未定義 → 拋出異常並提示行號

關鍵算法：遞歸宏展開流程圖

// RegularExpressionHandler 核心邏輯
private String expandMacro(String macroName) {
    String content = macroHandler.getMacro(macroName); // 從 Map 取得
    if (content == null) throw new RuntimeException("Undefined macro: " + macroName);
    
    // 檢查宏體內是否還有嵌套宏引用
    while (content.indexOf('{') != -1) {
        content = preProcessExpr(content); // 遞歸處理內層宏
    }
    return content;
}

處理雙引號內的大括號（轉義）

掃描時維護 inQuote 狀態：

• 遇到 " 切換狀態
• 在引號內遇到 { } 視為普通字符，不觸發宏展開

程式碼目錄結構

src/
├── MacroHandler.java          # 宏解析、儲存、展開介面
├── RegularExpressionHandler.java # 正則文本掃描、宏遞歸替換
├── InputSystem.java           # 統一輸入介面(控制台/檔案)
└── Main.java                  # 入口測試

下一階段預告

完成預處理後，下一步將實作：

1. 語法分析器：將展開後的正則轉為語法樹 (AST)
2. Thompson 構造：AST → NFA 片段 → 連接合併為完整 NFA
3. 子集構造法：NFA → DFA
4. DFA 最小化與代碼生成