Analisis Sintactico 6.6

Generacion de matriz predictiva ( calculo first y follow )

FIRST
Se define el conjunto FIRST de un símbolo, FIRST (X) (X ∈ {T ∪ N}), como el conjunto de los símbolos
terminales que pueden aparecer como primer símbolo terminal en las cadenas derivadas a partir de X.
 Si X es un terminal (X = t, con t ∈ T) entonces FIRST (X):= {t}.
 Si X es un no terminal (X ∈ N), para calcular FIRST (X) hay que estudiar cada una de las reglas de X. Se
ejecutarán los siguientes pasos hasta que no se puedan añadir más elementos al conjunto FIRST:
1. Si existe la regla X → λ, entonces añadir λ a FIRST (X) (λ es la cadena vacía o elemento nulo)
2. Para cada una de las restantes reglas gramaticales de X, X→ Y1 Y2... Yk , (donde Yi ∈ {T ∪ N}), se aplica
el siguiente algoritmo hasta que no se pueda añadir nada nuevo al conjunto FIRST (X):
Todos los elementos no nulos de FIRST(Y1) se añaden a FIRST(X)
if λ ϵ FIRST(Y1)
then Todos los elementos no nulos de FIRST(Y2) se añaden a FIRST(X)
if λ ϵ FIRST(Y2)
then Todos los elementos no nulos de FIRST(Y3) se añaden a FIRST(X)
…y así sucesivamente…
if λ ϵ FIRST(Yk-1)
then Todos los elementos no nulos de FIRST(Yk) se añaden a FIRST(X)
if λ ϵ FIRST(Yk)
then Añadir λ a FIRST(X)
También se puede calcular el conjunto FIRST de una cadena α de símbolos (según lo indicado en el paso 2):
Si α es cualquier cadena de símbolos gramaticales (α ∈ {T ∪ N}*
), se define FIRST (α) como el conjunto
formado por los símbolos terminales que encabezan las cadenas derivadas de α. Si α ⇒* λ, entonces λ (la
cadena vacía) también está en FIRST (α).
Sea α= Y1 Y2... Yk, donde Yi ∈ {T ∪ N}. Para calcular FIRST (α):
Todos los elementos no nulos de FIRST(Y1) se añaden a FIRST(α)
if λ ϵ FIRST(Y1)
then Todos los elementos no nulos de FIRST(Y2) se añaden a FIRST(α)
if λ ϵ FIRST(Y2)
then Todos los elementos no nulos de FIRST(Y3) se añaden a FIRST(α)
…y así sucesivamente…
if λ ϵ FIRST(Yk-1)
then Todos los elementos no nulos de FIRST(Yk) se añaden a FIRST(α)
if λ ϵ FIRST(Yk)
then Añadir λ a FIRST(α)
FOLLOW
Se define FOLLOW (A), para el no terminal A (A ∈ N), como el conjunto de terminales t (t ∈ T) que pueden
aparecer inmediatamente a la derecha de A en alguna forma sentencial, es decir, el conjunto de terminales
t tales que haya una derivación de la forma S ⇒* α A t β (siendo α, β ∈ (N ∪ T)*). Si A puede ser el símbolo de
más a la derecha en alguna forma sentencial, entonces λ está en FOLLOW (A).
Para calcular FOLLOW (A) se aplican las siguientes reglas hasta que no se pueda añadir nada más al conjunto
FOLLOW (A):
1. Si A es el axioma de la gramática, añadir $ a FOLLOW (A).
2. Si existe una regla B→ α A β, entonces todos los elementos no nulos de FIRST (β) se añaden a FOLLOW (A).
3. Si existe una regla B→ α A β y λ ∈ FIRST (β) (es decir, β ⇒* λ), o bien si existe una regla B→ α A, entonces
todo lo que esté en FOLLOW (B) se añade a FOLLOW (A).