Clase 13 — Tabla de Símbolos, Sistema de Tipos e Implementación Semántica en CAP

Resumen Ejecutivo

Clase de dos horas dividida en cuatro bloques. En el primero se profundiza en el diseño de la tabla de símbolos: tipos de identificadores, ámbitos de visibilidad, tabla hash y decisiones de cuándo insertar información (léxico vs. sintáctico). En el segundo se presenta el sistema de tipos del lenguaje: expresiones de tipo, inferencia, verificación, equivalencia estructural vs. nominal y conversión de tipos. En el tercero se aterriza en la implementación concreta en CAP: la clase Atributos, cómo declarar tipos para terminales y no terminales, y cómo se construyen las acciones semánticas para expresiones lógicas, aritméticas, comparaciones y arrays. En el cuarto se presenta el enunciado definitivo de la práctica grupal (analizador semántico de Pocket) y el formato del examen con un mini-simulacro guiado.

Conceptos Clave

Tabla de símbolos: Estructura flexible (tabla hash) donde se guarda información de todos los identificadores: constantes, variables, funciones, nombres de tipo. Se consulta y actualiza repetidamente durante el análisis semántico. ⚠️ EXAMEN
Expresión de tipo: Estructura de datos que representa el tipo de un identificador o expresión. Compuesta por un constructor (básico, array, función…) y la información adicional necesaria. ⚠️ EXAMEN
Inferencia de tipos: Determinar el tipo de una expresión a partir de sus componentes (p. ej., int + int = int).
Verificación de tipos: Comprobar que los operandos son compatibles con el operador y calcular el tipo del resultado.
Equivalencia estructural: Dos tipos son compatibles si tienen la misma estructura interna (independientemente del nombre).
Equivalencia nominal: Dos tipos son compatibles solo si tienen exactamente el mismo nombre de tipo definido.
Conversión explícita (coerción): El programador especifica la conversión ((float) x).
Conversión implícita: El compilador convierte automáticamente si el lenguaje lo permite (int → real).
Clase Atributos: Estructura Java que encapsula el estado semántico de un símbolo mientras viaja por el árbol: lexema, tipo (entero codificado), valor. ⚠️ EXAMEN

Desarrollo del Temario

1. Tabla de Símbolos — Diseño

La tabla de símbolos es la estructura central del análisis semántico. Tiene que ser flexible, porque todos los identificadores (constantes, variables, funciones, nombres de tipo) comparten la misma tabla.

Tipos de identificadores y su información asociada:

Tipo	Información mínima
Variable	Nombre, tipo, ámbito
Constante	Nombre, tipo, valor
Función	Nombre, tipo de retorno, número y tipo de parámetros
Array	Nombre, tipo base, rango (base, tamaño)
Nombre de tipo	Nombre, expresión de tipo asociada

La razón de usar una única tabla (no una por tipo de identificador) es precisamente la expresión de tipo: una misma estructura con un campo constructor que indica de qué tipo es, y campos adicionales que varían según el constructor.

1.1 Estructura de implementación recomendada

Tabla hash indexada por el lexema del identificador. Acceso \(O(1)\) medio. En Java: Hashtable<String, EntradaTabla>.

// Propuesta simplificada
class EntradaTabla {
    String lexema;
    int constructor;   // 0=variable, 1=función, 2=constante...
    ExpresionTipo tipo;
    Object valor;      // solo para constantes
}

1.2 Decisión de diseño: ¿cuándo inserta el léxico?

Opción A — El léxico inserta cada identificador que descubre: - Devuelve al sintáctico la entrada de la tabla (no solo el token). - El sintáctico rellena los campos de tipo cuando reconoce la declaración.

Opción B — El sintáctico inserta cuando reconoce la producción de declaración: - El léxico solo devuelve el lexema. - Más simple si no se necesita tabla en el léxico.

Ambas son válidas. La elección influye en la firma de Symbol y en cómo se gestiona el lexema en las acciones semánticas. ⚠️ EXAMEN

1.3 Gestión de ámbitos

Para lenguajes con funciones y bloques anidados, se usa una pila de tablas de símbolos (una tabla por ámbito). Al entrar en un bloque se apila una nueva tabla; al salir se desapila. Para buscar un identificador se recorre la pila de arriba a abajo.

flowchart TB
    G[Tabla global] --> F1[Tabla función f1]
    G --> F2[Tabla función f2]
    F1 --> B1[Tabla bloque interno]

En la práctica grupal de Pocket no hay cambios de ámbito complejos, pero el concepto es examinable.

2. Sistema de Tipos

El sistema de tipos es el conjunto de reglas semánticas y la expresión de tipo que permite representar y verificar los tipos del lenguaje.

2.1 Expresión de tipo

Una expresión de tipo tiene: - Constructor: indica la categoría del tipo (int, real, bool, array, función, puntero…). - Información adicional según el constructor:

Constructor	Info adicional
Tipo básico (`int`, `bool`)	Ninguna
Array	Tipo del índice (rango), tipo de los elementos
Puntero	Tipo al que apunta
Función	Lista de tipos de parámetros + tipo de retorno

Ejemplo: array [1..10] of real

constructor = ARRAY
rango       = [1, 10]
tipo_elem   = REAL

2.2 Inferencia de tipos

El compilador infiere el tipo de una expresión sin que el programador lo declare explícitamente. Ejemplos: - El léxico lee 3 → token CONST_ENTERA, tipo inferido = int. - El sintáctico ve E + E donde ambos son int → tipo del padre = int.

2.3 Verificación de tipos

Las comprobaciones se estructuran como if anidados. Patrón general para un operador binario:

1. ¿Son los dos operandos del mismo tipo? Si no → error "tipos incompatibles"
2. ¿Son compatibles con el operador? Si no → error "operador no aplicable a este tipo"
3. Calcular el tipo del resultado y pasarlo al padre (atributo sintetizado)

Ejemplos de verificación:

E AND E: ambos deben ser bool → resultado bool
E + E: ambos deben ser numéricos → resultado del tipo más general (int si los dos son int, real si hay un real)
E < E: ambos del mismo tipo (numérico o bool, no mezclados) → resultado bool
a[i]: a debe ser array, i debe ser int → resultado = tipo base del array

2.4 Comprobación de tipo seguro

Un lenguaje es fuertemente tipado si todas las comprobaciones de tipos se hacen en tiempo de compilación. Ejemplos: Ada, Pascal (casi totalmente). C, Java: fuertemente tipados con alguna excepción. Python, Lisp: tipado dinámico.

2.5 Equivalencia estructural vs. nominal

Estructural: compatibles si la estructura interna es idéntica.

type Vector = array[0..5] of real;
var a: array[0..5] of real;   // compatible con Vector (misma estructura)
var b: Vector;                 // también compatible

Nominal: compatibles solo si tienen el mismo nombre de tipo.

var x: Vector;
var y: array[0..5] of real;   // NO compatible con x (nombre distinto)

Pocket usa compatibilidad estructural simplificada (no hay nombres de tipo definidos por el usuario).

2.6 Conversión de tipos

Tipo	Descripción	Ejemplo
Explícita (coerción)	El programador la escribe	`(float) x` en C
Implícita	El compilador la realiza automáticamente	`int → real` en una expresión mixta

Las conversiones implícitas requieren que el generador de código emita instrucciones de conversión aunque no aparezcan explícitas en el fuente.

3. Implementación del Análisis Semántico en CAP

3.1 Clase Atributos

La clase Atributos es la estructura que viaja por el árbol durante el análisis (no confundir con las entradas de la tabla de símbolos):

class Atributos {
    String lexema;  // identificador o valor literal
    int tipo;       // 0 = entero, 1 = booleano (propuesta simplificada)
    int valor;      // para constantes enteras
}

Esta clase se declara en CAP como tipo de los terminales y no terminales:

terminal Atributos TOK_ID, TOK_CONST_ENT;
non terminal Atributos expr, decl;

3.2 Cómo pasa el léxico la información

// Constante entera
[0-9]+ {
    Atributos a = new Atributos();
    a.tipo  = 0;              // entero
    a.valor = Integer.parseInt(yytext());
    return new Symbol(sym.CONST_ENT, yyline, yycolumn, a);
}

// Identificador
[a-z][a-zA-Z0-9]* {
    Atributos a = new Atributos();
    a.lexema = yytext();
    a.tipo   = -1;            // desconocido hasta la declaración
    a.valor  = 0;             // null sería mejor
    return new Symbol(sym.ID, yyline, yycolumn, a);
}

Si el identificador es demasiado largo (error léxico), devolver Symbol(sym.ERROR, …) igualmente para no romper el sintáctico.

3.3 Acciones semánticas en CAP — Expresiones lógicas

expr ::= expr:e1 AND expr:e2  {:
    if (e1.tipo != 1 || e2.tipo != 1)
        System.err.println("Error: AND requiere operandos booleanos");
    Atributos r = new Atributos();
    r.tipo = 1;   // resultado booleano
    RESULT = r;
:}

Regla clave: si solo hay tipos int (0) y bool (1), comprobar que ambos sean 1 (bool). En un lenguaje con más tipos, comprobar primero que sean iguales, después que sean compatibles con el operador. ⚠️ EXAMEN

3.4 Acciones semánticas — Expresiones aritméticas

expr ::= expr:e1 PLUS expr:e2  {:
    if (e1.tipo != 0 || e2.tipo != 0)
        System.err.println("Error: + requiere operandos numéricos");
    Atributos r = new Atributos();
    r.tipo = e1.tipo;   // o el tipo más general si hay reales
    RESULT = r;
:}

Con tipos numéricos múltiples (int, real): 1. Comprobar si son iguales → si no, error. 2. Si son iguales y numéricos → resultado = ese tipo. 3. Si el lenguaje permite mezcla (C/Java) → resultado = tipo más general (real).

3.5 Acciones semánticas — Acceso a array `a[i]`

1. Buscar 'a' en tabla de símbolos → comprobar que su tipo es ARRAY
2. Comprobar que 'i' tiene tipo int
3. RESULT.tipo = tipo_base_del_array (p.ej. real)

En tiempo de compilación no se puede comprobar si el índice está dentro del rango (a menos que sea una constante literal). Solo se verifica el tipo del índice.

3.6 Inicialización de todos los atributos ⚠️ EXAMEN

En toda producción que reduzca a un no terminal con atributos, todos los campos deben inicializarse, aunque no se usen en esa producción. Un atributo no inicializado se comporta como una variable con valor basura.

// INCORRECTO: solo inicializa .id, deja .n sin valor
B ::= ID:i  {: Atributos r = new Atributos(); r.id = 1; RESULT = r; :}

// CORRECTO
B ::= ID:i  {: Atributos r = new Atributos(); r.id = 1; r.n = 0; RESULT = r; :}

4. Práctica Grupal — Analizador Semántico de Pocket

4.1 Qué se pide

Implementar el analizador semántico para el lenguaje Pocket, extendiendo el léxico y sintáctico de las actividades anteriores. Se añaden las producciones 7, 15, 16, 44, 48, 49 y 85 al sintáctico (necesarias para arrastrar atributos, aunque no añaden lógica sintáctica nueva).

4.2 Reglas semánticas a implementar ⚠️ EXAMEN

Regla	Descripción
Declaración única	Una variable no puede declararse dos veces en el mismo ámbito → buscar en tabla antes de insertar
Uso declarado	Toda variable debe estar declarada antes de usarse → buscar en tabla; si no existe, error
Expresiones lógicas	Solo operandos de tipo `bool` (AND, OR, NOT) → resultado `bool`
Expresiones aritméticas	Solo operandos numéricos (`int` o `real`) → resultado numérico
Expresiones de comparación	Operandos del mismo tipo (numérico o bool, no mezclados) → resultado `bool`
Asignaciones	Tipo izquierda = tipo derecha
Arrays	Solo tipo base básico (`int`, `real`, `bool`); máx. 64 elementos; índice de tipo `int`
`if` / `while`	La expresión de control debe ser de tipo `bool`
Entrada (`read`)	Solo `int` y `bool`
Salida (`write`)	`int`, `real` o `bool`

4.3 Diseño de errores semánticos

Cada error debe informar de qué, dónde (línea/columna) y por qué. Un mensaje Error semántico sin más detalle es insuficiente.

Propuesta de errores: - Error semántico (línea X): variable 'v' no declarada - Error semántico (línea X): variable 'v' ya declarada en este ámbito - Error semántico (línea X): operador AND requiere operandos booleanos - Error semántico (línea X): tipos incompatibles en asignación - Error semántico (línea X): índice de array debe ser entero

4.4 Entrega y evaluación

Todos los miembros del grupo suben los mismos archivos fuente + una hoja de control individual que evalúa la contribución de cada compañero.
Si un miembro no participa y las hojas de control lo reflejan, se le suspende individualmente.
La memoria puede tener un anexo individual si un miembro discrepa del contenido aprobado por el grupo.
Nota: compilación es requisito para la nota máxima, pero no compilar no implica automáticamente 0 si hay trabajo real.
Archivos de prueba disponibles en documentación de la asignatura (no usar ptrTablaSimbolos.java directamente en el proyecto; es solo un ejemplo de uso).

5. Formato del Examen y Mini-Simulacro

5.1 Estructura del examen ⚠️ EXAMEN

Pregunta	Tema	Puntos
1	Análisis léxico (JFlex)	3,0
2	Análisis sintáctico (CAP/LR)	3,5
3	Análisis semántico	3,5

Normas: - No se usan JFlex ni CAP en el examen. Se responde en pseudocódigo o en notación CAP de memoria. - Cada pregunta se corrige de forma independiente: un error en léxico no arrastra nota a sintáctico. - No se penalizan errores de sintaxis CAP leves si el concepto está claro.

5.2 Tipos de preguntas por bloque

Léxico: - Criterios de JFlex para seleccionar regla (regla más larga primero, luego orden de aparición). - Efecto del orden de las reglas (palabras reservadas antes que identificadores). - Qué retornar: Symbol(token) vs. Symbol(token, atributos). - Errores habituales: expresiones regulares incorrectas, valores innecesarios en todas las reglas.

Sintáctico: - Qué tokens necesitan valor asociado y de qué tipo. - Simulación de pila LR (desplazamiento / reducción / aceptar). - Construcción de un ítem LR y su cierre. - Conjuntos PRIMERO y SIGUIENTE. - Detección de conflictos.

Semántico: - Identificar las normas semánticas de un fragmento de lenguaje. - Qué atributos son necesarios y por qué (justificar cada uno). - Atributos sintetizados vs. heredados (cuáles se usan y dónde). - Acciones semánticas en pseudocódigo o CAP. - Comprobaciones de compatibilidad de tipos. - Cómo interviene la tabla de símbolos.

5.3 Mini-simulacro guiado

Gramática:

A → ( A )  |  ( A ) A  |  ε
B → id B   |  N B     |  id  |  N

Reglas léxicas: - Los identificadores empiezan por letra minúscula y pueden contener letras y dígitos. - N es una constante entera positiva.

Reglas semánticas: 1. El número de parejas de paréntesis debe ser igual al número de elementos de B. 2. El número de N debe ser menor o igual al número de identificadores.

Análisis de atributos:

Para la regla 1, se necesita un único atributo par (entero) que cuenta:

// Caso base
A → ( )       {: RESULT.par = 1; :}

// Recursivo
A → ( A1 ) A2 {: RESULT.par = A1.par + A2.par + 1; :}

// Al llegar al padre de A y B:
if (A.par != B.par) error("parejas ≠ elementos");

Para la regla 2, se necesitan dos atributos en B: numN y numID, ambos inicializados en todas las producciones:

B → id B1  {: RESULT.numID = B1.numID + 1; RESULT.numN = B1.numN; :}
B → N  B1  {: RESULT.numN  = B1.numN  + 1; RESULT.numID = B1.numID; :}
B → id     {: RESULT.numID = 1; RESULT.numN = 0; :}   // ← RESULT.numN = 0 obligatorio
B → N      {: RESULT.numN  = 1; RESULT.numID = 0; :}  // ← RESULT.numID = 0 obligatorio

// Comprobación final
if (B.numN > B.numID) error("número de N supera al de identificadores");

Lección clave: aunque en B → id nunca habrá N, hay que inicializar numN = 0 porque el padre va a leer ese atributo en la comprobación.

5.4 Recursividad izquierda vs. derecha en CAP

En la práctica, la gramática de Pocket usa recursividad izquierda para listas. La recursividad por la derecha acumula todos los nodos en la pila LR antes de empezar a reducir, lo que puede provocar desbordamiento para programas largos.

Recomendación para la práctica grupal: usar recursividad por la izquierda en las producciones de listas. En el examen, la profesora puede presentar gramáticas por la derecha porque son más fáciles de leer en un enunciado corto; ambas formas son válidas conceptualmente. ⚠️ EXAMEN

Preguntas de Autoevaluación

¿Por qué la tabla de símbolos tiene que ser una única tabla flexible en lugar de una tabla por tipo de identificador?
¿Qué diferencia hay entre la clase Atributos (que viaja por el árbol) y una entrada de la tabla de símbolos?
En la producción D → T L, ¿qué tipo de atributo fluye de T a L? ¿Cómo se simula en CAP?
¿Cuándo tiene sentido que el léxico inserte identificadores en la tabla de símbolos? ¿Y cuándo es mejor que lo haga el sintáctico?
Explica la diferencia entre equivalencia estructural y nominal con un ejemplo en Pascal.
¿Por qué la conversión implícita de tipos también requiere código en el generador de código?
En el acceso a array a[i], ¿qué comprobaciones semánticas se realizan? ¿Cuál nunca puede hacerse en tiempo de compilación en general?
¿Por qué hay que inicializar todos los atributos en todas las producciones, aunque en esa producción no se utilicen?
Dado el lenguaje Pocket, ¿qué tipo debe tener la expresión de control de un if? ¿Dónde se comprueba esto?
En el mini-simulacro, ¿por qué no es válido usar una única variable global para contar las N y los id en lugar de dos atributos?
Para un operador + en un lenguaje con int y real, ¿en qué orden harías las comprobaciones de tipo y por qué?
¿Qué ventaja tiene la recursividad por la izquierda frente a la derecha en un analizador LR para programas largos?