Analizador sintáctico LR

El analizador sintáctico LR es el que más se utiliza en la práctica en la construcción de compiladores. Este tipo de analizadores se utiliza porque la mayoría de los lenguajes de programación se pueden construir con analizadores LR. Además, es un método general de análisis que no necesita retroceso, por lo tanto es eficiente y detecta los errores tan pronto como es posible.

Pero con este método no todo son ventajas, ya que es difícil entender el proceso de construcción de las tablas, y más difícil corregir los problemas de análisis que puedan surgir.

En la siguiente figura puede verse un esquema de un analizador sintáctico LR.

Figura 38: Analizador sintáctico LR.

Básicamente un analizador sintáctico LR es un autómata finito de pila que reconoce prefijos viables y va construyendo el árbol sintáctico desde las hojas hasta la raíz.

Antes de entrar en detalles sobre la estructura del analizador, conviene definir qué es una configuración.

Una configuración es una tupla donde el primer componente es la pila y el segundo es la entrada restante por procesar.

Un analizador sintáctico LR tiene los siguientes componentes:

Buffer de entrada: Contiene la cadena a ser analizada.

Pila: En este caso guarda más información que el analizador sintáctico descendente predictivo. Los elementos registrados en la pila son de la forma donde es el símbolo de la cima de la pila. Los son estados que resumen el contenido de la pila. Los símbolos son símbolos de la gramática, tanto terminales como no terminales. En la práctica de construcción de este tipo de analizadores, no es necesario mantener los símbolos en las pilas, dado que el estado proporciona toda la información necesaria para acometer el análisis, pero aquí estamos desarrollando una herramienta orientada a la docencia, a la hora de seguir la traza del proceso de análisis es muy útil mantener también en la pila estos símbolos.

Tabla de análisis: La tabla de análisis tiene la misma función que en el analizador sintáctico predictivo, pero esta vez la tabla se divide en dos partes.

Tabla de acción: En las filas están los estados del autómata y en las columnas los símbolos terminales de la gramática. El contenido de las entradas de la tabla pueden ser:

Aceptar: El análisis sintáctico ha sido completado con éxito.

Error: El analizador sintáctico ha encontrado un error sintáctico.

Acción []= Desplazar y: es el siguiente estado al que hay que ir después de desplazar. La acción sería meter en la pila el símbolo actual de la entrada, avanzar la entrada y meter en la pila el estado . Por ejemplo, la configuración antes del desplazamiento debe ser:

Después de realizar el desplazamiento sería:

Acción[]Reducir : Se extraen símbolos de la pila (donde es la longitud de), se introduce en la pila la A y se calcula el nuevo estado con la tabla Ir_a[,A] = .

Tabla de Ir_a Tiene el mismo formato que la Tabla de acción. Cuando se realiza una reducción en la cima de la pila se queda un símbolo, pero siempre en la cima de la pila debe haber un símbolo de estado. La tabla de Ir_a sirve para saber cuál es el siguiente estado después de hacer una reducción.

El funcionamiento exacto del analizador se representa en este algoritmo:

Entrada: Tabla de Acción y la Tabla de Ir_a.

1:/* El símbolo S es el estado actual que está en la cima de la pila y el símbolo a es el terminal actual de la entrada.*/

2: loop

3: if Acción [S, a] = Desplazar y then

4: Meter en la Pila a y y avanzar en la cadena de entrada.

5: else if Acción[S, a] = Reducir por: then

6: Sacar símbolos de la pila. Sea S' el símbolo del tope de la pila, poner A y Luego Ir_a [S', A] en el tope de la pila.

7: else if Acción[S, a] = Aceptar then

8 terminar

9: else

10: Error

11: end if

12: end loop

Algoritmo 6: Algoritmo de análisis LR