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