¿Qué es un analizador IELR (1)?

14

Trato de enseñarme el uso del bisonte. La página de manual bison (1) dice acerca de bison:

Genere un analizador determinista LR o generalizado LR (GLR) empleando tablas LALR (1), IELR (1) o analizador canónico LR (1).

¿Qué es un analizador IELR? Todos los artículos relevantes que encontré en la red mundial tienen pagos.

FUZxxl
fuente
55
¿Incluyendo cs.clemson.edu/~malloy/papers/sac08/paper.pdf ?
reinierpost
@reinierpost Me siento tan estúpido en este momento. ¿Por qué no encontré esto?
FUZxxl
No lo sé: Google personaliza los resultados ...
reinierpost
@reinierpost, ¿le gustaría responder a esta pregunta citando su enlace, para limpiar esta pregunta ?
Merbs
Hmmm ... si eso es todo lo que se necesita, está bien.
reinierpost

Respuestas:

3

El algoritmo de análisis IELR (1)

El algoritmo de análisis IELR (1) fue desarrollado en 2008 por Joel E. Denny como parte de su Ph.D. investigación bajo la supervisión de Brian A. Malloy en la Universidad de Clemson. El algoritmo IELR (1) es una variación del llamado algoritmo LR (1) "mínimo" desarrollado por David Pager en 1977 , que en sí mismo es una variación del algoritmo de análisis LR (k) inventado por Donald Knuth en 1965 . El IE en IELR (1) representa la eliminación de la insuficiencia (ver la última sección).

LR (1) Algoritmos

El LR (1) parte de IELR (1) significa L eft a derecha, R ightmost derivación con 1 lookahead token. Los analizadores LR (1) también se denominan analizadores canónicos. Esta clase de algoritmos de análisis emplea una estrategia de análisis de reducción de desplazamiento de abajo hacia arriba con una tabla de transición de pila y estado que determina la siguiente acción a tomar durante el análisis.

Históricamente, los algoritmos LR (1) han sido desfavorecidos por los grandes requisitos de memoria para sus tablas de transición. La mejora de Pager fue desarrollar un método para combinar los estados de transición cuando se genera la tabla de transición, reduciendo significativamente el tamaño de la tabla. Por lo tanto, el algoritmo de Pager hace que los analizadores LR (1) sean competitivos con otras estrategias de análisis con respecto a la eficiencia de espacio y tiempo. La frase "analizador mínimo LR (1)" se refiere al tamaño mínimo de la tabla de transición introducida por el algoritmo de Pager.

Limitaciones del algoritmo de buscapersonas

Los algoritmos mínimos LR (1) producen la tabla de transición basada en una gramática de entrada particular para el lenguaje a analizar. Diferentes gramáticas pueden producir el mismo lenguaje. De hecho, es posible que una gramática no LR (1) produzca un lenguaje analizable LR (1). En la práctica, los generadores de analizadores LR (1) aceptan gramáticas no LR (1) con una especificación para resolver conflictos entre dos posibles transiciones de estado ("conflictos de reducción de desplazamiento") para acomodar este hecho. Denny y Malloy descubrieron que el algoritmo de Pager no puede generar analizadores lo suficientemente potentes como para analizar lenguajes LR (1) cuando se proporcionan ciertas gramáticas no LR (1) a pesar de que la gramática no LR (1) genera un lenguaje LR (1).

Denny y Malloy muestran que esta limitación no es meramente académica al demostrar que Gawk y Gpic, ambos software maduros ampliamente utilizados, realizan acciones incorrectas de análisis.

Mejoras de IELR (1)

Denny y Malloy estudiaron la fuente de las deficiencias del algoritmo de Pager comparando la tabla de transición generada por el algoritmo de Pager con la tabla de transición de una gramática LR (1) equivalente e identificaron dos fuentes de lo que denominan deficiencias que aparecen en la tabla de transición de Pager algoritmo pero no en la tabla de transición LR (1). El algoritmo IELR (1) ( Eliminación de falta de adecuación LR (1)) de Denny and Malloy es un algoritmo diseñado para eliminar estas deficiencias al generar la tabla de transición que tiene un tamaño prácticamente idéntico al del algoritmo de Pager.

Robert Jacobson
fuente
6

Un artículo que dice presentarlo: IELR (1): Tablas prácticas de analizador LR (1) para gramáticas no LR (1) con resolución de conflictos (a través de archive.org) por Joel E. Denny y Brian A. Malloy, Universidad de Clemson , está disponible gratuitamente en el sitio de Malloy.

Lo que valen es algo que no puedo responder. (Personalmente, no entiendo la necesidad de un análisis de CFG tan lisiado, ¿por qué limitar su poder expresivo cuando solo puede usar GLR ? Lo que tiene sentido para mí es algo como TAG o PEG (parecen naturales y agregan poder expresivo) o árbol gramáticas (para lenguajes como XML, en los que el reconocimiento de árboles de análisis no es problemático por diseño).

reinierpost
fuente
Si bien estoy de acuerdo con el principio con respecto a la tecnología, el problema a menudo es que el análisis determinista tradicional tiene implementaciones mejores y más completas. Otro problema es que el análisis general de CF es más poderoso, pero GLR puede no ser la mejor versión.
babou
44
La razón principal por la cual las personas han desarrollado analizadores CFG colapsados ​​es que un analizador GLR no necesariamente se ejecuta en tiempo lineal; este es un gran problema para muchas aplicaciones. Un analizador IELR puede garantizar un tiempo de ejecución lineal y más.
FUZxxl
No entiendo por qué sería un problema.
reinierpost
2
O(norte4 4)O(norte3)lyometroXO(norteX). Los humanos no viven para siempre y tienen mucho que hacer. Perder el tiempo es generalmente malo.
usuario
3
Me gustaría señalar que "Personalmente no entiendo la necesidad de un análisis de CFG tan lisiado, ¿por qué limitar su poder expresivo cuando solo puede usar GLR?" está bastante equivocado en este contexto. IELR (1) se utiliza para generar tablas de analizador LR (1) más eficientes , lo que permite analizadores GLR más eficientes .
orlp