Sig: Ejercicio: Construir los Sup: Análisis Sintáctico Predictivo Recursivo Ant: Derivaciones a vacío Err: Si hallas una errata ...

Construcción de los conjuntos de Primeros y Siguientes

Algoritmo 4.6.1   Construcción de los conjuntos $FIRST(X)$

Repita el siguiente conjunto de reglas hasta que no se puedan añadir mas símbolos terminales o a ningún conjunto $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;$$

   $$hacer$$

   $$FIRST(X) = FIRST(X) \cup FIRST^*(Y_i);$$

   $$i++;$$

   $$mientras (i \leq k y \epsilon \in FIRST(Y_i))$$

   
   
4. Añadir $\epsilon$ a $FIRST(X)$ si $i \geq k$ y $\epsilon \in FIRST(Y_k)$

Aqui $FIRST^*(Y)$ denota al conjunto $FIRST(Y) - \{ \epsilon \}$ .

Este algoritmo puede ser extendido para calcular $FIRST(\alpha)$ para $\alpha = X_1 X_2 \cdots X_n \in (V \cup \Sigma)^*$ . El esquema es anólogo al de un símbolo individual.

Algoritmo 4.6.2   Construcción del conjunto $FIRST(\alpha)$

Repita siguiente conjunto de reglas hasta que no se puedan añadir mas símbolos terminales o a ningún conjunto $FIRST(\alpha)$ :

$$i = 1;$$

$$FIRST(\alpha) = \emptyset;$$

$$hacer$$

$$FIRST(\alpha) = FIRST(\alpha) \cup FIRST^*(X_i);$$

$$i++;$$

$$mientras (i \leq n y \epsilon \in FIRST(X_i))$$

Algoritmo 4.6.3   Construcción de los conjuntos $FOLLOW(A) \forall 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 A \rightarrow \alpha B \beta y \epsilon \in FIRST(\beta) entonces$
   $$FOLLOW(B) = FOLLOW(B) \cup FOLLOW(A)$$

Sig: Ejercicio: Construir los Sup: Análisis Sintáctico Predictivo Recursivo Ant: Derivaciones a vacío Err: Si hallas una errata ...