Skip to content

Clase 10 — Análisis Sintáctico LR: Conflictos, SLR(1) y LR(1)

Resumen Ejecutivo

Última clase teórica de análisis sintáctico. Se revisa el autómata LR(0) construido en clases anteriores con foco en detectar estados conflictivos antes de construir la tabla. Se introduce la diferencia entre criterios de reducción de LR(0), SLR(1) y LR(1), usando una gramática que no es SLR para motivar el LR(1). Se explica el concepto de símbolo de lookahead (UCAG) y cómo elimina conflictos al acotar el criterio de reducción. El algoritmo LALR(1) que usa CAP se sitúa en este contexto como LR(1) compactado.

Conceptos Clave

  • Elemento LR(0): Producción con un punto (•) en alguna posición de la parte derecha. El punto indica cuánto se ha reconocido. ⚠️ EXAMEN
  • Estado conflictivo: Estado que tiene un elemento final (punto al final) y un desplazamiento por un terminal. O dos elementos finales de producciones distintas (reduce-reduce). ⚠️ EXAMEN
  • Criterio de reducción LR(0): Reducir para cualquier terminal de la gramática cuando hay un elemento final.
  • Criterio de reducción SLR(1): Reducir solo para los símbolos en \(\text{SIGUIENTE}(\text{parte izquierda})\). Elimina algunos conflictos. ⚠️ EXAMEN
  • Criterio de reducción LR(1): Reducir solo para el lookahead calculado en contexto al construir el autómata. Elimina más conflictos que SLR. ⚠️ EXAMEN
  • Símbolo de lookahead (UCAG): Símbolo añadido a cada elemento LR(0) para formar un elemento LR(1). Se calcula al completar estados, no al transitar.
  • LALR(1): LR(1) con estados de mismo núcleo unificados. Autómata más pequeño, potencia casi igual. Es el algoritmo que usa CAP. ⚠️ EXAMEN

Desarrollo del Temario

1. Repaso del autómata LR(0) — cómo detectar estados conflictivos

El autómata LR(0) se construye con elementos LR(0): producciones con el punto marcando la posición actual de reconocimiento.

Clasificación de elementos por posición del punto:

Tipo Descripción Ejemplo
Inicial Punto al extremo izquierdo \(B' \bullet \; B\)
Intermedio Punto en posición interior \(B \bullet \; \text{def}\)
Final Punto al extremo derecho \(D \to d \bullet\)

Regla para detectar estados conflictivos: ⚠️ EXAMEN

Un estado es candidato a conflicto si contiene: - Un elemento final y un elemento con un terminal a la derecha del punto → conflicto desplazamiento-reducción potencial. - Dos o más elementos finales de producciones distintas → conflicto reducción-reducción.

Los desplazamientos por no terminales nunca generan conflicto.

Un estado con solo reducciones (un único elemento final, sin desplazamientos por terminales) no es conflictivo.

2. Construcción del autómata — revisión de la gramática de ejemplo

La gramática usada en clase (gramática de bloques con begin/end) tiene los terminales renombrados para simplificar:

Nombre real Abreviatura
begin \(b\)
EYEC \(e\)
EN / end \(f\)
Declaraciones \(d\)

Al recorrer el autómata estado a estado:

  • Estado 0: Solo elementos iniciales (punto al extremo izquierdo en todos). No conflictivo.
  • Estado 7: Tiene un elemento final y un desplazamiento por el terminal punto-y-coma. Estado candidato a conflicto. ⚠️ EXAMEN
Estado 7 (conflictivo):
  E → e •              [elemento final → posible reducción]
  E → e • ; E          [desplazamiento por ';' → posible desplazamiento]
  E → e • , E          [desplazamiento por ',' → posible desplazamiento]

3. Tabla LR(0) — el problema

Con el criterio LR(0), al encontrar un elemento final en el estado 7 se rellena toda la fila con la reducción, para cualquier terminal. Esto genera conflicto desplazamiento-reducción en la columna ;.

4. SLR(1) — acotando la reducción con SIGUIENTE

El analizador SLR(1) mejora LR(0) cambiando solo el criterio de reducción:

SLR(1): En un estado con elemento final \(A \to \alpha \bullet\), se reduce únicamente para los símbolos en \(\text{SIGUIENTE}(A)\).

Cálculo de SIGUIENTE para la gramática del ejemplo:

\[\text{SIGUIENTE}(S) = \{\$\}$$ $$\text{SIGUIENTE}(A) = \{\$, b\}$$ $$\text{SIGUIENTE}(B) = \{\$, b\}\]

En el estado 7, la producción a reducir es \(D \to e\). Como \(\text{SIGUIENTE}(D) = \{f\}\), solo se pone la reducción en la columna \(f\), no en ;. El conflicto desaparece en este caso.

Límite de SLR(1): Hay gramáticas donde \(\text{SIGUIENTE}(A)\) sigue solapando con los terminales de desplazamiento. Entonces SLR(1) no resuelve el conflicto.

5. Gramática que no es SLR(1)

La profesora introduce una gramática donde SLR(1) falla:

S' → S
S  → A | X B
A  → A A | B
B  → b

Al construir el autómata, el estado 5 queda:

Estado 5:
  B → X •              [elemento final]
  S → X • B            [desplazamiento por B (no terminal) — OK]
  B → • b              [desplazamiento por b (terminal) — CONFLICTO]

Calculando conjuntos SIGUIENTE:

\[\text{SIGUIENTE}(S) = \{\$\}$$ $$\text{SIGUIENTE}(A) = \{\$, b\}$$ $$\text{SIGUIENTE}(B) = \{\$, b\}\]

Como \(\text{SIGUIENTE}(B)\) contiene \(b\) y en el estado 5 también se desplaza por \(b\), hay conflicto desplazamiento-reducción. Esta gramática no es SLR(1).

6. LR(1) — el símbolo de lookahead

El analizador LR(1) añade un símbolo de lookahead a cada elemento LR(0) en el momento de construir el autómata (no al rellenar la tabla).

Notación: \([A \to \alpha \bullet \beta, \; a]\) donde \(a\) es el lookahead.

Regla de cálculo del lookahead al completar un estado: ⚠️ EXAMEN

Dado un elemento \([A \to \alpha \bullet B \gamma, \; a]\) que provoca añadir los elementos de \(B\): $\(\text{lookahead para elementos de } B = \text{PRIMERO}(\gamma \; a)\)$ Si \(\gamma = \varepsilon\), entonces el lookahead es \(a\) (se hereda).

Estado 0 con lookaheads:

[S' → • S,   $]     ← axioma ampliado: lookahead siempre $
[S  → • A,   $]     ← nada tras S, se hereda $
[S  → • X B, $]     ← nada tras S, se hereda $
[A  → • A A, $]     ← nada tras A en S→A, hereda $
[A  → • B,   $]     ← igual
[A  → • A A, $/$]   ← A seguido de A, PRIMERO(A) = {b}, concat $ → b/$
[B  → • b,   $]     ← igual

Transición al estado con conflicto:

Al transitar al estado que tenía conflicto, los lookaheads se arrastran sin cambiar. El elemento final \(B \to X \bullet\) llega con lookahead \(\{\$\}\) (no \(\{b, \$\}\) como en SIGUIENTE). La reducción solo se aplica para $, el desplazamiento sigue siendo para b. Conflicto eliminado. ⚠️ EXAMEN

Por qué LR(1) es más potente que SLR(1):

SLR(1) usa \(\text{SIGUIENTE}(A)\) global, calculado sobre toda la gramática. LR(1) usa el lookahead calculado en el contexto concreto del estado, que puede ser un subconjunto estricto de \(\text{SIGUIENTE}(A)\).

7. Comparativa de analizadores LR

Analizador Criterio de reducción Nº de estados Conflictos
LR(0) Todos los terminales Pequeño Muchos
SLR(1) \(\text{SIGUIENTE}(\text{parte izq.})\) Igual que LR(0) Bastantes menos
LR(1) Lookahead calculado en contexto Muy grande Mínimos
LALR(1) Lookahead LR(1), estados unificados LR(1) compactado Mínimos, autómata manejable

Lo que cambia entre analizadores es solo el criterio de reducción. El autómata (elementos LR(0), transiciones) se construye igual en todos.

8. LALR(1) — lo que usa CAP

LALR(1) toma el autómata LR(1) y une los estados que tienen el mismo núcleo (mismos elementos LR(0) sin contar lookaheads), fusionando sus lookaheads. Resultado: un autómata con el mismo número de estados que LR(0)/SLR(1) pero con los lookaheads precisos de LR(1).

Ventaja: análisis más rápido (menos estados) con casi la misma potencia que LR(1). ⚠️ EXAMEN

9. Qué puede pedir el examen

La profesora avisa explícitamente: no pedirá construir un autómata LR completo (riesgo de gramáticas con 27+ estados). Lo que sí puede pedir:

  • Dado un estado del autómata, detectar si es conflictivo.
  • Dado un estado con un elemento final, indicar para qué símbolos se desplazaría y para qué se reduciría (según SLR o LR(1)).
  • Calcular conjuntos SIGUIENTE de una gramática.
  • Explicar la diferencia de criterio entre LR(0), SLR(1) y LR(1). ⚠️ EXAMEN

Ejemplos

Ejemplo: detectar estado conflictivo

Dado el estado:

A → α •           [elemento final]
B → β • c γ       [c es terminal]

Este estado es candidato a conflicto desplazamiento-reducción para el terminal \(c\), si \(c \in \text{SIGUIENTE}(A)\) (en SLR) o \(c \in \text{lookahead}(A \to \alpha)\) (en LR(1)).

Ejemplo: eliminar conflicto con lookahead LR(1)

Estado conflictivo en SLR(1):

B → X •     [reduce para SIGUIENTE(B) = {$, b}]
...         [desplaza por b]

Conflicto en b.

Mismo estado en LR(1), si el lookahead calculado en contexto es solo {$}:

[B → X •, $]    [reduce solo para $]
...              [desplaza por b]

No hay conflicto. LR(1) lo resuelve; SLR(1) no.

Preguntas de Autoevaluación

  1. ¿Qué condición debe cumplir un estado para ser candidato a conflicto desplazamiento-reducción? ¿Y para conflicto reducción-reducción?
  2. ¿Por qué los desplazamientos por no terminales nunca generan conflicto?
  3. ¿Qué diferencia hay entre el criterio de reducción de LR(0) y el de SLR(1)?
  4. Dado un elemento final \(A \to \alpha \bullet\) en un estado, ¿para qué símbolos se reduciría en SLR(1)? ¿Y en LR(1)?
  5. ¿Por qué hay gramáticas independientes del contexto que son LR(1) pero no SLR(1)?
  6. ¿Qué es el símbolo de lookahead (UCAG) en LR(1) y cuándo se calcula?
  7. ¿Cómo se propaga el lookahead al transitar entre estados del autómata LR(1)?
  8. ¿Cuándo el lookahead de un elemento LR(1) coincide con SIGUIENTE y cuándo es un subconjunto estricto?
  9. ¿Qué hace LALR(1) con los estados LR(1) que tienen el mismo núcleo?
  10. ¿Por qué LALR(1) tiene el mismo número de estados que SLR(1) pero mayor potencia?
  11. ¿Qué tipo de preguntas sobre análisis LR puede aparecer en el examen según la profesora? ¿Qué no pedirá?
  12. Si \(\text{SIGUIENTE}(A) = \{b, \$\}\) y el lookahead calculado en contexto para \(A \to \alpha \bullet\) es solo \(\{\$\}\), ¿cuál usa SLR y cuál usa LR(1)?