De Wikipedia, la enciclopedia libre
Ir a navegaciónSaltar a buscar

Un analizador GLR (GLR significa "LR generalizado", donde L significa "de izquierda a derecha" y R significa "más a la derecha (derivación)") es una extensión de un algoritmo de analizador LR para manejar gramáticas ambiguas y no deterministas . [1] La base teórica fue proporcionada en un artículo de 1974 [2] por Bernard Lang (junto con otros analizadores sintácticos 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 se le ha denominado "analizador en paralelo". Tomita presentó cinco etapas en su trabajo original, [3] aunque en la práctica es la segunda etapa la que se reconoce como analizador 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 el texto en lenguaje natural de manera exhaustiva y eficiente. Los analizadores sintácticos LR estándar no pueden adaptarse a la naturaleza ambigua y no determinista del lenguaje natural , y el algoritmo GLR sí.

Algoritmo

Brevemente, el algoritmo GLR funciona de manera similar al algoritmo del analizador LR , excepto que, dada una gramática particular, un analizador GLR procesará todas las posibles interpretaciones de una entrada dada en una búsqueda de amplitud primero . En el front-end, un generador de analizador GLR convierte una gramática de entrada en tablas de analizador, de manera similar a un generador de LR. Sin embargo, donde 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 cambiar / reducir y reducir / reducir conflictos.

Cuando se encuentra una transición en conflicto, la pila de análisis se bifurca en dos o más pilas de análisis en paralelo, donde el estado correspondiente a cada posible transición está en la parte superior. Luego, se lee el siguiente token de entrada y se usa para determinar la (s) próxima (s) transición (es) para cada uno de los estados "superiores", y pueden ocurrir 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 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 gráfico de búsqueda sea un gráfico acíclico dirigido (con restricciones adicionales sobre las "profundidades" de varios nodos), en lugar de un árbol.

Ventajas

El reconocimiento que utiliza el algoritmo GLR tiene la misma complejidad de tiempo en el peor de los casos que el algoritmo CYK y el algoritmo Earley : O ( n 3 ). [ cita requerida ] Sin embargo, GLR tiene dos ventajas adicionales:

  • El tiempo requerido para ejecutar el algoritmo es proporcional al grado de no determinismo en la gramática: en gramáticas deterministas, el algoritmo GLR se ejecuta en tiempo O ( n ) (esto no es cierto para los algoritmos Earley [ cita requerida ] y CYK, pero el original Los algoritmos de Earley se pueden modificar para garantizarlo)
  • El algoritmo GLR está "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 (también es cierto para 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 generalmente se resuelve 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 Earley o CYK), el algoritmo GLR ofrece un mejor rendimiento en estas gramáticas "casi deterministas", porque solo una sola pila estará activa durante la mayoría de las 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]

Ver también

Referencias

  1. ^ Masaru Tomita (6 de diciembre de 2012). Análisis de LR generalizado . Springer Science & Business Media. ISBN 978-1-4615-4034-2.
  2. ^ Lang, Bernard (1974). Loeckx, J. (ed.). "Técnicas deterministas para analizadores sintácticos no deterministas eficientes" . Autómatas, Lenguajes y Programación, 2º Coloquio . Apuntes de conferencias en Ciencias de la Computación. Saarbrücken: Springer. 14 : 255-269. doi : 10.1007 / 3-540-06841-4_65 . ISBN 978-3-540-06841-9. ISSN  0302-9743 .
  3. ^ Masaru Tomita. Análisis eficiente del lenguaje natural. Editores Académicos Kluwer, Boston, 1986.
  4. ^ Lang, Bernard (diciembre de 1971). "Análisis sintáctico ascendente no determinista paralelo" . Avisos ACM SIGPLAN . Actas del simposio internacional sobre lenguas extensibles. 6 (12): 56–57. doi : 10.1145 / 942582.807982 .
  5. ^ "Elkhound, Elsa y Cqual ++: análisis estático de código abierto para C ++" .

Lectura adicional

  • Grune, Dick; Jacobs, Ceriel JH (2008). Técnicas de análisis . Springer Science + Business Media. ISBN 978-0-387-20248-8.
  • Tomita, Masaru (1984). "Analizadores sintácticos LR para lenguajes naturales". COLING . X Congreso Internacional de Lingüística Computacional. págs. 354–357.
  • Tomita, Masaru (1985). "Un algoritmo de análisis sin contexto eficiente para lenguajes naturales". IJCAI . Conferencia conjunta internacional sobre inteligencia artificial. págs. 756–764.