如果你曾經開啟過 Yacc 的語法檔案，並疑惑為什麼建構一門語言需要學習第二門語言，那麼你並不孤單。parser generator很強大，但對於在 bounded context 中自然湧現的小型 DSL 來說，它們幾乎總是大材小用。

你可以用與應用程式其餘部分相同的語言來編寫parser。沒有建置步驟，沒有語法檔案，沒有你無法除錯的產生程式碼。

parser generator解決了一個你可能沒有的問題

ANTLR、Bison 或 PEG.js 等parser generator迫使你用領域特定的元語言表達語法。你編寫 .g4 或 .y 檔案，執行工具，取得產生的原始碼，將其匯入，然後在出問題時祈禱錯誤訊息能說得通。

對於一門完整的程式語言，這種權衡是值得的。產生的 LR parser速度很快，而且語法與實作的分離很清晰。

但我們大多數人並不是在建構程式語言。我們建構的是查詢篩選器、設定格式、規則引擎，或者是活在單一 bounded context 裡的微型表示式語言。parser generator的開銷、單獨的建置步驟、以及需要學習的第二套語法，都是純粹的摩擦。

parser combinator把解析變成普通程式碼

parser combinator是傳回parser的函式，而parser是消費輸入並傳回解析值或錯誤的函式。你用高階函式把小parser組合成大parser。

解析字串 "hello" 的parser是一個函式。解析 "hello" OR "world" 的parser是一個先嘗試第一個、失敗再嘗試第二個的函式。解析 "hello" THEN "world" 的parser按順序執行它們並組合結果。

這意味著你的語法就是程式碼。你用中斷點除錯它，而不是用語法視覺化工具。

40 行 TypeScript 的完整算術parser

下面是一個微型表示式語言的完整parser。它處理整數和帶括號的加法。沒有相依項目，沒有產生檔案。

type Result<T> = 
  | { ok: true; value: T; pos: number }
  | { ok: false; error: string; pos: number };

type Parser<T> = (input: string, pos: number) => Result<T>;

// Primitives: match a literal string or a regex
const str = (expected: string): Parser<string> => (input, pos) => {
  const end = pos + expected.length;
  return input.slice(pos, end) === expected
    ? { ok: true, value: expected, pos: end }
    : { ok: false, error: `expected "${expected}"`, pos };
};

const regex = (re: RegExp): Parser<string> => (input, pos) => {
  const m = input.slice(pos).match(new RegExp(`^(?:${re.source})`));
  return m
    ? { ok: true, value: m[0], pos: pos + m[0].length }
    : { ok: false, error: `expected /${re.source}/`, pos };
};

// Combinators: sequence, choice, map, lazy
const map = <A, B>(p: Parser<A>, f: (a: A) => B): Parser<B> => (input, pos) => {
  const r = p(input, pos);
  return r.ok ? { ...r, value: f(r.value) } : r;
};

const seq = <T extends Parser<unknown>[]>(...ps: T): Parser<any[]> => (input, pos) => {
  const values: unknown[] = [];
  let curr = pos;
  for (const p of ps) {
    const r = p(input, curr);
    if (!r.ok) return r;
    values.push(r.value);
    curr = r.pos;
  }
  return { ok: true, value: values, pos: curr };
};

const or = <A, B>(a: Parser<A>, b: Parser<B>): Parser<A | B> => (input, pos) => {
  const r = a(input, pos);
  return r.ok ? r : b(input, pos);
};

const lazy = <T>(fn: () => Parser<T>): Parser<T> => (input, pos) => fn()(input, pos);

// Grammar: expr := number | "(" expr "+" expr ")"
const ws = regex(/\s*/);
const number = map(regex(/\d+/), n => parseInt(n, 10));

let expr: Parser<{ val: number }>;

expr = or(
  map(
    seq(str("("), ws, lazy(() => expr), ws, str("+"), ws, lazy(() => expr), str(")")),
    ([, , left, , , , right]) => ({ val: left.val + right.val })
  ),
  map(number, val => ({ val }))
);

// Run it
const result = expr("(1 + (2 + 3))", 0);
console.log(result.ok ? result.value : result.error);
// Output: { val: 6 }

讓我們拆解一下實際發生了什麼。str、regex 和 number 是原始parser。seq 按順序執行parser。or 嘗試備選。map 轉換結果。lazy 是唯一微妙的環節。它將求值延後，以免遞迴語法在定義時就爆炸。

型別系統追蹤每個parser的產出。解析失敗時，你能得到精確的位置和期望的 token。這已經比大多數產生parser開箱即用的錯誤報告更好了。

為什麼它特別適合 bounded context

領域驅動設計中的 bounded context 被故意設計得很小。活在其中的 DSL 也應該很小。它只需要該 context 關心的那些構造，別的什麼都不需要。

parser combinator向下縮放得非常漂亮。你寫的是網域所需的那一個查詢篩選器的parser，而不是一門通用查詢語言。你新增新構造只需新增一個新函式，而不是重新產生上千行 C 程式碼。

parser與 bounded context 的其餘部分活在同一個儲存庫、同一門語言、同一種心智模型裡。領域模型變了，parser跟著變。沒有語法檔案在另一個目錄裡漸漸失步。

組合子的短板在哪裡

它們不是免費的。組合子在底層建構的是遞迴下降parser，而遞迴下降parser對左遞迴規則束手無策。如果你寫 expr := expr + number | number，parser會永遠呼叫自己。

你需要把左遞迴規則改寫成迴圈，或者使用替你處理左遞迴的函式庫。對於小型 DSL，這很少成為實際問題。

效能是另一個注意事項。手工調校的遞迴下降parser或產生的 LR parser在原始吞吐量上能擊敗組合子。對於啟動時只讀一次的設定檔，或者每個請求評估一次的規則，差距在微秒層級。在假設它重要之前，先測量。

如何開始建構你自己的

從最小的語法開始。解析一個構造，測試它，然後組合。

如果你寫 TypeScript，parsimmon、arcsecond 或 chevrotain 等函式庫能提供比上面從零實作的版本更好的錯誤訊息和左遞迴處理能力的生產級組合子。Rust 有 nom，Haskell 有 Parsec，Python 有 parsy。

模式到處都一樣：primitives、sequence、choice、repetition、transformation。學一次，用在任何語言裡。

FAQ

什麼是parser combinator？

parser combinator是一個接受一個或多個parser並傳回新parser的高階函式。它們讓你透過組合簡單parser來建構複雜parser，使用普通程式碼而不是單獨的語法語言。

什麼時候我仍然應該使用parser generator？

當你解析一門完整程式語言、需要最大解析吞吐量、或者你的團隊對某個特定產生器生態系統已有深厚專長時，再使用產生器。對於小型 DSL，通常不值得承擔這個開銷。

parser combinator慢嗎？

它們比手寫或產生的 LR parser慢，但對於大多數 DSL 使用案例來說，差距無關緊要。一個典型的組合子parser每毫秒能處理數千個 token。這對於設定檔、查詢字串和規則引擎來說已經夠快了。

我能在 TypeScript 以外的語言中使用parser combinator嗎？

當然。這個模式與語言無關。Rust 的 nom、Haskell 的 Parsec、Python 的 parsy 和 Haskell 的 attoparsec 都是成熟且廣泛使用的函式庫。

下次你在 bounded context 裡需要一門微型語言時，問問自己是否真的需要語法檔案和程式碼產生步驟。對於大多數 DSL，答案是否定的。一百行組合子程式碼就能給你一個可以在除錯器裡單步執行、無需重新產生即可擴充、而且半年後還能真正理解的parser。