Clase 8 — Análisis Sintáctico Ascendente: Autómata LR(0), Tabla y SLR(1)

Resumen Ejecutivo

Segunda parte (más teórica e implementacional) del análisis sintáctico ascendente. Se construye paso a paso el autómata LR(0) sobre una gramática de expresiones, formalizando los elementos LR(0) (producción con punto marcador), el cierre de estados, las transiciones por terminales y no terminales, y los estados finales (de reducción y de aceptación). A partir del autómata se derivan las dos partes de la tabla de análisis: ACCIÓN (sX, rX, acc, vacía=error) e IR-A. Se identifican los dos defectos del LR(0) puro (reducir para cualquier terminal) y se introduce SLR(1), que limita las reducciones a los símbolos del conjunto SIGUIENTE del no terminal padre. Se cierra con un repaso de la práctica 1 (lexer flex/JFlex) y el adelanto del laboratorio CUP de la práctica 2. ⚠️ EXAMEN: construcción del autómata LR(0), construcción de la tabla, identificación y diagnóstico de conflictos shift-reduce / reduce-reduce, y la mejora SLR(1).

Conceptos Clave

Elemento LR(0): Producción con un punto en alguna posición de su parte derecha. Indica qué porción ya está en la pila (a la izquierda del punto) y qué falta por reconocer (a la derecha del punto). ⚠️ EXAMEN
Elemento LR(0) inicial: punto al principio de la parte derecha. Significa "todavía no he empezado a reconocer esta producción".
Elemento LR(0) final: punto al final de la parte derecha. Toda la parte derecha está en la pila → es candidato a reducción.
Núcleo de un estado: elementos LR(0) cuyo punto no está al principio (excepto el del axioma ampliado). Sirve para decidir si dos estados son el mismo. ⚠️ EXAMEN
Cierre de un estado (closure): dado un conjunto de elementos, mientras a la derecha del punto haya un no terminal $A$, añadir todos los elementos LR(0) iniciales de las producciones de $A$. Se aplica de forma transitiva hasta no añadir nada nuevo.
Transición por símbolo $X$: desde un estado, todos los elementos cuyo símbolo a la derecha del punto sea $X$ pasan al estado destino con el punto desplazado una posición a la derecha.
Axioma ampliado $S' \to S \$$: ⚠️ EXAMEN. Se introduce una nueva producción con un símbolo no terminal nuevo y el delimitador $ para garantizar un único punto de aceptación.
Estado de aceptación: el que contiene el elemento LR(0) final del axioma ampliado, $S' \to S \cdot \$$ (tras desplazar $, $S' \to S \$ \cdot$).
Tabla LR de análisis: dos zonas. ACCIÓN indexada por estado × terminal (incluido $); IR-A indexada por estado × no terminal. ⚠️ EXAMEN
Acciones: sX (shift, desplaza al estado X), rX (reduce por la producción X), acc (aceptar), casilla vacía = error sintáctico.
Conflicto shift-reduce: una misma casilla de ACCIÓN admite tanto sX como rY. Suele resolverse por reglas heurísticas (precedencia, asociatividad). ⚠️ EXAMEN
Conflicto reduce-reduce: una casilla admite rX y rY con $X \neq Y$. Nunca aceptable: la gramática (o el analizador) no es válida. ⚠️ EXAMEN
LR(0): no consulta la entrada para reducir → reduce siempre que aparezca un elemento final, en todas las columnas de terminales. Conflictivo con frecuencia.
SLR(1) (Simple LR): mismo autómata que LR(0), pero la reducción $A \to \alpha \cdot$ se inscribe solo en las columnas de SIGUIENTE($A$). Resuelve muchos conflictos del LR(0) sin agrandar el autómata. ⚠️ EXAMEN
LR(1) / LALR(1): llevan símbolo de anticipación dentro de cada elemento; el autómata es mucho mayor. Es el que generan los compiladores reales (CUP, yacc, bison) tras compactación.

Desarrollo del Temario

1. Repaso: dirección de la construcción

El analizador ascendente parte de las hojas (entrada) y reduce hacia el axioma. Equivale a una derivación por la derecha invertida, de ahí la R de LR(k). El paréntesis (k) indica el número de tokens de lookahead.

Familia	Lookahead	Comentario
LR(0)	0	Decide solo con el estado. Frágil.
SLR(1)	1	Filtra reducciones por SIGUIENTE.
LR(1) canónico	1	Símbolo de anticipación en cada elemento. Tabla enorme.
LALR(1)	1	LR(1) compactado (estados con mismo núcleo). El más usado.
LR(k), k≥2	k	Teóricos; en la práctica innecesarios.

Hay también analizadores ascendentes no predictivos (con retroceso). Hoy están en desuso: si fallan, no sabes si el error es de la cadena o del propio algoritmo.

2. Elemento LR(0) y su semántica con la pila

Para una producción $E \to E + T$ son posibles cuatro elementos LR(0):

\[ E \to \cdot E + T \qquad E \to E \cdot + T \qquad E \to E + \cdot T \qquad E \to E + T \cdot \]

Significado en términos de la pila de análisis:

Punto al principio: nada de esa producción en la pila todavía.
Punto en posición intermedia: ya se reconoció (tras posibles reducciones) lo que está a su izquierda; falta lo de la derecha.
Punto al final: la pila contiene íntegramente la parte derecha → la reducción es legal.

Los elementos con punto no final generan transiciones; los finales generan reducciones.

3. Construcción del autómata LR(0): gramática de ejemplo

Gramática de expresiones (resumida):

\[ \begin{aligned} (0)\ E' &\rightarrow E \,\$ \\ (1)\ E &\rightarrow E + T \\ (2)\ E &\rightarrow T \\ (3)\ T &\rightarrow T * F \\ (4)\ T &\rightarrow F \\ (5)\ F &\rightarrow (E) \\ (6)\ F &\rightarrow \text{id} \end{aligned} \]

Se ha ampliado el axioma con $E' \to E\$$. ⚠️ EXAMEN: el $ es indispensable para detectar el final del análisis y disponer de un único estado de aceptación.

3.1 Estado inicial $S_0$

Se parte del elemento $E' \to \cdot E\$$. A la derecha del punto está $E$: por cierre, añadimos todos los iniciales de $E$ ($E \to \cdot E+T$, $E \to \cdot T$). Como $T$ aparece tras un punto, añadimos los de $T$, y a su vez los de $F$. Resultado:

S0 = { E' → ·E$,
       E  → ·E+T,
       E  → ·T,
       T  → ·T*F,
       T  → ·F,
       F  → ·(E),
       F  → ·id }

Sin reintroducir lo ya añadido. En LR(0) no diferenciamos por contexto: una producción con punto al inicio se mete una sola vez. (En LR(1) sí, porque cambia el lookahead).

3.2 Transiciones desde $S_0$

Por cada símbolo a la derecha del punto se genera una transición:

Por $E$: $\{E' \to E \cdot \$,\ E \to E \cdot + T\}$ → $S_1$
Por $T$: $\{E \to T \cdot,\ T \to T \cdot * F\}$ → $S_2$
Por $F$: $\{T \to F \cdot\}$ → $S_3$ (estado final → reducción $r4$)
Por (: $\{F \to ( \cdot E)\}$ + cierre con producciones de $E$, $T$, $F$ → $S_4$
Por id: $\{F \to \text{id} \cdot\}$ → $S_5$ (final → reducción $r6$)

Procedimiento ordenado: llegar a un estado, cerrar, definir todas sus transiciones, ir al siguiente. Si no se cierra antes de continuar, se generan estados inconsistentes. ⚠️ EXAMEN

3.3 Estado de aceptación

Desde $S_1$, una transición por $ lleva a $\{E' \to E\$ \cdot\}$. Es un elemento final del axioma ampliado → estado de aceptación (no es una reducción ordinaria).

3.4 Reutilización de estados (núcleo)

Al construir nuevos estados puede aparecer un núcleo idéntico al de un estado ya existente: en ese caso no se crea uno nuevo, se reutiliza el ya existente. ⚠️ EXAMEN: criterio formal = mismos elementos LR(0) con punto desplazado (núcleo, ignorando los iniciales del cierre).

4. Tipos de estado del autómata

Tipo	Característica	Acción asociada
Inicial	$S_0$, contiene $S' \to \cdot S\$$	Comienzo del análisis
Final de reducción	Contiene un elemento $A \to \alpha \cdot$ con $A \neq S'$	`rX` para todos los terminales (en LR(0))
De aceptación	Contiene $S' \to S\$ \cdot$	`acc` en columna `$`
Intermedio	Solo elementos no finales	Solo `shift` / `goto`

Hay estados con varios elementos finales: dan conflicto reduce-reduce salvo que SLR(1)/LR(1) los discrimine.

5. Construcción de la tabla a partir del autómata

Se rellena con tres reglas:

Transición por terminal $a$ desde $S_i$ a $S_j$ → ACCIÓN[i, a] = sj.
Transición por no terminal $A$ desde $S_i$ a $S_j$ → IR-A[i, A] = j.
Estado $S_i$ con elemento final $A \to \alpha \cdot$ (producción $k$):
LR(0): ACCIÓN[i, t] = rk para todo terminal $t$ (incluido $). ⚠️ EXAMEN: ese "todos" es el gran defecto del LR(0).
SLR(1): ACCIÓN[i, t] = rk solo si $t \in \text{SIGUIENTE}(A)$. ⚠️ EXAMEN
Estado de aceptación: ACCIÓN[i, \$] = acc.
Casillas en blanco = error sintáctico.

5.1 Tabla LR(0) (resumen del ejemplo de expresiones)

Estado	id	+	*	(	)	$	E	T	F
0	s5			s4			1	2	3
1		s6				acc
2		r2	s7		r2	r2
3		r4	r4		r4	r4
4	s5			s4			8	2	3
5		r6	r6		r6	r6
...	...	...	...	...	...	...	...	...	...

El relleno completo se obtiene aplicando los pasos 1–4 al autómata. Lo importante para el examen no es memorizar la tabla, sino derivarla del autómata.

6. Conflictos del LR(0)

6.1 Conflicto shift-reduce

Un mismo estado contiene un elemento final (que pide reducir) y una transición por un terminal $t$ (que pide desplazar). En LR(0), como la reducción se anota para todos los terminales, choca con la s de $t$.

Ejemplo de la clase: gramática con bloque → begin DECs ; EJECs end. En cierto estado se podría reducir $E \to E$ y simultáneamente desplazar ;.

6.2 Conflicto reduce-reduce

Un mismo estado contiene dos elementos finales distintos $A \to \alpha \cdot$ y $B \to \beta \cdot$ con $A \neq B$. El analizador no sabe por cuál reducir. ⚠️ EXAMEN: no se puede tolerar nunca. Hay que reescribir la gramática o usar un analizador más potente (LR(1)/LALR).

6.3 Lectura de la profesora

"Cuando construyes la tabla LR(0) y rellenas reducción para todos los terminales estás yendo a ciegas: no miras nada de la entrada. Por eso no funciona en gramáticas reales."

7. SLR(1) — primer paso de mejora

Misma idea, mismo autómata. Solo cambia el paso 3 de la construcción de la tabla:

En el estado $S_i$ con $A \to \alpha \cdot$ (producción $k$), poner rk únicamente en las columnas $t \in \text{SIGUIENTE}(A)$.

Beneficio: si SIGUIENTE($A$) no contiene los símbolos por los que existe shift, el conflicto desaparece. Coste: hay que calcular el conjunto SIGUIENTE de cada no terminal (lo mismo que se calculaba en LL(1)).

7.1 Comparativa

Aspecto	LR(0)	SLR(1)
Lookahead	0	1
Autómata	Igual	Igual
Reducción	Todos los terminales	Solo SIGUIENTE($A$)
Conflictos típicos	Muchos	Bastantes menos
Tabla	Más densa en `r`	Más limpia

7.2 Limitaciones del SLR(1)

SIGUIENTE se calcula fuera del contexto de la frase concreta. Hay reducciones legales en general que SLR(1) admite y que en ese punto del análisis no eran las correctas. Para esos casos hay que pasar a LR(1) canónico o LALR(1) (que es lo que genera CUP en la práctica 2).

8. Heurística para los conflictos en CUP

En la práctica con CUP la profesora adelanta:

Conflictos reduce-reduce: no permitir nunca. Si aparece, revisar la gramática.
Conflictos shift-reduce: a menudo aceptables si los provoca una construcción típica (p. ej. dangling else en if-then-else). Suele resolverse priorizando el shift sobre el reduce, lo que equivale a "asociar el else con el if más cercano". ⚠️ EXAMEN
Precedencia y asociatividad de operadores: declararlas en CUP. Si no, los conflictos en expresiones aritméticas son inevitables aunque la gramática esté factorizada, y la traducción posterior puede generar código incorrecto (sumas antes que productos).

9. Repaso de la práctica 1 (lexer flex/JFlex)

Comentarios sobre buenas prácticas detectadas en las correcciones:

Orden de las reglas: las palabras reservadas antes que el patrón de identificadores. flex elige siempre la primera regla que reconoce el lexema; si pones identificador primero, main se reconoce como identificador. ⚠️ EXAMEN (en prácticas)
Espacios en blanco al principio: mover [ \t\n]+ al inicio del archivo. Aunque funcionalmente da igual, el autómata generado es más eficiente: los blancos son lo más frecuente y se descartan en estado inicial.
Operadores y delimitadores antes que identificadores: sus autómatas son más cortos (un punto y coma se decide en un único estado), reconocer primero acelera el lexer.
Errores con localización: yyline y yycolumn permiten reportar la línea y columna. Imprimir además yytext ayuda a identificar el lexema fallido.
Identificadores demasiado largos: detectar con yylength(). La especificación pedía longitud $\leq 100$ (aunque en clase se mencionó 30 por error). Generar un token de error específico, no fallar silenciosamente.
Recomendación de robustez: terminar las reglas de error con un patrón explícito en lugar de usar . como catch-all, porque . no captura saltos de línea y deja agujeros.
Evitar main() dentro del .flex: sacarlo a una clase aparte. El léxico será una subrutina del sintáctico, así que su main desaparecerá en cuanto integremos CUP.

10. Adelanto de la práctica 2 (CUP / sintáctico)

Próxima práctica: codificar una especificación CUP del lenguaje Pocket (la gramática ya viene dada).

Estructura del archivo CUP:

Zonas de código (importaciones, atributos auxiliares).
Lista de terminales (deben coincidir con los tokens que retorna flex).
Lista de no terminales.
Declaraciones de precedencia y asociatividad de operadores. ⚠️ EXAMEN
Símbolo inicial de la gramática.
Producciones, con acciones semánticas mínimas: imprimir el token reconocido y la producción aplicada.

Conexión léxico–sintáctico:

El lexer deja de tener main: lo invoca CUP.
Cada acción de flex debe return el token correspondiente. Conviene devolver objetos enriquecidos (sema, línea, columna) en lugar de un entero pelado.
La salida pedida: archivo con un token por línea (lexema reconocido) y, en otra línea por cada reducción, el número de regla y la regla aplicada.

Gestión de errores en la práctica 2: solo reportar (línea + columna + mensaje "error"), no se exige recuperación de errores.

11. ¿Por qué no LR(k) con k≥2?

La profesora cierra el bloque destacando que LR(2), LR(3)… son teóricamente correctos pero inviables en la práctica:

El autómata crece exponencialmente con $k$.
Para gramáticas reales (decenas a cientos de producciones), basta con LALR(1).
Los compiladores modernos (CUP, bison, yacc) generan LALR(1) y aplican una compactación posterior para reducir estados/transiciones.

Ejemplos / Ejercicios resueltos

Ejemplo 1 — Cierre de un estado

Dada la gramática ampliada de §3 y el elemento inicial $E' \to \cdot E\$$:

A la derecha del punto: $E$ → añadir $E \to \cdot E + T$ y $E \to \cdot T$.
A la derecha del punto en los nuevos: $E$ (ya añadido) y $T$ → añadir $T \to \cdot T * F$, $T \to \cdot F$.
A la derecha en $T \to \cdot F$: $F$ → añadir $F \to \cdot (E)$, $F \to \cdot \text{id}$.
No quedan no terminales nuevos a la derecha de un punto. Cierre completo.

Ejemplo 2 — Detección de conflicto shift-reduce

Estado:

\[ S_i = \{ A \to \alpha \cdot,\ B \to \beta \cdot c\, \gamma \} \]

$A \to \alpha \cdot$ pide reducir $r(A \to \alpha)$ para todos los terminales (LR(0)) o solo SIGUIENTE($A$) (SLR(1)).
$B \to \beta \cdot c\, \gamma$ pide desplazar por c.

Hay conflicto si y solo si c aparece en la columna donde se inscribe la reducción. SLR(1) lo elimina si $c \notin \text{SIGUIENTE}(A)$.

Ejemplo 3 — Aplicación práctica del autómata sobre una cadena

Cadena id + id $. Pila inicial vacía, estado $0$.

Paso	Pila	Entrada	Acción
1	`0`	`id + id $`	s5 (shift `id` y va a $S_5$)
2	`0 id 5`	`+ id $`	r6 ($F \to \text{id}$): saca `id 5`, mete $F$, IR-A[0,F]=3
3	`0 F 3`	`+ id $`	r4 ($T \to F$): saca `F 3`, mete $T$, IR-A[0,T]=2
4	`0 T 2`	`+ id $`	r2 ($E \to T$): saca `T 2`, mete $E$, IR-A[0,E]=1
5	`0 E 1`	`+ id $`	s6 (shift `+` y va a $S_6$)
6	`0 E 1 + 6`	`id $`	s5
7	`0 E 1 + 6 id 5`	`$`	r6, r4 (sucesivamente hasta dejar $T$ encima de `+ 6`)
8	`0 E 1 + 6 T 9`	`$`	r1 ($E \to E + T$): saca tres pares, mete $E$, IR-A[0,E]=1
9	`0 E 1`	`$`	acc ✓

Cada reducción va seguida de un goto (usando IR-A) por el no terminal que acaba de aparecer en la pila. ⚠️ EXAMEN

Preguntas de Autoevaluación

¿Qué representa el punto en un elemento LR(0) y qué pasa con la pila a izquierda y derecha de él?
¿Por qué se amplía la gramática con $S' \to S\$$ antes de construir el autómata? ¿Qué problema evita el $?
Define el núcleo de un estado y explica cómo se usa para decidir si se crea un estado nuevo o se reutiliza uno existente.
Describe en cinco pasos el algoritmo de cierre de un estado LR(0).
¿Cómo se etiquetan las transiciones del autómata LR(0)? ¿Qué pasa con las que se hacen por no terminal?
Diferencia entre estado de aceptación y estado final de reducción. Pon un ejemplo de cada uno.
¿Cómo se rellena la zona ACCIÓN de la tabla LR(0) para un estado con un elemento final? ¿Y la zona IR-A?
¿Qué significa una casilla vacía en la tabla? ¿Por qué no hay que confundirla con acc?
Define conflicto shift-reduce y conflicto reduce-reduce. ¿Cuál es tolerable en la práctica y por qué?
¿Cuál es el "gran defecto" de LR(0) que SLR(1) corrige? Explícalo en términos de la columna de reducción.
¿Qué información adicional necesita SLR(1) sobre la gramática para construir su tabla? ¿Cómo se calcula?
Da una situación en la que SLR(1) no resuelve un conflicto y haga falta LR(1) canónico o LALR(1).
¿Por qué LR(k) con $k \geq 2$ no se usa en la práctica?
Al ejecutar el algoritmo shift-reduce, después de cada reducción se hace un movimiento adicional. ¿Cuál es y por qué?
En la práctica 1, ¿por qué conviene poner las palabras reservadas antes que la regla del identificador? ¿Y los espacios en blanco al principio?
En la especificación CUP de la práctica 2, ¿qué declaras antes de las producciones y por qué es crítico para evitar conflictos shift-reduce?