Sig: Algoritmo de Análisis LR Sup: Construcción de las Tablas Ant: Los conjuntos de Primeros Err: Si hallas una errata ...

Subsecciones

• • Clausura de un Conjunto de Estados
  • Ejemplo de Construcción del DFA
  • Las Tablas de Saltos y de Acciones
  • Ante que Terminales se debe Reducir
  • Algoritmo de Construcción de Las Tablas SLR
  • Conflictos en Un Analizador SLR
  • Ejemplo de Cálculo de las Tablas SLR
  • Las Tablas Construidas por eyapp

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 8.23 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.

Clausura de un Conjunto de Estados

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.$$ (8.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 8.1. Una forma de computarla viene dada por el siguiente seudocódigo:

function closure(I : set of LR(0)-items) 
begin
  J = I;
  repeat
    changes = FALSE;
    for A->alpha . B beta in J do
      for B->gamma in G do
        next if B->.gamma in J
        insert B->.gamma in J
        changes = TRUE;
      end for
    end for
  until nochanges;
  return J
end

Ejemplo de Construcción del DFA

Para el NFA mostrado en el ejemplo 8.23.1 el DFA construído mediante esta técnica es el que se muestra en la figura 8.24.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 eyapp (véase el cuadro 8.24.2).

Figura 8.2: DFA equivalente al NFA de la figura 8.23.1

Las Tablas de Saltos y de Acciones

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

Ante que Terminales se debe Reducir

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

Algoritmo de Construcción de Las Tablas SLR

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 8.24.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 8.23.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$ ''.

Conflictos en Un Analizador SLR

Definición 8.24.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 de Cálculo de las Tablas SLR

Ejemplo 8.24.1   Al aplicar el algoritmo 8.24.4 a la gramática 8.23.1

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

partiendo del autómata finito determinista que se construyó en la figura 8.24.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.

Las Tablas Construidas por eyapp

El método de análisis LALR usado por eyapp 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 eyapp aplica la construcción del subconjunto a la gramática del ejemplo 8.23.1. Para ello construimos el siguiente programa eyapp:

$ 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 eyapp 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 8.24.2. 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 8.2: Tablas generadas por eyapp. 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 8.24.1   Compare la tabla 8.24.2 resultante de aplicar eyapp con la que obtuvo en el ejemplo 8.24.1.

Sig: Algoritmo de Análisis LR Sup: Construcción de las Tablas Ant: Los conjuntos de Primeros Err: Si hallas una errata ...