Clase 14 — Generación de Código Intermedio: Cuartetos, Arrays y Semántica Dinámica

Resumen Ejecutivo

Sesión de taller (~2h con descanso). Tres bloques principales:

Introducción al código intermedio: Por qué existe una representación intermedia en el compilador, sus ventajas (independencia de máquina, optimización, portabilidad, simplificación del backend). Tipos de representación: cuartetos y tercetos.
Traducción dirigida por la sintaxis: Cómo se amplían las acciones semánticas para generar cuartetos. Ejemplos con expresiones aritméticas simples y acceso a arrays (tanto lectura como escritura).
Semántica dinámica y backpatching: Atributos de listas verdadero/falso/siguiente para expresiones booleanas. Técnica del backpatching. Diagramas del flujo de ejecución para E and M E y para if-then-else. Aclaración explícita: este bloque no entra en el examen.

Al final se retoma el simulacro de examen colgado en documentación (léxico, sintáctico, semántico) que se verá en la clase siguiente.

Conceptos Clave

Código intermedio: Representación independiente de la máquina, situada entre el análisis semántico y la generación de código final. ⚠️ EXAMEN
Código de tres direcciones: Cada instrucción referencia como máximo a tres posiciones (dos operandos y un resultado).
Cuarteto (cuádrupla): (operador, operando1, operando2, resultado). Genera variables temporales automáticamente. ⚠️ EXAMEN
Terceto (tripleta): (operador, operando1, operando2). El resultado es el propio terceto; se usa una referencia al terceto anterior en lugar de una temporal.
Variable temporal: Variable generada automáticamente por el compilador (T0, T1…) para guardar resultados intermedios. No aparece en el fuente.
Backpatching: Técnica que permite generar saltos sin conocer aún su destino, y rellenarlos en retroceso cuando el destino se conoce. ⚠️ EXAMEN (concepto, no implementación)
Marcadores M y N: Producciones epsilon insertadas en la gramática para capturar la posición de los cuartetos en el momento de la reducción.
Lista de verdadero / falso / siguiente: Atributos que agrupan cuartetos de salto sin rellenar, para expresiones booleanas y flujo de control.

Desarrollo del Temario

1. Posición del Código Intermedio en el Compilador

El compilador se divide en dos grandes partes:

flowchart LR
    src[Código fuente] --> lex[Léxico]
    lex --> sint[Sintáctico]
    sint --> sem[Semántico]
    sem --> ci[Código Intermedio]
    ci --> opt[Optimización]
    opt --> cobj[Código objeto/máquina]

    style ci fill:#f5a623,color:#000
    style opt fill:#f5a623,color:#000
    style cobj fill:#f5a623,color:#000

El frontend (léxico + sintáctico + semántico) es compartido por compiladores e intérpretes. El backend (síntesis) empieza con la generación de código intermedio.

Por qué existe el código intermedio:

Motivo	Explicación
Independencia de máquina	No se sabe sobre qué hardware se va a ejecutar; se trabaja sin registros ni instrucciones concretas
Optimización	A nivel intermedio hay todavía información contextual (ámbitos, tipos) que facilita la optimización; la profesora consiguió ~35% de ahorro en memoria y ~25% en tiempo optimizando bytecode Java en su tesis
Portabilidad	El mismo código intermedio funciona en distintas plataformas si cada una tiene su backend (como la JVM de Java)
Simplificación del backend	El código intermedio ya está diseñado para traducirse fácilmente a código máquina

Ejemplo real — Java: - El compilador de Java traduce el fuente a bytecode (código intermedio propio de Java). - La JVM (máquina virtual) instalada en cada plataforma traduce el bytecode al código máquina nativo. - Esto hace que Java no sea ni puramente compilado ni puramente interpretado.

2. Código de Tres Direcciones

Toda instrucción de alto nivel se descompone en instrucciones con máximo tres referencias a variables (dos operandos + un resultado).

2.1 Cuartetos

Forma: (operador, operando1, operando2, resultado)

Ejemplo: traducir x := a + b + 3

(+,  a,  b,  T0)   ← T0 = a + b
(+,  T0, 3,  T1)   ← T1 = T0 + 3
(:=, T1, _,  x )   ← x  = T1

Las variables T0, T1 son temporales, generadas automáticamente.
En cada instrucción binaria se genera una nueva temporal aunque luego el optimizador la elimine.
La asignación solo usa dos direcciones (origen y destino); el segundo operando queda vacío.

Ventajas: explícitas, fáciles de generar y de optimizar. Desventaja: requieren temporales.

2.2 Tercetos

Forma: (operador, operando1, operando2) — el resultado es el propio terceto (referenciado por número).

Mismo ejemplo:

0: (+, a, b)
1: (+, (0), 3)    ← (0) = referencia al resultado del terceto 0
2: (:=, (1), x)

No se usan temporales; se arrastra la referencia al terceto anterior.
Más compacto pero más difícil de optimizar (mover un terceto implica actualizar todas las referencias).

En el curso se trabaja exclusivamente con cuartetos.

2.3 Conjunto mínimo de instrucciones del código de tres direcciones

Categoría	Instrucciones
Operaciones binarias	`+`, `-`, `*`, `/`, `and`, `or`, …
Operaciones unarias	`-` (negación aritmética), `not` (negación lógica)
Asignación	`(:=, origen, _, destino)`
Salto incondicional	`(goto, _, _, etiqueta)`
Salto condicional	`(if<, op1, op2, etiqueta)`, `(if>, …)`, `(if=, …)`
Llamada a función	Cuartetos de evaluación de parámetros + `(call, función, n_params, _)`
Retorno	`(return, valor, _, _)` o `(return, _, _, _)`
Acceso a array (lectura)	`(asigna_de_array, base, desplazamiento, temp)`
Acceso a array (escritura)	`(asigna_a_array, valor, base, desplazamiento)`

3. Traducción Dirigida por la Sintaxis — Expresiones Aritméticas

La traducción usa los mismos atributos semánticos del análisis semántico, añadiendo la generación de cuartetos en las acciones. El atributo central es el lexema, que identifica la variable o temporal que contiene el resultado de una subexpresión.

3.1 Notación de acciones semánticas

$$    → atributo del padre (resultado que se pasa hacia arriba)
$1    → atributo del primer símbolo de la parte derecha
$3    → atributo del tercer símbolo
$1.lex, $3.lex → acceso al campo lexema

3.2 Estructura de la clase Atributos (simplificada para generación de código)

class Atributos {
    String lexema;      // nombre de la variable o temporal que guarda el valor
    // (en un compilador real: también tipo, desplazamiento, etc.)
}

3.3 Producciones y acciones para expresiones aritméticas

// Variable auxiliar global
static int numT = 0;
static ListaCuartetos LC = new ListaCuartetos();

// Genera un nuevo nombre de temporal: T0, T1, T2...
String nuevaTemporal() { return "T" + numT++; }

// Producciones
E ::= LITERAL:l  {: RESULT = new Atributos(l.lex); :}

E ::= NUM:n      {: RESULT = new Atributos(n.lex); :}

E ::= E:e1 MAS E:e2  {:
    String temp = nuevaTemporal();
    LC.generar("+", e1.lex, e2.lex, temp);
    RESULT = new Atributos(temp);
:}

E ::= LPAREN E:e RPAREN  {:
    RESULT = e;   // sin generación de código nueva
:}

Tras procesar a + b + 3 se genera en LC:

0: (+, a, b, T0)
1: (+, T0, 3, T1)
2: (:=, T1, _, x)

Por qué se genera T1 aunque parezca redundante: en la traducción genérica no se sabe cuántos operandos tiene la expresión padre; cada operación binaria genera su propia temporal. El optimizador elimina las que no son necesarias en una fase posterior.

4. Acceso a Arrays

Un array en memoria es un bloque contiguo. Para acceder al elemento a[i] hay que calcular la dirección:

\[\text{dirección} = \text{base}(a) + (i - \text{límite\_inferior}) \times \text{tamaño\_elemento}\]

El desplazamiento es \((i - \text{límite\_inferior}) \times \text{tamaño\_elemento}\).

4.1 Atributos del no terminal `I` (lado izquierdo de asignación)

class AtributosI {
    String lexema;        // nombre del identificador
    String desplazamiento; // null si no es array; valor si es elemento de array
}

Si I → id: lexema = id.lex, desplazamiento = null
Si I → id[E]: lexema = id.lex, desplazamiento = E.lex (ya calculado como cuarteto)

4.2 Lectura de array (array en la parte derecha de asignación)

Cuando el no terminal I aparece en la parte derecha de una asignación, se transforma a expresión E:

// I aparece en la derecha → hay que coger el valor
E ::= I:i  {:
    if (i.desplazamiento == null) {
        // Identificador simple: pasar el lexema directamente
        RESULT = new Atributos(i.lexema);
    } else {
        // Elemento de array: generar cuarteto de lectura
        String temp = nuevaTemporal();
        LC.generar("asigna_de_array", i.lexema, i.desplazamiento, temp);
        RESULT = new Atributos(temp);
    }
:}

4.3 Escritura en array (array en la parte izquierda de asignación)

Cuando I está en la izquierda (I := E):

sentencia ::= I:i DOS_PUNTOS_IGUAL E:e  {:
    if (i.desplazamiento == null) {
        // Variable simple
        LC.generar(":=", e.lexema, "_", i.lexema);
    } else {
        // Elemento de array: generar cuarteto de escritura
        LC.generar("asigna_a_array", e.lexema, i.lexema, i.desplazamiento);
    }
:}

Diferencia clave: - asigna_de_array: lee el valor en base + desplazamiento y lo guarda en una temporal. - asigna_a_array: escribe un valor en la dirección base + desplazamiento.

5. Semántica Dinámica y Backpatching (no entra en examen)

La profesora indica explícitamente que este bloque no cae en el examen porque es muy complejo. Se explica para entender cómo funciona realmente un compilador.

5.1 El problema

Las estructuras de control (if, while, for) no existen como tal en el código intermedio. Se traducen a saltos condicionales e incondicionales. El problema: cuando se genera un salto, a menudo no se conoce todavía el destino.

// if (E) then S1 else S2
// Al generar los saltos de E, no se sabe aún
// a qué cuarteto apunta el inicio de S1 ni de S2

5.2 Atributos de listas para expresiones booleanas

Cada expresión booleana E lleva tres atributos de lista:

Atributo	Contenido
`verdad`	Lista de cuartetos de salto condicional sin rellenar que deben saltar cuando la expresión es verdadera
`falso`	Lista de cuartetos de salto (normalmente `goto`) sin rellenar que deben saltar cuando la expresión es falsa
`siguiente`	Lista de cuartetos que deben saltar a la instrucción siguiente a la sentencia actual (para enlazar el flujo de ejecución)

5.3 Backpatching

La técnica consiste en: 1. Generar los saltos sin destino (campo de etiqueta vacío) y guardar sus posiciones en las listas. 2. Cuando se descubre el destino (al reducir la producción completa), recorrer la lista y rellenar todos los cuartetos con la misma etiqueta.

backpatch(lista, etiqueta):
    para cada cuarteto i en lista:
        LC[i].destino = etiqueta

5.4 Marcadores M y N

Para capturar la posición de un cuarteto en el momento exacto en que se va a necesitar como destino de salto, se insertan marcadores en la gramática:

M → ε  {: RESULT.cuarteto = LC.siguiente(); :}
     // Genera un cuarteto vacío y guarda su número

N → ε  {: 
    String temp = nuevaTemporal();
    LC.generar("goto", _, _, _);  // goto sin destino
    RESULT.siguiente = makeList(LC.posicion());
:}

5.5 Diagrama de E and M E

flowchart TB
    E1["E1\nverdad = {...}\nfalso = {...}"]
    M["M\ncuarteto = k"]
    E2["E2\nverdad = {...}\nfalso = {...}"]
    EAnd["E1 and M E2\nverdad = E2.verdad\nfalso = merge(E1.falso, E2.falso)"]

    E1 --> M
    M --> E2
    E2 --> EAnd

Acción semántica:

backpatch(E1.verdad, M.cuarteto)   // si E1 es verdad, evaluar E2
E.verdad  = E2.verdad
E.falso   = merge(E1.falso, E2.falso)

5.6 Diagrama de if-then-else

flowchart TB
    E["Expresión\nverdad/falso"]
    M1["M1 → primer cuarteto del then"]
    S1["S1 (then)\nsiguiente = {...}"]
    N["N → goto sin destino"]
    M2["M2 → primer cuarteto del else"]
    S2["S2 (else)\nsiguiente = {...}"]

    E --> M1 --> S1 --> N --> M2 --> S2