Construcción de las tablas de análisis LALR

El análisis LALR (lookahead-LR), es el que se utiliza normalmente en la práctica porque las tablas de análisis que genera son mucho más pequeñas que las del análisis LR canónico.

Por ejemplo, un analizador LR para un lenguaje como Pascal puede tener miles de estados, mientras que con un análisis SLR o LALR se pueden tener solo cientos de estados.

La reducción de estados es bastante significativa.

El inconveniente es que el conjunto de gramáticas que reconoce es menor que el LR, pero con el análisis LALR se pueden expresar la mayoría de los lenguajes de programación.

Lo que se hace en el análisis LALR es buscar estados con el mismo núcleo, es decir, estados que se diferencian únicamente en los símbolos de anticipación. Y se fusionan formando un único estado. Por ejemplo en el autómata anterior se puede ver que los estados 3 y 6 tienen el mismo núcleo.

Estado 3:

Estado 6:

Al realizar la fusión quedaría

El resultado final de fusionar los estados equivalentes puede verse en la siguiente figura (Figura 41). Como puede verse los estados equivalentes eran el (3, 6), (8, 9) y el (4, 7).

Figura 41: Autómata generada mediante el método LALR

Con lo que se puede comprobar que la reducción del número de estados es considerable. Ahora solo queda saber las consecuencias de realizar esta fusión de estados.

Supóngase que se tiene una gramática LR que no tiene conflictos de análisis. A continuación se fusionan los estados con el mismo núcleo, ahora queda resolver la cuestión de saber las consecuencias de dicha fusión. La fusión hecha puede tener un conflicto nuevo que no existía en el análisis LR, pero no es probable. El único conflicto nuevo que se puede generar, es un conflicto reducción/reducción, porque al unir dos estados puede pasar que en dos items de reducción de dos estados se tenga algún símbolo de anticipación común. Al estar separados en el análisis LR, no hay conflicto pero al juntarlos se genera el conflicto.

Por ejemplo, en la siguiente gramática

S→aAd|bBd|aBe|bAe

A→c

B→c

Al hacer el análisis LR no se genera ningún conflicto, pero al juntar los estados 6 y 9 se genera un conflicto nuevo reducción/reducción.

Estado 6:

Estado 9:

Nuevo estado:

Como puede verse hay dos items que reducen por el mismo terminal (d), con lo cual se genera un nuevo conflicto (reducción/reducción), que no existía en el análisis LR.

El otro conflicto es el desplazamiento/reducción, pero en el análisis LALR sólo puede ocurrir si previamente el análisis LR ya lo tenía, ya que la fusión de estados tiene que ver con juntar los símbolos de anticipación y estos símbolos no tienen nada que ver con los desplazamientos.

Construcción de la tabla de Acción/Ir_A

Las tablas de análisis LALR se pueden construir directamente a partir de una gramática, pero es más fácil construirlas a partir del conjunto de estados LR. Lo primero que se hace es fusionar los estados con el mismo núcleo, y a partir de este nuevo conjunto de estados generar de la misma forma que el análisis LR la tabla de acción y la de Ir_A.

En la siguiente tabla (Tabla 6) puede verse el resultado de generar la tabla de análisis del autómata de la figura 41. Como se puede ver, el método LALR ha conseguido reducir de 10 estados que generaba el LR a 7 estados que genera LALR.

Tabla 6: Tabla de análisis LALR