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