Sig: Construcción de las Tablas Sup: Construcción de las Tablas Ant: Construcción de las Tablas Err: Si hallas una errata ...

Los conjuntos de Primeros y Siguientes

Repasemos las nociones de conjuntos de Primeros y siguientes:

Definición 7.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 $... ...rightarrow} \epsilon$} \\ \emptyset & \mbox{en otro caso} \end{array}\right.$

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

Sig: Construcción de las Tablas Sup: Construcción de las Tablas Ant: Construcción de las Tablas Err: Si hallas una errata ...