Clase 15 — Backpatching de Bucles y Entornos de Ejecución

Resumen Ejecutivo

Sesión de dos bloques:

Repaso y ampliación de semántica dinámica / backpatching (continuación de la clase 14). Resolución detallada de dudas sobre el if-then-else, y traducción completa del while y del break. Se introduce la idea de que la estructura de atributos debe crecer con campos según lo que necesite cada producción (tipo, lexema, temporal, listas verdad/falso/siguiente/break). Aclaración importante: este bloque NO entra en el examen, pero ayuda a entender cómo funciona el compilador.
Nuevo tema — Entornos de ejecución. Qué son, de qué se responsabilizan, el árbol de activación, la pila de ejecución, los registros de activación y la organización de la memoria (código, datos estáticos, montículo y pila). Tema recién introducido, se verá en profundidad en la última clase.

Quedan dos sesiones: un taller de 1h30 (repaso de dudas + corrección de la actividad 3) y la clase final de 2h (clase + refuerzo). La parte de generación de código intermedio y semántica dinámica no cae en el examen.

Conceptos Clave

Lista de verdad / falso: atributos de toda expresión lógica (relacional o booleana). Las expresiones aritméticas NO tienen estas listas; tienen cuádrupla/temporal. ⚠️
Lista siguiente: atributo de los bloques de sentencias (no de las expresiones). Agrupa saltos que deben ir a la instrucción siguiente del bloque.
Atributo break: lista separada de la de siguiente, necesaria porque un break salta fuera del bucle, mientras que un salto de siguiente (p.ej. el goto que cierra un if anidado) solo vuelve a evaluar la condición del bucle. ⚠️ (distinción conceptual clave)
Clase Atributos: estructura con todos los campos posibles (lexema, desplazamiento, temporal, dirección, listas verdad/falso/siguiente/break) inicializados por defecto en el constructor. El tipo de la expresión decide qué campos están rellenos.
Entorno de ejecución: conjunto de estructuras y mecanismos que permiten ejecutar correctamente un programa. ⚠️ EXAMEN (concepto)
Árbol de activación: representación conceptual del flujo de llamadas; cada nodo es una activación de procedimiento/función.
Registro de activación: bloque en la pila con toda la información de una invocación (variables locales, parámetros, retorno, temporales).
Pila de ejecución: estructura LIFO que en la cima tiene siempre la activación en ejecución.

Desarrollo del Temario

1. Repaso del `if-then-else` (backpatching)

Producción: if E then M S N M S (la E es una expresión lógica).

Toda expresión lógica tiene dos listas de saltos sin rellenar: verdad y falso. No conocemos el destino al evaluarla porque el árbol aún no ha procesado las sentencias.
M → ε captura la posición de la siguiente cuádrupla (marca el destino de un salto).
N → ε genera un goto incondicional (lista siguiente) para que, tras ejecutar el then, no caiga en el else.

Acciones:

backpatch(E.verdad, M1.cuadrupla)   // si la condición es verdad → entrar al then
backpatch(E.falso,  M2.cuadrupla)   // si es falsa → entrar al else

Por qué el goto de N: las sentencias del then y las del else se generan consecutivamente según el orden de lectura de la gramática. Sin el goto intermedio, tras ejecutar el then el flujo continuaría directamente por el else.

Matiz de la profesora: en el if simple (sin else), la lista verdad se rellena con el inicio del then y la lista falso va directamente al siguiente. En el if-then-else, falso va al else.

2. Asignación de booleanos

La asignación de una expresión booleana no genera variables temporales. Como en tiempo de compilación no se sabe si la condición será verdadera o falsa, se generan dos asignaciones y un salto:

// x := (expresión booleana)
        if<  ...        // saltos de la lista verdad
        goto ...        // saltos de la lista falso
(verdad) := 1, _, x     // si es verdad, asigna 1
        goto fuera
(falso)  := 0, _, x     // si es falso, asigna 0
(fuera)  ...

Regla práctica: al reducir la asignación se comprueba el tipo de la expresión. - Tipo aritmético → se usa la temporal/cuádrupla y se genera (:=, temp, _, lexema). - Tipo booleano → cuádrupla = null, se usan las listas verdad/falso y se generan las dos asignaciones de 1/0.

⚠️ Error frecuente: crear una variable temporal "por si acaso" para una expresión booleana y dejarla sin usar. No se debe; el tipo determina qué hacer.

3. El `while` (traducción completa)

Diagrama de flujo:

flowchart TB
    M2["M2 → inicio de la condición"]
    E["Expresión (verdad/falso)"]
    M1["M1 → inicio del cuerpo S"]
    S["Cuerpo del while (S)\nsiguiente / break"]
    G["goto M2 (re-evaluar condición)"]
    OUT["Siguiente instrucción\n(salida del while)"]

    M2 --> E
    E -->|verdad| M1 --> S --> G --> M2
    E -->|falso| OUT
    S -.break.-> OUT

Producción: while M E do M S

Acciones al reducir:

genera goto M2.cuadrupla            // al final del cuerpo, volver a evaluar la condición
backpatch(E.verdad, M1.cuadrupla)   // condición verdad → entrar al cuerpo
S.siguiente += break                // los break del cuerpo se fusionan en siguiente
backpatch(S.siguiente, M2.cuadrupla)// los goto internos vuelven a la condición
while.siguiente = merge(E.falso, break)  // condición falsa o break → salir del bucle

Puntos clave: - Se marca el inicio de la condición (M2) porque el goto del final del cuerpo salta ahí. - Se marca el inicio del cuerpo (M1) porque la lista verdad salta ahí.

4. El `break` y por qué necesita su propio atributo

Caso a analizar: un if anidado dentro del cuerpo de un while.

Salto	Origen	Destino
`goto` que cierra el `then` del `if` (lista `siguiente`)	sale del ámbito del `if`	vuelve a evaluar la condición del `while`
`break`	sale del ámbito del `while`	fuera del `while` (a la instrucción siguiente)

Ambos "salen de algo", pero a sitios distintos. Por eso se necesita un atributo break independiente del siguiente:

break: B → BREAK  {: genera goto incondicional; B.break = makeList(cuadrupla) :}

El break va al mismo destino que la lista falso del while, pero no se puede mezclar con el siguiente general porque su semántica (salir del bucle) es distinta. Los nombres de los atributos son la única información que tenemos para decidir el destino de cada salto.

5. Encadenamiento de instrucciones y fin de bloque

L → L ; M S: lista de instrucciones. Cada vez que se va a generar una instrucción se marca (puede ser destino de un siguiente previo). Si la instrucción anterior tiene siguiente sin rellenar, se rellena con el inicio de la actual.
Varias sentencias secuenciales (p.ej. sumas) → listas siguiente vacías, no se rellena nada.
Fin del bloque principal: se genera un return (para la ejecución) y todos los siguiente pendientes se rellenan hacia ese return.

Idea de fondo: el código máquina ejecuta las instrucciones en el orden en que están escritas, salvo los saltos. El compilador es el responsable de que un for/while/if se ejecute como el programador espera; un error en la semántica dinámica cambia el lenguaje.

6. NUEVO TEMA — Entornos de Ejecución

6.1 ¿Qué es y de qué se responsabiliza?

El entorno de ejecución son todas las estructuras y mecanismos que permiten ejecutar correctamente un programa. Conecta el código intermedio/objeto con lo que realmente pasa en memoria. Una llamada a función en código intermedio (call, evaluación de parámetros) tiene que traducirse a algo concreto: eso es lo que estudia este tema.

Responsabilidades: - Gestión de la memoria. - Paso de parámetros. - Llamadas a procedimientos/funciones. - Almacenamiento de variables locales y globales. - Gestión de retornos. - Gestión de valores y variables temporales.

Conclusión importante: toda variable y toda sentencia tiene un lugar en la memoria.

En un lenguaje interpretado, todo el backend (incluido el entorno de ejecución) lo realiza una máquina virtual (modelo de Java). Pero el compilador sigue siendo responsable de generar el código intermedio correcto: si falta una instrucción (p.ej. marcar una llamada o la evaluación de un parámetro), la máquina virtual no podrá ejecutarlo bien.

6.2 Árbol de activación

Representa el flujo de ejecución de llamadas. Cada nodo es una activación; el primero es el main.

flowchart TB
    main["main"]
    A["A"]
    C["C"]
    B["B"]
    main --> A
    A --> C
    main --> B

Si el nodo A es padre de B, significa que A llamó a B; cuando B termina, el control vuelve a A.
Mientras A sigue activa, se ejecuta C: sus variables coexisten en memoria, aunque no sean mutuamente alcanzables (no es cuestión de ámbito, sino de que no se pueden machacar las variables de A o no se podría volver de la llamada).
Soporta llamadas anidadas y recursividad.

6.3 Pila de ejecución y registros de activación

Al pasar del árbol a la pila de ejecución:

En la cima está siempre la activación que se está ejecutando.
Cada llamada apila un registro de activación (variables locales, parámetros, retorno, temporales).
Cuando una función termina, su registro se desapila → esa zona de memoria queda inaccesible y reutilizable por la siguiente función.
El control "vuelve" cambiando el foco (punteros) del procesador de un registro a otro.

flowchart TB
    subgraph Pila
        direction TB
        c["RA de C (cima, ejecutándose)"]
        a["RA de A"]
        m["RA de main"]
    end

6.4 Organización de la memoria

flowchart TB
    cod["Código objeto (instrucciones)"]
    dat["Datos estáticos y globales"]
    heap["Montículo (heap) ↓ crece"]
    free["...memoria libre..."]
    stack["Pila (stack) ↑ crece"]
    cod --- dat --- heap --- free --- stack

Zona	Contenido
Código	El código objeto; el procesador lee de aquí las instrucciones
Datos estáticos/globales	Variables globales y estáticas
Montículo (heap)	Memoria dinámica: objetos, punteros, `new`…
Pila (stack)	Datos no dinámicos: registros de activación

El montículo y la pila crecen en sentidos contrarios para aprovechar al máximo el espacio libre intermedio (y pueden llegar a chocar → desbordamiento).

Hay lenguajes que solo usan pila (sin montículo), como variantes de BASIC/COBOL sin memoria dinámica. Y lenguajes que solo usan montículo (todo asignación dinámica), más difíciles de gestionar por la fragmentación y la liberación de huecos.

Preguntas de Autoevaluación

¿Por qué las expresiones aritméticas no tienen listas verdad/falso y las lógicas sí?
En el while, ¿por qué se marca con M tanto el inicio de la condición como el del cuerpo? ¿A dónde salta cada lista?
¿Por qué un break necesita un atributo propio y no puede usar la lista siguiente? Pon un ejemplo con un if dentro de un while.
Traduce x := (a < b) siendo x booleano. ¿Cuántas cuádruplas genera y por qué no usa temporal?
¿Qué es un registro de activación y qué información contiene?
Explica el árbol de activación de un main que llama a A (que llama a C) y luego a B. ¿Qué variables coexisten en memoria?
¿Por qué la pila y el montículo crecen en sentidos contrarios?
¿Qué zona de memoria usa la asignación dinámica (new, punteros)? ¿Y los registros de activación?
En un lenguaje interpretado, ¿quién asume el entorno de ejecución? ¿Sigue siendo necesario que el compilador genere bien el código intermedio?
¿De qué se responsabiliza el entorno de ejecución? Enumera al menos cuatro funciones.