next up previous contents index PLPL moodlepserratamodulosperlmonksperldocapuntes LHPgoogleetsiiullpcgull
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 4.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.


next up previous contents index PLPL moodlepserratamodulosperlmonksperldocapuntes LHPgoogleetsiiullpcgull
Sig: Construcción de los conjuntos Sup: Análisis Sintáctico Predictivo Recursivo Ant: Ejercicio: Factores Comunes Err: Si hallas una errata ...
Casiano Rodríguez León
2012-05-22