Yaccのgrammarファイルを開いて、なぜ言語を作るのに第二の言語を学ぶ必要があるのかと思ったことがあるなら、あなただけではない。パーサージェネレータは強力だが、bounded contextの中で自然に生まれる小さなDSLには、ほとんどの場合大げさすぎる。

パーサーは、アプリケーションの残りと同じ言語で書ける。ビルドステップなし、grammarファイルなし、デバッグできない生成コードなし。

パーサージェネレータが解決するのは、おそらくあなたが持っていない問題

ANTLR、Bison、PEG.jsのようなパーサージェネレータは、grammarをドメイン固有のメタ言語で表現することを強制する。.g4や.yファイルを書き、ツールを実行し、生成されたソースを取得してインポートし、何か壊れたときにエラーメッセージが意味をなすことを祈る。

完全なプログラミング言語なら、このトレードオフは価値がある。生成されたLRパーサーは高速で、grammarと実装の分離はクリーンだ。

だが私たちの多くはプログラミング言語を作っているわけではない。クエリフィルター、設定フォーマット、ルールエンジン、あるいは単一のbounded contextの中に閉じた小さなexpression languageを作っている。パーサージェネレータのオーバーヘッド、分離されたビルドステップ、学習が必要な第二の構文は、純粋な摩擦だ。

パーサーコンビネータは、パースを普通のコードに変える

パーサーコンビネータはパーサーを返す関数であり、パーサーは入力を消費して解析された値かエラーを返す関数だ。小さなパーサーをhigher-order functionを使って大きなパーサーに合成する。

文字列"hello"のパーサーは関数だ。"hello" OR "world"のパーサーは、最初を試し、失敗すれば次を試す関数だ。"hello" THEN "world"のパーサーは順番に実行して結果を結合する。

つまりgrammarはただのコードだ。ブレークポイントでデバッグし、grammar可視化ツールではない。

40行のTypeScriptで動作する算術パーサー

以下は極小のexpression language用の完全なパーサーだ。整数と括弧付き加算を扱う。依存関係なし、生成ファイルなし。

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はprimitiveパーサーだ。seqは順番にパーサーを実行する。orは代替を試す。mapは結果を変形する。lazyだけが微妙な部分だ。再帰的grammarが定義時に爆発しないよう、評価を遅延させる。

型システムが各パーサーの産出を追跡する。パースに失敗すると、正確な位置と期待されるトークンが得られる。これは既に、ほとんどの生成パーサーが標準で提供するより優れたエラーレポートだ。

なぜbounded contextに特に合うのか

Domain-Driven Designにおけるbounded contextは意図的に小さい。そこに住むDSLも小さいべきだ。そのcontextが気にする構造だけが必要で、他に何もいらない。

パーサーコンビネータは下方向に美しくスケールする。汎用クエリ言語ではなく、ドメインが必要とする唯一のクエリフィルターのパーサーを書く。新しい構造は関数を追加するだけで済み、数千行のCを再生成する必要はない。

パーサーは、bounded contextの残りと同じリポジトリ、同じ言語、同じメンタルモデルの中に生きる。ドメインモデルが変われば、パーサーも一緒に変わる。別のディレクトリで同期からずれていくgrammarファイルは存在しない。

コンビネータの限界

タダではない。コンビネータの裏で構築される再帰下降パーサーは、左再帰ルールに苦労する。expr := expr + number | numberと書くと、パーサーは永遠に自分を呼び出す。

これは左再帰ルールをループに書き換えるか、左再帰を自動で処理するライブラリを使うことで修正する。小さなDSLでは、実務上の問題になることは少ない。

もう一つの注意点はパフォーマンスだ。手調整された再帰下降パーサーや生成されたLRパーサーは、生のスループットでコンビネータを上回る。起動時に一度読まれる設定ファイルや、リクエストごとに評価されるルールでは、差はマイクロ秒単位だ。重要だと思い込む前に計測しよう。

自分用のビルドを始める方法

最小限のgrammarから始める。一つの構造をパースしてテストし、それから合成する。

TypeScriptを書くなら、parsimmon、arcsecond、chevrotainのようなライブラリが、上のスクラッチ実装より優れたエラーメッセージと左再帰処理を備えたproduction-readyなコンビネータを提供する。Rustにはnom、HaskellにはParsec、Pythonにはparsyがある。

パターンはどこでも同じ：primitives、sequence、choice、repetition、transformation。一度学べば、どの言語でも応用できる。

FAQ

パーサーコンビネータとは何か？

パーサーコンビネータは、一つ以上のパーサーを受け取って新しいパーサーを返すhigher-order functionだ。単純なパーサーを合成して複雑なパーサーを構築でき、別のgrammar言語ではなく普通のコードを使う。

いつパーサージェネレータを使うべきか？

完全なプログラミング言語をパースする場合、最大のパーススループットが必要な場合、あるいはチームが特定のジェネレータエコシステムに深い専門知識を持っている場合に使う。小さなDSLでは、オーバーヘッドに見合わないことが多い。

パーサーコンビネータは遅いか？

手書きや生成されたLRパーサーより遅いが、ほとんどのDSLユースケースではその差は無視できる。典型的なコンビネータパーサーはミリ秒あたり数千トークンを処理する。設定ファイル、クエリ文字列、ルールエンジンには十分速い。

TypeScript以外の言語でもパーサーコンビネータは使えるか？

もちろん。このパターンは言語に依存しない。Rustのnom、HaskellのParsec、Pythonのparsy、Haskellのattoparsecは、いずれも成熟して広く使われているライブラリだ。

次にbounded contextの中に小さな言語が必要になったら、本当にgrammarファイルとコード生成ステップが必要か自問してみよう。ほとんどのDSLでは、答えはノーだ。コンビネータコード100行で、デバッガーでステップ実行でき、何も再生成せずに拡張でき、6か月後にも実際に理解できるパーサーが手に入る。