Clase 11 — Repaso Analizador LR(1): Elementos, Cierre y Tabla
Resumen Ejecutivo
Clase de repaso sobre el analizador LR(1), con énfasis en la construcción del autómata y la tabla de análisis. La profesora detectó que en la clase anterior no habían quedado claros los pasos de la cerradura y el cálculo del lookahead, así que reconstruye el proceso desde cero con un ejemplo completo. Se cubre también la gramática conflictiva propuesta como ejercicio para el taller siguiente, y se resuelven dudas de la actividad 2 (práctica sintáctica con CAP/CUP).
Conceptos Clave
- Elemento LR(1): Par formado por un elemento LR(0) (producción con punto) y un símbolo de lookahead (símbolo de anticipación). Notación:
[A → α • β, a]. ⚠️ EXAMEN - Tipos de elementos LR(0):
- Inicial: punto en el extremo izquierdo
A → • α - Intermedio: punto en posición interior
A → α • β - Final: punto en el extremo derecho
A → α •→ activa posible reducción - Símbolo de lookahead / UCAG: Solo es relevante cuando el elemento es final. Se usa para decidir para qué terminales se hace la reducción. En transiciones, el lookahead no cambia; solo cambia al cerrar un estado. ⚠️ EXAMEN
- Cerradura de un estado: Dado un elemento con un no terminal \(B\) a la derecha del punto (símbolo de cerradura), se añaden todas las producciones de \(B\) con el punto al inicio, calculando el nuevo lookahead como \(\text{PRIMERO}(\beta \; a)\) donde \(\beta\) es lo que hay a la derecha de \(B\) en el elemento original y \(a\) es el lookahead heredado. ⚠️ EXAMEN
- Núcleo de un estado: Elementos con el punto en posición no inicial (intermedios y finales). Los iniciales se añaden por cerradura.
- Diferencia entre LR(0), SLR(1) y LR(1):
- LR(0): reduce para todos los terminales de la gramática
- SLR(1): reduce solo para \(\text{SIGUIENTE}(\text{parte izquierda})\)
- LR(1): reduce solo para el lookahead calculado en contexto ⚠️ EXAMEN
Desarrollo del Temario
1. Regla fundamental del lookahead
El lookahead en LR(1) no cambia durante las transiciones; solo se recalcula al cerrar un estado (al añadir nuevos elementos iniciales por cerradura).
Regla para calcular el lookahead al cerrar:
Dado
[A → α • B β, a], al añadir las producciones de \(B\): $\(\text{lookahead} = \text{PRIMERO}(\beta \; a)\)$ Si \(\beta = \varepsilon\), el lookahead es \(a\) (se hereda directamente).
2. Construcción del autómata LR(1) — ejemplo completo
Gramática:
S' → S
S → L = R | R
L → * R | id
R → L
Estado 0 (construcción paso a paso):
Se empieza siempre con la producción ampliada:
[S' → • S, $]
Como S es no terminal a la derecha del punto, se añaden las producciones de S. A la derecha de esta S no hay nada, así que el lookahead es $:
[S → • L = R, $]
[S → • R, $]
L aparece como símbolo de cerradura en S → • L = R. A la derecha de L hay = R, por tanto el lookahead es \(\text{PRIMERO}(= R \; \$) = \{=\}\):
[L → • * R, =]
[L → • id, =]
R aparece como símbolo de cerradura en S → • R. A la derecha no hay nada, lookahead = $:
[R → • L, $]
Al añadir R → • L, vuelve a aparecer L como símbolo de cerradura. Ahora el contexto es distinto (viene de R → • L, sin nada a la derecha), lookahead = $:
[L → • * R, =, $] ← se unifican los dos elementos que tienen el mismo LR(0)
[L → • id, =, $]
Así se acaba la cerradura del estado 0.
Resumen del estado 0:
[S' → • S, $]
[S → • L = R, $]
[S → • R, $]
[L → • * R, =, $]
[L → • id, =, $]
[R → • L, $]
Transiciones desde el estado 0:
| Símbolo leído | Núcleo del nuevo estado |
|---|---|
S |
[S' → S •, $] — estado de aceptación |
L |
[S → L • = R, $] y [R → L •, $] |
R |
[S → R •, $] |
* |
[L → * • R, =, $] → cerrar añadiendo producciones de R |
id |
[L → id •, =, $] — elemento final, reducción |
3. Detección de conflictos
Un estado es candidato a conflicto si contiene: - Un elemento final (reducción posible) y un elemento con un terminal a la derecha del punto que coincide con algún lookahead del final → conflicto desplazamiento-reducción. - Dos o más elementos finales con lookaheads solapados → conflicto reducción-reducción.
El LR(1) resuelve conflictos que el SLR(1) no puede resolver porque el lookahead en LR(1) es el subconjunto de \(\text{SIGUIENTE}\) válido en el contexto concreto, no la totalidad.
Ejemplo del estado con L:
[S → L • = R, $] ← desplaza por '='
[R → L •, $] ← reduce por R → L, solo para '$'
El desplazamiento ocurre para = y la reducción para $. No hay solapamiento: sin conflicto.
En SLR(1) habría conflicto porque \(\text{SIGUIENTE}(R)\) contiene =.
4. Construcción de la tabla LR(1)
La tabla se construye directamente del autómata:
- Por cada transición del estado \(i\) al estado \(j\) por terminal \(a\):
acción[i, a] = desplazar j - Por cada transición por no terminal \(A\):
goto[i, A] = j - Por cada elemento final
[A → α •, a]en el estado \(i\):acción[i, a] = reducir por A → α - Estado de aceptación:
acción[i, $] = aceptar
La clave es que la reducción solo se pone para el lookahead del elemento, no para todos los terminales.
5. Diferencia práctica entre SLR(1) y LR(1)
| Aspecto | SLR(1) | LR(1) |
|---|---|---|
| Criterio de reducción | \(\text{SIGUIENTE}(\text{parte izq.})\) global | Lookahead calculado en contexto |
| Tamaño del autómata | Igual que LR(0) | Puede ser muy grande |
| Conflictos resueltos | Más que LR(0) | Más que SLR(1) |
| Uso en la práctica | Raro | LALR(1) (versión compactada) |
6. Ejercicio propuesto para el taller
La profesora propone construir el autómata LR(1) de esta gramática conflictiva:
S → A | A S B
A → S A | a
B → A
Características de este autómata: - Es recursiva: en casi todos los estados se meten prácticamente todas las producciones por cerradura. - Tiene múltiples conflictos desplazamiento-reducción (se estima alrededor de 6 estados conflictivos). - Es un buen ejercicio para identificar conflictos por su estructura.
La profesora indica que no pedirá construir autómatas completos de este tamaño en el examen, pero sí analizar estados concretos y detectar/explicar conflictos.
7. Dudas sobre la Actividad 2 (práctica con CAP/CUP)
Recuperación de errores sintácticos:
El analizador sintáctico se detiene al encontrar un error si no se implementa una rutina de recuperación. Lo más sencillo sería avanzar tokens hasta encontrar un punto y coma y reanudar. Esta estrategia se llama recuperación en modo pánico. No se pide en la actividad, pero si se implementa hay que documentarlo en la memoria.
Separación léxico/sintáctico:
Los errores léxicos los gestiona el léxico; el sintáctico recibe el token ERROR y lo trata como un error sintáctico. No se debe mezclar la responsabilidad de ambos módulos.
Ambigüedad y precedencias:
La gramática de la práctica es ambigua (operadores sin precedencia definida). El núcleo de la actividad es: 1. Definir correctamente las precedencias y asociatividades de los operadores en CAP para eliminar conflictos. 2. Gestionar el menos unario vs. menos binario asignando a la producción unaria la precedencia de un terminal ficticio con mayor prioridad.
Punto de atención: los warnings de CAP sobre conflictos shift/reduce deben resolverse mediante las directivas %left, %right, %nonassoc y %prec, no ignorarlos.
Formato de salida:
El enunciado puede tener inconsistencias de formato entre las instrucciones y los ficheros de salida de ejemplo. La profesora indica que lo importante es que el formato sea coherente y que la memoria explique las decisiones tomadas; no se penalizará por diferencias menores de puntuación o separadores.
Preguntas de Autoevaluación
- ¿Cuándo se recalcula el lookahead en la construcción del autómata LR(1): en la transición o en la cerradura?
- Dado el elemento
[A → α • B β, a], ¿cuál es el lookahead para los elementos de \(B\) que se añaden por cerradura? - ¿Qué diferencia hay entre el lookahead LR(1) y el conjunto \(\text{SIGUIENTE}\) usado en SLR(1)?
- ¿Por qué el estado con
[S → L • = R, $]y[R → L •, $]no tiene conflicto en LR(1) pero sí lo tendría en SLR(1)? - ¿Cómo se identifica un conflicto desplazamiento-reducción en un estado del autómata LR(1)?
- ¿Qué es el núcleo de un estado? ¿Qué elementos forman parte de él?
- ¿Por qué en el estado 0 solo se añaden las producciones de los no terminales que aparecen a la derecha del punto, y no todas las producciones de la gramática?
- ¿Qué estrategia básica de recuperación de errores sintácticos es la más sencilla de implementar?
- ¿Cómo se resuelve en CAP el conflicto entre el menos unario y el menos binario?
- ¿Qué indica el lookahead
$en el elemento inicial[S' → • S, $]?