Clase 7 — Análisis Sintáctico Ascendente (Shift-Reduce, LR)

Resumen Ejecutivo

Esta clase arranca el tema 6: análisis sintáctico ascendente, el paradigma que usan los compiladores reales y el que genera CUP en la actividad práctica. A diferencia del descendente, el ascendente parte de las hojas (tokens de entrada) y construye el árbol reduciendo subcadenas a no terminales hasta llegar al axioma. Se introducen los conceptos de mango, reducción, elemento LR(0) con punto marcador, la equivalencia con derivaciones por la derecha invertidas, la familia de analizadores LR(k) y la arquitectura shift-reduce con dos pilas y tabla de acciones + IR-A. ⚠️ EXAMEN: el algoritmo completo de análisis, la interpretación de la tabla (sX, rX, acc, vacía = error) y los conflictos shift-reduce / reduce-reduce.

Conceptos Clave

Análisis ascendente (bottom-up): Construye el árbol desde las hojas (tokens) hacia el axioma aplicando reducciones (parte derecha → parte izquierda). Inverso del descendente. ⚠️ EXAMEN
Reducción: Sustituir una subcadena que coincide con la parte derecha de una producción por su parte izquierda. Es el proceso inverso a la derivación.
Mango (handle): Subcadena en el buffer/pila que coincide con la parte derecha de una producción y cuya reducción es un paso correcto en alguna derivación por la derecha invertida. Identificar el mango correcto es el problema central del parser ascendente.
Derivación por la derecha: En cada paso de derivación se expande el no terminal más a la derecha de la forma sentencial. Construir un árbol ascendente equivale a realizar una derivación por la derecha en orden inverso. ⚠️ EXAMEN
Analizador LR(k): Left-to-right scan, Rightmost derivation (en orden inverso), k tokens de lookahead. En la práctica k = 0 o 1 bastan. Tienen mayor potencia que los LL(k).
Gramática LR: Gramática independiente del contexto para la que puede construirse un analizador LR. No toda gramática es LR: pueden aparecer conflictos.
Analizador shift-reduce (desplazamiento-reducción): Otro nombre para los LR. En cada paso decide entre desplazar (shift: leer el siguiente token y apilarlo) o reducir (reduce: aplicar una producción sobre la cima de la pila).
Elemento LR(0): Producción con un punto marcador en algún lugar de su parte derecha, por ejemplo E → E + · T. Representa que ya se ha leído lo que está a la izquierda del punto y queda por leer lo que está a la derecha. ⚠️ EXAMEN
Conflicto shift-reduce: En un estado, el analizador no sabe si desplazar o reducir.
Conflicto reduce-reduce: En un estado, el analizador no sabe por cuál de dos producciones reducir.

Desarrollo del Temario

1. Repaso: cómo un compilador "entiende" una expresión

Ante una cadena como id + id * id, el compilador:

Léxico: transforma el texto en una secuencia de tokens (ya resuelto).
Sintáctico: comprueba que la secuencia está bien estructurada según la gramática, construyendo un árbol de análisis.
Semántico: analiza significado (fuera del alcance sintáctico; se estudia más adelante).

Esta clase se centra en el punto 2 con un enfoque ascendente.

2. Diferencia con el descendente: construcción vs descomposición

	Descendente (LL)	Ascendente (LR)
Dirección	Raíz → hojas	Hojas → raíz
Operación base	Derivación (expandir no terminal)	Reducción (colapsar cadena en no terminal)
Derivación equivalente	Por la izquierda	Por la derecha, invertida
Símbolo sobre el que opera	El más a la izquierda	El más a la derecha
Potencia	Menor	Mayor

El ascendente es más potente porque acumula contexto antes de decidir, en lugar de comprometerse con una producción desde el primer token.

3. Ejemplo conceptual: reconocer `id + id * (id − id)`

Sobre la gramática:

\[ \begin{aligned} (1)\ E &\rightarrow E + T \\ (2)\ E &\rightarrow E - T \\ (3)\ E &\rightarrow T \\ (4)\ T &\rightarrow T * F \\ (5)\ T &\rightarrow T / F \\ (6)\ T &\rightarrow F \\ (7)\ F &\rightarrow (E) \\ (8)\ F &\rightarrow \text{id} \end{aligned} \]

El analizador va leyendo tokens de izquierda a derecha y, cuando reconoce en la pila un mango que coincide con la parte derecha de alguna producción, lo reduce:

Lee id → reduce $F \rightarrow \text{id}$ (producción 8), luego $T \rightarrow F$ (6), luego $E \rightarrow T$ (3).
Lee +, lee id → reduce a F, luego a T.
Lee *, lee (, reconoce el bloque interior id − id reduciéndolo a E.
Lee ) → reduce $F \rightarrow (E)$ (producción 7).
Ahora la pila contiene T * F → reduce $T \rightarrow T * F$ (4).
Pila: E + T → reduce $E \rightarrow E + T$ (1). Axioma alcanzado + entrada consumida = cadena aceptada. ⚠️ EXAMEN: solo se acepta cuando se alcanza el axioma y se ha leído toda la entrada (incluido $).

La lista de producciones aplicadas es una representación implícita del árbol: basta con esa secuencia y la cadena de entrada para reconstruirlo cuantas veces se quiera.

4. Equivalencia con derivación por la derecha invertida

Una derivación por la derecha de la cadena anterior tiene el orden inverso de las reducciones del ascendente. Si el árbol se reconstruye con la secuencia 7 4 1 ..., la derivación por la derecha aplicaría ... 1 4 7 en orden contrario.

Consecuencia formal: construir un árbol ascendente $\equiv$ derivación por la derecha leída al revés. De ahí la R de LR(k).

5. Familia LR(k)

L: lectura de izquierda a derecha de la entrada.
R: equivalencia con derivación por la derecha (invertida).
k: tokens de lookahead para decidir la acción. Normalmente 0 o 1.

Las gramáticas reconocibles por un analizador LR(k) se llaman gramáticas LR(k). Hay gramáticas independientes del contexto que no son LR porque generan conflictos irresolubles.

6. Analizadores shift-reduce: arquitectura

flowchart LR
    Input[Buffer de entrada: tokens + $] --> Parser
    Parser[Algoritmo de análisis] --> Stack[Pila: símbolos + estados]
    Parser --> Table[Tabla de análisis]
    Table --> Action[ACCIÓN: terminales]
    Table --> Goto[IR-A: no terminales]
    Parser --> Output[Salida: lista de producciones]

Estructuras: - Buffer de entrada terminado en $. - Pila que almacena símbolos y estados intercalados (símbolo, estado, símbolo, estado…). El estado siempre queda en la cima. - Tabla de análisis con dos partes: - ACCIÓN: filas = estados, columnas = terminales + $. Celda puede contener: sX (shift a estado X), rY (reduce por producción Y), acc (aceptar), o vacía (error). - IR-A (goto): filas = estados, columnas = no terminales. Indica a qué estado saltar después de una reducción. - Salida: lista de producciones reducidas (árbol implícito).

7. Algoritmo de análisis LR

Inicialización: pila con estado 0, buffer con la cadena seguida de $.

Bucle: sea s la cima de la pila y a el token actual.

flowchart TD
    A[s = cima estado, a = token actual] --> B{ACCIÓN[s, a]?}
    B -->|sX shift| C[apilar a y X, avanzar entrada]
    B -->|rY reduce Y: A→β| D[desapilar 2|β| elementos<br/>apilar A y IR-A[cima, A]]
    B -->|acc| E([ACEPTAR])
    B -->|vacío| F([ERROR])
    C --> A
    D --> A

Detalle de la reducción: al aplicar $A \rightarrow \beta$, se desapilan $|\beta|$ símbolos y $|\beta|$ estados (cada símbolo trae su estado asociado en la cima). Luego se apila $A$, se consulta IR-A[nueva_cima, A] y se apila el estado resultante.

8. Elementos LR(0) y estados del autómata

Los estados del analizador se construyen a partir de elementos LR(0): producciones con un punto · indicando el progreso del análisis.

E → · E + T — estado inicial, todavía no se ha leído nada de esta producción.
E → E · + T — ya se ha reducido un E, se espera un +.
E → E + · T — leído E +, se espera reducir una T.
E → E + T · — parte derecha completa en la pila: reducción aplicable.

Un estado del autómata es un conjunto de elementos LR(0) que representa todas las producciones compatibles con el prefijo ya leído. Los items con el punto al final indican posiciones de reducción; los que lo tienen en medio indican desplazamientos posibles.

Intuición: a la izquierda del punto está lo que ya se ha "consumido" en la pila; a la derecha, lo que queda por reconocer. Cuando el punto llega al final, se puede reducir por esa producción.

9. Conflictos y gramáticas no LR

En un estado pueden darse dos problemas:

Conflicto shift-reduce: el estado contiene un item A → β · (listo para reducir) y otro B → γ · a δ (espera desplazar a). Con lookahead a, ambos son aplicables.
Conflicto reduce-reduce: el estado contiene A → β · y B → γ ·. Con el mismo lookahead, dos reducciones distintas son aplicables.

Si existen conflictos irresolubles, la gramática no es LR con ese lookahead y no puede analizarse sin transformarla. ⚠️ EXAMEN: saber diagnosticar un conflicto a partir de un estado.

Los ascendentes son más potentes porque existen estrategias de resolución de conflictos (precedencia, asociatividad) que CUP/YACC aplican automáticamente. Es muy raro que se dé un caso irresoluble en las gramáticas reales.

10. Ejemplo de traza con tabla

Gramática del libro de Aho (similar a la del ejemplo anterior). Tabla (extracto relevante):

Estado	`id`	`+`	`*`	`(`	`)`	`$`	E	T	F
0	s5			s4			1	2	3
1		s6				acc
2		r3	s7		r3	r3
3		r6	r6		r6	r6
4	s5			s4			8	2	3
5		r8	r8		r8	r8
6	s5			s4				9	3
7	s5			s4					10
8		s6			s11
9		r1	s7		r1	r1
10		r4	r4		r4	r4
11		r7	r7		r7	r7

Traza sobre id * id $:

Pila (estados con símbolos)	Entrada	Acción
`0`	`id * id $`	ACCIÓN[0, id] = s5 → apilar `id 5`
`0 id 5`	`* id $`	ACCIÓN[5, *] = r6 ($T \rightarrow F$... en realidad $F \rightarrow \text{id}$, prod 8): desapilar `id 5`, apilar `F`, IR-A[0, F] = 3
`0 F 3`	`* id $`	ACCIÓN[3, *] = r6 ($T \rightarrow F$): desapilar `F 3`, apilar `T`, IR-A[0, T] = 2
`0 T 2`	`* id $`	ACCIÓN[2, ] = s7 → apilar ` 7`
`0 T 2 * 7`	`id $`	ACCIÓN[7, id] = s5 → apilar `id 5`
`0 T 2 * 7 id 5`	`$`	r8 → `F`, IR-A[7, F] = 10
`0 T 2 * 7 F 10`	`$`	ACCIÓN[10, $] = r4 ($T \rightarrow T * F$): desapilar 3 elementos × 2, apilar `T`, IR-A[0, T] = 2
`0 T 2`	`$`	ACCIÓN[2, $] = r3 ($E \rightarrow T$): apilar `E`, IR-A[0, E] = 1
`0 E 1`	`$`	ACCIÓN[1, $] = acc → ACEPTAR

11. Relación con la práctica y CUP

CUP genera un analizador LR ascendente. La dificultad de la práctica no está en el algoritmo (ya hecho por CUP) sino en:

Escribir bien la gramática — detectar y resolver conflictos que surjan.
Conectar léxico (JFlex) con sintáctico (CUP) — que los tokens que emite uno sean los que espera el otro.

Los conflictos shift-reduce y reduce-reduce que aparezcan en CUP se entenderán mejor cuando se vea el análisis semántico, porque ahí se ve el efecto real de cada reducción.

Preguntas de Autoevaluación

Diferencia fundamental entre análisis descendente y ascendente. Descendente construye desde el axioma aplicando derivaciones; ascendente construye desde los tokens aplicando reducciones.
¿Qué significa LR(1)? Lectura L→R, derivación por la derecha (invertida), 1 token de lookahead.
¿Qué es un mango? Subcadena en la pila que coincide con la parte derecha de una producción y cuya reducción corresponde a un paso correcto de la derivación por la derecha invertida.
¿Qué representa un elemento LR(0) con el punto al final? Una posición en la que se puede aplicar una reducción.
¿Qué hace la acción sX en la tabla? Desplaza: apila el token leído y el estado X, avanza en la entrada.
¿Qué hace rY si Y es $A \rightarrow \beta$? Desapila $2|\beta|$ elementos (símbolo + estado por cada uno de $\beta$), apila A y el estado IR-A[cima, A].
¿Qué diferencia hay entre la tabla ACCIÓN y la tabla IR-A? ACCIÓN se consulta con terminales e indica shift/reduce/acc/error; IR-A se consulta con no terminales tras una reducción e indica el siguiente estado.
¿Qué es un conflicto shift-reduce? Situación en la que un estado puede tanto desplazar como reducir con el mismo lookahead.
¿Por qué los LR son más potentes que los LL? Acumulan contexto en la pila antes de comprometerse con una producción; no requieren que la decisión pueda tomarse con solo el primer token de la parte derecha.
¿Cuándo se acepta la cadena? Cuando la acción es acc, es decir, cuando el axioma se ha reducido a partir de toda la entrada y el lookahead es $.
Si ACCIÓN[s, a] está vacía, ¿qué significa? Error sintáctico detectado en esa posición exacta.
Relación entre reducción y derivación por la derecha. La secuencia de reducciones que hace un analizador ascendente es la derivación por la derecha de la cadena en orden inverso.

Referencias

Aho, Ullman & Sethi — Compiladores: Principios, Técnicas y Herramientas (libro del dragón). El ejemplo de tabla y traza procede directamente de allí.
Próxima clase: cómo se construye la tabla a partir de los estados y los elementos LR(0), con gramáticas concretas y preparación de la actividad práctica con CUP.
Clase doble el viernes siguiente: clase de refuerzo (solución de la primera actividad) + más análisis ascendente.

Estado	`id`	`+`	`*`	`(`	`)`	`$`	E	T	F
0	s5			s4			1	2	3
1		s6				acc
2		r3	s7		r3	r3
3		r6	r6		r6	r6
4	s5			s4			8	2	3
5		r8	r8		r8	r8
6	s5			s4				9	3
7	s5			s4					10
8		s6			s11
9		r1	s7		r1	r1
10		r4	r4		r4	r4
11		r7	r7		r7	r7

Estado	`id`	`+`	`*`	`(`	`)`	`$`	E	T	F
0	s5			s4			1	2	3
1		s6				acc
2		r3	s7		r3	r3
3		r6	r6		r6	r6
4	s5			s4			8	2	3
5		r8	r8		r8	r8
6	s5			s4				9	3
7	s5			s4					10
8		s6			s11
9		r1	s7		r1	r1
10		r4	r4		r4	r4
11		r7	r7		r7	r7