Scala 解析器組合子實戰：為 Java 開發者構建計算器 DSL（下）

領域特定語言（DSL）近年來備受關注，而函數式語言因其天然的組合特性，成為構建 DSL 的利器。本系列最後一篇將延續上一篇的計算器 DSL 實作，深入探討如何利用 Scala 強大的解析器組合子庫，將文本輸入轉換為抽象語法樹（AST），完成「外部 DSL」的關鍵一環——解析階段。

回顧：AST 與解釋器的基石

在上一篇中，我們已定義好計算器語言的核心 AST 節點：二元運算（加減乘除）、一元運算（正負號）與數值字面量。同時實作了 simplify（代數簡化）與 evaluate（遞歸求值）兩大核心函數。Lex Spoon 更提供了優化版的 simplify：先遞歸簡化子表達式（邊緣），再對頂層節點做模式匹配簡化，極大提升了優化的完整性。

從手寫解析器到解析器組合子

傳統上，構建解析器有兩條路：手寫遞歸下降解析器，或使用 Lex/Yacc 類工具生成。前者靈活但隨語法增長難以維護；後者雖標準卻引入額外構建步驟與外部依賴。Scala 提供了第三種路徑——解析器組合子：純函數式、內嵌於語言、無需代碼生成，且語法幾乎與 BNF 範式一一對應。

BNF 與組合子的無縫映射

以簡化版計算器文法為例：

expr   ::= term { '+' term | '-' term }
term   ::= factor { '*' factor | '/' factor }
factor ::= floatingPointNumber | '(' expr ')'

對應的 Scala 代碼幾乎是逐行翻譯：

object ArithParser extends JavaTokenParsers {
  def expr: Parser[Any]   = term ~ rep("+" ~ term | "-" ~ term)
  def term: Parser[Any]   = factor ~ rep("*" ~ factor | "/" ~ factor)
  def factor: Parser[Any] = floatingPointNumber | "(" ~ expr ~ ")"
}

~ 表示序列，rep 表示零次或多次重複，| 表示選擇。繼承 JavaTokenParsers 即可免費獲得標識符、數字、字符串等基礎詞法單元的解析能力。

解析器組合子的內部機制

本質上，每個解析器都是函數 Input => ParseResult[T]。Input 封裝字符流，ParseResult 要么是 Success(result, nextInput)，要么是 Failure(msg, nextInput)。組合子（如 ~、rep、|）將底層解析器組合成更高層級的解析器，形成「解析器的解析器」。

從 ParseResult 到 AST：還缺最後一步

初版解析器返回的是嵌套的 List 與 String，而非我們定義的 Expr 案例類。雖然可事後手工轉換，但組合子庫內建了 ^^ 操作符，能在解析成功時直接將結果映射為任意類型：

def factor: Parser[Expr] = 
  floatingPointNumber ^^ (s => Number(s.toDouble)) |
  "(" ~> expr <~ ")"

同理，term 與 expr 也可在組合時直接構建 BinaryOp 節點，實現「解析即構建 AST」的一體化流程。

結語與展望

至此，計算器 DSL 的完整鏈路已貫通：文本 → 解析器組合子 → AST → 簡化優化 → 求值。解析器組合子展示了函數式語言在語言工具構建上的極致表達力。下一步可嘗試擴展語法（變量、函數調用、控制流），或探索 PackratParsers 解決左遞歸與回溯性能問題。