Construcción de las tablas de
análisis SLR
Una vez
generado al autómata, se pueden generar las tablas de
análisis.
La
generación de la tabla de análisis se hace en dos
pasos:
Generación
de la tabla de acción
Generación
de la tabla Ir_a
Generación de la tabla de
acción
La idea
básica del algoritmo es sencilla, el algoritmo hace lo
siguiente.
Para el
j-ésimo
item del i-ésimo
estado hacer:
Si el item
es un desplazamiento( A)
agregar la acción: "Desplazar a i". Donde i es el
índice del i-ésimo
estado.
Si el item
es una reducción ( )
agregar la acción: "Reducir por
 ".
Si es el
item
 ,
agregar la acción: "Aceptar"
Cualquier
otra entrada no rellenada de la tabla poner error. En el siguiente
algoritmo (Algoritmo10) se muestran los resultados.
Entrada:
C, la colección canónica de estados del autómata.
Salida:
Tabla de Acción
1:
for all
 
C do
2:
for all item
do
3:
if []
and Sucesor
(,a)
=
 then
4:
Acción
[,a]
= Desplazar y
5:
else if [ ]
then
6:
for all a
FOLLOW (A) do
7:
Acción
[,a]
= Reducir por
8:
end for
9: end
if
10:
if [
] then
11:
Acción
[,
$] = Aceptar
12:
end if
13:
end for
14:
end for
Algoritmo
10: Algoritmo de generación
de la tabla de acción.
Para las
restantes entradas de la tabla que no están rellenadas poner
ERROR.
Generación de la tabla Ir_A
Para
generar la tabla “Ir_A” lo único que hay que hacer
es ver en cada estado, las transiciones que hay debidas a no
terminales. En ese estado y con dicho no terminal hay que poner el
identificador del estado destino. En el siguiente algoritmo
(Algoritmo 11) se describe este procedimiento de manera más
formal.
Entrada:
C, la colección canónica de estados del autómata.
Salida:
Tabla de Ir_A
1:
for all X
C
do
2:
if Sucesor (,
X) =
then
3: Ir_A
[,
X] =
4:
else
5: ERROR
6:
end if
7: end
for
Algoritmo
11: Algoritmo de generación
de la tabla Ir_A
En la
siguiente tabla puede verse un ejemplo de generación de la
tabla de análisis utilizando el método SLR. Esta tabla
ha sido generada a partir del autómata de la figura anterior
(Figura 39).
|
|
+
|
(
|
)
|
num
|
$
|
E
|
T
|
|
0
|
|
D3
|
|
D4
|
|
1
|
2
|
|
1
|
D5
|
|
|
|
Aceptar
|
|
|
|
2
|
R2
|
|
R2
|
|
R2
|
|
|
|
3
|
|
D3
|
|
D4
|
|
6
|
2
|
|
4
|
R4
|
|
R4
|
|
R4
|
|
|
|
5
|
|
D3
|
|
D4
|
|
|
7
|
|
6
|
D5
|
|
D8
|
|
|
|
|
|
7
|
R1
|
|
R1
|
|
R1
|
|
|
|
8
|
R3
|
|
R3
|
|
R3
|
|
|
Tabla
4: Tabla de análisis LR1
Por
ejemplo, en el estado 0 hay dos desplazamientos, el debido al símbolo
( y al del símbolo num. Por eso en la tabla de
análisis en la fila 0 y en las correspondientes columnas hay
una D y un número indicando el siguiente estado.
También en ese estado se rellena la parte de Ir_A, ya que hay
dos transiciones con los no terminales 'E'
y 'T'. En resumen, en cada estado sólo hay
que comprobar que tipo de acción realizar y anotarla en la
tabla.
|
