APLR(1): Un Algoritmo para Generar Parsers LR(1) Compactos y Robustos

El problema fundamental en la construcción de parsers para lenguajes de programación es equilibrar la capacidad expresiva de la gramática con la eficiencia y el tamaño del autómata de parsing generado. Los algoritmos LR(1) canónicos, aunque potentes, producen autómatas excesivamente grandes. LALR(1), una alternativa más compacta, introduce ambigüedades misteriosas que complican el desarrollo de gramáticas. La aparición de APLR(1) aborda esta tensión al ofrecer un método para generar parsers LR(1) compactos que preservan la "adecuación" del LR(1) canónico, eliminando los conflictos problemáticos sin sacrificar la eficiencia en tiempo de ejecución.

Históricamente, desde el descubrimiento del algoritmo LR(k) por Knuth en 1965, la investigación se ha centrado en reducir el tamaño del autómata sin perder la capacidad de reconocimiento. LALR(1) de DeRemer (1969) fue un avance práctico, pero sus limitaciones en el manejo de conflictos han persistido. Algoritmos posteriores como PGM LR(1) e IELR(1) buscaron mejorar la compacidad y la adecuación, pero a menudo con una complejidad conceptual o de implementación significativa. APLR(1) se posiciona como una solución más sencilla y robusta, especialmente relevante en un contexto donde las gramáticas de lenguajes modernos son cada vez más complejas y ambiguas, y donde la depuración de conflictos en parsers es una tarea costosa.

Arquitectura del Sistema

APLR(1) opera en dos fases principales sobre un autómata LR(1) canónico (opcionalmente resuelto). Primero, realiza una búsqueda exhaustiva de subgrafos de estados isocóricos que pueden ser remergidos sin alterar el lenguaje reconocido. Un estado isocórico se refiere a un conjunto de ítems LR(0) idénticos, pero con diferentes conjuntos de lookahead (ítems LR(1)). La compatibilidad para la remerger se evalúa transitivamente, considerando transiciones de tipo shift, reduce y goto. Para que dos subgrafos sean remergeables, sus transiciones de salida deben cumplir criterios específicos: shifts a estados sucesores iguales o transitivamente remergeables; reducciones idénticas o acciones disjuntas; y gotos a estados sucesores iguales o transitivamente remergeables.

La segunda fase consiste en la remerger y reindexación de todos los conjuntos de estados compatibles descubiertos. El algoritmo es voraz (greedy), lo que significa que el orden de las pruebas de remergeabilidad puede influir en el autómata resultante, produciendo autómatas compactos pero no necesariamente globalmente mínimos (un problema NP-hard). La implementación de Hocc utiliza una cola de trabajo para procesar los "state nubs" (representaciones de conjuntos de ítems LR(1) antes de la expansión completa del estado) en un orden aproximadamente breadth-first, asegurando una indexación consistente. La corrección de lookahead (LAC) es una mitigación implementada para manejar errores de sintaxis que pueden surgir de secuencias de acciones de reducción en estados remergidos, capturando y restaurando el estado del parser antes de la reducción si se encuentra un error.

Fundamentos Teóricos

El problema de la minimización de autómatas de parsing se remonta a los trabajos fundacionales de Donald Knuth sobre los algoritmos LR(k) en 1965. La búsqueda de parsers más compactos y eficientes ha sido un tema recurrente en la teoría de compiladores. El algoritmo LALR(1) de Frank DeRemer (1969) fue una de las primeras soluciones prácticas para reducir el tamaño del autómata LR(1) canónico, aunque a costa de introducir ambigüedades. El concepto de APLR(1) de remerger de estados para obtener autómatas compactos tiene paralelos con la minimización de autómatas finitos deterministas (DFA), un problema bien estudiado en la teoría de la computación. La minimización de DFA es un problema clásico con algoritmos eficientes como el de Hopcroft, pero la minimización de autómatas LR(1) es NP-hard, como lo demuestra el trabajo de Wuu Yang (2021).

La conexión con la academia también se extiende a los algoritmos de "lane tracing" como IELR(1) (Denny y Malloy, 2010), que buscan eliminar las inadecuaciones de LALR(1) mediante la división selectiva de estados. APLR(1) puede verse como un dual de IELR(1) en el sentido de que, en lugar de dividir estados para resolver conflictos, fusiona estados que no introducen conflictos. La idea de generar un autómata canónico y luego minimizarlo fue planteada por François Pottier en 2015, lo que sugiere que el concepto subyacente a APLR(1) ha sido una línea de pensamiento independiente en la comunidad de compiladores.