Construcción de las tablas de
análisis LR
La clave
del análisis LR son las reducciones, mientras que en análisis
SLR se hacía la reducción por todos los seguidores de
la parte izquierda del item a reducir, en el LR solo se hace
la reducción por los símbolos de anticipación
del item.
Para
realizar el análisis LR hay que modificar la función de
cierre y la de la generación de la tabla de acción.
Cálculo del cierre
Al
calcular el cierre de un item de un estado en el análisis SLR,
lo que se hacía era ver el símbolo a la derecha del
marcador y crear nuevos items (si no existían previamente),
con las producciones donde el símbolo marcado sea la parte
izquierda. En cambio, en el análisis LR, se registra que
símbolos pueden aparecer detrás del símbolo
marcado, para cuando se tenga que realizar la reducción,
reducir solo por estos símbolos y no por todos los
seguidores.
Por
ejemplo, si se tuviera el siguiente item:
El nuevo
item que se genera es
Como se
puede ver, se añade a los nuevos items los iniciales de la
parte que le sigue al símbolo marcado, como se verá en
el siguiente algoritmo (Algoritmo 12).
Por
ejemplo:
S'→S
S→Ab
S→Bc
A→a
B→a
A→cBb
El cierre
de I sería:
S'→S,
$
S
→Ab, $
S
→Bc, $
A→a,
b
B→a,
b
A→cBb,
c
Si al
rellenar la tabla se llega a un conflicto (desplazamiento/reducción,
reducción/reducción), el método no es aplicable
y la gramática no es LR. Si no existen conflictos entonces la
gramática es LR.
La ventaja
del método LR es que reconoce un número mayor de
lenguajes que el SLR, pero tiene el inconveniente de que las tablas
de análisis son mayores.
Entrada:
I, conjunto de elementos de una gramática ampliada G' =
(V',T,P ' ,S ' )
Salida:
1:
I: =
2:
repeat
3:
for all [ ,
a]
do
4:
for all
 B
P
'do
5:
for all b
FIRST(
 )
do
6:
if
then
7:
:=
 {
[
 ]}
8:
end if
9:
end for
10:
end for
11: end
for
12: until
no hay cambio
Algoritmo
12: Algoritmo del cálculo
del cierre LR.
Por
ejemplo sea la siguiente gramática:
S→C
C
C→c
C
C→d
Aplicando
el mismo método que se aplicó para generar la tabla de
análisis SLR, pero con las nuevas versiones para el LR se
generaría el autómata que se puede ver en la siguiente
figura (Figura 40).
Ahora con
el método LR los items incorporan los símbolos de
anticipación, a diferencia del análisis LR. Por
ejemplo, con el método SLR los estados 3 y 6 no hubieran
existido por separado, solo hubiera habido uno de ellos. En
cambio, con el método LR como sí tiene en cuenta los
símbolos de anticipación, sí que son estados
diferentes.
 
Figura
40: Autómata generada mediante el método LR
Generación de la tabla de
acción
La parte
de esta función que hay que modificar con respecto al análisis
SLR, es la parte concerniente a la reducción. En vez de
reducir por todos los símbolos seguidores, solo hay que
reducir por los símbolos de anticipación. En el
siguiente algoritmo (Algoritmo13) se ve el algoritmo completo.
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 FOLLOW
(,
a) =
then
4:
Acción
[,
a] = Desplazar y
5:
else if [ ]
then
6:
Acción
[,
b]
= Reducir por
7:
end if
8:
if [ ]
then
9:
Acción
[,
$] = Aceptar
10:
end if
11:
end for
12:
end for
13: Para
las restantes entradas de la tabla que no están rellenadas
poner ERROR.
Algoritmo
13: Algoritmo de generación
de la tabla de acción
Como puede
verse en la siguiente tabla (Tabla5), cuando se hace una reducción,
sólo se reduce por los símbolos de anticipación.
|
|
c
|
d
|
$
|
S
|
C
|
|
0
|
D3
|
D4
|
|
1
|
2
|
|
1
|
|
|
ACEPTAR
|
|
|
|
2
|
D6
|
D7
|
|
|
5
|
|
3
|
D3
|
D4
|
|
|
8
|
|
4
|
R3
|
R3
|
|
|
|
|
5
|
|
|
R1
|
|
|
|
6
|
D6
|
D7
|
|
|
9
|
|
7
|
|
|
R3
|
|
|
|
8
|
R2
|
R2
|
|
|
|
|
9
|
|
|
R2
|
|
|
Tabla
5: Tabla de analisis LR
Por
ejemplo, en el estado 9 hay una reducción, al generar la tabla
de análisis si se utilizara el método SLR, habría
que poner dicha reducción en todos los seguidores del no
terminal C, que son los terminales {c, d, $}. En cambio al utilizar
el método LR solo se pone la reducción en su
símbolo de anticipación.
|
