Parser combinators en TypeScript, paso a paso

⏱️ Lectura: 15 min

Una regex para separar fecha, hora y zona horaria funciona hasta que aparece un formato que no previste, y ahí hay que reescribir la expresión completa desde cero. Los parser combinators resuelven ese problema de otra manera: en vez de una expresión gigante, componés funciones chicas que se van pasando el resto del texto entre sí, como piezas que encajan.

📑 En este artículo

1. TL;DR
2. ¿Qué es parser combinators?
3. Por qué importan los combinadores de parsers
4. Cómo funcionan los parsers combinables
   1. El parser más chico posible
   2. Secuencias con pSeq
   3. Transformar resultados con pMap y elegir con pOr
5. Ejemplos prácticos y cómo empezar
   1. Cómo empezar
6. Casos de uso reales
7. Errores comunes y buenas prácticas
8. Comparativa con alternativas
9. Profundizando: de dónde viene esta idea
10. Preguntas frecuentes
    1. ¿Los parser combinators reemplazan una gramática formal como BNF?
    2. ¿Qué diferencia hay entre parsers combinables y expresiones regulares?
    3. ¿El parsing combinatorio es más lento que un parser generado?
    4. ¿Necesito saber programación funcional para usar combinadores de parsers?
    5. ¿Qué librerías de parsing combinatorio existen en JavaScript o TypeScript?
    6. ¿Los parsers combinables sirven para compiladores de lenguajes completos?
11. Referencias
    1. 📚 Artículos relacionados

TL;DR

• Un parser es una función que recibe texto y devuelve el valor extraído junto con lo que falta por leer.
• pSeq, pMap y pOr arman analizadores complejos sin escribir una gramática BNF por separado.
• TypeScript tipa cada parser como Parser<T> y el compilador avisa si mezclás tipos distintos.
• Parsimmon aplica esta técnica en JavaScript para parsear JSON, fechas o configuraciones propias.
• pBind deja que un valor ya leído decida cómo parsear lo que sigue, útil para campos de longitud variable.

¿Qué es parser combinators?

Parser combinators es el nombre de una técnica de programación funcional para construir analizadores sintácticos combinando funciones pequeñas y puras. Cada función, llamada parser, recibe una cadena de texto y devuelve el valor extraído junto con el resto sin consumir. Combinarlos permite armar parsers complejos sin escribir una gramática formal aparte.

Pensalo como una línea de ensamblaje: cada estación toma la pieza que le pasó la anterior, hace su trabajo puntual y entrega el resto a la siguiente estación. Ninguna estación necesita saber qué hace el resto de la línea, así que podés reordenar, quitar o agregar estaciones sin tocar las demás.

Por qué importan los combinadores de parsers

Entre una regex de una línea y un generador de parsers como ANTLR hay un vacío enorme. El blog de T3 lo plantea con dos extremos. Una regex se vuelve ilegible apenas el formato tiene estructura anidada, y tree-sitter, la librería que impulsa el resaltado de sintaxis de muchos editores de código, es demasiado pesada para un parser que vas a usar una sola vez. Los combinadores de parsers ocupan ese punto medio.

La ventaja aparece en el trabajo diario de un backend: parsear una cabecera HTTP propia, un formato de log, un mini lenguaje de configuración o un protocolo binario simple. Ninguno de esos casos justifica instalar un generador de gramáticas, pero todos se vuelven frágiles con una sola regex gigante que nadie quiere tocar después.

Cómo funcionan los parsers combinables

Así es como los parser combinators consumen la cadena de entrada paso a paso: cada parser recibe el string completo que falta procesar, se queda con la porción que entiende y devuelve el resto para el siguiente. El tipo que describe esa idea en TypeScript es compacto.

type Parser<T> = (input: string) => [T, string];

Un Parser<T> es una función de un string a una tupla con el valor T y el string restante. No hay clase, no hay estado compartido, no hay configuración previa que inicializar.

flowchart LR
A["Texto de entrada"] --> B["Parser 1 consume una parte"]
B --> C["Parser 2 consume la siguiente parte"]
C --> D["Parser 3 consume el resto"]
D --> E["Resultado final y string vacio"]

El parser más chico posible

El parser más simple reconoce dígitos y los convierte en número.

const pNumber: Parser<number> = (input) => {
  const match = input.match(/^\d+/);
  if (match === null) throw new Error("se esperaba un numero");
  const digits = match[0];
  return [Number(digits), input.slice(digits.length)];
};

console.log(pNumber("42 manzanas"));

La salida es [ 42, ' manzanas' ]. El parser cortó los dígitos iniciales y devolvió el número junto con todo lo que todavía no se procesó.

Secuencias con pSeq

Un solo parser no alcanza para nada real. pSeq encadena varios parsers pasando el resto de uno como entrada del siguiente.

sequenceDiagram
participant P as pSeq
participant A as pVerbo
participant B as pEspacio
participant C as pNumber
P->>A: entrada completa
A-->>P: devuelve verbo y resto
P->>B: resto despues del verbo
B-->>P: devuelve espacio y resto
P->>C: resto despues del espacio
C-->>P: devuelve numero y resto final
Note over P: combina los tres resultados en una tupla

const pLiteral = (texto: string): Parser<string> => (input) => {
  if (!input.startsWith(texto)) throw new Error(`se esperaba "${texto}"`);
  return [texto, input.slice(texto.length)];
};

function pSeq<T extends unknown[]>(
  ...parsers: { [K in keyof T]: Parser<T[K]> }
): Parser<T> {
  return (input) => {
    const resultados: unknown[] = [];
    let resto = input;
    for (const parser of parsers) {
      const [valor, nuevoResto] = parser(resto);
      resultados.push(valor);
      resto = nuevoResto;
    }
    return [resultados as T, resto];
  };
}

const pMetodo = pLiteral("GET");
const pEspacio = pLiteral(" ");
const pLinea = pSeq(pMetodo, pEspacio, pNumber);

console.log(pLinea("GET 200 restante"));

La salida es [ [ 'GET', ' ', 200 ], ' restante' ]. Cada parser de la secuencia se quedó con su porción y el último dejó el resto sin tocar.

Transformar resultados con pMap y elegir con pOr

pMap aplica una función al valor ya extraído sin tocar el resto del string, y pOr prueba varias alternativas en orden hasta encontrar la primera que no lance error.

function pMap<A, B>(parser: Parser<A>, fn: (valor: A) => B): Parser<B> {
  return (input) => {
    const [valor, resto] = parser(input);
    return [fn(valor), resto];
  };
}

function pOr<T>(...parsers: Parser<T>[]): Parser<T> {
  return (input) => {
    for (const parser of parsers) {
      try {
        return parser(input);
      } catch {
        continue;
      }
    }
    throw new Error("ninguna alternativa coincidio");
  };
}

const pVerboHttp = pOr(pLiteral("GET"), pLiteral("POST"), pLiteral("DELETE"));

const pEntradaLog = pMap(
  pSeq(pVerboHttp, pEspacio, pNumber),
  ([verbo, _, status]) => ({ verbo, status })
);

console.log(pEntradaLog("POST 201 ok"));

La salida es [ { verbo: 'POST', status: 201 }, ' ok' ]. El parser combinado ya devuelve un objeto útil, no una tupla posicional que hay que recordar cómo leer.

flowchart TD
A["Parsers basicos: pNumber, pLiteral"] --> B["Combinadores de secuencia: pSeq"]
A --> C["Combinadores de eleccion: pOr"]
B --> D["Combinadores de transformacion: pMap"]
C --> D
D --> E["Combinadores de repeticion: pSepBy"]
E --> F["Combinadores dependientes: pBind"]

Ejemplos prácticos y cómo empezar

El combinador que falta para casos reales es el de repetición. pSepBy parsea una lista de ítems separados por un delimitador, algo que una regex puede hacer para casos chicos pero que se vuelve ilegible con separadores anidados.

function pSepBy<T>(item: Parser<T>, separador: Parser<unknown>): Parser<T[]> {
  return (input) => {
    const items: T[] = [];
    let resto = input;
    while (true) {
      try {
        const [valor, nuevoResto] = item(resto);
        resto = nuevoResto;
        items.push(valor);
        const [, despuesDeSeparador] = separador(resto);
        resto = despuesDeSeparador;
      } catch {
        break;
      }
    }
    return [items, resto];
  };
}

const pListaNumeros = pSepBy(pNumber, pLiteral(","));
console.log(pListaNumeros("10,20,30 fin"));

La salida es [ [ 10, 20, 30 ], ' fin' ]. El bucle usa while en lugar de recursión a propósito: la recursión en JavaScript y TypeScript no hace tail-call optimization, así que una lista de miles de ítems resuelta de forma recursiva puede desbordar la pila.

Cómo empezar

Para correr estos ejemplos tal cual, necesitás Node.js instalado (versión 18 o superior) y nada más. Los comandos son los mismos en Linux, macOS y Windows con PowerShell, porque son comandos de npm y no del shell del sistema.

mkdir parser-combinators-demo && cd parser-combinators-demo
npm init -y
npm install --save-dev typescript ts-node @types/node
npx tsc --init

Con el proyecto creado, guardá el código de los ejemplos anteriores en un archivo parser.ts y corrélo con:

npx ts-node parser.ts

Para confirmar que el tipado funciona de verdad, cambiá pNumber por un parser que devuelva string dentro de pSeq(pMetodo, pEspacio, pNumber) y corré npx tsc --noEmit. El compilador tiene que fallar con un error de tipos en esa línea, antes de ejecutar nada.

Casos de uso reales

Los parsers combinables aparecen en el código de producción con más frecuencia de la que parece. Un equipo de backend los usa para leer líneas de log con un formato propio, donde cada campo tiene un tipo distinto y una regex terminaría con grupos de captura imposibles de mantener.

También sirven para lenguajes de configuración caseros, el tipo de sintaxis que un equipo inventa para su propia herramienta interna y que no justifica una gramática formal versionada aparte. Y aparecen en protocolos de red simples: formatos donde un campo indica la longitud del que sigue, como se ve más adelante en la sección de combinadores dependientes.

Parsimmon es la librería de parsing combinatorio más usada en el ecosistema de JavaScript y aplica exactamente esta idea para parsear JSON, fechas con formatos no estándar o lenguajes de plantillas propios, sin depender de un generador externo.

Errores comunes y buenas prácticas

• Orden en pOr: la primera alternativa que coincide gana, aunque no sea la más específica. Si pLiteral("GET") y pLiteral("GETX") compiten, poné primero la más larga o vas a cortar mal el texto.
• Espacios olvidados: si el formato permite espacios entre tokens, hay que consumirlos explícitamente en cada punto donde pueden aparecer, no solo al principio de la cadena completa.
• Recursión sin límite: un combinador de repetición escrito con recursión en vez de un bucle puede desbordar la pila con entradas largas, por eso pSepBy usa while en el ejemplo anterior.
• Excepciones como control de flujo: usar throw/catch para señalar que un parser falló es simple de leer, pero mezcla manejo de errores con lógica de parseo. Para producción conviene migrar a un tipo Result explícito que distinga éxito de fallo sin lanzar excepciones.
• Mensajes de error sin posición: un parser que solo dice «no coincide» es inútil para debuggear un archivo de miles de líneas. Hay que envolver cada parser para que reporte también el índice donde falló.

Comparativa con alternativas

Ninguna de estas técnicas es universalmente mejor; cada una resuelve un rango distinto de formatos.

Profundizando: de dónde viene esta idea

Los parser combinators heredan esta idea directamente de Parsec, la librería de Haskell de los años 90 que popularizó el patrón de componer parsers con operadores en lugar de generar código desde una gramática. La clave teórica es que cada parser implementa lo que en Haskell se llama una mónada, una estructura que define cómo encadenar operaciones que pueden fallar o depender del resultado anterior.

💭 Clave: pSeq y pMap alcanzan para combinar parsers independientes entre sí, pero no sirven cuando el segundo parser depende del valor que devolvió el primero, no solo de su tipo. Para eso hace falta un combinador más, pBind.

Un caso real de esa dependencia es un campo con longitud variable: primero se lee un número, y ese número dice cuántos caracteres leer después. Es el mismo patrón que usan el protocolo RESP de Redis y el formato bencode de BitTorrent.

function pBind<A, B>(parser: Parser<A>, fn: (valor: A) => Parser<B>): Parser<B> {
  return (input) => {
    const [valor, resto] = parser(input);
    return fn(valor)(resto);
  };
}

const pTomar = (n: number): Parser<string> => (input) => [input.slice(0, n), input.slice(n)];

const pCampoConLongitud: Parser<string> = pBind(pNumber, (longitud) =>
  pMap(pSeq(pLiteral(":"), pTomar(longitud)), ([, texto]) => texto)
);

console.log(pCampoConLongitud("5:holamundo"));

La salida es [ 'holam', 'undo' ]. pNumber lee el 5, y ese valor decide que pTomar debe cortar exactamente cinco caracteres después de los dos puntos. pSeq no podría expresar esto porque no conoce el valor del parser anterior, solo encadena su resto.

La otra pieza avanzada es el rendimiento del backtracking: cuando pOr prueba varias alternativas sobre la misma posición del texto, puede repetir trabajo si esas alternativas comparten un prefijo largo. La técnica clásica para evitarlo es el packrat parsing, que cachea el resultado de cada parser en cada posición de entrada para no volver a calcularlo.

📖 Resumen en Telegram: Ver resumen

Tu próximo paso: tomá el ejemplo de pSepBy de esta guía, modificalo para que ignore espacios opcionales antes y después de la coma usando un parser de espacios en blanco entre item y separador, y probalo contra "10, 20 ,30" para ver dónde falla.

Preguntas frecuentes

¿Los parser combinators reemplazan una gramática formal como BNF?

No necesariamente. Para lenguajes grandes y estables, una gramática declarativa que alimenta un generador como ANTLR sigue siendo más mantenible. Los combinadores de parsers brillan en formatos chicos o cambiantes donde versionar una gramática aparte no se justifica.

¿Qué diferencia hay entre parsers combinables y expresiones regulares?

Una regex describe un patrón plano con backtracking interno oculto. Un parser combinable es una función explícita que se puede testear, componer y tipar por separado; el costo es más código para resolver el mismo patrón simple.

¿El parsing combinatorio es más lento que un parser generado?

Puede serlo si el backtracking recorre la misma porción del texto varias veces. La solución clásica es el packrat parsing, que cachea el resultado de cada parser en cada posición para no repetir trabajo.

¿Necesito saber programación funcional para usar combinadores de parsers?

Ayuda entender funciones de orden superior, pero no hace falta Haskell ni mónadas para empezar. pSeq, pMap y pOr se leen y se escriben como cualquier función de TypeScript o JavaScript.

¿Qué librerías de parsing combinatorio existen en JavaScript o TypeScript?

Parsimmon es la más usada en el ecosistema de Node.js. También hay variantes pensadas para TypeScript puro, todas con la misma idea de parsers chicos combinados con funciones de orden superior.

¿Los parsers combinables sirven para compiladores de lenguajes completos?

Sí, con matices. Proyectos reales los usan para el frontend de lenguajes de tamaño moderado, pero cuando la gramática crece mucho el costo de mantenimiento suele empujar hacia un generador de parsers o un parser de descenso recursivo escrito a mano.

Referencias

• T3: Parser Combinators: el artículo original que inspira esta guía, con el tipo Parser<T> y los ejemplos de pSeq y pHello.
• Wikipedia: Parser combinator: definición y contexto histórico de la técnica.
• Parsimmon en GitHub: librería de parsing combinatorio para JavaScript usada en producción.
• ANTLR: generador de parsers de referencia para gramáticas grandes y formales.
• tree-sitter: librería de parsing incremental que impulsa el resaltado de sintaxis de editores modernos.

📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @programacion donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.

Imagen destacada: Foto de Max Chen en Unsplash