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 sólo 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.
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 sólo 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, sólo 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
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, sólo 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 sólo se pone la reducción en su símbolo de anticipación.