Un analizador sintáctico GLR ( generalized left-to-right rightmost derivation parser ) es una extensión de un algoritmo de analizador sintáctico LR para manejar gramáticas no deterministas y ambiguas . [1] La base teórica fue proporcionada en un artículo de 1974 [2] por Bernard Lang (junto con otros analizadores sintácticos generales libres de contexto como GLL). Describe una forma sistemática de producir tales algoritmos y proporciona resultados uniformes con respecto a las pruebas de corrección, la complejidad con respecto a las clases de gramática y las técnicas de optimización. La primera implementación real de GLR fue descrita en un artículo de 1984 por Masaru Tomita , también se lo ha denominado "analizador paralelo". Tomita presentó cinco etapas en su trabajo original, [3] aunque en la práctica es la segunda etapa la que se reconoce como el analizador sintáctico GLR.
Aunque el algoritmo ha evolucionado desde sus formas originales, los principios se han mantenido intactos. Como se muestra en una publicación anterior, [4] Lang estaba principalmente interesado en analizadores sintácticos más fáciles de usar y más flexibles para lenguajes de programación extensibles . El objetivo de Tomita era analizar texto en lenguaje natural de manera exhaustiva y eficiente. Los analizadores sintácticos LR estándar no pueden adaptarse a la naturaleza no determinista y ambigua del lenguaje natural , y el algoritmo GLR sí puede.
Brevemente, el algoritmo GLR funciona de manera similar al algoritmo del analizador sintáctico LR , excepto que, dada una gramática particular, un analizador sintáctico GLR procesará todas las interpretaciones posibles de una entrada dada en una búsqueda en amplitud . En el front-end, un generador de analizador sintáctico GLR convierte una gramática de entrada en tablas de analizador sintáctico, de manera similar a un generador LR. Sin embargo, mientras que las tablas de análisis sintáctico LR permiten solo una transición de estado (dado un estado y un token de entrada), las tablas de análisis sintáctico GLR permiten múltiples transiciones. En efecto, GLR permite conflictos de cambio/reducción y reducción/reducción.
Cuando se encuentra una transición conflictiva, la pila de análisis se bifurca en dos o más pilas de análisis paralelas, donde el estado correspondiente a cada transición posible está en la parte superior. Luego, se lee el siguiente token de entrada y se lo utiliza para determinar la(s) siguiente(s) transición(es) para cada uno de los estados "superiores" y pueden producirse más bifurcaciones. Si un estado superior y un token de entrada determinados no dan como resultado al menos una transición, entonces esa "ruta" a través de las tablas de análisis no es válida y se puede descartar.
Una optimización crucial conocida como pila estructurada en grafos permite compartir prefijos y sufijos comunes de estas pilas, lo que limita el espacio de búsqueda general y el uso de memoria necesarios para analizar el texto de entrada. Las estructuras complejas que surgen de esta mejora hacen que el grafo de búsqueda sea un grafo acíclico dirigido (con restricciones adicionales en las "profundidades" de varios nodos), en lugar de un árbol.
El reconocimiento mediante el algoritmo GLR tiene la misma complejidad temporal en el peor de los casos que el algoritmo CYK y el algoritmo Earley : O ( n 3 ). [ cita requerida ] Sin embargo, GLR conlleva dos ventajas adicionales:
En la práctica, las gramáticas de la mayoría de los lenguajes de programación son deterministas o "casi deterministas", lo que significa que cualquier no determinismo suele resolverse dentro de un número pequeño (aunque posiblemente ilimitado) de tokens [ cita requerida ] . En comparación con otros algoritmos capaces de manejar la clase completa de gramáticas libres de contexto (como el analizador Earley o el algoritmo CYK ), el algoritmo GLR ofrece un mejor rendimiento en estas gramáticas "casi deterministas", porque solo una única pila estará activa durante la mayor parte del proceso de análisis.
GLR se puede combinar con el algoritmo LALR (1), en un analizador híbrido, lo que permite un rendimiento aún mayor. [5]