En informática , un analizador LALR [a] ( look-ahead, left-to-right, rightmost derivation parser ) es parte del proceso de compilación donde 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 de acuerdo con un conjunto de reglas de producción especificadas por una gramática formal para un lenguaje de computadora .
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, Practical Translators for LR(k) language (Traductores prácticos para lenguajes 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), mientras que requiere el mismo número de estados que el analizador LR(0) para un lenguaje que puede ser reconocido por ambos analizadores. Esto hace que el analizador LALR sea 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 son LALR debido a que son ambiguas . [2]
La tesis original no proporcionó ningún algoritmo para construir un analizador de este tipo 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 altamente eficientes en el uso de la memoria. [5] Los analizadores LALR se pueden generar 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 aumentar 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, más a la derecha ). El analizador LR puede reconocer cualquier lenguaje libre de contexto determinista en un tiempo linealmente acotado. [6] La derivación más a la derecha tiene requisitos de memoria muy grandes e implementar un analizador LR era poco práctico 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 LR de anticipación (LALR) [1] y el analizador LR simple (SLR) que tenía requisitos de memoria mucho menores a costa de un menor poder de reconocimiento de idiomas, 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 se publicó en 1982. [5]
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 búsqueda anticipada de un token, para resolver las diferencias entre los 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 poco comunes en el 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 búsqueda anticipada, LR(0)) o, de manera más general, LALR( k ) = LA( k )LR(0) (k tokens de búsqueda anticipada, LR(0)). De hecho, existe una familia de dos parámetros de analizadores sintácticos LA( k )LR( j ) para todas las combinaciones de j y k , que pueden derivarse del analizador sintáctico LR( j + k ), [9] pero no tienen un uso práctico.
Al igual que con otros tipos de analizadores LR, un analizador LALR es bastante eficiente para encontrar el único análisis correcto de abajo a arriba en un solo escaneo de izquierda a derecha sobre el flujo de entrada, porque no necesita usar el retroceso . Al ser un analizador de búsqueda anticipada por definición, siempre usa una búsqueda anticipada, 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 de núcleo idénticos , porque durante el proceso de construcción de estados LR(0) no se conocen los símbolos de anticipación. Esto reduce la potencia 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 da como resultado 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 muestra dicho conflicto de reducción/reducción, es: [10] [11]
S → a E c → un F d → b F c → b y d E → e F → e
En la construcción de la tabla LALR, se fusionarán dos estados en un solo estado y, más adelante, se descubrirá que los valores anticipados son ambiguos. El único estado con valores anticipados es:
E → e. {c,d} F → e. {c,d}Un analizador LR(1) creará dos estados diferentes (con valores anticipados no conflictivos), ninguno de los cuales es ambiguo. En un analizador LALR, este estado tiene acciones conflictivas (dado el valor anticipado c o d, reducir a E o F), un "conflicto reducción/reducción"; un generador de analizador LALR declarará ambigua la gramática anterior y se informarán los conflictos.
Para solucionar esta ambigüedad, se elige 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 a la correcta (F → e) c, pero b E cno está en la gramática.
Los analizadores sintácticos LALR( j ) son incomparables con los analizadores sintácticos 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 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 tienen solo una derivación vacía, la gramática puede ser o no LALR(1). [12]
