手把手教你寫腳本引擎（四）：詞法分析 DFA 與運算子優先語法分析

本文實作高階語言腳本引擎的前端核心：詞法分析器與語法分析器。採用手寫 DFA 詞法掃描器，結合運算子優先分析法構建表達式語法樹，避免複雜文法產生式的維護困境。

詞法分析：手寫 DFA 掃描器

狀態編號從 0 開始連續分配，利用 switch-case 產生跳躍表實現高效狀態轉移。核心流程：

1. 複製輸入指標 Current，記錄最後接受狀態位置 Last，狀態變數 Status 初始為 0
2. 死循環計算新狀態：若當前為接受狀態，更新 Last = Current 並記錄 Token 類型
3. 從 Current 取字元轉移狀態，直到字串結束或無法轉移
4. 若 Last 為 NULL 則報錯；否則 Input 到 Last 為一完整 Token

語法分析：運算子優先分析法

專為處理大量運算子優先級設計，避免為每個優先級編寫獨立函數。核心演算法處理不含括號的表達式（括號遞迴處理）：

1. 維護根節點指標 Root 與當前節點指標 Current
2. 提取「單元」（括號表達式、函數呼叫、常數/變數、前綴運算子組合）
3. 循環讀取「二元運算子 + 單元」對，向上尋找優先級較低的祖先節點
4. 若達根節點：整棵樹作左運算元，新單元作右運算元，更新根節點
5. 否則：將找到節點從父節點分離，作為左運算元，新運算子接回父節點
6. 遇到右括號、逗號等終結符結束

演算法演示：解析 1+2*3+4

語法樹資料結構：多態設計

拒絕單一類別巨型 switch，採用虛函數多態：

class ExpBase {
public:
    virtual TypeBase* GetType(vector& Errors) = 0;
};

enum BinOpType { Plus, Minus, Multiply, Division, ... };
enum SinOpType { Negative, Not, ... };

class ExpBinOp : public ExpBase {
public:
    ExpBase* ParamA;
    ExpBase* ParamB;
    BinOpType Operator;
};

class ExpSinOp : public ExpBase {
public:
    ExpBase* Param;
    SinOpType Operator;
};

class ExpInvoke : public ExpBase {  // 函數呼叫
public:
    ExpBase* Name;
    vector Params;
};

class ExpToken : public ExpBase {  // 葉節點：變數/常數
public:
    Token* Content;
};

下篇預告

語義分析與符號表：運算式型別推導、多載解析、作用域驗證等。