next up previous contents index PLPL moodlepserratamodulosperlmonksperldocapuntes LHPgoogleetsiiullpcgull
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$
        $\displaystyle i = 1;$  
        $\displaystyle hacer$  
        $\displaystyle \ \ FIRST(X) = FIRST(X) \cup FIRST^*(Y_i);$  
        $\displaystyle \ \ i++;$  
        $\displaystyle 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)$ :

    $\displaystyle i = 1;$  
    $\displaystyle FIRST(\alpha) = \emptyset;$  
    $\displaystyle hacer$  
    $\displaystyle \ \ FIRST(\alpha) = FIRST(\alpha) \cup FIRST^*(X_i);$  
    $\displaystyle \ \ i++;$  
    $\displaystyle 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$

    $\displaystyle 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$

    $\displaystyle FOLLOW(B) = FOLLOW(B) \cup FOLLOW(A)$

next up previous contents index PLPL moodlepserratamodulosperlmonksperldocapuntes LHPgoogleetsiiullpcgull
Sig: Ejercicio: Construir los Sup: Análisis Sintáctico Predictivo Recursivo Ant: Derivaciones a vacío Err: Si hallas una errata ...
Casiano Rodríguez León
2012-05-22