Análisis sintáctico gramáticas LR (1)

UNIVERSIDAD IDEP

Iván Villanueva Naquid

Análisis sintáctico

Francisco Fernando Gosch Acosta

Ingeniería en Sistemas Computacionales

Análisis sintáctico gramáticas LR (1)

Este es el método más poderoso que existe, a costa de que se incrementa la complejidad. Las limitaciones del método LR (0) y SLR (1) radican en que tienen en cuenta el símbolo de pre análisis después de la construcción del AFD de ítems LR (0), que por sı misma ignora los símbolos siguientes en la entrada.

El algoritmo LR (1) se compone de tres procedimientos

La cerradura nos permite establecer el conjunto de símbolos de adelanto, que  nos indica que reducción es posible aplicar en presencia de un símbolo y en esto se basa el aumento de precisión del análisis LR (1).

El conjunto de elementos hace que avance el indicador de proceso de la entrada en un símbolo que ya ha procesado y llama a la cerradura con el nuevo indicador de entrada para esa producción.

Y la rutina principal para construir el conjunto de elementos.

ANALISIS LR (1) Definición de Elemento LR (1) y Construcción del Autómata finito de elementos LR (1).

Un elemento de análisis sintáctico LR (1) de una gramática G, es un par consistente de un ítem LR (0) y un símbolo de pre análisis.

[pic 1]

Siendo A->α●β un ítem LR (0) y a el token del pre análisis.

Un ítem completo [A->αβ●, a], indica que ya se ha reconocido por completo una cadena derivable de A y reduciré siempre que en la entrada tenga el token a.

AFD LR(1)

Los estados son los propios ítems LR (1).

Las transiciones son de la forma:

Si X Є Vt tenemos una transición

[pic 2]

Si X Є Vnt tenemos una transicion

[pic 3]

Y ademas Є-transiciones

[pic 4])

El estado inicial del AFD se obtiene ampliando la gramatica, como para el caso de items LR(0), y poniendo como simbolo de preanalisis $.

[S’->●S,$]

que significa que reconoceremos una cadena derivable de S seguida del simbolo $.

Es básicamente lo mismo que el SLR (1), solo que usa el símbolo de pre análisis en vez del conjunto SIG.

Sea S el estado de la cima de la pila. Entonces:

• Si el estado S contiene cualquier ítem de la forma [A->α● X β, a] con X terminal  (X Є Vt) y X es el siguiente terminal en la entrada, entonces la acción es desplazar X a la pila. Como nuevo estado al que pasa el analizador apilamos aquel que contenga un ítem de la forma [A->αX● β, a].
• Si el estado S contiene un ítem de la forma [A->α● X β,a] y el siguiente token en la entrada es a, entonces la acción es reducir aplicando la producción A->α. Sacamos 2 │α│elementos de la pila y el estado que queda al descubierto debe contener un ítem de la forma [pic 5] metemos el no terminal A en la pila y como nuevo estado, aquel que contenga el ítem de la forma [pic 6]
• Si el símbolo en la entrada es tal que no se puede realizar ninguna de las acciones anteriores entonces error.

Se dice que una gramática es LR (1) si la aplicación de las reglas anteriores no son ambiguas. Es LR (1) si cumple para cada estado una de las siguientes condiciones.

...