Primerosiguiente

Cálculo de PRIMERO
El conjunto PRIMERO(α), siendo α una forma sentecial, es el conjunto de
Terminales que pueden aparecer los primeros en cadenas derivadas de α.
El conjunto PRIMERO puede referirse a una forma sentencial (PRIMERO(α),
siendo α por ejemplo aBD ), pero también a un símbolo No Terminal de la
gramática considerada (PRIMERO(A)). Si la gramática está formada por reglas
Aàαi el conjuntoPRIMERO(A) será la unión de todos los PRIMERO(αi), que
deben ser calculados por separado.
Para calcular PRIMERO(α) basta con seguir las siguientes reglas para cada regla de
producción de la gramática:
1. Si α ≡ ∈, donde ∈ es la cadena vacía :
Añadir { ∈ } a PRIMERO(α)
2. Si α ≡ a, donde a es un Terminal:
Añadir { a } a PRIMERO(α)
3. Si α ≡ A, donde A es un No Terminal:
Añadir PRIMERO(A) aPRIMERO(α).
4. Si α ≡ AB, donde A y B son No Terminales y PRIMERO(A) incluye { ∈ }:
Añadir PRIMERO(A) a PRIMERO(α), pero sin incluir de momento { ∈ }.
Además, y puesto que A puede ser vacío, añadir PRIMERO(B) a PRIMERO(α).
Esta regla puede extenderse a todos los No Terminales que aparezcan detrás de
A. Por ejemplo, si α ≡ ABCD y PRIMERO (A), PRIMERO(B) y PRIMERO(C)
incluyen { ∈ }, entonces habrá que añadira PRIMERO(α) la unión de
PRIMERO(A), PRIMERO(B), PRIMERO(C) y PRIMERO(D), sin incluir { ∈ }.
Por último se decide si incluir { ∈ } en PRIMERO(α): sólo debe incluirse si
aparece en los conjuntos PRIMERO de todos los No Terminales. Por ejemplo en
el caso anterior, si PRIMERO(D) también incluyese { ∈ }, entonces
PRIMERO(α) incluiría { ∈ }.

Primer ejemplo detallado de cálculo de PRIMERO
Veamos unejemplo de cálculo detallado de PRIMERO para la siguiente gramática, que
describe expresiones aritméticas con sumas y multiplicaciones:
E à T E’
E’ à + T E’ | ∈
T à F T’
T’ à * F T’ | ∈
F à ( E ) | ident
•

PRIMERO(E) = PRIMERO(TE’) (en adelante escribiremos simplemente
PRIMERO(E) ).
PRIMERO(E) = PRIMERO(T) por la Regla 3, así que pasamos a calcular
PRIMERO(T).

•

PRIMERO(T) = PRIMERO(F) por laRegla 3, así que pasamos a calcular
PRIMERO(F).

•

PRIMERO(F) = { ( , ident } por la Regla 2.

•

En este punto ya sabemos que PRIMERO(E) = PRIMERO(T) = PRIMERO(F)=
{ ( , ident }

•

PRIMERO(E’) = { + , ∈ } por las Reglas 2 y 1.

•

PRIMERO(T’) = { * , ∈ } por las Reglas 2 y 1.

Resultado:
PRIMERO(E) = { ( , ident }
PRIMERO(E’) = { + , ∈ }
PRIMERO(T) = { ( , ident }
PRIMERO(T’) = { * , ∈ }PRIMERO(F) = { ( , ident }

Segundo ejemplo detallado de cálculo de PRIMERO
Veamos otro ejemplo de cálculo detallado de PRIMERO para la siguiente gramática,
con el objetivo de aclarar el uso de la Regla 4:
A à Aa | BCD
Bàb|∈
Càc|∈
D à d | Ce
•

PRIMERO(A) = PRIMERO(Aa) ∪ PRIMERO(BCD) = PRIMERO(BCD)

•

Calculamos el resto de los conjuntos PRIMERO, ya que vamos a necesitarlos

•

PRIMERO(B) = { b , ∈ }por las Reglas 2 y 1.

•

PRIMERO(C) = { c , ∈ } por las Reglas 2 y 1.

•

PRIMERO(D) = { d } ∪ PRIMERO(Ce).
Como PRIMERO(Ce) incluye el elemento vacío, aplicamos la Regla 4 y
calculamos PRIMERO(e) = { e }, quedando PRIMERO(D) = { d, c, e }.
Obsérvese que por la Regla 4, { ∈ } no se incluye: intuitivamente se comprueba
que D no puede derivar la cadena vacía.

•

PRIMERO(A) = PRIMERO(Aa) ∪PRIMERO(BCD)
PRIMERO(BCD) = PRIMERO(B) ∪ PRIMERO(C) ∪ PRIMERO(D) = { b , c ,
d , e }. Por la Regla 4 sabemos que { ∈ } no debe incluirse: no está incluida en
PRIMERO(D), y por tanto resulta imposible deducir la cadena vacía a partir de
A.
PRIMERO(Aa) es un caso al que conviene prestar atención, aunque no deja de
ser un caso más de aplicación de la Regla 4: si PRIMERO(BCD) incluyese {∈},
habría que incluir{a} en PRIMERO(A). Como no es así, no lo incluimos,
quedando:
PRIMERO(A) = PRIMERO(BCD) = { b , c , d , e }

Resultado:
PRIMERO(A) = { b , c , d , e }
PRIMERO(B) = { b , ∈ }
PRIMERO(C) = { c , ∈ }
PRIMERO(D) = { d , c , e }

Cálculo de SIGUIENTE
Si A es un símbolo No Terminal de una gramática, SIGUIENTE(A) es el conjunto
de Terminales (incluyendo el símbolo de fin de cadena, $) que pueden...