Clase 6 — Análisis Sintáctico Descendente Predictivo LL(1)

Resumen Ejecutivo

Esta sesión se centra en el análisis sintáctico descendente, continuando el tema 5 introducido en la clase anterior. Se descartan los analizadores recursivos con retroceso por ineficiencia y se presenta el analizador predictivo LL(1) como la alternativa correcta. Se estudian los conjuntos primero, siguiente y de predicción, la construcción de la tabla de análisis predictivo y el algoritmo con pila que simula el autómata con pila. Se cierra con un ejemplo sobre la gramática clásica de expresiones aritméticas (Aho, Ullman & Sethi). ⚠️ EXAMEN: la clase siguiente aborda análisis ascendente (LR), que es el que genera CUP en la actividad práctica.

Conceptos Clave

Análisis descendente (top-down): Construye el árbol desde la raíz (axioma) hasta las hojas (terminales de la cadena). Es el más intuitivo pero menos potente que el ascendente.
Analizador recursivo con retroceso: Elige siempre la primera producción; si falla, retrocede y prueba la siguiente. Se descarta por ineficiencia y porque con gramáticas recursivas por la izquierda entra en bucle infinito. ⚠️ EXAMEN: recordar que no es predictivo y que puede no terminar.
Analizador predictivo LL(1): Decide qué regla aplicar sin retroceso, consultando un único token de lookahead. La nomenclatura LL(k): primera L = lectura de izquierda a derecha, segunda L = derivación por la izquierda, k = número de tokens de anticipación. ⚠️ EXAMEN
Conjunto primero (PRIMERO(α)): Terminales con los que pueden empezar las cadenas derivables desde α. Incluye λ (palabra vacía) si α puede derivar en nada.
Conjunto siguiente (SIGUIENTE(A)): Terminales que pueden aparecer inmediatamente detrás del no terminal A en alguna forma sentencial. Solo se calcula para no terminales que derivan λ.
Conjunto de predicción (PRED(A → α)): Conjunto que dicta cuándo aplicar la producción. Se construye a partir de PRIMERO(α) y, si α deriva λ, se añade SIGUIENTE(A). ⚠️ EXAMEN
Gramática LL(1): Aquella en la que, para cada no terminal, los conjuntos de predicción de sus producciones son disjuntos. Si no lo son, o la gramática tiene recursividad por la izquierda, no es LL(1). ⚠️ EXAMEN
Tabla de análisis predictivo: Matriz [no terminal × terminal]. Cada celda contiene como mucho una producción a aplicar. Celda vacía = error sintáctico.
Algoritmo con pila: Simula el autómata con pila. Pila inicializada con $ y el axioma. Se compara la cima con el token actual; si coincide, se desapila y se avanza; si la cima es no terminal, se consulta la tabla y se sustituye por la parte derecha en orden (el primer símbolo queda en la cima).

Desarrollo del Temario

1. Contexto dentro de la asignatura

El tema 5 (clase anterior) introdujo el análisis sintáctico. Este tema 6 cubre el análisis descendente; la clase siguiente cubrirá el ascendente, que es el verdaderamente utilizado en compiladores modernos (CUP/YACC/Bison generan analizadores ascendentes). ⚠️ EXAMEN: el descendente se imparte de forma semi teórica, el ascendente se trabaja en profundidad porque sustenta la actividad práctica con CUP.

Los analizadores descendentes tienen menor potencia que los ascendentes: solo algunos lenguajes sencillos y antiguos pueden soportarse íntegramente con LL(1).

2. Analizador recursivo con retroceso (por qué se descarta)

Funciona así: al expandir un no terminal, intenta siempre la primera producción disponible. Si el análisis no progresa, retrocede y prueba la siguiente. Repite hasta reconocer o agotar todas las opciones.

Problemas críticos: - Ineficiencia: Para una cadena larga, un error en la quinta posición puede obligar a deshacer múltiples niveles del árbol y rehacerlos muchas veces. - Bucle infinito con recursividad por la izquierda: Si existe una producción $A \rightarrow A\alpha$, el analizador expande A aplicando siempre su primera regla, metiendo otra A en la cima, y así indefinidamente. Nunca llega a probar la segunda producción.

Matización importante: El retroceso no recorre un árbol ya construido; destruye el subárbol en conflicto y lo reconstruye con otra producción. No es búsqueda en anchura ni en profundidad del árbol completo; es construcción del árbol de derivación mediante ensayo y error.

3. Analizador predictivo LL(1)

Exige que la elección de producción se haga sin retroceso, consultando solo un token por adelantado. Para lograrlo, se precomputa información sobre la gramática: los conjuntos de predicción.

Requisitos de una gramática LL(1): ⚠️ EXAMEN 1. Sin recursividad por la izquierda. Se elimina convirtiéndola en recursividad por la derecha (tema de la asignatura previa, no se pide transformar en el examen, pero sí diagnosticar). 2. Conjuntos de predicción disjuntos para todas las producciones del mismo no terminal. Si dos reglas de A comparten un terminal en su PRED, no es LL(1).

Diagnóstico de examen: dada una gramática, sin construir la tabla ni el autómata, basta con comprobar estos dos criterios para decir si es LL(1).

4. Conjuntos primero, siguiente y de predicción

4.1. Conjunto PRIMERO

Para una forma sentencial $\alpha$, PRIMERO(α) contiene los terminales que pueden aparecer al principio de alguna cadena derivable desde α.

Casos: - Si $\alpha$ empieza por un terminal $a$: PRIMERO(α) = {a}. - Si $\alpha$ empieza por un no terminal $B$: se calcula PRIMERO(B) recursivamente (unión de los primeros de las partes derechas de todas las producciones de B). - Si $\alpha \Rightarrow^* \lambda$: se añade $\lambda$ a PRIMERO(α).

4.2. Conjunto SIGUIENTE

Solo se calcula para no terminales cuyas producciones pueden derivar λ.

SIGUIENTE(A) contiene los terminales que pueden aparecer inmediatamente después de A en alguna forma sentencial derivable desde el axioma.

Regla clave: si A aparece al final de la parte derecha de una producción de otro no terminal B, entonces SIGUIENTE(B) ⊆ SIGUIENTE(A). Para el axioma, SIGUIENTE contiene siempre $ (final de cadena). ⚠️ EXAMEN

4.3. Conjunto de PREDICCIÓN

Para una producción $A \rightarrow \alpha$:

\[\text{PRED}(A \rightarrow \alpha) = \begin{cases} \text{PRIMERO}(\alpha) & \text{si } \lambda \notin \text{PRIMERO}(\alpha) \\ (\text{PRIMERO}(\alpha) \setminus \{\lambda\}) \cup \text{SIGUIENTE}(A) & \text{si } \lambda \in \text{PRIMERO}(\alpha) \end{cases}\]

Este conjunto indica los terminales de entrada para los que tiene sentido aplicar esa producción.

5. Tabla de análisis predictivo

Matriz bidimensional [no terminal × terminal]. Para cada producción $A \rightarrow \alpha$ y cada terminal $a \in \text{PRED}(A \rightarrow \alpha)$, se coloca la producción en la celda [A, a].

Propiedad clave de las gramáticas LL(1): ⚠️ EXAMEN - Cada celda contiene a lo sumo una producción. Si alguna celda tiene más de una, la gramática no es LL(1). - Celda vacía = error sintáctico detectado en ese punto exacto de la cadena.

Esta característica — errores detectados en su posición real — es una de las grandes ventajas de los predictivos frente a los recursivos con retroceso.

6. Algoritmo de análisis LL(1) con pila

Estructuras: - Buffer de entrada terminado en $. - Pila inicializada con $ (fondo) y el axioma (cima). - Tabla de análisis predictivo precomputada. - Salida: lista de producciones aplicadas (representación implícita del árbol).

Iteración: se consulta la cima de la pila X y el token actual a de la entrada.

flowchart TD
    Start([X = cima, a = token actual]) --> Check{X == $?}
    Check -->|sí y a == $| Accept([ACEPTAR])
    Check -->|no| Term{X es terminal?}
    Term -->|sí, X == a| Pop[desapila X, avanza entrada]
    Term -->|sí, X != a| Err1([ERROR])
    Term -->|no, X es no terminal| Tab{tabla[X, a]?}
    Tab -->|hay producción X→Y1...Yn| Apply[desapila X, apila Yn...Y1]
    Tab -->|celda vacía| Err2([ERROR])
    Pop --> Start
    Apply --> Start

Detalles de la sustitución: al aplicar $X \rightarrow Y_1 Y_2 \dots Y_n$, se apila $Y_n, Y_{n-1}, \dots, Y_1$ de forma que $Y_1$ quede en la cima (el símbolo más a la izquierda de la parte derecha). Si la parte derecha es λ, se desapila X sin apilar nada.

7. Ejemplo: gramática de expresiones aritméticas (Aho)

Gramática clásica ya sin recursividad por la izquierda:

\[ \begin{aligned} E &\rightarrow T\,E' \\ E' &\rightarrow +\,T\,E' \mid \lambda \\ T &\rightarrow F\,T' \\ T' &\rightarrow *\,F\,T' \mid \lambda \\ F &\rightarrow (\,E\,) \mid \text{id} \end{aligned} \]

Tabla de análisis predictivo (resumen):

	`id`	`+`	`*`	`(`	`)`	`$`
$E$	$E \rightarrow T E'$			$E \rightarrow T E'$
$E'$		$E' \rightarrow +T E'$			$E' \rightarrow \lambda$	$E' \rightarrow \lambda$
$T$	$T \rightarrow F T'$			$T \rightarrow F T'$
$T'$		$T' \rightarrow \lambda$	$T' \rightarrow *F T'$		$T' \rightarrow \lambda$	$T' \rightarrow \lambda$
$F$	$F \rightarrow \text{id}$			$F \rightarrow (E)$

Traza sobre la cadena id + id:

Pila (cima a la izquierda)	Entrada	Acción
`E $`	`id + id $`	aplicar $E \rightarrow T E'$
`T E' $`	`id + id $`	aplicar $T \rightarrow F T'$
`F T' E' $`	`id + id $`	aplicar $F \rightarrow \text{id}$
`id T' E' $`	`id + id $`	emparejar `id`, avanzar
`T' E' $`	`+ id $`	aplicar $T' \rightarrow \lambda$
`E' $`	`+ id $`	aplicar $E' \rightarrow + T E'$
`+ T E' $`	`+ id $`	emparejar `+`, avanzar
`T E' $`	`id $`	aplicar $T \rightarrow F T'$, $F \rightarrow \text{id}$, avanzar, $T' \rightarrow \lambda$, $E' \rightarrow \lambda$
`$`	`$`	ACEPTAR

Preguntas de Autoevaluación

¿Por qué se descarta el analizador recursivo con retroceso? Por ineficiencia (recomputación del árbol ante cada fallo) y porque con recursividad por la izquierda entra en bucle infinito.
¿Qué significa LL(1)? Left-to-right scan, Leftmost derivation, 1 token de lookahead.
¿Cuándo una gramática es LL(1)? Cuando no tiene recursividad por la izquierda y los conjuntos de predicción de las producciones de cada no terminal son disjuntos.
¿Cuándo se usa SIGUIENTE en el cálculo de predicción? Solo cuando la parte derecha de la producción puede derivar λ.
¿Qué representa una celda vacía en la tabla de análisis predictivo? Un error sintáctico en esa posición exacta.
Dado $A \rightarrow \alpha$, ¿cómo se construye PRED? PRIMERO(α) si α no deriva λ; en otro caso, (PRIMERO(α) \ {λ}) ∪ SIGUIENTE(A).
Si al sustituir $X \rightarrow Y_1 Y_2 Y_3$, ¿cómo queda la pila? Se apila $Y_3, Y_2, Y_1$, quedando $Y_1$ en la cima.
¿Qué se hace si la parte derecha es λ? Se desapila X sin apilar nada.
¿Cómo se elimina la recursividad por la izquierda? Se transforma en recursividad por la derecha (no se pide aplicar en el examen, solo diagnosticar que la gramática no es LL(1) si existe).
¿Por qué el descendente es menos potente que el ascendente? Porque requiere disjunción estricta de los conjuntos de predicción; muchas gramáticas útiles no cumplen ese requisito pero sí las condiciones de LR.

Referencias

Aho, Ullman & Sethi — Compiladores: Principios, Técnicas y Herramientas (el "libro del dragón"). Ejercicio base de esta gramática desarrollado allí.
Próxima clase: análisis ascendente (LR), base de CUP y de la actividad práctica.

	`id`	`+`	`*`	`(`	`)`	`$`
\(E\)	\(E \rightarrow T E'\)			\(E \rightarrow T E'\)
\(E'\)		\(E' \rightarrow +T E'\)			\(E' \rightarrow \lambda\)	\(E' \rightarrow \lambda\)
\(T\)	\(T \rightarrow F T'\)			\(T \rightarrow F T'\)
\(T'\)		\(T' \rightarrow \lambda\)	\(T' \rightarrow *F T'\)		\(T' \rightarrow \lambda\)	\(T' \rightarrow \lambda\)
\(F\)	\(F \rightarrow \text{id}\)			\(F \rightarrow (E)\)

Pila (cima a la izquierda)	Entrada	Acción
`E $`	`id + id $`	aplicar \(E \rightarrow T E'\)
`T E' $`	`id + id $`	aplicar \(T \rightarrow F T'\)
`F T' E' $`	`id + id $`	aplicar \(F \rightarrow \text{id}\)
`id T' E' $`	`id + id $`	emparejar `id`, avanzar
`T' E' $`	`+ id $`	aplicar \(T' \rightarrow \lambda\)
`E' $`	`+ id $`	aplicar \(E' \rightarrow + T E'\)
`+ T E' $`	`+ id $`	emparejar `+`, avanzar
`T E' $`	`id $`	aplicar \(T \rightarrow F T'\), \(F \rightarrow \text{id}\), avanzar, \(T' \rightarrow \lambda\), \(E' \rightarrow \lambda\)
`$`	`$`	ACEPTAR