Los parser combinators son una técnica para construir analizadores sintácticos componiendo pequeñas funciones que reconocen unidades de texto. Este tutorial explica, de forma práctica y accesible, cómo construir una biblioteca mínima de análisis sintáctico usando Scheme, aunque los principios son aplicables a cualquier lenguaje con funciones de primera clase y clausuras, como JavaScript, Python o Rust.
El artículo parte de una motivación concreta: el autor quiere reescribir en Gambit un proyecto propio, un lanzador de dados, y dotarlo de un pequeño lenguaje para interpretar tiradas. Ante la ausencia de bibliotecas de parsing en Gambit, decide crear la suya propia y documentar el proceso. Antes de entrar al código, define qué es un combinador (una función que combina o modifica otras funciones, como compose, flip o complement) y aplica esa idea a los analizadores: cada parser es una función que toma una entrada y, si coincide, devuelve el texto reconocido junto con el resto pendiente.
A partir de la definición formal de las expresiones regulares, identifica los cinco elementos mínimos necesarios: un parser de fin de entrada (eof), un parser de una sola unidad (char), y tres combinadores — secuencia, alternancia y cerradura de Kleene (cero o más repeticiones). Con esos cinco bloques se obtiene una biblioteca completa, a la que luego se le añaden atajos como «uno o más», implementado como una secuencia seguida de «muchas» repeticiones.
El texto muestra el código en Scheme para los parsers constantes (eof y char) y avanza hacia el combinador de secuencia (seq). Compara los parser combinators con herramientas como regex (más potentes que estas) y con generadores LL o LR como Bison (más rápidos, pero menos legibles). También señala una trampa habitual: las gramáticas recursivas por la izquierda provocan bucles infinitos, un problema que se aborda tanto en el diseño de la gramática como en el código del parser.