Skip to content

Tutoría 2 — Taller LALR(1), Gramática Conflictiva y Preguntas Tipo Examen

Resumen Ejecutivo

Sesión de tutoría/taller de ~1h35m. Tres bloques:

  1. Gramática conflictiva y autómata LR(1): Análisis del autómata de la gramática propuesta como ejercicio (con múltiples conflictos shift/reduce). Introducción al algoritmo LALR(1) y cómo compacta estados del LR(1) unificando los que tienen el mismo núcleo.
  2. Preguntas tipo examen: Revisión de ejercicios de léxico y sintáctico sobre una gramática de ejemplo, con resolución participativa. La profesora aclara el formato del examen.
  3. Aclaración sobre declaración de terminales en CAP: Corrección de un error de la clase anterior sobre el significado de poner tipo (integer) a un terminal en la especificación CAP.

Bloque 1 — Gramática Conflictiva y LALR(1)

Autómata LR(1) de la gramática conflictiva

Gramática propuesta: 

S  → A  |  A S B
A  → S A |  a
B  → A

Esta gramática es recursiva y ambigua. Al construir el autómata:

  • En casi todos los estados se meten prácticamente todas las producciones de la gramática por cerradura (porque los símbolos de cerradura provocan que se vuelvan a añadir S, A y B).
  • Lo que varía entre estados son principalmente los lookaheads.

Conflictos detectados:

En al menos 6 estados se produce un conflicto desplazamiento-reducción. El patrón es:

  1. Hay un elemento final (punto al extremo derecho) → posible reducción para el lookahead a.
  2. En el mismo estado hay un elemento con a (terminal) a la derecha del punto → posible desplazamiento por a.

El conflicto existe si el lookahead del elemento final coincide con algún terminal por el que se desplaza en ese estado.

Estado de aceptación: Solo tiene la producción aumentada con lookahead $. La reducción solo ocurre para $, que no coincide con ningún desplazamiento. Sin conflicto.

Para analizar el autómata correctamente, ordenar los estados poniendo primero los elementos que tienen el punto en posición no inicial (el núcleo) y luego los añadidos por cerradura.

Algoritmo LALR(1) ⚠️ EXAMEN

El LALR(1) es el algoritmo que usa CAP/CUP. Parte del autómata LR(1) y lo compacta unificando estados con el mismo núcleo (mismo conjunto de elementos LR(0), sin contar lookaheads).

Procedimiento:

  1. Construir el autómata LR(1) completo.
  2. Identificar grupos de estados con el mismo núcleo.
  3. Por cada grupo, crear un estado unificado con:
  4. Los mismos elementos LR(0) del núcleo.
  5. La unión de los lookaheads de todos los estados del grupo.
  6. Redirigir las aristas:
  7. Las aristas que llegaban a cualquier estado del grupo ahora llegan al estado unificado.
  8. Las aristas que salían de cualquier estado del grupo salen del estado unificado.
  9. Una vez redirigidas las aristas de entrada, las de salida quedan automáticamente recolocadas.

Ejemplo con el autómata de la gramática S' → S; S → L=R | R; L → *R | id; R → L:

El autómata LR(1) tiene 9 estados. Aplicando LALR(1):

  • Estados 3 y 6 tienen el mismo núcleo [B → A • B, ...] (con distinto lookahead: {a, B} vs {$}). Se unifican en estado 36 con lookahead {a, B, $}.
  • Estados 4 y 7 tienen el mismo núcleo [B → B •, ...]. Se unifican en estado 47.
  • Estados 8 y 9 tienen el mismo núcleo [B → A B •, ...]. Se unifican en estado 89.
  • El estado 5 no tiene pareja y permanece igual.

Resultado: de 9 estados se pasa a 7 estados. En autómatas más grandes la reducción es proporcional (puede eliminarse hasta la mitad de estados).

Ventaja de LALR(1):

Autómata más pequeño que LR(1), con casi la misma potencia. La misma cantidad de estados que SLR(1) pero con lookaheads más precisos.

Visualizar el autómata de CAP con Graphviz:

CAP/CUP tiene una función dump (método .dot() del parser) que exporta la tabla de análisis en formato DOT. Con Graphviz se puede convertir a imagen del autómata:

# En el código Java del parser, llamar al método dump/dot
# Luego procesar el fichero .dot:
dot -Tpng parser.dot -o automata.png

No rellena todos los detalles de los estados, pero permite ver cuántos estados hay, las transiciones y los estados finales.

Bloque 2 — Preguntas Tipo Examen

Formato del examen ⚠️ EXAMEN

  • Preguntas cortas y concretas: definir tokens, escribir expresiones regulares, declarar terminales en CAP, implementar una acción semántica, construir un estado del autómata, detectar conflictos.
  • No se pide construir un autómata LR completo.
  • No se usa IDE durante el examen.
  • Se puede explicar con palabras en vez de código exacto; lo importante es demostrar que se entiende el concepto.
  • Próximo día: simulacro de examen completo.

Gramática de ejemplo usada en los ejercicios

S  → A ;
A  → [ A ]
C  → N C | T C | N U M C | N T | N U M | ε

Donde: - N — palabra reservada - T — palabra reservada o identificador de tipo - N U M — entero positivo (no empieza por cero) - [, ] — delimitadores

Ejercicios de léxico

1. Definir tokens y expresiones regulares en JFlex

Definiciones regulares: 

DIGITO     = [1-9]
NUMERO     = {DIGITO}[0-9]*
ID         = [a-zA-Z][a-zA-Z0-9]*

Tokens principales: CORCH_ABRE, CORCH_CIERRA, N, T, NUM, PUNTICOMA.

2. Símbolo (clase Symbol) — qué valor asociar a cada token ⚠️ EXAMEN

Token ¿Necesita valor? Motivo
[ / ] No Se representa a sí mismo; el token es el lexema
N No Palabra reservada; siempre el mismo símbolo
T Sí (yytext) Puede actuar como tipo o como identificador dependiendo del contexto; el sintáctico necesita el texto para decidir
NUM Puede Si se van a hacer operaciones con el valor, convertir a entero. Si solo se comprueba la sintaxis, no es necesario hasta el semántico

Regla: si el token se representa a sí mismo o siempre tiene el mismo significado, no necesita valor adicional. Si el valor del lexema importa para análisis posterior, se pasa como yytext (o convertido al tipo adecuado).

3. Ambigüedad léxica

Existe ambigüedad léxica cuando una misma cadena puede ser reconocida por dos reglas distintas. En esta gramática, no hay ambigüedad porque no se define una regla de identificador que pudiera capturar N o T. Si existiese una regla ID = [a-zA-Z]+, habría ambigüedad entre palabras reservadas e identificadores.

Resolución de la ambigüedad en JFlex: colocar primero las reglas de palabras reservadas. JFlex aplica la regla que aparece antes en caso de empate.

Motivo adicional para ordenar reglas:

Optimización. Las reglas que reconocen lexemas cortos o muy frecuentes (espacios, tabuladores) deben ir primero para evitar que el autómata tenga que recorrer muchos estados antes de reconocerlos.

4. Errores léxicos

Ejemplos válidos: - Número mal formado: 0[1-9][0-9]* — cero seguido de más dígitos (el cero solo está permitido como número independiente). - Carácter no permitido: . (cualquier carácter no reconocido por otras reglas).

Ejercicios de sintáctico

5. Declarar terminales y no terminales en CAP ⚠️ EXAMEN

terminal          CORCH_ABRE, CORCH_CIERRA, N, T, PUNTICOMA;
terminal Integer  NUM;
non terminal      S, A, C;
  • Los terminales son los tokens devueltos por el léxico.
  • Si se asocia tipo (Integer) a un terminal, se indica que su atributo semántico es de ese tipo; es la estructura que luego se usa en las acciones semánticas.
  • Los no terminales no tienen tipo salvo que se indique (para gramáticas de atributos).

Aclaración sobre terminal Integer NUM;:

Poner Integer delante de un terminal no es para declarar un terminal ficticio de precedencia; es para decir que el atributo (valor) que acompaña a ese token tiene tipo Integer. Esto es relevante cuando en las acciones semánticas se quiere acceder al valor numérico. No tiene sentido en gramáticas sin semántica numérica.

6. Recursividad izquierda ⚠️ EXAMEN

La gramática de C tiene recursividad por la derecha (N C, T C): la C aparece al final de la parte derecha, no al principio. La recursividad por la derecha no causa problemas al analizador LR.

Sería recursiva por la izquierda si apareciese como: C → C N | C T | ..., lo cual sí causaría problemas.

7. Construir un estado LR inicial (estado 0)

Solo se incluyen en el estado 0 las producciones que se alcancen por cerradura, partiendo de [S' → • S, $]. No se meten todas las producciones de la gramática. ⚠️ EXAMEN

Error común: creer que el estado 0 siempre tiene todas las producciones. Solo se añaden las que tienen un símbolo de cerradura (no terminal) a la derecha del punto, y así recursivamente.

Ejemplo con la gramática anterior: 

Estado 0:
  [S' → • S,      $]      ← inicio
  [S  → • A ;,    $]      ← S es símbolo de cerradura, se añaden sus producciones
  [A  → • [ A ],  $]      ← A es símbolo de cerradura, se añaden sus producciones
                           ← [ es terminal, cerradura se detiene aquí

Las producciones de C no se añaden al estado 0 porque C no aparece a la derecha del punto en ningún elemento del estado 0.

Acciones posibles desde el estado 0: - Por [ → desplazamiento a nuevo estado - Por S → transición al estado de aceptación - Por A → desplazamiento a un nuevo estado

No hay reducciones en el estado 0 porque ningún elemento es final.

8. Detección de conflictos en un estado

Dado un estado con: 

[S → N • C,   $]      ← elemento intermedio (C es no terminal a la derecha del punto)
[C → • N C,   $]      ← añadido por cerradura
[C → • T C,   $]
[C → •,       $]      ← elemento final (lambda/épsilon)

Pregunta: ¿hay conflicto?

  • El elemento [C → •, $] es final → reducción para $.
  • Los demás elementos desplazan por N, T, NUM (terminales).
  • $ no coincide con N, T ni NUM → no hay conflicto en este estado.

Si se redujera también para N o T, habría conflicto desplazamiento-reducción.

9. Definición de token vs. lexema

Concepto Significado
Lexema La cadena concreta reconocida: x, myVar, 42
Token La categoría del lexema: IDENTIFICADOR, NUM
yytext Devuelve el lexema (la cadena reconocida por la regla JFlex)

yytext no devuelve el token; devuelve la cadena del lexema. El token es el identificador de categoría que se retorna con return new Symbol(...).

10. Por qué ordenar las reglas léxicas

  1. Para resolver ambigüedades: las palabras reservadas antes que los identificadores.
  2. Para optimización: las reglas más frecuentes y con autómatas más cortos primero (espacios, tabuladores, delimitadores simples).

Bloque 3 — Aclaración sobre Tipos en Terminales CAP

La profesora corrige una afirmación incorrecta de la sesión anterior:

Lo que se dijo (incorrecto): Que terminal Integer NUM; declaraba un terminal ficticio para gestionar precedencias.

Lo correcto: Poner un tipo delante de un terminal en CAP indica que ese terminal lleva asociado un atributo de ese tipo, que se usará en las acciones semánticas. Es la misma idea que la clase Symbol usada para conectar léxico y sintáctico.

Si no se van a usar valores en las acciones semánticas (gramática sin semántica numérica), no tiene sentido declarar el tipo. Si se hace, debe justificarse en la memoria.

Para declarar terminales ficticios de precedencia (como UMINUS), sí se declaran como terminales, pero sin tipo y solo para usarlos con la directiva %prec en la producción correspondiente.

Preguntas de Autoevaluación

  1. ¿Por qué en la gramática conflictiva casi todos los estados del autómata LR(1) contienen prácticamente las mismas producciones?
  2. ¿Qué condición deben cumplir dos estados del autómata LR(1) para poder unificarse en LALR(1)?
  3. Al unificar dos estados en LALR(1), ¿cómo se obtiene el lookahead del estado unificado?
  4. ¿Cómo se redirigen las aristas al unificar estados en LALR(1)? ¿Solo las de entrada, solo las de salida, o ambas?
  5. ¿Por qué el estado 0 del autómata LR no contiene siempre todas las producciones de la gramática?
  6. ¿Qué diferencia hay entre un lexema y un token? ¿Qué devuelve yytext?
  7. ¿Por qué hay que ordenar las reglas en JFlex? ¿Qué dos motivos existen?
  8. ¿Qué significa poner terminal Integer NUM; en CAP? ¿Para qué sirve ese tipo?
  9. ¿Cómo se declara y usa un terminal ficticio de precedencia (como UMINUS) en CAP?
  10. Dado un estado con un elemento final de lookahead {$} y desplazamientos por N y T, ¿hay conflicto? ¿Por qué?