GUÍA 11-11-26 Teoría de la Computación

NE111 · miércoles 11/11/2026 · 16:00-17:15 · Sesión 27

Parsers: análisis sintáctico descendente

LA SEGUNDA FASE DEL COMPILADOR

El analizador sintáctico recibe los tokens del analizador léxico y construye el árbol de derivación según la gramática del lenguaje. Es la aplicación directa del bloque de gramáticas.

DOS FAMILIAS

• Descendente — se parte de S y se intenta llegar a la cadena. Construye el árbol de la raíz a las hojas.
• Ascendente — se parte de la cadena y se reduce hacia S. Construye el árbol de las hojas a la raíz.

DESCENSO RECURSIVO

Se escribe una función por cada no terminal, y el cuerpo de la función sigue la producción. Es el parser más fácil de escribir a mano y el más fácil de depurar, porque la pila de llamadas refleja el árbol.

Es también la aplicación más directa de la recursión de la sesión 8: la gramática es recursiva y el parser también.

LL(1)

Lee de izquierda a derecha, produce derivación por la izquierda y decide con un solo símbolo de anticipación. Se construye una tabla a partir de los conjuntos PRIMERO y SIGUIENTE.

• PRIMERO(α) — los terminales con que puede empezar una cadena derivada de α.
• SIGUIENTE(A) — los terminales que pueden aparecer inmediatamente después de A.

DOS OBSTÁCULOS Y SUS ARREGLOS

• Recursión por la izquierda — A → Aα causa recursión infinita. Se elimina reescribiendo con A → βA' y A' → αA' | ε.
• Prefijos comunes — A → αβ | αγ impide decidir con un símbolo. Se factoriza por la izquierda: A → αA' con A' → β | γ.

LA TENSIÓN CON LA SESIÓN 24

Ahí eliminamos la ambigüedad usando recursión por la izquierda para imponer asociatividad. Aquí hay que quitar esa misma recursión para poder usar LL(1). Las dos transformaciones tiran en direcciones opuestas, y esa tensión es exactamente lo que motiva los parsers ascendentes.

EJERCICIO

Eliminar la recursión izquierda de la gramática de expresiones, calcular PRIMERO y SIGUIENTE, y construir la tabla LL(1).