Tutoría 3 — Simulacro de Examen: Léxico, Sintáctico y Semántico

Resumen Ejecutivo

Sesión de tutoría/taller (~2h) dividida en dos bloques:

1. Continuación de la clase 14 (código intermedio): Breve repaso de cuartetos y tercetos, con intercambio sobre la actividad 3 (generación de código en NASM). La profesora aclara que el enunciado correcto está en documentación y que el código NASM no se pide en la actividad.
2. Simulacro de examen guiado: Resolución participativa de un examen completo sobre una gramática de ejemplo. Bloques de léxico (JFlex), sintáctico (CAP/LR) y semántico. La profesora va resolviendo en directo con comentarios sobre qué se valora y cómo justificar las respuestas.

---

Conceptos Clave

• Ambigüedad léxica: Cuando una misma cadena puede ser reconocida por dos reglas distintas. Se resuelve poniendo la regla más prioritaria primero en JFlex. ⚠️ EXAMEN
• Símbolo (clase Symbol): Objeto devuelto por el léxico al sintáctico. Lleva el token y, opcionalmente, el valor asociado (lexema o valor convertido). ⚠️ EXAMEN
• Valor asociado a un token: Solo se necesita si el valor del lexema importa para análisis posterior (semántico). Palabras reservadas y delimitadores no lo necesitan. ⚠️ EXAMEN
• Cierre del estado LR: Solo se añaden producciones de los no terminales que aparecen a la derecha del punto. No se meten todas las producciones de la gramática. ⚠️ EXAMEN
• Recursividad por la izquierda: El primer símbolo de la parte derecha de la producción es el mismo que el de la izquierda. No causa problemas en analizadores LR ascendentes.
• Regla del axioma ampliado: El símbolo inicial real de la gramática es S; S' es solo un recurso para que el autómata detecte la aceptación. No forma parte de la gramática formal.
• Acción semántica justificada: El examen valora más una respuesta correctamente explicada con algún error menor que una respuesta correcta sin ninguna explicación.

---

Desarrollo del Temario

1. Aclaraciones Sobre Cuartetos y la Actividad 3

Diferencia cuarteto vs. terceto en arrays:

En cuartetos, si hay un acceso a[i] en la parte derecha de una asignación, se genera:

(asigna_de_array, a, desplazamiento, T0)   // T0 = valor en a[i]

En tercetos no hace falta la temporal T0; el terceto siguiente apunta al resultado del anterior. La complejidad es mayor porque mover un terceto rompe las referencias.

Actividad 3 — Aclaraciones:

• El enunciado del campus pide generación de código NASM, pero ese enunciado es incorrecto (no se ha actualizado). El enunciado correcto y vigente está en la sección de documentación de la asignatura.
• No se pide generar código NASM ejecutable. Lo que se pide es el analizador semántico con comprobaciones de tipo; la generación de código es opcional y se valora con muy poca nota.
• Si se sube una segunda versión de un archivo, cambiar el nombre (añadir _v2, etc.): la plataforma conserva el primer archivo subido y el mentor solo ve ese.
• La práctica es grupal: todos los miembros deben entregar los mismos archivos fuente.

---

2. Simulacro de Examen — Gramática de Ejemplo

Gramática utilizada

S  → L @ R
L  → L , E  |  id  |  NUM
E  → E + E  |  ( E )  |  id  |  NUM
R  → R , T  |  T
T  → x E    |  y E

Axioma: S

Terminales: @, ,, +, (, ), x, y, id, NUM

Reglas adicionales: - id comienza por letra minúscula y puede contener letras mayúsculas, minúsculas o dígitos. - NUM es un entero positivo (no empieza por cero). - Gramática recursiva por la izquierda (en L y R).

Restricciones semánticas: - El número de elementos de L debe coincidir con el número de elementos de R. - La suma de todos los valores NUM que aparecen en L debe ser mayor o igual al número de símbolos presentes en R.

---

3. Bloque Léxico

3.1 Tabla de tokens y valores asociados ⚠️ EXAMEN

Lexema / Patrón	Token	¿Valor asociado?	Motivo
@	TOK_ARROBA	No	Se representa a sí mismo
,	TOK_COMA	No	Se representa a sí mismo
+	TOK_MAS	No	Se representa a sí mismo
(	TOK_PAR_IZQ	No	Se representa a sí mismo
)	TOK_PAR_DER	No	Se representa a sí mismo
x	TOK_X	No	Palabra reservada; el token la identifica completamente
y	TOK_Y	No	Palabra reservada; el token la identifica completamente
id	TOK_ID	Sí (yytext)	El semántico necesita saber qué identificador es (tabla de símbolos)
NUM	TOK_NUM	Sí (Integer.parseInt(yytext()))	El semántico necesita el valor numérico para la regla de la suma

3.2 Expresiones regulares y reglas JFlex ⚠️ EXAMEN

%%

// Definiciones regulares
MINUSCULA    = [a-z]
LETRA        = [a-zA-Z]
DIGITO       = [0-9]
DIGITO_NULO  = [1-9]
ID           = {MINUSCULA}({LETRA}|{DIGITO})*
NUM          = {DIGITO_NULO}{DIGITO}*

%%

// Espacios en blanco (descartar)
[ \t\n\r]+   { /* ignorar */ }

// Palabras reservadas — ANTES que el identificador (ambigüedad léxica)
"x"          { return new Symbol(sym.TOK_X); }
"y"          { return new Symbol(sym.TOK_Y); }

// Delimitadores y operadores
"@"          { return new Symbol(sym.TOK_ARROBA); }
","          { return new Symbol(sym.TOK_COMA); }
"+"          { return new Symbol(sym.TOK_MAS); }
"("          { return new Symbol(sym.TOK_PAR_IZQ); }
")"          { return new Symbol(sym.TOK_PAR_DER); }

// Tokens con valor asociado
{NUM}        { return new Symbol(sym.TOK_NUM, yyline, yycolumn,
                   Integer.parseInt(yytext())); }
{ID}         { return new Symbol(sym.TOK_ID, yyline, yycolumn, yytext()); }

// Error léxico — carácter no reconocido
.            { System.err.println("Error léxico (línea " + yyline + "): carácter '" + yytext() + "' no reconocido"); }

3.3 Ambigüedad léxica ⚠️ EXAMEN

Existe ambigüedad léxica entre x/y y la regla de id:

• x empieza por minúscula → podría reconocerse como identificador.
• Lo mismo para y.
• Si la regla de id apareciese antes, x e y quedarían clasificados como identificadores en lugar de como palabras reservadas.

Resolución: colocar las reglas de palabras reservadas antes de la regla de identificador. JFlex aplica la primera regla que coincida en caso de empate en longitud.

3.4 Errores léxicos

Ejemplos de entradas que producirían error léxico:

• Número con cero inicial: 042 — la regla NUM exige que empiece por [1-9].
• Carácter no definido: #, $, %, &, etc. — capturado por la regla de error (.).
• Identificador que empiece por mayúscula: MyVar — no coincide con la regla ID (empieza por minúscula).

3.5 Clase Symbol — qué devuelve

Cada Symbol es un objeto con: - Constructor sin valor: new Symbol(token) — para tokens que se representan a sí mismos. - Constructor con valor: new Symbol(token, yyline, yycolumn, valor) — para tokens cuyo valor importa.

La clase Symbol interna de JFlex/CAP ya define estos constructores. El campo value es el atributo semántico que el sintáctico recupera como $1.value, etc.

---

4. Bloque Sintáctico

4.1 Declaración de terminales y no terminales en CAP ⚠️ EXAMEN

terminal                TOK_ARROBA, TOK_COMA, TOK_MAS;
terminal                TOK_PAR_IZQ, TOK_PAR_DER;
terminal                TOK_X, TOK_Y;
terminal String         TOK_ID;       // lleva lexema (String)
terminal Integer        TOK_NUM;      // lleva valor numérico (Integer)

non terminal            S, R, T;
non terminal            L, E;         // en fase semántica, tendrán tipo Atributos

Nota: poner un tipo delante de un terminal en CAP no es para precedencias; indica que ese terminal lleva un atributo asociado de ese tipo. Solo tiene sentido si las acciones semánticas van a usar ese valor.

4.2 Símbolo inicial y producciones en CAP

start with S;

S   ::= L TOK_ARROBA R
    ;

L   ::= L TOK_COMA E
    |   TOK_ID
    |   TOK_NUM
    ;

E   ::= E TOK_MAS E
    |   TOK_PAR_IZQ E TOK_PAR_DER
    |   TOK_ID
    |   TOK_NUM
    ;

R   ::= R TOK_COMA T
    |   T
    ;

T   ::= TOK_X E
    |   TOK_Y E
    ;

4.3 Recursividad por la izquierda ⚠️ EXAMEN

Las producciones de L y R son recursivas por la izquierda: el primer símbolo de la parte derecha es el mismo no terminal del lado izquierdo.

• L → L , E: el primer símbolo a la derecha es L → recursiva por izquierda.

Esto no es un problema en analizadores LR ascendentes (como LALR(1)). Sería problemático en analizadores descendentes LL.

4.4 Cierre del estado inicial (estado 0) ⚠️ EXAMEN

Partiendo del ítem aumentado [S' → • S, $]:

Estado 0:
  [S' → • S,           $]      ← ítem inicial
  [S  → • L @ R,       $]      ← S es no terminal a la derecha del punto → cerradura
  [L  → • L , E,       @]      ← L es no terminal → cerradura; lookahead @ (por PRIMERO(@ R) = {@})
  [L  → • id,          @]
  [L  → • NUM,         @]
  [L  → • L , E,       ,]      ← segundo lookahead por PRIMERO(, E @ R)
  [L  → • id,          ,]
  [L  → • NUM,         ,]

Las producciones de E, R y T no se añaden en este estado porque ningún símbolo de las producciones del estado 0 tiene E, R ni T a la derecha del punto.

Error común: añadir todas las producciones de la gramática al estado 0. Solo se añaden las alcanzables por cerradura.

4.5 Transiciones desde el estado 0

Por símbolo	Acción
S	Transición al estado de aceptación (S' → S •)
L	Transición a nuevo estado con [S → L • @ R] y [L → L • , E]
id	Desplazamiento (shift) → estado con [L → id •]
NUM	Desplazamiento (shift) → estado con [L → NUM •]

No hay reducciones en el estado 0 (ningún ítem tiene el punto al final).

---

5. Bloque Semántico

5.1 Reglas semánticas de la gramática ⚠️ EXAMEN

Regla	Descripción
R1	El número de elementos de L debe ser igual al número de elementos de R
R2	La suma de todos los valores NUM presentes en L debe ser ≥ al número de símbolos en R

5.2 Análisis de atributos necesarios

Para R1: se necesita un atributo entero en L y en R que cuente los elementos.

L.nElem : entero (sintetizado — sube desde las hojas hacia la raíz)
R.nElem : entero (sintetizado)

Para R2: se necesitan dos atributos en L:

L.nElem  : número de elementos de L (reutilizable de R1)
L.sumNum : suma de los valores NUM que aparecen en L

La comprobación se hace en la producción de S:

S ::= L:l TOK_ARROBA R:r  {:
    if (l.nElem != r.nElem)
        System.err.println("Error semántico: número de elementos de L distinto al de R");
    if (l.sumNum < r.nElem)
        System.err.println("Error semántico: suma de NUM en L menor que número de elementos en R");
:}

5.3 Clase Atributos para esta gramática

class Atributos {
    int nElem;    // número de elementos en L o R
    int sumNum;   // suma de valores NUM en L (solo relevante para L)
}

5.4 Acciones semánticas completas ⚠️ EXAMEN

// Producciones de L
L   ::= L:l1 TOK_COMA E:e  {:
    Atributos r = new Atributos();
    r.nElem  = l1.nElem + 1;
    r.sumNum = l1.sumNum;   // E no aporta NUM de L directamente
    RESULT = r;
:}
    |   TOK_ID:i  {:
    Atributos r = new Atributos();
    r.nElem  = 1;
    r.sumNum = 0;   // SIEMPRE inicializar aunque id no tenga valor NUM
    RESULT = r;
:}
    |   TOK_NUM:n  {:
    Atributos r = new Atributos();
    r.nElem  = 1;
    r.sumNum = n;   // el valor entero del NUM (pasado desde el léxico)
    RESULT = r;
:}
    ;

// Producciones de R
R   ::= R:r1 TOK_COMA T:t  {:
    Atributos r = new Atributos();
    r.nElem  = r1.nElem + 1;
    r.sumNum = 0;   // sumNum no relevante para R, pero inicializar
    RESULT = r;
:}
    |   T:t  {:
    Atributos r = new Atributos();
    r.nElem  = 1;
    r.sumNum = 0;
    RESULT = r;
:}
    ;

Lección clave: aunque en L → id nunca habrá valor sumNum que contar, hay que inicializarlo a 0 porque el padre L → L , E leerá l1.sumNum. Un campo no inicializado produce comportamiento indefinido. ⚠️ EXAMEN

5.5 Atributos sintetizados vs. heredados

En esta gramática solo se usan atributos sintetizados (suben de hijos a padre). No se necesitan heredados porque no hay información que tenga que bajar del padre a los hijos.

Un ejemplo de cuándo se necesitarían heredados: en D → T L, el tipo declarado en T tiene que "bajar" a cada identificador de L para que sepa de qué tipo declararse.

---

6. Formato del Examen — Resumen ⚠️ EXAMEN

Parte	Contenido	Puntos
Léxico	Tokens, expresiones regulares JFlex, ambigüedades, errores léxicos	3,0
Sintáctico	Declaración en CAP, estado LR, transiciones, conflictos, recursividad	3,5
Semántico	Identificar reglas semánticas, atributos, acciones en CAP/pseudocódigo	3,5

Normas: - No se usa IDE. Las respuestas en pseudocódigo o notación CAP de memoria son válidas. - Cada parte se corrige de forma independiente (error en léxico no penaliza sintáctico). - Las respuestas deben estar justificadas: una respuesta correcta sin explicación puede no puntuar; una respuesta con error menor pero bien explicada puede puntuar. - No se pedirá construir el autómata LR completo. - Si os equivocáis en algo pero lo explicáis, la profesora puede valorarlo; si solo ponéis el resultado sin explicar, no tiene margen para hacerlo.

---

Preguntas de Autoevaluación

1. ¿Por qué hay que colocar las reglas de palabras reservadas antes de la regla de identificador en JFlex? ¿Qué problema se produce si no se hace?
2. ¿Qué tokens de la gramática del simulacro necesitan valor asociado y por qué? ¿Cuáles no lo necesitan?
3. ¿Cuál es la diferencia entre el lexema y el token? ¿Qué devuelve yytext()?
4. ¿Qué significa poner terminal Integer TOK_NUM; en CAP? ¿Y terminal TOK_ARROBA;?
5. ¿Por qué la recursividad por la izquierda no es un problema en un analizador LR?
6. ¿Qué ítems forman el estado 0 (cierre) de la gramática del simulacro? ¿Por qué no se añaden las producciones de E, R y T?
7. ¿Cuántos atributos se necesitan para verificar las dos restricciones semánticas de la gramática? Justifica por qué.
8. En la producción L → id, ¿por qué hay que inicializar sumNum = 0 aunque un identificador no sea un número?
9. ¿Qué diferencia hay entre un atributo sintetizado y uno heredado? Da un ejemplo de cuándo se necesita uno heredado.
10. ¿Qué pasa si en el examen pones el resultado correcto pero sin ninguna justificación? ¿Cómo afecta eso a la nota?