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 34.5.1   Dada una gramática $G =(\Sigma,V,P,S)$ y una frase $\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 34.5.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 34.5.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 34.5.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 34.5.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.$$ (34.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 jison (véase el cuadro 35.1).

Figura 35.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$, $i$ denota al i-ésimo estado resultante de aplicar la construcción del subconjunto y que $I_i$ denota al conjunto de LR(0) item asociado con dicho estado):

$\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) = shift \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?

Se define $action(i, a) = reduce A \rightarrow \alpha$ ¿Pero, para que $a \in \Sigma$?

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)$.

Se define $action(i, b) = reduce A \rightarrow \alpha$ Para $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 34.5.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 34.5.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 34.5.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 jison 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 jison aplica la construcción del subconjunto a la gramática del ejemplo 35.2.1. Para ello construimos el siguiente programa jison:

[~/srcPLgrado/aSb(develop)]$ cat -n aSb.jison 
     1  %lex
     2  %%
     3  .               { return yytext; }
     4  /lex
     5  %%
     6  P: S            { return $1; }
     7  ;
     8  S: /* empty */  { console.log("empty");    $$ = ''; }
     9     | 'a' S 'b'  { console.log("S -> aSb"); $$ = $1+$2+$3; }
    10  ;
    11  %%

y lo compilamos con jison. Estas son las opciones disponibles:

nereida:[~/PLgradoBOOK(eps)]$ jison --help

Usage: jison [file] [lexfile] [options]

file        file containing a grammar
lexfile     file containing a lexical grammar

Options:
   -o FILE, --outfile FILE       Filename and base module name of the generated parser
   -t, --debug                   Debug mode
   -t TYPE, --module-type TYPE   The type of module to generate (commonjs, amd, js)
   -V, --version                 print version and exit

Desafortunadamente carece de la típica opción -v que permite generar las tablas de análisis. Podemos intentar usar bison, pero, obviamente, bison protesta ante la entrada:

[~/srcPLgrado/aSb(develop)]$ bison -v aSb.jison 
aSb.jison:1.1-4: invalid directive: `%lex'
aSb.jison:3.1: syntax error, unexpected identifier
aSb.jison:4.1: invalid character: `/'

El error es causado por la presencia del analizador léxico empotrado en el fichero aSb.jison. Si suprimimos provisionalmente las líneas del analizador léxico empotrado, bison es capaz de analizar la gramática:

[~/srcPLgrado/aSb(develop)]$ bison -v aSb.jison 
[~/srcPLgrado/aSb(develop)]$ ls -ltr | tail -1
-rw-rw-r--  1 casiano  staff    926 19 mar 13:29 aSb.output

Que tiene los siguientes contenidos:

[~/srcPLgrado/aSb(develop)]$ cat -n aSb.output 
     1  Grammar
     2  
     3      0 $accept: P $end
     4  
     5      1 P: S
     6  
     7      2 S: /* empty */
     8      3  | 'a' S 'b'
     9  
    10  
    11  Terminals, with rules where they appear
    12  
    13  $end (0) 0
    14  'a' (97) 3
    15  'b' (98) 3
    16  error (256)
    17  
    18  
    19  Nonterminals, with rules where they appear
    20  
    21  $accept (5)
    22      on left: 0
    23  P (6)
    24      on left: 1, on right: 0
    25  S (7)
    26      on left: 2 3, on right: 1 3
    27  
    28  
    29  state 0
    30  
    31      0 $accept: . P $end
    32  
    33      'a'  shift, and go to state 1
    34  
    35      $default  reduce using rule 2 (S)
    36  
    37      P  go to state 2
    38      S  go to state 3
    39  
    40  
    41  state 1
    42  
    43      3 S: 'a' . S 'b'
    44  
    45      'a'  shift, and go to state 1
    46  
    47      $default  reduce using rule 2 (S)
    48  
    49      S  go to state 4
    50  
    51  
    52  state 2
    53  
    54      0 $accept: P . $end
    55  
    56      $end  shift, and go to state 5
    57  
    58  
    59  state 3
    60  
    61      1 P: S .
    62  
    63      $default  reduce using rule 1 (P)
    64  
    65  
    66  state 4
    67  
    68      3 S: 'a' S . 'b'
    69  
    70      'b'  shift, and go to state 6
    71  
    72  
    73  state 5
    74  
    75      0 $accept: P $end .
    76  
    77      $default  accept
    78  
    79  
    80  state 6
    81  
    82      3 S: 'a' S 'b' .
    83  
    84      $default  reduce using rule 3 (S)

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 1: 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.