Analizador GLR

Un analizador GLR ( analizador de derivación generalizado de izquierda a derecha ) es una extensión de un algoritmo de analizador 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 libres de contexto generales 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 ha sido 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 GLR.

Aunque el algoritmo ha evolucionado desde sus versiones originales, sus principios se han mantenido intactos. Como se muestra en una publicación anterior, ^{[ 4 ]} Lang estaba interesado principalmente 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 forma exhaustiva y eficiente. Los analizadores LR estándar no pueden adaptarse a la naturaleza no determinista y ambigua del lenguaje natural, mientras que el algoritmo GLR sí.

En resumen, el algoritmo GLR funciona de manera similar al algoritmo de análisis sintáctico LR , con la diferencia de que, dada una gramática específica, un analizador GLR procesa todas las interpretaciones posibles de una entrada dada mediante una búsqueda en amplitud . En la etapa inicial, un generador de analizadores GLR convierte una gramática de entrada en tablas de análisis sintáctico, de manera similar a un generador LR. Sin embargo, mientras que las tablas de análisis LR permiten solo una transición de estado (dado un estado y un token de entrada), las tablas de análisis GLR permiten múltiples transiciones. En efecto, GLR permite conflictos de desplazamiento/reducción y reducción/reducción.

Cuando se encuentra una transición conflictiva, la pila de análisis se divide en dos o más pilas paralelas, donde el estado correspondiente a cada transición posible se ubica en la parte superior. A continuación, se lee el siguiente token de entrada y se utiliza para determinar la(s) siguiente(s) transición(es) para cada uno de los estados superiores; 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 puede descartarse.

Una optimización crucial, conocida como pila con estructura de grafo, permite compartir prefijos y sufijos comunes entre estas pilas, lo que limita el espacio de búsqueda y el uso de memoria necesarios para analizar el texto de entrada. Las estructuras complejas que surgen de esta mejora convierten el grafo de búsqueda en un grafo dirigido acíclico (con restricciones adicionales en la profundidad de los distintos 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³ ). Sin embargo, GLR presenta dos ventajas adicionales:

• El tiempo necesario para ejecutar el algoritmo es proporcional al grado de no determinismo de la gramática: en gramáticas deterministas, el algoritmo GLR se ejecuta en tiempo O ( n ) (esto no es cierto para los algoritmos de Earley y CYK, pero los algoritmos originales de Earley se pueden modificar para garantizarlo).
• El algoritmo GLR es " en línea ", es decir, consume los tokens de entrada en un orden específico y realiza la mayor cantidad de trabajo posible después de consumir cada token (esto también se aplica a Earley).

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 se resuelve generalmente con un número reducido (aunque posiblemente ilimitado) de tokens . En comparación con otros algoritmos capaces de manejar toda la clase 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", ya que solo una 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 ]}

• Comparación de generadores de analizadores sintácticos
• Kit de herramientas para la reingeniería de software de DMS
• GNU Bison , un generador de analizadores sintácticos que puede crear analizadores sintácticos LALR y GLR.
• Packrat parser , otro analizador que puede analizar lenguajes ambiguos y no deterministas.

• Grune, Dick; Jacobs, Ceriel JH (2008). Técnicas de análisis sintáctico . Springer Science+Business Media. ISBN 978-0-387-20248-8.
• Tomita, Masaru (1984). "Analizadores LR para lenguajes naturales". COLING . 10.ª Conferencia Internacional sobre Lingüística Computacional. pp. 354–357 . 
• Tomita, Masaru (1985). "Un algoritmo de análisis sintáctico libre de contexto eficiente para lenguajes naturales". IJCAI . Conferencia Internacional Conjunta sobre Inteligencia Artificial. págs. 756–764 .