Generación de la tabla de análisis

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.

Cálculo del cierre o clausura

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.

Cálculo del sucesor

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.

Cálculo del conjunto de estados

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.