Analizador GLR (del inglés. Analizador de derivación generalizado de izquierda a derecha - Analizador de almacenamiento ascendente generalizado ): en informática , un algoritmo de analizador LR extendido , diseñado para analizar gramáticas no deterministas y ambiguas . Descrito por primera vez por Masaru Tomita en 1984 , también se le llama "parser paralelo" .
Dado que este algoritmo se deriva del analizador LR, los principios de su funcionamiento siguen siendo los mismos: Tomita se fijó el objetivo de lograr un reconocimiento rápido y eficiente de los textos escritos en lenguaje natural . El analizador LR normal no puede resolver la indeterminación y la ambigüedad de los lenguajes naturales, mientras que el algoritmo GLR sí puede.
El algoritmo GLR funciona exactamente como el algoritmo LR , excepto que para una gramática determinada, el analizador GLR procesa todas las interpretaciones posibles de la secuencia de entrada mediante la búsqueda en amplitud . Los generadores de analizadores GLR convierten la gramática original en tablas de analizadores, al igual que los generadores de analizadores LR. Pero, mientras que las tablas del analizador LR permiten solo una transición de estado (definida por el estado inicial del analizador y el símbolo del terminal de entrada), las tablas del analizador GLR permiten muchos estados resultantes. Como resultado, el algoritmo GLR permite cambiar/reducir y reducir/reducir conflictos.
Cuando ocurre un conflicto, la pila del analizador (collapse store) se bifurca en dos o más pilas paralelas, cuyos estados superiores corresponden a cada transición posible. En lo que sigue, el siguiente símbolo de entrada se usa para determinar las próximas transiciones en los estados superiores de cada rama de la pila. En este caso, puede ser necesario volver a ramificar la pila. Si para cualquier estado superior y símbolo de entrada no hay transición (en la tabla del analizador), entonces esta rama de la pila se considera errónea y se descarta.
La base para la optimización es la capacidad de compartir partes de la pila con varias de sus ramas, lo que reduce la cantidad total de memoria necesaria para analizar la secuencia de entrada. La estructura compleja resultante de esta optimización hace que la pila se parezca más a un gráfico acíclico dirigido que a un árbol.
El algoritmo GLR en el peor de los casos tiene la misma complejidad que el algoritmo Kok-Younger-Kasami y el algoritmo Earley - O ( n³ ). Sin embargo, el algoritmo GLR tiene dos ventajas:
En la práctica, la mayoría de los lenguajes de programación son deterministas o "casi deterministas". Esto significa que el no determinismo generalmente se puede resolver leyendo un número pequeño (aunque ilimitado) de caracteres de entrada. En comparación con otros algoritmos capaces de procesar toda la clase de gramáticas libres de contexto (como el algoritmo Early o el algoritmo Kok-Younger-Kasami ), el algoritmo GLR tiene un mayor rendimiento en gramáticas "casi deterministas", ya que solo una rama de la pila.