Analizador LALR (con ejemplos)

Analizador LALR:
el analizador LALR es un analizador LR anticipado. Es el analizador más poderoso que puede manejar grandes clases de gramática. El tamaño de la tabla de análisis de CLR es bastante grande en comparación con otras tablas de análisis. LALR reduce el tamaño de esta tabla. LALR funciona de manera similar a CLR. La única diferencia es que combina los estados similares de la tabla de análisis de CLR en un solo estado. 
La sintaxis general se convierte en [A->∝.B, a ]
donde A->∝.B es producción y a es un terminal o marcador de extremo derecho $
LR(1) elementos=LR(0) elementos + anticipación

¿Cómo agregar lookahead con la producción?

CASO 1 –

A->∝.BC, a

Supongamos que esta es la producción número 0. Ahora, desde ‘ . ‘ precede a B, así que también tenemos que escribir las producciones de B.

B->.D [1st production]

Supongamos que esta es la producción de B. La mirada hacia el futuro de esta producción se da como: miramos la producción anterior, es decir, la producción 0. Lo que sea que esté después de B, encontramos PRIMERO (de ese valor), que es la anticipación de la primera producción. Entonces, aquí en la producción 0, después de B, está C. Suponga que FIRST(C)=d, luego se convierte en la primera producción.

B->.D, d

CASO 2 –
Ahora bien, si la 0ª producción fuera así,

A->∝.B, a

Aquí, podemos ver que no hay nada después de B. Por lo tanto, la anticipación de la producción 0 será la anticipación de la producción 1. es decir-

B->.D, a

CASO 3 –
Suponga una producción A->a|b

A->a,$ [0th production]
A->b,$ [1st production]

Aquí, la primera producción es parte de la producción anterior, por lo que la anticipación será la misma que la de su producción anterior.

Pasos para construir la tabla de análisis LALR:

1. Escritura de gramática aumentada
2. LR(1) colección de elementos a encontrar
3. Definición de 2 funciones: ir a [lista de terminales] y acción [lista de no terminales] en la tabla de análisis LALR

EJEMPLO
Construya una tabla de análisis CLR para la gramática libre de contexto dada

S-->AA    
A-->aA|b

Solución:

PASO 1- Encuentra la gramática
aumentada La gramática aumentada de la gramática dada es: –

S'-->.S ,$   [0th production]    
S-->.AA ,$ [1st production]    
A-->.aA ,a|b [2nd production]      
A-->.b ,a|b [3rd production]

Apliquemos la regla de anticipación a las producciones anteriores.

• La previsión inicial siempre es $
• Ahora, la primera producción nació debido a ‘. ‘ antes de ‘S’ en la 0.ª producción. No hay nada después de ‘S’, por lo que la anticipación de la 0.ª producción será la anticipación de la 1.ª producción. es decir: S–>.AA,$
• Ahora, la segunda producción nació debido a ‘. ‘ antes de ‘A’ en la primera producción.
  Después de ‘A’, está ‘A’. Entonces, PRIMERO(A) es a,b. Por lo tanto, la previsión de la segunda producción se convierte en a|b.
• Ahora, la 3.ª producción es parte de la 2.ª producción. Entonces, el futuro será el mismo.

PASO 2: busque la colección de elementos LR(0)
A continuación se muestra la figura que muestra la colección de elementos LR(0). Vamos a entender todo uno por uno.

Los terminales de esta gramática son {a,b}
Los no terminales de esta gramática son {S,A}

NORMAS –

1. Si algún no terminal tiene ‘ . ‘ precediéndolo, tenemos que escribir toda su producción y agregar ‘ . ‘ anterior a cada una de sus producciones.
2. de cada estado al siguiente estado, el ‘ . ‘ cambia a un lugar a la derecha.

• En la figura, I0 consiste en gramática aumentada.
• Io va a I1 cuando ‘ . ‘ de la producción 0 se desplaza hacia la derecha de S(S’->S.). Este estado es el estado de aceptación. S es visto por el compilador. Dado que I1 es parte de la producción 0, la anticipación es la misma, es decir, $
• Io va a I2 cuando ‘ . ‘ de la 1ª producción se desplaza hacia la derecha (S->AA) . A es visto por el compilador. Dado que I2 es parte de la primera producción, la anticipación es la misma, es decir, $.
• I0 va a I3 cuando ‘ . ‘ de 2ª producción se desplaza hacia la derecha (A->aA) . a es visto por el compilador. Dado que I3 es parte de la segunda producción, la anticipación es la misma, es decir, a|b.
• I0 va a I4 cuando ‘ . ‘ de la 3ª producción se desplaza hacia la derecha (A->b.) . b es visto por el compilador. Dado que I4 es parte de la tercera producción, la anticipación es la misma, es decir, a|b.
• I2 va a I5 cuando ‘ . ‘ de la 1ª producción se desplaza hacia la derecha (S->AA.) . A es visto por el compilador. Dado que I5 es parte de la primera producción, la anticipación es la misma, es decir, $.
• I2 va a I6 cuando ‘ . ‘ de 2ª producción se desplaza hacia la derecha (A->aA) . A es visto por el compilador. Dado que I6 es parte de la segunda producción, la anticipación es la misma, es decir, $.
• I2 va a I7 cuando ‘ . ‘ de la 3ª producción se desplaza hacia la derecha (A->b.) . A es visto por el compilador. Dado que I6 es parte de la tercera producción, la anticipación es la misma, es decir, $.
• I3 va a I3 cuando ‘ . ‘ de la 2ª producción se desplaza hacia la derecha (A->aA) . a es visto por el compilador. Dado que I3 es parte de la segunda producción, la previsión es la misma, es decir, a|b.
• I3 va a I8 cuando ‘ . ‘ de 2ª producción está desplazada hacia la derecha (A->aA.) . A es visto por el compilador. Dado que I8 es parte de la segunda producción, la previsión es la misma, es decir, a|b.
• I6 va a I9 cuando ‘ . ‘ de 2ª producción está desplazada hacia la derecha (A->aA.) . A es visto por el compilador. Dado que I9 es parte de la segunda producción, la anticipación es la misma, es decir, $.
• I6 va a I6 cuando ‘ . ‘ de la 2ª producción se desplaza hacia la derecha (A->aA) . a es visto por el compilador. Dado que I6 es parte de la segunda producción, la anticipación es la misma, es decir, $.
• I6 va a I7 cuando ‘ . ‘ de la 3ª producción se desplaza hacia la derecha (A->b.) . b es visto por el compilador. Dado que I6 es parte de la tercera producción, la anticipación es la misma, es decir, $.

PASO 3:
definición de 2 funciones: ir a [lista de terminales] y acción [lista de no terminales] en la tabla de análisis. A continuación se muestra la tabla de análisis de CLR

Una vez que creamos una tabla de análisis de CLR, podemos crear fácilmente una tabla de análisis de LALR a partir de ella.

En el diagrama del paso 2, podemos ver que 

• I3 e I6 son similares excepto por sus anticipaciones.
• I4 e I7 son similares excepto por sus anticipaciones.
• I8 e I9 son similares excepto por sus anticipaciones.

En la construcción de la tabla de análisis LALR, fusionamos estos estados similares. 

• Donde sea que haya 3 o 6, que sea 36 (forma combinada)
• Donde sea que haya 4 o 7, que sea 47 (forma combinada)
• Donde sea que haya 8 o 9, que sea 89 (forma combinada)

A continuación se muestra la tabla de análisis LALR. 

Ahora tenemos que eliminar las filas no deseadas.

• Como podemos ver, la fila 36 tiene los mismos datos dos veces, por lo que eliminamos 1 fila.
• Combinamos dos filas de 47 en una combinando cada valor en la única fila de 47.
• Combinamos dos filas de 89 en una combinando cada valor en la única fila de 89.

La tabla LALR final se parece a la siguiente.