使用 C# 打造四則運算解譯器：從 Tokenize 到 AST 建構完整實作

本文記錄從零建立一個簡易四則運算解譯器的完整過程，涵蓋詞法分析、抽象語法樹（AST）建構、優先序處理與遞迴求值。雖然功能基礎，但展示了解譯器核心架構，適合理解編譯原理入門。

整體架構：兩大階段

1. Tokenizer（詞法分析）：將輸入字串（如 "1 + 2 * 3"）切分為 Token 序列（數字 Token、運算子 Token）。
2. Parser + AST（語法分析與樹建構）：依運算子優先序與結合性，將 Token 組合成 AST，葉節點為數字，內部節點為運算子，根節點為最後執行的運算。

Token 定義

internal abstract class Token { }

internal sealed class NumToken : Token
{
    public double Value { get; }
}

internal sealed class OpToken : Token
{
    public Op Value { get; }
    public Priority Priority { get; }
}

internal enum Op : int { Plus = '+', Minus = '-', Multiply = '*', Divide = '/' }
internal enum Priority { Lv0 = 0, Lv1 = 1, Lv2 = 2 } // 越大優先序越高

Tokenizer 實作重點

• 掃描字串，忽略空白字元。
• 使用緩衝區累積數字字元，遇非數字時轉為 double 產生 NumToken；偵測重複小數點拋錯。
• 遇 + - * / 產生 OpToken，攜帶優先序資訊。
• 遇未定義字元直接拋出解析錯誤。

AST 建構演算法

採用啟發式規則，依序處理 Token：

• 數字 Token：永遠掛為右子節點。
• 運算子 Token：
  • 若樹為空或根為數字 → 新運算子成根，舊樹成左子樹。
  • 若根為運算子：
    • 新運算子優先序 較高 → 移至右子樹根，原右子樹下沉為其左子樹。
    • 新運算子優先序 較低或相等（左結合） → 新運算子成根，舊樹成左子樹。

範例：1 + 2 * 3 產生的 AST 根為 -（若完整式為 1 + 2 * 3 - 4），* 在最深層優先執行。

遞迴求值

private double Eval(SyntaxNode root)
{
    if (root.Token is NumToken n) return n.Value;
    if (root.Token is OpToken op)
    {
        double l = Eval(root.Left), r = Eval(root.Right);
        return op.Value switch
        {
            Op.Plus => l + r,
            Op.Minus => l - r,
            Op.Multiply => l * r,
            Op.Divide => l / r,
            _ => throw new ParseFailureException("Unknown operator")
        };
    }
    throw new ParseFailureException("Invalid node");
}

錯誤偵測

解譯器能識別：非法字元、格式錯誤的數字（如 2.3.4）、運算子連續（2 * + 3）、缺少運算元等語法錯誤，並回報錯誤位置。

未來擴充方向

• 支援一元運算子（正負號）與括號。
• 引入變數表與 let 綁定。
• 支援 lambda 函數定義與呼叫。