Hispanopedia WikiUn analizador LALR [ a ] ( analizador de anticipación, de izquierda a derecha, de derivación más a la derecha ) es un tipo de analizador para lenguajes de programación. Es una versión simplificada de un analizador LR canónico .
El analizador LALR fue inventado por Frank DeRemer en su tesis doctoral de 1969, Practical Translators for LR(k) languages , [ 1 ] en su análisis de las dificultades prácticas que existían entonces para implementar analizadores LR(1). Demostró que el analizador LALR tiene mayor capacidad de reconocimiento de lenguaje que el analizador LR(0), a la vez que requiere el mismo número de estados que este último para un lenguaje que puede ser reconocido por ambos analizadores. Esto convierte al analizador LALR en una alternativa eficiente en memoria al analizador LR(1) para lenguajes LALR. También se demostró que existen lenguajes LR(1) que no son LALR. A pesar de esta limitación, la potencia del analizador LALR es suficiente para muchos lenguajes de programación convencionales, [ 2 ] incluyendo Java , [ 3 ] aunque las gramáticas de referencia para muchos lenguajes no son LALR debido a su ambigüedad . [ 2 ]
La tesis original no proporcionó ningún algoritmo para construir un analizador sintáctico de este tipo a partir de una gramática formal. Los primeros algoritmos para la generación de analizadores sintácticos LALR se publicaron en 1973. [ 4 ] En 1982, DeRemer y Tom Pennello publicaron un algoritmo que generaba analizadores sintácticos LALR altamente eficientes en cuanto al uso de memoria. [ 5 ] Los analizadores sintácticos LALR pueden generarse automáticamente a partir de una gramática mediante un generador de analizadores sintácticos LALR como Yacc o GNU Bison . El código generado automáticamente puede ampliarse con código escrito manualmente para aumentar la potencia del analizador resultante.
Historia
En 1965, Donald Knuth inventó el analizador LR ( de izquierda a derecha, derivación más a la derecha ) . El analizador LR puede reconocer cualquier lenguaje determinista libre de contexto en tiempo lineal acotado. [ 6 ] La derivación más a la derecha tiene requisitos de memoria muy grandes y la implementación de un analizador LR era impracticable debido a la memoria limitada de las computadoras en ese momento. Para abordar esta deficiencia, en 1969, Frank DeRemer propuso dos versiones simplificadas del analizador LR, a saber, el Look-Ahead LR (LALR) [ 1 ] y el analizador LR simple (SLR) que tenían requisitos de memoria mucho menores a costa de una menor potencia de reconocimiento de lenguaje, siendo el analizador LALR la alternativa más potente. [ 1 ] En 1977, se inventaron optimizaciones de memoria para el analizador LR [ 7 ] pero aún así el analizador LR era menos eficiente en memoria que las alternativas simplificadas.
En 1979, Frank DeRemer y Tom Pennello anunciaron una serie de optimizaciones para el analizador LALR que mejorarían aún más su eficiencia de memoria. [ 8 ] Su trabajo se publicó en 1982. [ 5 ]
Descripción general
En general, el analizador LALR se refiere al analizador LALR(1), [ b ] al igual que el analizador LR generalmente se refiere al analizador LR(1). El "(1)" denota una anticipación de un token, para resolver diferencias entre patrones de reglas durante el análisis. De manera similar, existe un analizador LALR(2) con anticipación de dos tokens, y analizadores LALR( k ) con búsqueda de k tokens, pero estos son raros en uso real. El analizador LALR se basa en el analizador LR(0), por lo que también se puede denotar LALR(1) = LA(1)LR(0) (1 token de anticipación, LR(0)) o, más generalmente, LALR( k ) = LA( k )LR(0) (k tokens de anticipación, LR(0)). De hecho, existe una familia de analizadores LA( k )LR( j ) de dos parámetros para todas las combinaciones de j y k , que se pueden derivar del analizador LR( j + k ), [ 9 ] pero estos no se utilizan en la práctica.
Al igual que otros tipos de analizadores LR, un analizador LALR es bastante eficiente para encontrar el único análisis correcto de abajo hacia arriba en un solo escaneo de izquierda a derecha sobre el flujo de entrada, ya que no necesita usar retroceso . Siendo un analizador de anticipación por definición, siempre usa una anticipación, siendo LALR(1) el caso más común.
Relación con otros analizadores sintácticos
analizadores LR
El analizador LALR(1) es menos potente que el analizador LR(1) y más potente que el analizador SLR(1), aunque todos usan las mismas reglas de producción . La simplificación que introduce el analizador LALR consiste en fusionar reglas que tienen conjuntos de elementos de núcleo idénticos , porque durante el proceso de construcción de estado LR(0) no se conocen las búsquedas anticipadas. Esto reduce la potencia del analizador porque no conocer los símbolos de búsqueda anticipada puede confundir al analizador sobre qué regla gramatical elegir a continuación, lo que resulta en conflictos de reducción/reducción . Todos los conflictos que surgen al aplicar un analizador LALR(1) a una gramática LR(1) no ambigua son conflictos de reducción/reducción. El analizador SLR(1) realiza una fusión adicional, lo que introduce conflictos adicionales.
El ejemplo estándar de una gramática LR(1) que no puede ser analizada con el analizador LALR(1), que exhibe tal conflicto reduce/reduce, es: [ 10 ] [ 11 ]
S → a E c → un F d → b F c → b E d E → e F → e
En la construcción de la tabla LALR, dos estados se fusionarán en un solo estado y posteriormente se encontrará que las proyecciones son ambiguas. El único estado con proyecciones es:
E → e. {c,d} F → e. {c,d}Un analizador LR(1) creará dos estados diferentes (con anticipaciones no conflictivas), ninguno de los cuales es ambiguo. En un analizador LALR, este estado presenta acciones conflictivas (con anticipaciones c o d, reducir a E o F), lo que genera un "conflicto de reducción/reducción". La gramática anterior será declarada ambigua por un generador de analizadores LALR y se informarán los conflictos.
Para recuperarse, esta ambigüedad se resuelve eligiendo E, porque aparece antes que F en la gramática. Sin embargo, el analizador resultante no podrá reconocer la secuencia de entrada válida b e c, ya que la secuencia ambigua e cse reduce a (E → e) c, en lugar de la correcta (F → e) c, pero b E cno está en la gramática.
analizadores LL
Los analizadores LALR( j ) son incomparables con los analizadores LL( k ) : para cualquier j y k mayores que 0, existen gramáticas LALR( j ) que no son gramáticas LL( k ) y viceversa. De hecho, es indecidible si una gramática LL(1) dada es LALR( k ) para cualquier. [ 2 ]
Dependiendo de la presencia de derivaciones vacías, una gramática LL(1) puede ser igual a una gramática SLR(1) o a una gramática LALR(1). Si la gramática LL(1) no tiene derivaciones vacías, es SLR(1), y si todos los símbolos con derivaciones vacías tienen derivaciones no vacías, es LALR(1). Si existen símbolos que solo tienen una derivación vacía, la gramática puede ser o no LALR(1). [ 12 ]
Véase también
Notas
Referencias
- 1 2 3 DeRemer 1969 .
- 1 2 3 Análisis sintáctico LR: Teoría y práctica, Nigel P. Chapman, págs. 86-87
- ↑ "Generar el analizador" . Proyecto Eclipse JDT . Consultado el 29 de junio de 2012 .
- ↑ Anderson, T.; Eve, J.; Horning, J. (1973). "Analizadores LR(1) eficientes". Acta Informatica (2): 2– 39.
- 1 2 DeRemer, Frank; Pennello, Thomas (octubre de 1982). "Cálculo eficiente de conjuntos de anticipación LALR(1)" (PDF) . ACM Transactions on Programming Languages and Systems . 4 (4): 615– 649. doi : 10.1145/69622.357187 .
- ↑ Knuth, DE (julio de 1965). "Sobre la traducción de lenguas de izquierda a derecha" . Information and Control . 8 (6): 607– 639. doi : 10.1016/S0019-9958(65)90426-2 .
- ↑ Pager, D. (1977), "Un método general práctico para construir analizadores LR(k)", Acta Informatica 7 , vol. 7, n.º 3, págs. 249–268 , doi : 10.1007/BF00290336
- ↑ Frank DeRemer, Thomas Pennello (1979), "Cálculo eficiente de conjuntos de anticipación LALR(1)", Sigplan Notices - SIGPLAN, vol. 14, n.º 8 , págs. 176–187
- ↑ Técnicas de análisis sintáctico: una guía práctica, por Dick Grune y Ceriel JH Jacobs, "9.7 LALR(1)", pág. 302
- ↑ " 7.9 LR(1) pero no LALR(1) Archivado el 4 de agosto de 2010 en Wayback Machine ", CSE 756: Diseño e implementación de compiladores Archivado el 23 de julio de 2010 en Wayback Machine , Eitan Gurari, primavera de 2008
- ↑ " ¿Por qué esta gramática LR(1) no es LALR(1)? "
- ↑ ( Beatty 1982 )
- DeRemer, Franklin L. (1969). Traductores prácticos para lenguas LR(k) (PDF) (PhD). MIT. Archivado del original (PDF) el 19 de agosto de 2013. Recuperado el 13 de noviembre de 2012 .
- Beatty, JC (1982). "Sobre la relación entre las gramáticas LL(1) y LR(1)" (PDF) . Journal of the ACM . 29 (4 (octubre)): 1007–1022 . doi : 10.1145/322344.322350 .
Enlaces externos
- Simulador de análisis sintáctico Este simulador se utiliza para generar tablas de análisis sintáctico LALR y resolver los ejercicios del libro.
- Implementación basada en JavaScript (JS/CC) de un generador de analizadores LALR(1), que se puede ejecutar en un navegador web o desde la línea de comandos.
- Tutorial de LALR(1) en Wayback Machine (archivado el 7 de mayo de 2021) , un tutorial tipo tarjetas didácticas sobre el análisis de LALR(1).
- Algoritmos de análisis sintáctico
