A)
agregar la acción: "Desplazar a i". Donde i es el
índice del i-ésimo
estado.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
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.
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.