Conjunto FOLLOW (siguiente)

El conjunto FOLLOW (siguiente) de un no terminal X es el conjunto de símbolos terminales, que pueden aparecer inmediatamente después del símbolo no terminal X.

Por ejemplo, si se tiene la cadena αXtβ el terminal t habría que agregarlo a los seguidores de X, ya que está después del no terminal X.

Entrada: Conjunto de no terminales (V), donde S es el símbolo inicial de la gramática.

Salida: tabla con el FOLLOW

1: for all X V do

2: FOLLOW[X]:= {}

3: end for

4: FOLLOW[S]:= {$}

5: repeat

6: for cada producción do

7: for i:= 1 to k-1 do

8: if V then

9: FOLLOW []:= FOLLOW [] FOLLOW []

10: j:= i+2

11: while esAnulable () and j<=k do

12: FOLLOW []:= FOLLOW [] FIRST []

13: j := j+1

14: end while

15: if esAnulable () and j>k then

16: FOLLOW []:= FOLLOW [] FOLLOW[X]

17: end if

18: end if

19: end for

20: if V then

21: FOLLOW []:= FOLLOW [] FOLLOW[X]

22: end if

23: end for

24: until no hay más cambios

Algoritmo 3: Algoritmo de cálculo del conjunto FOLLOW

Por ejemplo en la siguiente gramática:

Z→d | XYZ

Y→c | ε

X→a | Y

Se obtendrían el siguiente FOLLOW:

X:{a, c, d}

Y:{a, c, d}

Z:{$}

Por defecto el símbolo inicial de la gramática tiene al símbolo final $ como primer follow. El símbolo Z ya no tiene más FOLLOW ya que aunque aparece en la producción Z→XYZ, aparece al final de la producción. Por lo tanto no hay que agregar ningún FOLLOW más. Los seguidores de X son los símbolos {a, c, d}, ya que el no terminal X aparece en la producción Z→XYZ. Estos seguidores se calculan con el FIRST del no terminal Y, y al ser Y anulable también se incluyen los de Z.