Jika pernah kamu membuka file grammar Yacc dan bertanya-tanya mengapa membangun bahasa memerlukan belajar bahasa kedua, kamu tidak sendirian. Parser generator memang powerful, tetapi untuk DSL kecil yang muncul secara alami di dalam bounded context, hampir selalu berlebihan.

Kamu bisa menulis parser dalam bahasa yang sama dengan aplikasi lainnya. Tanpa langkah build, tanpa file grammar, tanpa kode yang dihasilkan yang tidak bisa kamu debug.

Parser generator menyelesaikan masalah yang mungkin tidak kamu miliki

Parser generator seperti ANTLR, Bison, atau PEG.js memaksamu mengekspresikan grammar dalam metalanguage khusus domain. Kamu menulis file .g4 atau .y, menjalankan tool, mendapatkan source yang dihasilkan, mengimpornya, dan berharap pesan error masuk akal ketika sesuatu rusak.

Untuk bahasa pemrograman lengkap, trade-off ini worth it. Parser LR yang dihasilkan cepat, dan pemisahan antara grammar dan implementasi bersih.

Tapi sebagian besar dari kita tidak membangun bahasa pemrograman. Kita membangun query filter, format config, rule engine, atau expression language kecil yang hidup di dalam satu bounded context. Overhead parser generator, langkah build terpisah, dan sintaks kedua yang harus dipelajari adalah friksi murni.

Parser combinator mengubah parsing menjadi kode biasa

Parser combinator adalah fungsi yang mengembalikan parser, dan parser adalah fungsi yang mengonsumsi input dan mengembalikan nilai yang di-parse atau error. Kamu menyusun parser kecil menjadi parser yang lebih besar menggunakan higher-order function.

Parser untuk string "hello" adalah sebuah fungsi. Parser untuk "hello" OR "world" adalah fungsi yang mencoba yang pertama, dan jika gagal, mencoba yang kedua. Parser untuk "hello" THEN "world" menjalankannya secara berurutan dan menggabungkan hasilnya.

Ini berarti grammar-mu hanyalah kode. Kamu mendebugnya dengan breakpoint, bukan dengan tool visualisasi grammar.

Parser aritmatika yang berfungsi dalam 40 baris TypeScript

Berikut adalah parser lengkap untuk bahasa ekspresi yang sangat kecil. Ia menangani integer dan penjumlahan dalam tanda kurung. Tanpa dependencies, tanpa file yang dihasilkan.

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 }

Mari kita uraikan apa yang sebenarnya terjadi. str, regex, dan number adalah parser primitif. seq menjalankan parser secara berurutan. or mencoba alternatif. map mentransformasi hasil. lazy adalah bagian yang paling subtle. Ia menunda evaluasi sehingga grammar rekursif tidak meledak saat definisi.

Type system melacak apa yang dihasilkan setiap parser. Ketika parsing gagal, kamu mendapatkan posisi yang tepat dan token yang diharapkan. Itu sudah merupakan error reporting yang lebih baik daripada kebanyakan parser yang dihasilkan out of the box.

Mengapa ini cocok sekali dengan bounded context

Bounded context dalam Domain-Driven Design sengaja dibuat kecil. DSL yang hidup di dalamnya juga harus kecil. Ia membutuhkan persis konstruk yang diperhatikan context tersebut, dan tidak ada yang lain.

Parser combinator scale down dengan indah. Kamu menulis parser untuk satu query filter yang dibutuhkan domain-mu, bukan untuk bahasa query general-purpose. Kamu menambahkan konstruk baru dengan menambahkan fungsi baru, bukan dengan meregenerasi ribuan baris C.

Parser hidup di repository yang sama, bahasa yang sama, dan model mental yang sama dengan sisa bounded context-mu. Ketika domain model berubah, parser berubah bersamanya. Tidak ada file grammar yang menyimpang di direktori lain.

Di mana combinator gagal

Mereka tidak gratis. Parser recursive descent, yang dibangun combinator di balik layar, kesulitan dengan aturan left-recursive. Jika kamu menulis expr := expr + number | number, parser memanggil dirinya sendiri selamanya.

Kamu memperbaikinya dengan menulis ulang aturan left-recursive menjadi loop, atau dengan menggunakan library yang menangani left recursion untukmu. Untuk DSL kecil, ini jarang menjadi masalah praktis.

Performance adalah caveat lainnya. Parser recursive descent yang di-tune manual atau parser LR yang dihasilkan akan mengalahkan combinator dalam throughput murni. Untuk file config yang dibaca sekali saat startup, atau rule yang dievaluasi per request, perbedaannya adalah mikrodetik. Ukur sebelum mengasumsikan bahwa itu penting.

Cara mulai membangun milikmu sendiri

Mulailah dengan grammar sekecil mungkin. Parse satu konstruk, uji, lalu susun.

Jika kamu menulis TypeScript, library seperti parsimmon, arcsecond, atau chevrotain memberimu combinator production-ready dengan pesan error yang lebih baik dan penanganan left recursion daripada implementasi scratch di atas. Rust punya nom. Haskell punya Parsec. Python punya parsy.

Pattern-nya sama di mana saja: primitives, sequence, choice, repetition, transformation. Pelajari sekali, terapkan di bahasa apa pun.

FAQ

Apa itu parser combinator?

Parser combinator adalah higher-order function yang mengambil satu atau lebih parser dan mengembalikan parser baru. Mereka memungkinkanmu membangun parser kompleks dengan menyusun parser sederhana, menggunakan kode biasa alih-alih bahasa grammar yang terpisah.

Kapan saya masih harus menggunakan parser generator?

Gunakan generator ketika kamu mem-parse bahasa pemrograman lengkap, ketika kamu membutuhkan throughput parsing maksimal, atau ketika timmu sudah memiliki expertise mendalam dalam ekosistem generator tertentu. Untuk DSL kecil, biasanya tidak worth overhead-nya.

Apakah parser combinator lambat?

Mereka lebih lambat dari parser LR yang ditulis tangan atau dihasilkan, tetapi gap-nya tidak relevan untuk sebagian besar kasus penggunaan DSL. Parser combinator yang tipikal menangani ribuan token per milidetik. Itu cukup cepat untuk file config, query string, dan rule engine.

Bisakah saya menggunakan parser combinator dalam bahasa selain TypeScript?

Tentu saja. Pattern-nya tidak bergantung pada bahasa. nom di Rust, Parsec di Haskell, parsy di Python, dan attoparsec di Haskell adalah library yang matang dan banyak digunakan.

Lain kali kamu membutuhkan bahasa kecil di dalam bounded context, tanyakan pada dirimu sendiri apakah kamu benar-benar membutuhkan file grammar dan langkah code generation. Untuk sebagian besar DSL, jawabannya adalah tidak. Seratus baris kode combinator akan memberimu parser yang bisa kamu step through di debugger, perluas tanpa meregenerasi apa pun, dan benar-benar pahami enam bulan kemudian.