Si vous avez déjà ouvert un fichier de grammaire Yacc et vous êtes demandé pourquoi construire un langage nécessite d’apprendre un deuxième langage, vous n’êtes pas seul. Les générateurs de parsers sont puissants, mais pour les petits DSLs qui émergent naturellement à l’intérieur de contextes bornés, ils sont presque toujours surdimensionnés.
Vous pouvez écrire un parser dans le même langage que le reste de votre application. Pas d’étapes de build, pas de fichiers de grammaire, pas de code généré que vous ne pouvez pas debugger.
Les générateurs de parsers résolvent un problème que vous n’avez probablement pas
Les générateurs de parsers comme ANTLR, Bison ou PEG.js vous obligent à exprimer votre grammaire dans un métalangage spécifique au domaine. Vous écrivez un fichier .g4 ou .y, exécutez un outil, obtenez du code source généré, l’importez et espérez que les messages d’erreur auront un sens quand quelque chose casse.
Pour un langage de programmation complet, ce trade-off en vaut la peine. Les parsers LR générés sont rapides, et la séparation entre grammaire et implémentation est propre.
Mais la plupart d’entre nous ne construisons pas de langages de programmation. Nous construisons des filtres de query, des formats de config, des rule engines ou de minuscules expression languages qui vivent à l’intérieur d’un seul bounded context. L’overhead d’un générateur de parsers, une étape de build séparée et une deuxième syntaxe à apprendre est une friction pure.
Les combinateurs de parsers transforment le parsing en code ordinaire
Les combinateurs de parsers sont des fonctions qui retournent des parsers, et les parsers sont des fonctions qui consomment de l’input et retournent soit une valeur parsée, soit une erreur. Vous composez de petits parsers en parsers plus grands à l’aide de higher-order functions.
Un parser pour la string "hello" est une fonction. Un parser pour "hello" OR "world" est une fonction qui essaie le premier, et s’il échoue, essaie le second. Un parser pour "hello" THEN "world" les exécute en séquence et combine les résultats.
Cela signifie que votre grammaire n’est que du code. Vous le debuggez avec un breakpoint, pas avec un outil de visualisation de grammaire.
Un parser arithmétique fonctionnel en 40 lignes de TypeScript
Voici un parser complet pour un minuscule language d’expressions. Il gère les entiers et l’addition entre parenthèses. Pas de dependencies, pas de fichiers générés.
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 }Décortiquons ce qui se passe réellement. str, regex et number sont des parsers primitifs. seq exécute des parsers dans l’ordre. or essaie des alternatives. map transforme le résultat. lazy est le seul élément subtil. Il diffère l’évaluation pour que les grammaires récursives n’explosent pas au moment de la définition.
Le type system trace ce que chaque parser produit. Quand le parsing échoue, vous obtenez la position exacte et le token attendu. C’est déjà un meilleur error reporting que la plupart des parsers générés ne vous offrent out of the box.
Pourquoi cela correspond particulièrement bien aux bounded contexts
Les bounded contexts en Domain-Driven Design sont intentionnellement petits. Un DSL qui vit à l’intérieur de l’un d’eux devrait être petit aussi. Il a besoin exactement des constructes dont ce context se soucie, et rien d’autre.
Les combinateurs de parsers se mettent à l’échelle admirablement vers le bas. Vous écrivez le parser pour le seul query filter dont votre domaine a besoin, pas pour un language de query à usage général. Vous ajoutez un nouveau constructe en ajoutant une nouvelle fonction, pas en régénérant mille lignes de C.
Le parser vit dans le même repository, le même langage et le même modèle mental que le reste de votre bounded context. Quand le domain model change, le parser change avec lui. Il n’y a pas de fichier de grammaire qui dérive hors synchronisation dans un autre répertoire.
Où les combinateurs atteignent leurs limites
Ils ne sont pas gratuits. Les parsers par recursive descent, ce que les combinateurs construisent sous le capot, ont du mal avec les règles left-recursive. Si vous écrivez expr := expr + number | number, le parser s’appelle lui-même éternellement.
Vous corrigez cela en réécrivant les règles left-recursive en loops, ou en utilisant une library qui gère la left recursion pour vous. Pour les petits DSLs, c’est rarement un problème pratique.
La performance est l’autre caveat. Un parser recursive descent affiné à la main ou un parser LR généré battra les combinateurs en throughput brut. Pour un fichier de config lu une fois au démarrage, ou une rule évaluée par requête, la différence est de microsecondes. Mesurez avant de supposer que cela compte.
Comment commencer à construire le vôtre
Commencez avec la grammaire la plus petite possible. Parsez un constructe, testez-le, puis composez.
Si vous écrivez du TypeScript, des libraries comme parsimmon, arcsecond ou chevrotain vous donnent des combinateurs prêts pour la production avec de meilleurs messages d’erreur et une gestion de la left recursion que l’implémentation scratch ci-dessus. Rust a nom. Haskell a Parsec. Python a parsy.
Le pattern est le même partout : primitives, sequence, choice, repetition, transformation. Apprenez-le une fois, appliquez-le dans n’importe quel langage.
FAQ
Qu’est-ce qu’un parser combinator ?
Un parser combinator est une higher-order function qui prend un ou plusieurs parsers et retourne un nouveau parser. Ils vous permettent de construire des parsers complexes en composant des parsers simples, en utilisant du code ordinaire au lieu d’un langage de grammaire séparé.
Quand devrais-je encore utiliser un parser generator ?
Recourez à un generator quand vous parsez un langage de programmation complet, quand vous avez besoin d’un throughput de parsing maximal, ou quand votre équipe a déjà une expertise approfondie dans un écosystème de generator spécifique. Pour les petits DSLs, ce n’est généralement pas worth l’overhead.
Les parser combinators sont-ils lents ?
Ils sont plus lents que les parsers LR écrits à la main ou générés, mais l’écart est irrelevant pour la plupart des cas d’usage de DSLs. Un parser combinator typique traite des milliers de tokens par milliseconde. C’est assez rapide pour les fichiers de config, les query strings et les rule engines.
Puis-je utiliser des parser combinators dans des langages autres que TypeScript ?
Absolument. Le pattern est indépendant du langage. nom en Rust, Parsec en Haskell, parsy en Python et attoparsec en Haskell sont toutes des libraries matures et largement utilisées.
La prochaine fois que vous aurez besoin d’un minuscule langage à l’intérieur d’un bounded context, demandez-vous si vous avez vraiment besoin d’un fichier de grammaire et d’une étape de code generation. Pour la plupart des DSLs, la réponse est non. Une centaine de lignes de code combinator vous donneront un parser que vous pouvez traverser pas à pas dans un debugger, étendre sans rien régénérer, et réellement comprendre six mois plus tard.