Compiladores · Análisis Sintáctico · Top-Down

FIRST · FOLLOW ·
PREDICT · Recognition Table

Guía visual y didáctica — con la gramática de ejemplo del curso

Paso 1
FIRST
¿Con qué tokens puede INICIAR?
→
Paso 2
FOLLOW
¿Qué tokens pueden venir DESPUÉS?
→
Paso 3
PREDICT
¿Qué tokens ACTIVAN cada producción?
→
Paso 4
Tabla
M[NT, token] = producción

📐 Gramática de trabajo — usada en todos los ejemplos

E ::= T E'
E' ::= + T E' | ε
T ::= F T'
T' ::= * F T' | ε
F ::= (E) | id
Paso 1 FIRST

¿Qué es FIRST?

FIRST(α) es el conjunto de terminales con los que pueden comenzar las cadenas derivadas de α. En otras palabras: ¿qué token puede aparecer primero?

FIRST(α) = { a ∈ VT | α →* aβ } ∪ { ε si α →* ε }
🚪
Terminal
FIRST(a) = {a}
Es su propio FIRST
🔍
No-Terminal
Mira qué puede producir y busca el primer terminal
👻
ε (epsilon)
Si puede desaparecer, ε entra en FIRST y se mira el siguiente símbolo
R1
El símbolo es un Terminal
Caso más simple
SI α es un terminal a
ENTONCES FIRST(a) = { a } — él mismo
R2
Producción con ε
El símbolo puede desaparecer
SI A ::= ε
ENTONCES FIRST(A) incluye ε
R3
Secuencia A ::= X₁ X₂ X₃...
La cadena de preguntas
SIEMPRE Agrega FIRST(X₁) sin ε a FIRST(A)
SI X₁ →* ε Agrega también FIRST(X₂) sin ε
SI X₂ →* ε Agrega también FIRST(X₃) sin ε ... y así sucesivamente
SI TODOS →* ε Agrega ε a FIRST(A)

Cálculo paso a paso con la gramática

NT Razonamiento FIRST resultado
F F ::= (E) → empieza con (
F ::= id → empieza con id
Ninguna alternativa tiene ε → no se agrega ε 		(id
T' T' ::= *FT' → empieza con *
T' ::= ε → agrega ε 		*ε
T T ::= FT'
Toma FIRST(F) = {(, id}
¿F puede ser ε? NO → nos detenemos aquí 		(id
E' E' ::= +TE' → empieza con +
E' ::= ε → agrega ε 		+ε
E E ::= TE'
Toma FIRST(T) = {(, id}
¿T puede ser ε? NO → nos detenemos aquí 		(id

🔑 Regla de oro para FIRST

Cuando tienes una secuencia A B C, avanza al siguiente símbolo SOLO cuando el anterior puede ser ε. En cuanto encuentres uno que no puede ser ε, para.

Paso 2 FOLLOW
👑
Regla 1 — Símbolo inicial
S es el símbolo inicial → $ siempre entra en FOLLOW(S)
👉
Regla 2 — Hay algo después
A ::= αBβ → FIRST(β) sin ε entra en FOLLOW(B)
🏁
Regla 3 — Al final o β→ε
A ::= αB o β puede ser ε → FOLLOW(A) entra en FOLLOW(B)

Cálculo paso a paso

FOLLOW(E) E es el símbolo inicial + aparece en F::=(E)
E es símbolo inicial → agrega $
F ::= (E) → E seguido de )
          FIRST()) = {)} → agrega )
FOLLOW(E) = { ) $ }
FOLLOW(E') Aparece al final en E::=TE' y en E'::=+TE'
E ::= TE' → E' al final → hereda FOLLOW(E) = {), $} → agrega )$
E' ::= +TE' → E' al final → hereda FOLLOW(E') = ya los tiene (no agrega nada nuevo)
FOLLOW(E') = { ) $ }
FOLLOW(T) Aparece en E::=TE' y E'::=+TE'
E ::= TE' → T seguido de E'
  FIRST(E') sin ε = {+} → agrega +
  ¿E' puede ser ε? SÍ → hereda FOLLOW(E) = {), $} → agrega )$

E' ::= +TE' → misma lógica → ya están todos
FOLLOW(T) = { + ) $ }
FOLLOW(T') Aparece al final en T::=FT' y T'::=*FT'
T ::= FT' → T' al final → hereda FOLLOW(T) = {+, ), $} → agrega +)$
T' ::= *FT' → T' al final → hereda FOLLOW(T') = ya los tiene
FOLLOW(T') = { + ) $ }
FOLLOW(F) Aparece en T::=FT' y T'::=*FT'
T ::= FT' → F seguido de T'
  FIRST(T') sin ε = {*} → agrega *
  ¿T' puede ser ε? SÍ → hereda FOLLOW(T) = {+, ), $} → agrega +)$

T' ::= *FT' → misma lógica → ya están todos
FOLLOW(F) = { * + ) $ }
E)$
E')$
T+)$
T'+)$
F*+)$

🔑 Pregunta clave para FOLLOW

Al analizar B en cualquier producción: (1) ¿Hay algo a la derecha? → agrega su FIRST sin ε. (2) ¿Ese algo puede ser ε o B está al final? → agrega FOLLOW del jefe (lado izquierdo del renglón).

Paso 3 PREDICT

¿Qué es PREDICT?

PREDICT de una producción A::=α es el conjunto de tokens que activan esa producción. Le dice al parser: "cuando veas este token, usa esta regla".

La fórmula

SIEMPRE Agrega FIRST(α) sin ε
SI ε ∈ FIRST(α) Agrega también FOLLOW(A)
❌
Sin ε en FIRST
PREDICT = FIRST(α)
Simple y directo
✅
Con ε en FIRST
PREDICT = FIRST(α) sin ε + FOLLOW(A)
Porque α puede desaparecer
# Producción FIRST(α) ¿ε? FOLLOW(A) PREDICT
1 E → TE' (id NO — (id
2 E' → +TE' + NO — +
3 E' → ε ε SÍ )$ )$
4 T → FT' (id NO — (id
5 T' → *FT' * NO — *
6 T' → ε ε SÍ +)$ +)$
7 F → (E) ( NO — (
8 F → id id NO — id

🔑 Regla de oro para PREDICT

Solo hay dos casos: (1) Si la producción NO tiene ε, PREDICT = FIRST. (2) Si la producción SÍ tiene ε, PREDICT = FIRST sin ε + FOLLOW del no-terminal izquierdo.

Paso 4 Recognition Table

¿Qué es la Recognition Table?

Es una tabla M[A, a] donde A es un No-Terminal (fila) y a es un terminal o $ (columna). La celda contiene el número de producción a aplicar. Las celdas vacías significan ERROR.

CÓMO LLENARLA Para cada producción, usa su PREDICT para saber en qué columnas va
Prod 1: PREDICT = {(, id} → M[E, (] = 1 y M[E, id] = 1
Prod 2: PREDICT = {+} → M[E', +] = 2
Prod 3: PREDICT = {), $} → M[E', )] = 3 y M[E', $] = 3
Prod 4: PREDICT = {(,id} → M[T, (] = 4 y M[T, id] = 4
Prod 5: PREDICT = {*} → M[T', *] = 5
Prod 6: PREDICT = {+,),$}→ M[T', +] = 6, M[T', )] = 6, M[T', $] = 6
Prod 7: PREDICT = {(} → M[F, (] = 7
Prod 8: PREDICT = {id} → M[F, id] = 8
NT id + * ( ) $
E 1 — — 1 — —
E' — 2 — — 3 3
T 4 — — 4 — —
T' — 6 5 — 6 6
F 8 — — 7 — —

Simulación de reconocimiento — cadena: id + id $

ALGORITMO Qué hacer en cada paso
x = tope del stack, a = token actual

SI x == a == $ → ✅ Cadena reconocida
SI x == a != $ → Consume: saca x del stack, avanza entrada
SI x es NT → Consulta M[x, a] → expande en el stack
SI celda vacía → ❌ ERROR de sintaxis
Paso Stack Input Acción
1 $E id+id$ M[E,id]=1 → E→TE'
2 $E'T id+id$ M[T,id]=4 → T→FT'
3 $E'T'F id+id$ M[F,id]=8 → F→id
4 $E'T'id id+id$ id==id → consume, avanza
5 $E'T' +id$ M[T',+]=6 → T'→ε (desaparece)
6 $E' +id$ M[E',+]=2 → E'→+TE'
7 $E'T+ +id$ +==+ → consume, avanza
8 $E'T id$ M[T,id]=4 → T→FT'
9 $E'T'F id$ M[F,id]=8 → F→id
10 $E'T'id id$ id==id → consume, avanza
11 $E'T' $ M[T',$]=6 → T'→ε (desaparece)
12 $E' $ M[E',$]=3 → E'→ε (desaparece)
13 $ $ ✅ $==$ → CADENA RECONOCIDA

🔑 Regla de oro para la tabla

Fila = No-Terminal que proceso ahora. Columna = Token que veo en la entrada. Celda = Qué producción aplico. Si la celda está vacía → ERROR. Si una celda tiene dos producciones → la gramática NO es LL(1).