5.8 - Generación de matriz predictiva (cálculo first y follow)

FIRST: Si α es cualquier cadena de símbolos gramaticales, se considera FIRST (α) como el conjunto de terminales que encabezan las cadenas derivadas de α. Si α = * => λ, entonces λ también está en FIRST (α). Para calcular FIRST(X) para algún símbolo X de la gramática, se aplican las siguientes reglas hasta que no se pueda añadir nada nuevo al conjunto

FIRST: Sea G:= (V; ∑; Q0; P) una gramática libre de contexto. Para cada forma sentencial α Є (V U ∑)* y para cada k Є N definiremos la función.

FOLLOW: Se define FOLLOW(A), para él no terminal A, como el conjunto de terminales a que pueden aparecer inmediatamente a la derecha de A en alguna forma sentencia, es decir, el conjunto de terminales a tal que haya una derivación de la forma S= * =>αAaβ para algún α y β. Si A puede ser el símbolo de más a la derecha en alguna forma sentencia, entonces $ está en FOLLOW(A).

Para calcular FOLLOW(A) para un símbolo no terminal A, se aplican las siguientes reglas hasta que no se pueda añadir nada más al conjunto FOLLOW.

1. $ está en FOLLOW(S), siendo S el axioma de G.

2. Si existe una producción A → αBβ, entonces todo lo que esté en FIRST (β), excepto λ, está en FOLLOW (B).

3. Si existe la producción A → αBβ y FIRST (β) contiene λ (es decir, β= * =>λ), o bien si existe una producción A → αB, entonces todo lo que esté en FOLLOW(A) está en FOLLOW (B).