Pratt parsing: la caja negra que simplifica tu parser

El algoritmo de Pratt cabe en 9 líneas y no ha cambiado desde 1973

Un parser de Pratt completo puede ocupar apenas 9 líneas de código en un lenguaje de alto nivel como Rhombus. Y ese es, según el autor del análisis, el dato menos importante de todos: el algoritmo no ha cambiado desde 1973 y no necesita cambiar. Lo que un equipo de ingeniería necesita entender no es su implementación, sino las propiedades que habilita.

La comparación que plantea el artículo es directa: nadie exige saber implementar un sistema de archivos desde cero para usar archivos, ni entender el quicksort para ordenar una lista. Con Pratt pasa lo mismo. El autor relata que escribió la base de un compilador fuertemente apoyado en Pratt sin detenerse a entender el fragmento de código en detalle.

Por qué importa para un founder: el costo real de un parser no está en escribirlo, sino en mantenerlo. Cada gramática nueva, cada operador nuevo y cada extensión del lenguaje se traduce en horas de ingeniería. Elegir una arquitectura de parsing que reduzca ese costo es una decisión de producto, no un detalle académico.

Nuds y leds: el cambio de mentalidad que lo cambia todo

La cita que el artículo destaca es de Douglas Crockford, en su charla de GOTO 2013: "Pratt toma el parsing, que es algo realmente complicado, y lo reduce a una sola pregunta: ¿qué esperamos ver a la izquierda de un token?".

Esa pregunta es todo el framework. En Pratt se registran acciones semánticas para dos categorías:

• Nud (null denotation): un token que no espera nada a su izquierda.
• Led (left denotation): un token que sí espera algo a su izquierda.

El cambio de fondo es dónde se engancha la lógica. Las técnicas tradicionales registran acciones semánticas en reglas de producción, es decir en símbolos no terminales, como muestra el ejemplo que el artículo toma del manual de GNU Bison. Pratt las registra en los terminales mismos. Ese solo desplazamiento explica casi todas las ventajas.

Un caso concreto que el artículo usa: el paréntesis de apertura en una llamada a función siempre espera algo a su izquierda, así que es un led. Con eso, parsear llamadas a funciones deja de ser un problema de gramática y pasa a ser una entrada en una tabla.

Qué gana un equipo de ingeniería al adoptar Pratt

El artículo enumera propiedades que se derivan de ese único cambio de diseño:

• No hay problemas de recursión por la izquierda. La acción semántica se despacha con el token ya consumido del stream, así que la recursión por izquierda simplemente no ocurre.
• No hay backtracking. El motor no prueba alternativas ni retrocede, lo que elimina el dilema clásico entre velocidad y memoria que aparece en comparaciones como PEG frente a packrat.
• Las acciones semánticas se ejecutan exactamente una vez. No hace falta revertir estado si un match falla, así que las acciones pueden tener efectos secundarios. El autor los usa para reservar y liberar nombres en el ámbito léxico, aunque advierte contra abusar de ellos.
• La acción semántica siempre sabe que es el match correcto, así que puede mirar hacia adelante lo que quiera. Eso permite anidar parsers PEG o parsers de Pratt dentro de las propias acciones.
• Las ambigüedades de gramática se convierten en colisiones de tabla, lo que reduce el tiempo dedicado a los casos simples.
• Los huecos en las tablas son puntos de extensión. Se pueden llenar en respuesta al texto ya parseado, lo que abre la puerta a macros y a lenguajes que extienden sus propios operadores.

El contraste con la escuela tradicional es el argumento más fuerte para un CTO: extender una gramática basada en reglas de producción es, en palabras del artículo, un trabajo con la complejidad de una investigación de doctorado.

Los contratos que debes respetar para usar Pratt como caja negra

Tratar Pratt como caja negra no significa ignorar sus reglas. El artículo enumera los contratos mínimos:

• Solo los tokens con un led asociado necesitan un valor en la tabla de binding power.
• Nunca asignes binding power cero a un led.
• Separadores como la coma, y tokens de error o fin de archivo, deben tener binding power cero.
• Si escribes en decimal, usa incrementos de 10 en la tabla: el espacio extra entre operadores habilita trucos.

Para asociatividad de derecha a izquierda, el truco estándar es usar bp - 1 en lugar de bp. El artículo es explícito: por qué funciona no importa hoy, importa saber que existe.

Modal lexing: el truco que multiplica lo que puedes parsear

El artículo dedica una sección al lexer, la parte que suele quedar más descuidada. Como el parser de Pratt es minúsculo, el lexer termina siendo el componente más grande del proyecto. Y cada nud y cada led es, en la práctica, un subparser: el lexer es el único punto en común entre todos ellos.

De ahí que la técnica de lexing más importante para quien adopta Pratt sea el modal lexing: agregar un parámetro al lexer para que reciba retroalimentación del parser. Los lexers nunca conocen la estructura gramatical; el parser sí. Alimentar esa información de vuelta permite composiciones de lenguaje donde cada sublenguaje tiene definiciones de tokens en conflicto.

El ejemplo que da el artículo es Rust, que tiene un sublenguaje distinto solo para expresar tipos, delimitado después de los dos puntos y hasta el signo igual o un delimitador. Con modal lexing, cada sublenguaje tiene su propio parser de Pratt.

Dos advertencias prácticas: el lexer debe tener un diseño de tipo pull y no lexear todos los tokens por adelantado, y no debe hacer IO ni bufferizar nada. Trabajar sobre una copia del lexer debe ser barato, lo que habilita lookahead arbitrario.

¿Qué significa esto para tu startup?

Primero, evalúa el costo de mantenimiento, no el de la primera versión. Si tu producto depende de un DSL, un motor de reglas, un lenguaje de configuración o un compilador interno, la gramática va a cambiar muchas veces. Una arquitectura donde extender el lenguaje es agregar una entrada en una tabla es una ventaja competitiva concreta: puedes responder a clientes enterprise que piden sintaxis propia sin abrir un proyecto de meses.

Segundo, no bloquees a tu equipo pidiendo que entienda el algoritmo. El artículo es claro: la abstracción es la herramienta. Si alguien del equipo necesita modificar el algoritmo de Pratt para acomodar su forma de pensar, está perdiendo el punto. El autor menciona que Alex Kladov cambió el algoritmo en 2020 para hacer ese tipo de concesiones, y lo señala como un error que él mismo cometió una vez.

Acciones concretas para esta semana:

• Si vas a construir un parser, empieza por la tabla de nuds y leds, no por el motor. Ahí vive la mayor parte de tu lógica de negocio.
• Reserva un incremento de 10 en la tabla de binding power desde el día uno. Cambiar la escala después es un refactor innecesario.
• Diseña el lexer como copiable y sin efectos secundarios. Es la decisión que más te va a habilitar después.

Limitaciones que conviene conocer antes de decidir

Pratt no es una bala de plata. El artículo lo deja claro:

• Requiere un lexer separado. A diferencia de motores scannerless como PEG.
• No parsea sentencias. Hay que combinarlo con otras técnicas para lenguajes con statements.
• No sirve para parsing incremental, como el que usa tree-sitter con GLR.

También hay una advertencia sobre el ecosistema de tutoriales. El autor señala que la mayoría dedica todo el espacio a explicar el algoritmo y ninguno a las propiedades que importan. El único recurso que recomienda para alguien sin exposición previa es la charla de Crockford. Y menciona el post de Andy Chu sobre parsers de Pratt sin herencia prototipal, que contrasta dos estilos opuestos de escribirlos.

Conclusión

Pratt no es solo precedence climbing. Es una forma de organizar el código. Aprenderlo primero como caja negra ayuda justamente a no reducirlo a una variación de precedence climbing. El algoritmo no ha cambiado desde 1973, cabe en 9 líneas y su valor no está ahí: está en el cambio de mentalidad que obliga a razonar en términos de nuds y leds, y en las propiedades que eso desbloquea.

Para un founder técnico, la lección es de arquitectura: las mejores decisiones de infraestructura son las que reducen el costo de los cambios futuros. Pratt es una de ellas.

Nota de verificación: la búsqueda web realizada no devolvió datos adicionales verificables sobre el tema. Este análisis se basa exclusivamente en el artículo original.

Fuentes

• Pratt parsing is a black box (fuente original)