Sig: Construcción de los conjuntos Sup: Análisis Sintáctico Predictivo Recursivo Ant: Ejercicio: Factores Comunes Err: Si hallas una errata ...

Derivaciones a vacío

Surge un problema cuando $A \rightarrow \gamma_1 \mid \ldots \mid \gamma_n$ y la palabra vacía está en alguno de los conjuntos $FIRST(\gamma_i)$. ¿Que hacer entonces?

Nótese que si $A \rightarrow \gamma$ y $\epsilon \in FIRST(\gamma)$ es porque existe una derivación $\gamma \stackrel{*}{\Longrightarrow} \epsilon$. ¿Que terminales podemos legalmente encontrarnos cuando estamos en la subrutina A? Consideremos una derivación desde el símbolo de arranque en la que se use la producción $A \rightarrow \gamma$. Dicha derivación forzosamente tendrá la forma:

$S \stackrel{*}{\Longrightarrow} \beta A a \mu \Longrightarrow \beta \gamma a \mu \stackrel{*}{\Longrightarrow} \beta a \mu$.

Cualquier terminal $a \in \Sigma$ que pueda aparecer en una derivación desde el símbolo de arranque inmediatamente a continuación de la variable $A$ es susceptible de ser visto cuando se esta analizando $A$ y se aplicó $A \rightarrow \gamma$ con $\gamma \stackrel{*}{\Longrightarrow} \epsilon$. Esto nos lleva a la definición del conjunto $FOLLOW(A)$ como conjunto de terminales que pueden aparecer a continuación de $A$ en una derivación desde el símbolo de arranque:

Definición 11.6.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.$

Aqui $\$ denota el final de la entrada (que se corresponde en el código Perl anterior con el terminal EOI).

Si $A \rightarrow \gamma_1 \mid \ldots \mid \gamma_n$ dado que los conjuntos $FIRST(\gamma_i)$ han de ser disjuntos para que un analizador predictivo APDR funcione, sólo una parte derecha puede contener la palabra vacía en su $FIRST$. Supongamos que es $\gamma_n$. Podemos reformular la construcción del procedimiento para la variable $A$ siguiendo este seudocódigo:

sub A {
  if ($lookahead in FIRST(gamma_1)) { imitar gamma_1 }
  elsif ($lookahead in FIRST(gamma_2)) { imitar gamma_2 }
  ...
  else ($lookahead in FIRST(gamma_n) or $lookahead in FOLLOW(A)) { imitar gamma_n }
}

Un caso particular de $\gamma_n \stackrel{*}{\Longrightarrow} \epsilon$ es que $\gamma_n = \epsilon$. En tal caso, y como es obvio, el significado de imitar gamma_n es equivalente a ejecutar una sentencia vacía.

Sig: Construcción de los conjuntos Sup: Análisis Sintáctico Predictivo Recursivo Ant: Ejercicio: Factores Comunes Err: Si hallas una errata ...