un item del cierre de I y
una producción de la gramática.En esta sección se explica la generación de las tablas de análisis. Existen tres tipos de tablas:
SLR (1): Es la forma más sencilla de construirla, pero tiene el inconveniente de que reconoce un número reducido de gramáticas.
LR (1): Es la técnica más general, pudiendo reconocer una número mayor de gramáticas que el SLR (1).
LALR (1): En potencia está entre el SLR (1) y el LR (1), pero tiene la ventaja de que las tablas de análisis tienen un tamaño más reducido.
Antes de entrar en los detalles de la generación de la tabla, hay que definir el termino item de análisis sintáctico (en adelante item). Un item, es una producción de la gramática con un marcador. Como se verá después, el marcador sirve para registrar hasta que zona de la parte derecha de una producción ha sido reconocida por el autómata. Por ejemplo, para la producción S → if C then B, se podrían tener los siguientes items:
S→• if C then B
S→if • C then B
S→if C • then B
S→if C then • B
S→if C then B •
El primer item indica que todavía no se ha procesado nada de la entrada y queda por ver if C then B, en cambio el segundo de ellos indica que ya se ha procesado en la entrada el if y queda por procesar C then B.
La producción S → ε, genera el item S → •
La idea básica del método SLR es construir un autómata finito determinista para reconocer los prefijos viables. Para facilitar la construcción del analizador no se trabaja directamente con la gramática, se trabaja con una gramática aumentada. La gramática aumentada es la misma, pero se le añade una producción más, donde su parte izquierda es el nuevo símbolo inicial y su parte derecha es el antiguo símbolo inicial de la gramática. Es decir, si se tuviera la siguiente gramática:
S→CC
C→cC
C→d
Su gramática extendida sería:
S'→S
S →CC
C→cC
C→d
La razón para hacer esta modificación es porque de esta manera es más fácil reconocer cuando se ha reconocido con éxito la cadena de entrada. Ya que una forma fácil de saber si el análisis ha finalizado con éxito, es cuando se reduzca el item S'→S.
Para la construcción de la tabla de análisis SLR, se utilizan las funciones presentadas a continuación.
Esta operación parte de un conjunto I de ítems cualquiera, donde inicialmente todo item del conjunto I pertenece al cierre de I, ahora con cada item de I aplicar la siguiente regla.
Sea S →
un item del cierre de I y
una producción de la gramática.
Entonces
hay que agregar el item
A
al cierre de I (si no se había agregado previamente),es decir,
hay que agregar todas las producciones de A con la marca al
principio.
Este procedimiento hay que aplicarlo continuamente hasta que ya no se puedan agregar más items al conjunto del cierre.
De manera
informal lo que hace el cierre, es calcular todos los items que a
partir de un item pueden ser generados en el análisis
sintáctico. Es decir, si se tiene el item
,
es posible que en la entrada exista una cadena que derive en alguna
producción de C.
Por ejemplo, si se tiene la siguiente gramática (ya es la gramática extendida):
S'→S
S →CC
C→cC
C→d
Y se parte
del conjunto I, con su primer item {
},
el cierre de I, daría como resultado:
Como se puede ver en el ejemplo anterior lo único que hay que hacer es expandir los no terminales de los items donde el marcador esté delante de un símbolo no terminal.
El procedimiento para calcular el cierre puede verse en el siguiente algoritmo (Algoritmo7):
Entrada: I, conjunto de items de una gramática ampliada G’ = (V ', T, P ‘, S’)
Salida:
1:
I: =
2: repeat
3:
for all
do
4:
for all
B
P
' do
5:
if [
]
then
6:
:=
[{[
]}
7: end if
8: end for
9: end for
10: until no hay cambio
Algoritmo 7: Algoritmo del cálculo del cierre.
La función
sucesor parte de I, un conjunto de items y X
un símbolo de la gramática. La función
sucesor es la cerradura del conjunto de todos los elementos
siempre y cuando
exista previamente en I.
De manera
informal lo que hace la función sucesor es calcular el
siguiente estado, al cual se puede ir a partir del símbolo X,
con los items de I, en los cuales el marcador está de la
forma:
El procedimiento para calcular el sucesor puede verse en el siguiente algoritmo (Algoritmo 8).
Entrada: I, conjunto de items de una gramática ampliada G' = (V',T' ,P',S')
,
X es un símbolo de la gramática (terminal o no
terminal)
Salida: Conjunto sucesor.
1: S: = Ø
2:
for all
I do
3:
S: =
4: end for
5: return Cierre(S)
Algoritmo 8: Algoritmo del cálculo del sucesor.
Por último, sólo queda la función del cálculo de todos los estados. Partiendo del estado inicial se calcula el cierre de dicho estado y el sucesor de ese estado con todos los símbolos terminales de la gramática.
Con los nuevos estados se procede de igual forma hasta que no se puedan agregar más estados al conjunto de estados.
El procedimiento se muestra en el siguiente algoritmo (Algoritmo 9).
Entrada: G es la gramática aumentada para la que se construye el analizador sintáctico
Salida: C
1: i:= 0
2:
:
= Cierre ([])
3: C: = C
{}
4: while C cambie do
5:
for all S
C do
6:
for all X
V
T do
7: J: = FOLLOW(S, X)
8:
if (J
Ø)
and (J
C)
then
9: i:= i+1
10:
:= J
11:
C: = C
{}
12: end if
13: end for
14: end for
15: end while
Algoritmo 9: Algoritmo del cálculo del conjunto de estados.
Por ejemplo sea la siguiente gramática:
E→E +T
E→T
T→ (E)
T→num
Se genera el autómata que reconoce los prefijos viables, que se puede ver en la siguiente figura (Figura 39).
Figura 39: Autómata finito generado por el método SLR.