Se alguma vez abriste um arquivo de gramática Yacc e te perguntaste por que construir uma linguagem exige aprender uma segunda linguagem, não estás sozinho. Os geradores de parsers são poderosos, mas para as pequenas DSLs que emergem naturalmente dentro de contextos limitados, são quase sempre excessivos.
Podes escrever um parser na mesma linguagem que o resto da tua aplicação. Sem passos de build, sem arquivos de gramática, sem código gerado que não consigas debugar.
Os geradores de parsers resolvem um problema que provavelmente não tens
Os geradores de parsers como ANTLR, Bison ou PEG.js forçam-te a expressar a tua gramática num metalinguagem específica do domínio. Escreves um arquivo .g4 ou .y, executas uma ferramenta, obténs código fonte gerado, importas-o e esperas que as mensagens de erro façam sentido quando algo parte.
Para uma linguagem de programação completa, este trade-off vale a pena. Os parsers LR gerados são rápidos, e a separação entre gramática e implementação é limpa.
Mas a maioria de nodes não está a construir linguagens de programação. Estamos a construir filtros de query, formatos de config, rule engines ou linguagens de expressão minúsculas que vivem dentro de um único bounded context. A sobrecarga de um gerador de parsers, um passo de build separado e uma segunda sintaxe a aprender é fricção pura.
Os combinadores de parsers transformam o parsing em código ordinário
Os combinadores de parsers são funções que devolvem parsers, e os parsers são funções que consomem input e devolvem ou um valor parseado ou um erro. Compones parsers pequenos em parsers maiores usando higher-order functions.
Um parser para a string "hello" é uma função. Um parser para "hello" OR "world" é uma função que tenta o primeiro, e se falhar, tenta o segundo. Um parser para "hello" THEN "world" executa-os em sequência e combina os resultados.
Isto significa que a tua gramática é apenas código. Debugas-no com um breakpoint, não com uma ferramenta de visualização de gramáticas.
Um parser aritmético funcional em 40 linhas de TypeScript
Aqui está um parser completo para uma linguagem de expressões minúscula. Lida com inteiros e adição entre parênteses. Sem dependencies, sem arquivos gerados.
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 }Vamos desconstruir o que realmente acontece. str, regex e number são parsers primitivos. seq executa parsers por ordem. or tenta alternativas. map transforma o resultado. lazy é a única peça subtíl. Diferencia a avaliação para que gramáticas recursivas não explodam no momento da definição.
O type system rastreia o que cada parser produz. Quando o parsing falha, obténs a posição exata e o token esperado. Isso já é um error reporting melhor do que a maioria dos parsers gerados oferece out of the box.
Por que isto se adequa particularmente bem aos bounded contexts
Os bounded contexts em Domain-Driven Design são intencionalmente pequenos. Uma DSL que vive dentro de um também deve ser pequena. Precisa exatamente dos construtos de que esse context se importa, e nada mais.
Os combinadores de parsers escalam lindamente para baixo. Escreves o parser para o único query filter de que o teu domínio precisa, não para uma linguagem de query de propósito geral. Adicionas um novo construto adicionando uma nova função, não regenerando mil linhas de C.
O parser vive no mesmo repository, na mesma linguagem e no mesmo modelo mental que o resto do teu bounded context. Quando o domain model muda, o parser muda com ele. Não há arquivo de gramática a desfasar-se noutro diretório.
Onde os combinadores falham
Não são de borla. Os parsers de recursive descent, que é o que os combinadores constroem por baixo, têm dificuldade com regras left-recursive. Se escreveres expr := expr + number | number, o parser chama-se a si próprio para sempre.
Corriges isto reescrevendo regras left-recursive em loops, ou usando uma library que trate da left recursion por ti. Para DSLs pequenas, raramente é um problema prático.
A performance é a outra ressalva. Um parser recursive descent afinado manualmente ou um parser LR gerado vencerá os combinadores em throughput puro. Para um arquivo de config lido uma vez no arranque, ou uma rule avaliada por pedido, a diferença é em microssegundos. Mede antes de assumir que importa.
Como começar a construir o teu
Começa com a gramática mais pequena possível. Faz parse de um construto, testa-o, depois compõe.
Se estiveres a escrever TypeScript, libraries como parsimmon, arcsecond ou chevrotain dão-te combinadores prontos para produção com melhores mensagens de erro e tratamento de left recursion do que a implementação scratch acima. Rust tem nom. Haskell tem Parsec. Python tem parsy.
O padrão é o mesmo em todo o lado: primitives, sequence, choice, repetition, transformation. Aprende-o uma vez, aplica-o em qualquer linguagem.
FAQ
O que é um parser combinator?
Um parser combinator é uma higher-order function que aceita um ou mais parsers e devolve um novo parser. Permitem-te construir parsers complexos compondo parsers simples, usando código ordinário em vez de uma linguagem de gramática separada.
Quando devo ainda usar um parser generator?
Recorre a um generator quando estás a fazer parse de uma linguagem de programação completa, quando precisas de throughput de parsing máximo, ou quando a tua equipa já tem expertise profunda num ecossistema de generator específico. Para DSLs pequenas, geralmente não vale a sobrecarga.
Os parser combinators são lentos?
São mais lentos do que parsers LR escritos à mão ou gerados, mas a diferença é irrelevante para a maioria dos casos de uso de DSLs. Um parser combinator típico processa milhares de tokens por milissegundo. Isso é suficientemente rápido para arquivos de config, query strings e rule engines.
Posso usar parser combinators em linguagens que não sejam TypeScript?
Absolutamente. O padrão é independente da linguagem. nom em Rust, Parsec em Haskell, parsy em Python e attoparsec em Haskell são todas libraries maduras e amplamente utilizadas.
Da próxima vez que precisares de uma linguagem minúscula dentro de um bounded context, pergunta a ti mesmo se realmente precisas de um arquivo de gramática e um passo de code generation. Para a maioria das DSLs, a resposta é não. Cem linhas de código combinator dar-te-ão um parser em que podes fazer step through no debugger, estender sem regenerar nada, e realmente compreender seis meses depois.