Compiladores · Análisis Sintáctico

RDCP
Guía Visual

Recursive Descent by Code Parser — Las 7 reglas para traducir una gramática BNF a código

🍳 La analogía del Chef

El parser es un chef que sigue una receta (la gramática). Cada producción es una instrucción. El chef lee los ingredientes disponibles (tokens) y decide qué hacer.

🧂 Terminal Ingrediente concreto. Se consume directamente con Expect()
📋 No-Terminal Sub-receta. Se sigue llamando a otra función
❓ [ ] Opcional Solo agrega si lo tienes disponible → if
🔁 { } Repetición Sigue agregando mientras tengas → while
🍴 | Alternativas Elige una opción según lo que tengas enfrente → if-else
📝 Secuencia Primero esto, luego esto, luego esto → llamadas en orden

⚡ Referencia rápida — ¿Qué función usar?

T
Terminal
→ Expect(T)
NT
No-Terminal
→ NT()
[ T ]
Opcional terminal
→ if(CurrentToken)
[NT]
Opcional no-terminal
→ if(CurrentTokenInFirst)
{ T }
Repetición terminal
→ while(CurrentToken)
{NT}
Repetición no-terminal
→ while(CurrentTokenInFirst)
Las 7 Reglas
R1
No-Terminal produce No-Terminal
Simplemente delega a otra función
función()
📐 BNF
A ::= B
💻 Código
void A() {
  B();
}
Lógica: A no hace nada por sí sola, simplemente le dice a B que haga su trabajo.
R2
No-Terminal produce Terminal
Consume el token directamente
Expect()
📐 BNF
B ::= a
💻 Código
void B() {
  Expect(a);
}
Lógica: Expect() dice "exijo exactamente este token ahora". Si no está, es error de sintaxis.
R3
Secuencia de símbolos
Cada símbolo se procesa en orden
secuencial
📐 BNF
A ::= α₁ α₂ α₃
💻 Código
void A() {
  δ(α₁);
  δ(α₂);
  δ(α₃);
}

¿Qué es δ(αᵢ)?

αᵢ es Terminal → Expect(αᵢ)
αᵢ es No-Terminal → αᵢ()
Ejemplo Eiichi: InstrIfCrash ::= IF_CRASH Instruction

void InstrIfCrash() { Expect(IF_CRASH); Instruction(); }
R4
Opcional [ ]
Aparece 0 o 1 vez
if
📐 BNF — Terminal
B ::= [a]
💻 Código — Terminal
void B() {
  if(CurrentToken(a))
    Expect(a);
}
📐 BNF — No-Terminal
B ::= [A]
💻 Código — No-Terminal
void B() {
  if(CurrentTokenInFirst(A))
    A();
}
Lógica: Los corchetes [ ] dicen "puede estar o no". Si el token actual coincide, lo proceso; si no, simplemente lo ignoro y sigo.
R5
Repetición { }
Aparece 0 o más veces
while
📐 BNF — Terminal
B ::= {a}
💻 Código — Terminal
void B() {
  while(CurrentToken(a))
    Expect(a);
}
📐 BNF — No-Terminal
B ::= {A}
💻 Código — No-Terminal
void B() {
  while(CurrentTokenInFirst(A))
    A();
}
Ejemplo Eiichi: Program ::= Instruction; {Instruction;}

void Program() {
  Instruction(); Expect(SEMICOLON);
  while(CurrentTokenInFirst(Instruction)) {
    Instruction(); Expect(SEMICOLON);
  }
}
R6
Alternativas |
Elige una opción según el token actual
if-else if
📐 BNF — Terminales
A ::= a | b | c
💻 Código — Terminales
void A() {
  if(CurrentToken(a))
    Expect(a);
  else if(CurrentToken(b))
    Expect(b);
  else if(CurrentToken(c))
    Expect(c);
}
📐 BNF — No-Terminales
A ::= B | C | D
💻 Código — No-Terminales
void A() {
  if(CurrentTokenInFirst(B))
    B();
  else if(CurrentTokenInFirst(C))
    C();
  else if(CurrentTokenInFirst(D))
    D();
}
Ejemplo Eiichi:

Instruction ::= InstrTurn | InstrAdvance | InstrIfCrash | InstrObject

El parser mira el token actual y elige la alternativa cuyo FIRST lo contiene.
R7
Mezcla de reglas
Combinación de R1–R6 en una sola producción
combinación
📐 BNF — Eiichi
InstrAdvance ::=
  ADVANCE Num
  | GOBACK
💻 Código
void InstrAdvance() {
  if(CurrentToken(ADVANCE)) {
    Expect(ADVANCE); // R2
    Expect(NUM);     // R2
  }
  else if(CurrentToken(GOBACK))
    Expect(GOBACK); // R2
}
Lógica: Primero tienes alternativas (R6), y dentro de cada alternativa hay una secuencia (R3). Simplemente combinas las reglas que necesites.

🌳 Árbol de decisión — ¿Qué regla aplicar?

¿Qué forma tiene mi producción?
│
├─ A ::= B (solo un NT) ────────────────→ Regla 1: B()
│
├─ B ::= a (solo un T) ────────────────→ Regla 2: Expect(a)
│
├─ A ::= α₁ α₂ α₃ (secuencia) ──────→ Regla 3: δ(α₁); δ(α₂); δ(α₃)
│
├─ B ::= [α] (opcional) ───────────────→ Regla 4: if(Current...) ...
│
├─ B ::= {α} (repetición) ──────────→ Regla 5: while(Current...) ...
│
├─ A ::= α₁ | α₂ | α₃ (alternativas) → Regla 6: if-else if-else if
│
└─ Combinación de las anteriores ──→ Regla 7: mezcla

📊 Tabla resumen completa

Regla BNF Estructura Keyword clave
R1 A ::= B B() llamada
R2 B ::= a Expect(a) Expect
R3 A ::= α₁ α₂ δ(α₁); δ(α₂) secuencia
R4 B ::= [a] if(CurrentToken(a)) if
R5 B ::= {a} while(CurrentToken(a)) while
R6 A ::= a | b if...else if... if-else if
R7 combinación mezcla de R1–R6 combinar