LALR (1) (LA del inglés lookahead - vista previa) - algoritmo de análisis de abajo hacia arriba .
Es una extensión del algoritmo SLR(1) . En algunos casos, funciona cuando no es posible construir una tabla de análisis SLR(1) para una gramática dada debido a conflictos shift-reduce o reduce-reduce. Por lo tanto, la clase de gramáticas analizadas por LALR(1) es más amplia que la clase de gramáticas SLR(1).
El algoritmo de análisis (ejecución del analizador según el flujo de entrada) es el mismo para LALR(1) y SLR(1) y es más amplio que para LR(0) . Solo difieren los algoritmos para construir la tabla de análisis sintáctico por gramática en el proceso de generación del analizador.
Que haya una gramática que no se analice debido a conflictos shift-reduce o fold-reduce utilizando el algoritmo SLR(1).
En este caso, la gramática se transforma de la siguiente manera:
Para la gramática transformada (es isomorfa a la original), se intenta construir una tabla de análisis sintáctico SLR(1).
La acción se basa en que Follow(A) es la unión de todos los Follow(Ak). En cada estado específico, la nueva gramática ya no tiene A, sino uno de Ak, es decir, el conjunto Follow para este estado tiene menos elementos que para A en la gramática original.
Esto da como resultado menos intentos de LALR(1) de colocar un "reparto" en una celda de la tabla de análisis, lo que reduce el riesgo de conflictos con los cambios, a veces eliminándolos por completo, y crea una gramática que SLR no analiza. (1) analizado después de las transformaciones.
El conjunto Follow(Ak) se denomina conjunto anticipado para A y k-ésimo encuentro en las reglas, de ahí el nombre del algoritmo.
Los conflictos shift-reduce y fold-reduce pueden permanecer después de la transformación gramatical LALR(1). Esto significa que se necesita un analizador LR(1) completo para esta gramática, que es mucho más compleja (los algoritmos LR(0)/SLR(1)/LALR(1) no retienen absolutamente ninguna información sobre la parte ya analizada de el flujo de entrada, mientras que LR(1) completo lo hace, y por lo tanto más difícil), pero puede analizar cualquier gramática inequívoca libre de contexto.
Según cierta información (¡especifique!), todas las gramáticas LL(1) se pueden convertir a una forma analizada por LALR(1).
Se utiliza en el generador de analizadores yacc y sus derivados, como GNU bison.
La mayoría de los lenguajes de programación actualmente utilizados tienen gramáticas LALR(1), es decir, este tipo de analizadores son suficientes para analizar la mayoría de los lenguajes realmente utilizados.
El compilador GNU C usa yacc para construir el analizador. Quizás (la presencia de la cadena grammar.y y yacc en el cuerpo del módulo ejecutable), Microsoft hace lo mismo para construir su compilador C.