En informática , un analizador LALR [a] ( analizador de derivación anticipado, de izquierda a derecha y más a la derecha ) es parte del proceso de compilación en el que el texto legible por humanos se convierte en una representación estructurada para ser leída por computadoras. Un analizador LALR es una herramienta de software para procesar ( analizar ) texto en una representación interna muy específica con la que otros programas, como los compiladores, pueden trabajar. Este proceso ocurre según un conjunto de reglas de producción especificadas por una gramática formal para un lenguaje informático .
Un analizador LALR 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, Traductores prácticos para idiomas LR(k) , [1] en su tratamiento de las dificultades prácticas en ese momento de implementar analizadores LR(1). Demostró que el analizador LALR tiene más poder de reconocimiento de lenguaje que el analizador LR(0), al tiempo que requiere el mismo número de estados que el analizador LR(0) para un lenguaje que pueda ser reconocido por ambos analizadores. Esto convierte al analizador LALR en una alternativa eficiente en memoria al analizador LR(1) para lenguajes que son LALR. También se demostró que existen lenguajes LR(1) que no son LALR. A pesar de esta debilidad, el poder del analizador LALR es suficiente para muchos lenguajes informáticos convencionales, [2] incluido Java , [3] aunque las gramáticas de referencia para muchos lenguajes no llegan a ser LALR debido a que son ambiguas . [2]
La disertación original no proporcionó ningún algoritmo para construir dicho analizador dada una gramática formal. Los primeros algoritmos para la generación de analizadores LALR se publicaron en 1973. [4] En 1982, DeRemer y Tom Pennello publicaron un algoritmo que generaba analizadores LALR con alta eficiencia de memoria. [5] Los analizadores LALR pueden generarse automáticamente a partir de una gramática mediante un generador de analizadores LALR como Yacc o GNU Bison . El código generado automáticamente se puede complementar con código escrito a mano para aumentar la potencia del analizador resultante.
En 1965, Donald Knuth inventó el analizador LR ( derivación de izquierda a derecha, extremo derecho ). El analizador LR puede reconocer cualquier lenguaje determinista libre de contexto en un tiempo lineal. [6] La derivación más a la derecha tiene requisitos de memoria muy grandes y la implementación de un analizador LR no era práctica 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 Simple LR (SLR), que tenían requisitos de memoria mucho menores a un costo de menos. poder de reconocimiento de lenguaje, siendo el analizador LALR la alternativa más poderosa. [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 la eficiencia de su memoria. [8] Su trabajo fue publicado en 1982. [5]
Generalmente, el analizador LALR se refiere al analizador LALR(1), [b] del mismo modo que el analizador LR generalmente se refiere al analizador LR(1). El "(1)" indica 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 búsqueda anticipada de dos tokens y analizadores LALR( k ) con búsqueda de k tokens, pero estos son raros en el uso real. El analizador LALR se basa en el analizador LR(0), por lo que también se puede indicar como 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 pueden derivarse del analizador LR( j + k ), [9] pero estos no parecen prácticos. usar.
Al igual que con otros tipos de analizadores LR, un analizador LALR es bastante eficiente para encontrar el único análisis ascendente correcto en un único escaneo de izquierda a derecha sobre el flujo de entrada, porque no necesita utilizar retroceso . Al ser un analizador anticipado por definición, siempre utiliza un analizador anticipado, siendo LALR(1) el caso más común.
El analizador LALR(1) es menos potente que el analizador LR(1) y más potente que el analizador SLR(1), aunque todos utilizan las mismas reglas de producción . La simplificación que introduce el analizador LALR consiste en fusionar reglas que tienen conjuntos de elementos del núcleo idénticos , porque durante el proceso de construcción del estado LR(0) no se conocen las búsquedas anticipadas. Esto reduce el poder del analizador porque no conocer los símbolos de anticipación puede confundir al analizador en cuanto a 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) inequívoca son conflictos de reducción/reducción. El analizador SLR(1) realiza más fusiones, lo que introduce conflictos adicionales.
El ejemplo estándar de una gramática LR(1) que no se puede analizar con el analizador LALR(1) y que presenta un conflicto de reducción/reducción de este tipo es: [10] [11]
S → a mi c → a F d → b F c → b mi d mi → mi F → mi
En la construcción de la tabla LALR, dos estados se fusionarán en uno y luego se encontrará que las búsquedas anticipadas son ambiguas. El único estado con anticipación es:
mi → mi. {cd} F → e. {cd}Un analizador LR(1) creará dos estados diferentes (con búsquedas anticipadas no conflictivas), ninguno de los cuales es ambiguo. En un analizador LALR, este estado tiene acciones conflictivas (dada la anticipación c o d, reducir a E o F), un "conflicto reducir/reducir"; La gramática anterior será declarada ambigua por un generador de analizador LALR y se informarán los conflictos.
Para recuperar, esta ambigüedad se resuelve eligiendo E, porque aparece antes de 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.
Los analizadores LALR( j ) son incomparables con los analizadores LL( k ) : para cualquier j y k ambos mayores que 0, hay 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 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 LALR(1) o no. [12]
