Construcción de las Tablas para el Análisis SLR

Los conjuntos de Primeros y Siguientes

Repasemos las nociones de conjuntos de Primeros y siguientes:

Definición 35.3.1   Dada una gramática $G =(\Sigma,V,P,S)$ y un símbolo $\alpha \in (V \cup \Sigma)^*$ se define el conjunto $FIRST(\alpha)$ como:

$FIRST(\alpha) = \left \{ b \in \Sigma : \alpha \stackrel{*}{\Longrightarrow} b \beta \right \} \cup N(\alpha)$

donde:

$N(\alpha) = \left \{ \begin{array}{ll} \left \{ \epsilon \right \}& \mbox{si ... ...htarrow} \epsilon$} \\ \emptyset & \mbox{en otro caso} \end{array} \right.$

Definición 35.3.2   Dada una gramática $G =(\Sigma,V,P,S)$ y una variable $A \in V$ se define el conjunto $FOLLOW(A)$ como:

$FOLLOW(A) = \left \{ b \in \Sigma : \exists S \stackrel{*}{\Longrightarrow} \alpha A b \beta \right \} \cup E(A)$

donde

$E(A) = \left \{ \begin{array}{ll} \{ \$ \}& \mbox{si $S \stackrel{*}{\Longrightarrow} \alpha A$} \\ \emptyset & \mbox{en otro caso} \end{array} \right.$

Algoritmo 35.3.1   Construcción de los conjuntos $FIRST(X)$

1. $Si X \in \Sigma entonces FIRST(X) = {X}$
2. $Si X \rightarrow \epsilon entonces FIRST(X) = FIRST(X) \cup \{ \epsilon \}$
3. $Si X \in V y X \rightarrow Y_1 Y_2 \cdots Y_k \in P entonces$
   

   $$i = 1;$$

   $$do$$

   $$FIRST(X) = FIRST(X) \cup FIRST(Y_i) - \{ \epsilon \};$$

   $$i++;$$

   $$mientras (\epsilon \in FIRST(Y_i) and (i \leq k))$$

   $$si (\epsilon \in FIRST(Y_k) and i > k) FIRST(X) = FIRST(X) \cup \{ \epsilon \}$$

   
   

Este algoritmo puede ser extendido para calcular $FIRST(\alpha)$ para $\alpha = X_1 X_2 \cdots X_n \in (V \cup \Sigma)^*$.

Algoritmo 35.3.2   Construcción del conjunto $FIRST(\alpha)$

$$i = 1;$$

$$FIRST(\alpha) = \emptyset;$$

$$do$$

$$FIRST(\alpha) = FIRST(\alpha) \cup FIRST(X_i) - \{ \epsilon \};$$

$$i++;$$

$$mientras (\epsilon \in FIRST(X_i) and (i \leq n))$$

$$si (\epsilon \in FIRST(X_n) and i > n) FIRST(\alpha) = FIRST(X) \cup \{ \epsilon \}$$

Algoritmo 35.3.3   Construcción de los conjuntos $FOLLOW(A)$ para las variables sintácticas $A \in V$:

Repetir los siguientes pasos hasta que ninguno de los conjuntos $FOLLOW$ cambie:

1. $FOLLOW(S) = \{\$\}$ ($\$ representa el final de la entrada)
2. $Si A \rightarrow \alpha B \beta entonces$
   $$FOLLOW(B) = FOLLOW(B) \cup (FIRST(\beta) - \{\epsilon\})$$

3. $Si A \rightarrow \alpha B$ o bien $A \rightarrow \alpha B \beta$ y $\epsilon \in FIRST(\beta)$ entonces
   $$FOLLOW(B) = FOLLOW(B) \cup FOLLOW(A)$$

Construcción de las Tablas

Para la construcción de las tablas de un analizador SLR se construye el autómata finito determinista (DFA) $(Q, \Sigma, \delta, q_0)$ equivalente al NFA presentado en la sección 35.2 usando el algoritmo de construcción del subconjunto.

Como recordará, en la construcción del subconjunto, partiendo del estado de arranque $q_0$ del NFA con $\epsilon$-transiciones se calcula su clausura $\overline{\{q_0\}}$ y las clausuras de los conjuntos de estados $\overline{\delta(\overline{\{q_0\}},a)}$ a los que transita. Se repite el proceso con los conjuntos resultantes hasta que no se introducen nuevos conjuntos-estado.

La clausura $\overline{A}$ de un subconjunto de estados del autómata $A$ esta formada por todos los estados que pueden ser alcanzados mediante transiciones etiquetadas con la palabra vacía (denominadas $\epsilon$ transiciones) desde los estados de $A$. Se incluyen en $\overline{A}$, naturalmente los estados de $A$.

$\overline{A} = \{ q \in Q / \exists q' \in Q : \hat{\delta}(q, \epsilon) = q \}$

Aquí $\hat{\delta}$ denota la función de transición del autómata extendida a cadenas de $\Sigma^*$.

$$\hat{\delta}(q, x) = \left \{ \begin{array}{ll} \delta(\hat{\delt... ...,y),a) & \mbox{si $x = ya$} q & \mbox{si $x = \epsilon$} \end{array} \right.$$ (35.1)

En la práctica, y a partir de ahora así lo haremos, se prescinde de diferenciar entre $\delta$ y $\hat{\delta}$ usándose indistintamente la notación $\delta$ para ambas funciones.

La clausura puede ser computada usando una estructura de pila o aplicando la expresión recursiva dada en la ecuación 35.1.

Para el NFA mostrado en el ejemplo 35.2.1 el DFA construído mediante esta técnica es el que se muestra en la figura 35.2. Se ha utilizado el símbolo # como marcador. Se ha omitido el número 3 para que los estados coincidan en numeración con los generados por yapp (véase el cuadro 35.1).

Figura 34.2: DFA equivalente al NFA de la figura 35.1

Un analizador sintáctico LR utiliza una tabla para su análisis. Esa tabla se construye a partir de la tabla de transiciones del DFA. De hecho, la tabla se divide en dos tablas, una llamada tabla de saltos o tabla de gotos y la otra tabla de acciones.

La tabla goto de un analizador SLR no es más que la tabla de transiciones del autómata DFA obtenido aplicando la construcción del subconjunto al NFA definido en 35.2.4. De hecho es la tabla de transiciones restringida a $V$ (recuerde que el alfabeto del autómata es $V \cup \Sigma$). Esto es,

$\delta_{\vert V \times Q} : V \times Q \rightarrow Q$.

donde se define $goto(i, A) = \delta(A,I_i)$

La parte de la función de transiciones del DFA que corresponde a los terminales que no producen rechazo, esto es, $\delta_{\vert \Sigma \times Q} : \Sigma \times Q \rightarrow Q$ se adjunta a una tabla que se denomina tabla de acciones. La tabla de acciones es una tabla de doble entrada en los estados y en los símbolos de $\Sigma$. Las acciones de transición ante terminales se denominan acciones de desplazamiento o (acciones shift):

$\delta_{\vert \Sigma \times Q} : \Sigma \times Q \rightarrow Q$

donde se define $action(i, a) = \delta(a,I_i)$

Cuando un estado $s$ contiene un LR(0)-item de la forma $A \rightarrow \alpha_\uparrow$, esto es, el estado corresponde a un posible rechazo, ello indica que hemos llegado a un final del prefijo viable, que hemos visto $\alpha$ y que, por tanto, es probable que $A \rightarrow \alpha$ sea el handle de la forma sentencial derecha actual. Por tanto, añadiremos en entradas de la forma $(s,a)$ de la tabla de acciones una acción que indique que hemos encontrado el mango en la posición actual y que la regla asociada es $A \rightarrow \alpha$. A una acción de este tipo se la denomina acción de reducción.

La cuestión es, ¿para que valores de $a \in \Sigma$ debemos disponer que la acción para $(s,a)$ es de reducción? Podríamos decidir que ante cualquier terminal $a \in \Sigma$ que produzca un rechazo del autómata, pero podemos ser un poco mas selectivos. No cualquier terminal puede estar en la entrada en el momento en el que se produce la antiderivación o reducción. Observemos que si $A \rightarrow \alpha$ es el handle de $\gamma$ es porque:

$\exists S \begin{array}{c} * \Longrightarrow {\scriptstyle RM} \end{array... ...* \Longrightarrow {\scriptstyle RM} \end{array} \beta \alpha b x = \gamma$

Por tanto, cuando estamos reduciendo por $A \rightarrow \alpha$ los únicos terminales legales que cabe esperar en una reducción por $A \rightarrow \alpha$ son los terminales $b \in FOLLOW(A)$.

Dada una gramática $G =(\Sigma,V,P,S)$, podemos construir las tablas de acciones (action table) y transiciones (gotos table) mediante el siguiente algoritmo:

Algoritmo 35.3.4   Construcción de Tablas SLR

1. Utilizando el Algoritmo de Construcción del Subconjunto, se construye el Autómata Finito Determinista (DFA) $(Q, V \cup \Sigma, \delta, I_0, F)$ equivalente al Autómata Finito No Determinista (NFA) definido en 35.2.4. Sea $C = \left \{ I_1, I_2, \cdots I_n \right \}$ el conjunto de estados del DFA. Cada estado $I_i$ es un conjunto de LR(0)-items o estados del NFA. Asociemos un índice $i$ con cada conjunto $I_i$.
2. La tabla de gotos no es más que la función de transición del autómata restringida a las variables de la gramática:
   $goto(i,A) = \delta(I_i, A)$ para todo $A \in V$
3. Las acciones para el estado $I_i$ se determinan como sigue:
   1. Si $A \rightarrow \alpha _\uparrow a \beta \in I_i$, $\delta(I_i,a) = I_j$, $a \in \Sigma$ entonces:
      $action[i][a] = shift j$
   2. Si $S' \rightarrow S_\uparrow \in I_i$ entonces
      $action[i][\$] = accept$
   3. Para cualquier otro caso de la forma $A \rightarrow \alpha _\uparrow \in I_i$ distinto del anterior hacer
      $\forall a \in FOLLOW(A): action[i][a] = reduce A \rightarrow \alpha$
4. Las entradas de la tabla de acción que queden indefinidas después de aplicado el proceso anterior corresponden a acciones de ``$error$''.

Definición 35.3.3   Si alguna de las entradas de la tabla resulta multievaluada, decimos que existe un conflicto y que la gramática no es SLR.

1. En tal caso, si una de las acciones es de `reducción'' y la otra es de `desplazamiento'', decimos que hay un conflicto shift-reduce o conflicto de desplazamiento-reducción.
2. Si las dos reglas indican una acción de reducción, decimos que tenemos un conflicto reduce-reduce o de reducción-reducción.

Ejemplo 35.3.1   Al aplicar el algoritmo 35.3.4 a la gramática 35.2.1

1	S $\rightarrow$ a S b
2	S $\rightarrow$ $\epsilon$

partiendo del autómata finito determinista que se construyó en la figura 35.2 y calculando los conjuntos de primeros y siguientes

	FIRST	FOLLOW
S	a, $\epsilon$	b, $

obtenemos la siguiente tabla de acciones SLR:

	a	b	$
0	s2	r2	r2
1			aceptar
2	s2	r2	r2
4		s5
5		r1	r1

Las entradas denotadas con $s$ $n$ ($s$ por shift) indican un desplazamiento al estado $n$, las denotadas con $r$ $n$ ($r$ por reduce o reducción) indican una operación de reducción o antiderivación por la regla $n$. Las entradas vacías corresponden a acciones de error.

El método de análisis LALR usado por yapp es una extensión del método SLR esbozado aqui. Supone un compromiso entre potencia (conjunto de gramáticas englobadas) y eficiencia (cantidad de memoria utilizada, tiempo de proceso). Veamos como yapp aplica la construcción del subconjunto a la gramática del ejemplo 35.2.1. Para ello construimos el siguiente programa yapp:

$ cat -n aSb.yp
     1  %%
     2  S:  # empty
     3      |   'a' S 'b'  
     4  ;
     5  %%
     ......

y compilamos, haciendo uso de la opción -v para que yapp produzca las tablas en el fichero aSb.output:

$ ls -l aSb.*
-rw-r--r--  1 lhp lhp  738 2004-12-19 09:52 aSb.output
-rw-r--r--  1 lhp lhp 1841 2004-12-19 09:52 aSb.pm
-rw-r--r--  1 lhp lhp  677 2004-12-19 09:46 aSb.yp

El contenido del fichero aSb.output se muestra en la tabla 35.1. Los números de referencia a las producciones en las acciones de reducción vienen dados por:

                      0:	$start -> S $end
                      1:	S -> /* empty */
                      2:	S -> 'a' S 'b'

Observe que el final de la entrada se denota por $end y el marcador en un LR-item por un punto. Fíjese en el estado 2: En ese estado están también los items

S -> . 'a' S 'b' y S -> .

sin embargo no se explicitan por que se entiende que su pertenencia es consecuencia directa de aplicar la operación de clausura. Los LR items cuyo marcador no está al principio se denominan items núcleo.

Tabla 35.1: Tablas generadas por yapp. El estado 3 resulta de transitar con $

Estado 0	Estado 1	Estado 2
$start -> . S $end 'a' shift 2 $default reduce 1 (S) S go to state 1	$start -> S . $end $end shift 3	S -> 'a' . S 'b' 'a' shift 2 $default reduce 1 (S) S go to state 4
Estado 3	Estado 4	Estado 5
$start -> S $end . $default accept	S -> 'a' S . 'b' 'b' shift 5	S -> 'a' S 'b' . $default reduce 2 (S)

Puede encontrar el listado completo de las tablas en aSb.output en el apéndice que se encuentra en la página .

Ejercicio 35.3.1   Compare la tabla 35.1 resultante de aplicar yapp con la que obtuvo en el ejemplo 35.3.1.