Clase 12 — Análisis Semántico: Gramáticas de Atributos y Tabla de Símbolos

Resumen Ejecutivo

Primera clase del bloque de análisis semántico. Se introduce el concepto de gramática de atributos como herramienta para añadir comprobaciones semánticas al análisis sintáctico. Se explica por qué el análisis semántico se hace de forma entrelazada con el sintáctico (no en dos fases separadas), se presentan los tipos de atributos (sintetizados y heredados) y se trabajan dos ejemplos completos: evaluación de expresiones aritméticas con tipos y procesamiento de listas de declaraciones. Al final se presenta la estructura de la tabla de símbolos.

En la segunda parte de la clase se revisan dos soluciones de la actividad entregada y se aclara un error de la sesión anterior sobre el tipo de los terminales en CAP.

Conceptos Clave

Análisis semántico: Fase del compilador que comprueba reglas que la gramática no puede expresar: compatibilidad de tipos, declaración previa de variables, inicialización, etc. ⚠️ EXAMEN
Semántica dirigida por la sintaxis: El análisis semántico se apoya en la estructura del árbol sintáctico. ⚠️ EXAMEN
Gramática de atributos: Gramática independiente del contexto extendida con un sistema de atributos (atributos semánticos y acciones semánticas asociadas a cada producción). Formalmente es una quíntupla: \(G_A = (T, N, S, P, K)\). ⚠️ EXAMEN
Atributo semántico: Par nombre-tipo asociado a un símbolo de la gramática. Ejemplos: tipo (string), valor (int), texto (string).
Acción semántica: Fragmento de código que se ejecuta al reducir por una producción. Calcula o comprueba atributos. En CAP, se escribe entre {: y :} al final de la producción.
Atributo sintetizado: El valor del padre se calcula a partir de los valores de sus hijos (flujo de información de abajo a arriba). ⚠️ EXAMEN
Atributo heredado: El valor de un nodo se hereda de su padre o de un hermano en la misma producción (flujo lateral o de arriba a abajo). ⚠️ EXAMEN
Tabla de símbolos: Estructura de datos (habitualmente una tabla hash) donde se guarda la información semántica de los identificadores: nombre, tipo, ámbito, etc. ⚠️ EXAMEN

Desarrollo del Temario

1. Qué comprueba el análisis semántico

El análisis semántico comprueba reglas que dependen del contexto, no de la estructura sintáctica. Ejemplos:

Comprobación	Descripción
Compatibilidad de tipos en operadores	`int * char` puede ser error según el lenguaje
Compatibilidad en asignaciones	El tipo de la expresión debe ser compatible con la variable
Declaración previa	Las variables deben declararse antes de usarse
Inicialización	Algunos lenguajes exigen que la variable tenga valor antes de usarse
Número de argumentos	La llamada a función debe coincidir con la signatura

La lista exacta de comprobaciones depende del lenguaje. Python, por ejemplo, no obliga a declarar el tipo de una variable; Java sí. Cada lenguaje tiene su manual de referencia que describe todas las reglas semánticas.

2. Por qué se hace de forma entrelazada con el sintáctico

Conceptualmente el semántico "recibe el árbol sintáctico completo" y lo recorre para hacer las comprobaciones. En la práctica, el CAP hace ambos análisis al mismo tiempo:

Al mismo tiempo que el sintáctico reconoce una producción y construye el árbol, ejecuta la acción semántica asociada a esa producción.

Esto hace el compilador más eficiente: en lugar de dos pasadas sobre el código, se hace una sola.

La salida teórica del sintáctico es una representación implícita del árbol (la lista de producciones aplicadas). El semántico usa esa estructura para "decorar" los nodos con información.

flowchart LR
    A[Código fuente] --> B[Análisis léxico]
    B -->|tokens| C[Análisis sintáctico + semántico]
    C -->|árbol decorado| D[Generación de código]
    E[(Tabla de símbolos)] <--> C

3. Gramática de atributos — definición formal

\[G_A = (T, N, S, P, K)\]

Donde \(K\) es el sistema de atributos: el conjunto de atributos semánticos definidos para los símbolos y las acciones semánticas asociadas a cada producción.

Comparación con la gramática independiente del contexto:

Gramática IC	Gramática de atributos
Cuádrupla \((T, N, S, P)\)	Quíntupla \((T, N, S, P, K)\)
Solo estructura sintáctica	Añade información semántica

La actividad 2 ya es una gramática de atributos: cada producción tiene una acción que imprime información. Aunque no use atributos con valor, el mecanismo es el mismo.

4. Ejemplo 1 — Expresiones aritméticas con tipos

Gramática:

E → E + E  |  E - E  |  - E  |  E * E  |  ( E )  |  C  |  R
C → constante_entera
R → constante_real

Expresión de ejemplo: 3 + (4 * 5.5)

Atributos de cada nodo: - valor: el valor numérico (relevante en calculadoras; en compiladores reales, el valor en tiempo de compilación solo es útil para constantes simples). - tipo: I (entero) o R (real).

Árbol decorado (construcción ascendente):

Paso 1: C → 3        => E.valor = 3,   E.tipo = I
Paso 2: R → 5.5      => E.valor = 5.5, E.tipo = R
Paso 3: E → 4        => E.valor = 4,   E.tipo = I
Paso 4: E → E * E    => comprobar tipos, E.valor = 22.0, E.tipo = R (int*real = real)
Paso 5: E → (E)      => arrastrar: E.valor = 22.0, E.tipo = R
Paso 6: E → E + E    => comprobar tipos, E.valor = 25.0, E.tipo = R

Por qué el valor no siempre es útil en tiempo de compilación:

En un programa real con bucles y entrada del usuario, el valor de una variable no se puede conocer en tiempo de compilación. La expresión x = x + 2 dentro de un for que depende de una variable leída por teclado no puede evaluarse estáticamente. Solo en una calculadora simple (sin funciones ni entrada dinámica) se puede ir calculando el valor.

Por tanto, en un compilador de lenguaje de propósito general, el atributo valor se incluye solo si el lenguaje requiere evaluación de expresiones constantes en compilación (p. ej., para dimensionar arrays).

Acciones semánticas en pseudo-código (CAP):

E → E:e1 + E:e2    {:
    // Comprobar compatibilidad de tipos
    if (e1.tipo == e2.tipo)
        RESULT = new Simbolo(e1.valor + e2.valor, e1.tipo);
    else
        RESULT = new Simbolo(e1.valor + e2.valor, "R");  // promoción a real
:}

E → C:c    {:
    RESULT = new Simbolo(Integer.parseInt(c.texto), "I");
:}

E → R:r    {:
    RESULT = new Simbolo(Double.parseDouble(r.texto), "R");
:}

Regla por defecto: En producciones con un solo símbolo a la derecha, el atributo del padre puede ser simplemente el del hijo (no hace falta escribir la acción explícitamente si se trata de un arrastre directo).

5. Flujo de atributos — sintetizados vs. heredados

En la declaración int var1, x, y:

T detecta que es entero → atributo tipo = entero (sintetizado hacia arriba).
T.tipo debe propagarse lateralmente a L (están al mismo nivel en la producción D → T L).
L recibe el tipo y lo propaga hacia abajo a cada identificador de la lista (heredado hacia abajo).

Atributos sintetizados: de hijos a padre. Compatibles con el análisis ascendente (LR).

Atributos heredados: de padre a hijos, o entre hermanos. Requieren un recorrido distinto o técnicas especiales (acciones semánticas intermedias en la gramática). ⚠️ EXAMEN

En CAP, las gramáticas de atributos usan principalmente atributos sintetizados. Los heredados se simulan mediante variables globales o modificaciones de la gramática.

6. Ejemplo 2 — Listas de declaraciones

Gramática:

D → T L
T → int  |  real
L → L , id  |  id

Frase de ejemplo: int var1, x, y

Proceso de decoración:

int se reduce a T → T.tipo = entero
var1 se reduce a L → pero L necesita el tipo de T (que está al mismo nivel)
La información fluye de T a L lateralmente (heredado entre hermanos de D → T L)
L propaga el tipo hacia abajo a cada identificador:
I.tipo = entero, guardar (var1, entero) en la tabla de símbolos
I.tipo = entero, guardar (x, entero) en la tabla de símbolos
I.tipo = entero, guardar (y, entero) en la tabla de símbolos

En pseudo-código (CAP):

D → T:t L:l   {:
    // Pasa el tipo de T a L (atributo heredado simulado)
    l.tipo = t.tipo;
:}

T → INT        {:  RESULT = new Simbolo("entero"); :}
T → REAL       {:  RESULT = new Simbolo("real");   :}

L → L:l COMA ID:i  {:
    i.tipo = l.tipo;
    tablaSimbolos.insertar(i.texto, i.tipo);
    RESULT = l;
:}

L → ID:i           {:
    i.tipo = /* heredado del padre */;
    tablaSimbolos.insertar(i.texto, i.tipo);
    RESULT = i;
:}

7. La tabla de símbolos

La tabla de símbolos es la estructura donde el compilador guarda información sobre cada identificador. Es imprescindible para:

Comprobar si una variable está declarada antes de usarse.
Conocer el tipo de una variable al evaluar expresiones.
Gestionar ámbitos (una variable local puede tener el mismo nombre que una global).
Generar código: saber cuánta memoria reservar para cada variable según su tipo.

Estructura típica de una entrada:

Campo	Descripción
Nombre	Cadena del identificador (`yytext`)
Tipo	`int`, `real`, `bool`, etc.
Ámbito	Local, global, parámetro de función...
Valor	Solo para constantes, si aplica
Posición de memoria	Para generación de código

Implementación recomendada: tabla hash (acceso en \(O(1)\) medio).

En CAP: la tabla de símbolos suele implementarse como una clase Java con métodos insertar(nombre, tipo) y buscar(nombre). Se instancia una sola vez y se comparte entre todas las acciones semánticas.

8. Orden de recorrido y compatibilidad con el análisis ascendente

El análisis LR es ascendente: las reducciones van de hojas a raíz. Los atributos sintetizados (de hijos a padre) son naturalmente compatibles con este recorrido.

Los atributos heredados (de padre a hijos) van en sentido contrario y generan tensión con el análisis ascendente. Soluciones:

Variables globales: guardar el tipo en una variable accesible desde cualquier acción.
Acciones semánticas intermedias: añadir producciones épsilon (A → ε) como marcadores dentro de la producción para ejecutar código en un punto intermedio.
Restructurar la gramática para evitar herencia.

Para la práctica grupal (análisis semántico) se usarán principalmente atributos sintetizados y variables globales o de la tabla de símbolos para simular los heredados.

Errores Comunes y Aclaraciones

Aclaración sobre `terminal Integer NUM;` en CAP

Poner Integer delante de un terminal no declara un terminal ficticio de precedencia. Significa que el atributo del token NUM es de tipo Integer (entero Java). Se usa cuando en las acciones semánticas se quiere acceder al valor numérico del número reconocido.

terminal Integer NUM;
// En la acción semántica:
// NUM.intValue() devuelve el valor entero

Si no se van a hacer operaciones con el valor numérico (gramática sin semántica aritmética), no hace falta declarar el tipo.

Para un terminal ficticio de precedencia (p. ej., para el menos unario):

terminal UMINUS;   // sin tipo, solo para la directiva %prec
%prec UMINUS       // mayor prioridad que los operadores binarios

Valores en tiempo de compilación vs. ejecución

El valor de una variable no puede conocerse en tiempo de compilación en general, porque depende de la entrada del usuario, de llamadas a funciones, de iteraciones, etc. Solo en calculadoras simples (sin bucles ni entrada dinámica) tiene sentido arrastrar valores durante la compilación. En un compilador real, lo que se arrastra es el tipo, no el valor.

Preguntas de Autoevaluación

¿Qué diferencia hay entre un error sintáctico y un error semántico? Pon un ejemplo de cada uno.
¿Por qué se dice que el análisis semántico está "dirigido por la sintaxis"?
¿Qué es una gramática de atributos? ¿En qué se diferencia de una gramática independiente del contexto?
¿Qué es un atributo sintetizado? ¿Y uno heredado? ¿Con qué tipo de recorrido del árbol es compatible cada uno? ⚠️ EXAMEN
En la producción D → T L, ¿qué tipo de atributo se necesita para pasar el tipo de T a L?
¿Por qué los atributos sintetizados son compatibles con el análisis LR ascendente y los heredados no?
¿Qué información suele guardarse en la tabla de símbolos? ¿Qué estructura de datos se recomienda para implementarla?
En tiempo de compilación, ¿se puede siempre calcular el valor de una variable? ¿Por qué sí o por qué no?
Dado E → E + E, ¿cuál sería la acción semántica si el lenguaje solo permite sumar valores del mismo tipo?
¿Cuándo tiene sentido declarar terminal Integer NUM; en CAP? ¿Qué implica no declarar el tipo?
¿Cómo se simula en CAP un atributo heredado que no puede expresarse directamente con atributos sintetizados?
¿Por qué es importante el manual de referencia de un lenguaje para implementar el análisis semántico?