Compiladores

La estructura de un compilador y un traductor simple

Un compilador lee un programa en un lenguaje fuente y escribe un programa equivalente en un lenguaje destino. El programa nuevo se ejecuta después, solo. Un intérprete no escribe un programa nuevo. Lee tu programa y hace lo que dice, en el momento, usando la entrada que da el usuario.

Las fases

El compilador es una cadena de fases. Cada fase recibe lo que produjo la anterior. La primera mitad, llamada front end, entiende el programa fuente. La segunda mitad, el back end, escribe el programa para la máquina destino.

caracteres
    |  análisis léxico
    v
 tokens
    |  análisis sintáctico
    v
 árbol sintáctico
    |  análisis semántico
    v
 árbol verificado
    |  generación de código intermedio
    v
 código intermedio   <-- aquí termina el front end
    |  optimización, generación de código
    v
 código destino      <-- back end

Un token es un pedacito del texto con una etiqueta. Normalmente es un par: el nombre del token (por ejemplo id) y un atributo (por ejemplo un puntero a la entrada de ese nombre en la tabla de símbolos). La fase léxica es la que lee el flujo de caracteres, los agrupa en pedazos y entrega los tokens a la fase siguiente.

La tabla de símbolos es la guía telefónica del compilador. Para cada nombre del programa (una variable, una función, un tipo) guarda un registro con los atributos de ese nombre: el tipo, el ámbito, dónde se guarda y, para las funciones, el número y los tipos de los parámetros. Las fases de análisis la llenan y todas las fases, hasta la generación de código, la consultan. Cuando el lenguaje tiene bloques anidados, suele haber una tabla por ámbito, y cada tabla se encadena con la tabla del bloque que la rodea.

Por qué el front end y el back end están separados

El front end depende del lenguaje fuente. El back end depende de la máquina destino. Los dos solo se encuentran en la representación intermedia. Así, con m lenguajes y n máquinas escribes m + n componentes y obtienes m × n compiladores.

Por eso sistemas como LLVM y GCC atienden muchos lenguajes y muchas arquitecturas.

Del texto al programa en ejecución

1. El preprocesador expande macros e incluye otros archivos.
2. El compilador genera código ensamblador.
3. El ensamblador (assembler) convierte el ensamblador en código de máquina reubicable.
4. El enlazador (linker) une los archivos objeto y las bibliotecas y resuelve las direcciones de lo definido en otro lugar.
5. El cargador (loader) pone el ejecutable en la memoria.

Ámbito y parámetros

El ámbito (scope) de un nombre dice dónde se puede usar ese nombre. En el ámbito estático (también llamado léxico), un uso de un nombre se refiere a la declaración del bloque que lo rodea en el texto del programa. El compilador puede decidirlo antes de ejecutar. En el ámbito dinámico, se refiere a la declaración más reciente todavía activa en la pila de llamadas, algo que solo se sabe durante la ejecución.

var x = 1;
function show() { print(x); }
function test() { var x = 2; show(); }
test();

Los parámetros se pueden pasar de dos formas principales. En el paso por valor, el parámetro es una variable nueva que recibe una copia del argumento, así que cambiarlo no cambia la variable de quien llamó. En el paso por referencia, el parámetro recibe la dirección del argumento y se convierte en otro nombre para la misma memoria. Si dos parámetros apuntan al mismo lugar, son alias: escribir por uno cambia lo que lee el otro.

void f(int a, int b) { a = a + 10; b = b * 2; }
int x = 1;
f(x, x);
print(x);

Un traductor diminuto: de infija a posfija

En la notación posfija el operador va después de los operandos. La traducción de E1 op E2 es la traducción de E1, luego la de E2, luego el operador. Los paréntesis desaparecen, porque la posición del operador ya dice a qué operandos se aplica. Un esquema de traducción imprime el operador al final de cada producción, y el resultado es exactamente el programa de una máquina de pila.

Análisis léxico: regex, AFN y AFD

Cuando lees 'el gato duerme', no miras letra por letra. Ves palabras. El analizador léxico (o lexer) hace lo mismo con un programa: convierte el flujo de caracteres en un flujo de tokens como id, num e if. También tira los espacios en blanco y los comentarios. Así la fase siguiente trabaja con palabras y no con letras, y el lexer puede usar autómatas finitos, que son muy rápidos.

Patrón, lexema y token

• El patrón es la regla que dice cómo son las cadenas de una categoría.
• El lexema es una cadena real del programa que coincide con un patrón, por ejemplo total o 42.
• El token es lo que el lexer entrega al parser: el nombre de la categoría más un atributo opcional.

Entonces total y sum son dos lexemas distintos del mismo token id.

Expresiones regulares

Una expresión regular (regex) es una forma corta de describir un conjunto de cadenas. Usa tres operaciones: concatenación (una cosa después de otra), alternancia | (esto o aquello) y la clausura de Kleene * (cero o más repeticiones). Precedencia: el asterisco liga primero, luego la concatenación, y el | al final. Una definición regular le da un nombre a una expresión para que la reutilices.

letter = [A-Za-z]
digit  = [0-9]
id     = letter (letter | digit)*

La expresión de arriba dice: un identificador empieza con una letra y sigue con cualquier cantidad de letras o dígitos.

¿Qué token gana? La coincidencia más larga

La regla de la coincidencia más larga (maximal munch) dice que el lexer debe tomar el prefijo más largo de la entrada que coincida con algún patrón. Solo cuando dos patrones coinciden con el mismo lexema el orden de las reglas desempata. Así if se vuelve palabra reservada y no identificador: su regla va antes que id. Juntas, las dos reglas dan una única forma de dividir la entrada.

Un lexer implementado con un AFD lee mientras haya transición. Recuerda la posición y la regla del último estado de aceptación que visitó. Cuando se atasca, retrocede el puntero de la entrada hasta esa posición, emite el token guardado y vuelve a leer los caracteres de más como parte de los tokens siguientes.

Leer la entrada rápido

Pedirle un carácter a la vez al sistema operativo sería muy lento. Por eso el lexer lee bloques grandes. Usa un par de búferes: dos mitades, para que un lexema pueda cruzar la frontera entre dos bloques. Al final de cada mitad hay un carácter especial, el centinela. El bucle ya tiene que mirar cada carácter, así que la prueba de fin de búfer pasa a ser un caso más de esa misma mirada, y se quita una comparación del bucle más ejecutado del compilador.

AFN y AFD

Un autómata finito es una máquina con pocos estados y flechas entre ellos, rotuladas con símbolos. Piensa en un juego de mesa con casillas y flechas. Un AFD (determinista) tiene exactamente una flecha por cada estado y símbolo, así que hay un único camino. Un AFN (no determinista) puede tener varias flechas con el mismo símbolo y también transiciones ε, que no gastan símbolo de la entrada. Un AFN acepta si algún camino termina en un estado de aceptación. Los dos tienen el mismo poder: reconocen exactamente los lenguajes regulares.

• Clausura ε de un conjunto de estados: todo lo que se alcanza desde ellos siguiendo solo flechas ε, cero o más veces. El propio conjunto está incluido. Se calcula con una búsqueda en un grafo.
• La construcción de Thompson convierte una regex en un AFN, pieza por pieza. Cada símbolo da un autómata de 2 estados. La alternancia y la clausura añaden 2 estados nuevos cada una (uno inicial y uno de aceptación). La concatenación une el estado de aceptación de la primera pieza con el inicial de la segunda. El tamaño crece solo linealmente: como máximo alrededor del doble del número de símbolos y operadores. Ejemplo: ab* tiene 2 + (2 + 2) estados, menos 1 estado unido, o sea 5.
• La construcción de subconjuntos convierte un AFN en un AFD. Cada estado del AFD es un conjunto de estados del AFN, los lugares donde el AFN puede estar después de leer un prefijo. Empieza con la clausura del estado inicial y, para cada conjunto nuevo y cada símbolo, junta los destinos. En teoría puede haber hasta 2^n conjuntos, pero solo se crean los alcanzables, y suelen ser pocos.
• La minimización une estados equivalentes. Dos estados son equivalentes si ninguna cadena lleva a uno a la aceptación y al otro al rechazo. Empieza separando los estados de aceptación de los demás, luego divide cualquier grupo cuyos estados van, con el mismo símbolo, a grupos distintos. Cuando ya nada se divide, cada grupo es un estado. El AFD mínimo es único.

Tiempo contra espacio

Los números fueron medidos por el mini-proyecto regex-engine de este repositorio. Un patrón así en un servicio que recibe entrada de usuarios puede bloquearlo (ReDoS). Comparar con autómatas no explota de esta manera.

Qué puede y qué no puede hacer un lexer

El lexer ve un lexema a la vez y no conoce la estructura del programa. Solo encuentra errores donde ningún patrón coincide con el resto de la entrada: un carácter inválido, una cadena o comentario que nunca se cierra, un número mal formado. Un orden equivocado de tokens es un error sintáctico. Un significado equivocado es un error semántico.

Análisis sintáctico: gramáticas y árboles

Las palabras sueltas no son una frase. 'Gato el duerme' tiene las palabras correctas en el orden equivocado. El parser revisa que los tokens sigan la gramática del lenguaje y arma un árbol que muestra cómo encajan las piezas.

Gramáticas libres de contexto

Una gramática libre de contexto tiene cuatro partes: terminales (los tokens, las palabras de verdad), no terminales (nombres para tipos de frase), producciones (reglas, cada una con un no terminal a la izquierda y una secuencia de símbolos a la derecha) y un símbolo inicial. El lenguaje de la gramática es el conjunto de cadenas de terminales que se derivan del símbolo inicial.

S -> A B
A -> a
B -> b

Una derivación empieza en el símbolo inicial y, en cada paso, reemplaza un no terminal por el lado derecho de una de sus producciones. En la derivación por la izquierda siempre reemplazas el no terminal más a la izquierda; en la derivación por la derecha, el más a la derecha. Las dos pueden armar el mismo árbol, solo cambia el orden.

izquierda: S => A B => a B => a b
derecha:   S => A B => A b => a b

Árbol de derivación y árbol sintáctico abstracto

El árbol de derivación (parse tree) tiene un nodo por cada símbolo de la gramática usado, incluso los no terminales que existen solo para codificar la precedencia. El árbol sintáctico abstracto (AST) guarda solo lo que importa para las fases siguientes: cada construcción y sus partes. La forma del árbol ya dice lo que decían los paréntesis y los niveles de la gramática.

árbol de derivación de 1 + 2    AST

        E                    +
      / | \                 / \
     E  +  T               1   2
     |     |
     T     F
     |     |
     F     2
     |
     1

Ambigüedad, precedencia y asociatividad

Una gramática es ambigua cuando una cadena tiene más de un árbol de derivación. El caso clásico es E -> E + E | E * E | id: la cadena id + id * id se puede agrupar de dos formas. Como el compilador da significado a partir del árbol, la ambigüedad hay que quitarla, reescribiendo la gramática o con reglas de desempate de precedencia y asociatividad.

E -> E + T | T       (menor precedencia, cerca del inicio)
T -> T * F | F
F -> id | ( E )       (mayor precedencia, cerca de los operandos)

• Cada nivel de precedencia recibe su propio no terminal. Los operadores de menor precedencia quedan cerca del símbolo inicial, y los de mayor precedencia más al fondo, cerca de los operandos. Por eso * liga más fuerte que + aquí: sus partes deben agruparse primero, más al fondo del árbol.
• La recursión por la izquierda (E -> E + T) hace que un operador sea asociativo por la izquierda: 1 - 2 - 3 significa (1 - 2) - 3. La recursión por la derecha lo haría asociativo por la derecha.

Errores

La recuperación más simple es el modo pánico. Cuando el parser encuentra un error, descarta tokens hasta hallar un token de sincronización, normalmente un delimitador como un punto y coma o una llave de cierre, y entonces sigue. Puede saltarse un tramo largo sin revisarlo, pero nunca entra en un bucle infinito, y deja que el compilador informe varios errores en una sola ejecución.

Análisis descendente: descenso recursivo y LL(1)

Un parser descendente (top-down) empieza en el símbolo inicial e intenta armar el árbol hacia los tokens, como armar un rompecabezas mirando la imagen de la caja. El más simple es el descenso recursivo: escribe una función por no terminal. La pila de llamadas del lenguaje hace el papel de la pila del parser. Es predictivo cuando el siguiente token basta para elegir la producción, sin backtracking.

Dos problemas que resolver antes

Recursión por la izquierda. Una producción A -> A α hace que la función de A se llame a sí misma antes de leer ningún token. Nunca termina. La solución, para A -> A α | β, es A -> β A' y A' -> α A' | ε. El lenguaje es el mismo, pero ahora la repetición ocurre a la derecha.

antes:    E -> E + T | T
después:  E  -> T E'
          E' -> + T E' | ε

Prefijo común. Cuando dos alternativas empiezan igual, un parser predictivo no puede elegir mirando un solo token. La factorización por la izquierda aplaza la decisión: A -> α β1 | α β2 pasa a ser A -> α A' y A' -> β1 | β2. El parser lee primero el prefijo común y elige solo donde las alternativas difieren.

antes:    S -> if E then S | if E then S else S
después:  S  -> if E then S S'
          S' -> else S | ε

FIRST y FOLLOW

Para decidir, el parser necesita dos conjuntos. FIRST(α) es el conjunto de terminales que pueden iniciar una cadena derivada de α, más ε si α puede derivar la cadena vacía. Para un cuerpo X1 X2 ... Xn tomas FIRST(X1) sin ε y, mientras todos los símbolos hasta ahí puedan ser vacíos, sumas el FIRST del siguiente. ε solo entra si todos los símbolos del cuerpo pueden ser vacíos.

FOLLOW(A) es el conjunto de terminales que pueden aparecer justo después de A en alguna derivación. $ representa el fin de la entrada. Para cada producción X -> α A β, suma FIRST(β) sin ε; si β es vacío o puede ser vacío, suma también FOLLOW(X). El FOLLOW del símbolo inicial siempre tiene $, y ε nunca aparece en un conjunto FOLLOW.

S -> A d
A -> a | ε

FIRST(A)  = { a, ε }
FIRST(S)  = { a, d }     (A puede ser vacío, así que d puede iniciar S)
FOLLOW(A) = { d }

La tabla LL(1)

La tabla LL(1) M[A, t] dice qué producción usar cuando el no terminal A está en el tope de la pila y el siguiente token es t. Una producción A -> α se coloca en M[A, t] para todo terminal t en FIRST(α) y, si α puede derivar ε, también para todo terminal en FOLLOW(A). Las celdas vacías son errores de sintaxis. La primera L significa que la entrada se lee de izquierda a derecha, la segunda L que se construye una derivación por la izquierda, y 1 es un token de lookahead.

Una gramática es LL(1) cuando ninguna celda recibe más de una producción. De forma equivalente, para cada par de alternativas A -> α | β: FIRST(α) y FIRST(β) son disjuntos y, si una puede derivar ε, el FIRST de la otra no puede cruzarse con FOLLOW(A).

Escalada de precedencia (parser de Pratt)

Un parser de Pratt le da a cada operador un poder de enlace (binding power), un número que dice con qué fuerza agarra a sus vecinos. La función que analiza una expresión recibe el poder mínimo que acepta. Después de un operando, solo toma el siguiente operador si su poder es mayor que ese mínimo. Para un operador asociativo por la izquierda, el operando de la derecha se analiza con el mínimo igual al poder del propio operador, así que un segundo operador igual no es tragado por el operando de la derecha.

Análisis ascendente: shift-reduce y LR

Un parser ascendente (bottom-up) trabaja al revés: empieza por los tokens y los junta en piezas cada vez más grandes hasta que toda la entrada se convierte en el símbolo inicial. Piensa en construir con bloques pequeños hasta tener el castillo completo. Construye una derivación por la derecha, de atrás hacia adelante.

Shift y reduce

Un parser shift-reduce mantiene una pila. En cada paso elige entre dos movimientos: shift (apilar el siguiente token) o reduce (reemplazar el tope de la pila, que coincide con el cuerpo de una producción, por la cabeza de esa producción). Un handle es una pieza que coincide con el cuerpo de una producción y cuya reducción es un paso de una derivación por la derecha hecha al revés.

Ítems LR, closure y goto

Un ítem LR(0) es una producción con un punto, como A -> α · β. El punto marca cuánto del cuerpo ya se vio. El closure de un conjunto de ítems agrega los ítems iniciales de todo no terminal que aparece justo después de un punto. El goto de un conjunto y un símbolo mueve el punto sobre ese símbolo. Los conjuntos de ítems son los estados del parser.

Un estado con un ítem completo (punto al final) y otro ítem que quiere hacer shift es un conflicto en LR(0). SLR(1) lo resuelve cuando el token del shift no pertenece al FOLLOW del no terminal que se va a reducir.

Tres métodos LR

Comparten un solo algoritmo. Solo se diferencian en cómo deciden cuándo reducir.

Conflictos

• Conflicto shift/reduce: en el mismo estado y con el mismo lookahead el parser podría hacer shift o reduce.
• Conflicto reduce/reduce: dos producciones distintas podrían reducirse.
• Yacc resuelve el primero haciendo shift y el segundo eligiendo la producción que aparece primero en la gramática, siempre con una advertencia.

El ejemplo famoso es el else colgante (dangling else). Con if c then S y if c then S else S, ante el token else un estado tiene un ítem completo y otro que puede hacer shift de else. Hacer shift significa que cada else se queda con el if más cercano que todavía no tiene else, que es la regla que la gente espera.

Traducción dirigida por la sintaxis

Ahora el compilador conoce la forma del programa. ¿Cómo descubre el significado? La idea: colgar notitas, llamadas atributos, de los nodos del árbol (un tipo, un valor, un trozo de código) y escribir reglas para calcularlas. Eso es la traducción dirigida por la sintaxis.

Atributos sintetizados y heredados

SDD y esquema de traducción

Una definición dirigida por la sintaxis (SDD) asocia atributos a símbolos de la gramática y reglas a producciones, sin decir en qué orden se ejecutan las reglas. Un esquema de traducción (SDT) está más cerca del programa real: las acciones entre llaves se escriben en posiciones exactas dentro de los cuerpos de las producciones y se ejecutan cuando el parser llega a ellas. La SDD es más fácil de leer como especificación. El esquema es más eficiente porque ya lleva el orden de evaluación.

Árboles anotados y el grafo de dependencias

Un árbol de derivación anotado muestra el valor de cada atributo en cada nodo. Con atributos sintetizados, los valores se calculan desde las hojas hasta la raíz. Para decidir el orden en el caso general, dibuja el grafo de dependencias: un nodo por cada instancia de atributo y una flecha de x a y cuando la regla de y usa x. Cualquier orden topológico de ese grafo (cada atributo después de todo lo que necesita) es un orden de evaluación válido. Si el grafo tiene un ciclo, no existe orden y la definición no se puede evaluar.

E -> E1 + T   E.val = E1.val + T.val
E -> T        E.val = T.val
T -> num      T.val = num.value

entrada 2 + 3 + 4:  T.val=2, 3, 4  ->  E.val = 2 -> 5 -> 9

S-atribuida y L-atribuida

• S-atribuida: solo atributos sintetizados. Se pueden calcular de abajo hacia arriba durante el análisis.
• L-atribuida: cada atributo es sintetizado, o es un atributo heredado de un símbolo X del cuerpo que depende solo de atributos heredados de la cabeza, de atributos de símbolos a la izquierda de X en el cuerpo y de atributos del propio X, sin ciclo. La información fluye de izquierda a derecha, así que todo se puede evaluar en un solo recorrido en profundidad, como hace un parser descendente.

Construir un AST

Un AST se construye con reglas sintetizadas: cuando la producción representa una construcción, crea un nodo; en producciones auxiliares como E -> T, solo pasa el puntero hacia arriba. El atributo es sintetizado, así que la definición es S-atribuida y el árbol se arma de abajo hacia arriba durante el análisis. El árbol de a + b + c tiene 5 nodos: tres hojas y dos nodos +.

¿Cuándo se ejecutan las acciones?

En un esquema de traducción, una acción se ejecuta en cuanto se procesó todo lo que está a su izquierda. En el árbol de derivación, las acciones cuentan como hojas extra, y el orden es un recorrido en profundidad, de izquierda a derecha. Una acción colocada después de un no terminal recursivo solo se ejecuta cuando se recorrió todo el subárbol de ese no terminal.

T -> x { print('x') } T { print('y') }
T -> ε

entrada: x x     salida: x x y y

Atributos en un parser de descenso recursivo

En un parser de descenso recursivo cada no terminal es una función. Los atributos heredados pasan a ser parámetros y los sintetizados pasan a ser valores de retorno. Después de quitar la recursión por la izquierda, el operando de la izquierda de un operador lo reconoce otra función. Para mantener la asociatividad por la izquierda, el valor calculado hasta ahí baja como atributo heredado, y el resultado final vuelve hacia arriba como atributo sintetizado cuando se llega a la producción ε.

// E -> T R      R -> - T R | ε
function R(acc: number): number {
	if (next() === "-") {
		match("-");
		return R(acc - T());   // (acc - t), no (acc - (resto))
	}
	return acc;              // ε: devuelve el resultado hacia arriba
}

Generación de código intermedio

El árbol sintáctico es bueno para entender el programa, pero no para ejecutarlo ni para hacerlo rápido. Por eso el compilador lo convierte en un lenguaje simple y plano, que no es ni fuente ni máquina: el código intermedio.

Código de tres direcciones

En el código de tres direcciones cada instrucción tiene como máximo un operador en el lado derecho, como en x = y op z. Una expresión larga se desarma, y el compilador inventa nombres temporales para los valores intermedios. Una dirección puede ser un nombre del programa, una constante o un temporal.

a = b * c + d

t1 = b * c
t2 = t1 + d
a  = t2

Entonces el número de temporales es igual al número de nodos de operador del árbol. Partir de un DAG (abajo) crea menos, porque las subexpresiones repetidas se vuelven un solo nodo.

Cómo guardarlo: cuádruplas y tripletas

Las tripletas ahorran temporales, pero son difíciles de mover: cuando una tripleta cambia de lugar, toda referencia a ella cambia. Las tripletas indirectas lo arreglan.

Asignación única estática (SSA)

En la forma SSA toda variable se asigna en exactamente un lugar del texto del programa. Cada asignación nueva crea una versión nueva (x1, x2, y así sucesivamente). Cuando dos caminos con versiones distintas se encuentran, después de un if o en lo alto de un bucle, una función φ crea una versión nueva cuyo valor es una u otra, según el camino por el que llegó el control. Esto deja claro qué definición llega a cada uso.

x1 = 1
if c goto L1 else L2
L1: x2 = 2
L2: x3 = φ(x1, x2)    // x1 si saltamos L1, x2 si pasamos por él

Tipos y conversiones

Una conversión puede ser explícita (el programador escribe un cast) o implícita (el compilador la inserta solo, lo que se llama coerción). Muchos lenguajes permiten solo coerciones de ensanchamiento (widening), que conservan toda la información, como entero a punto flotante. En el código intermedio la coerción es una instrucción de conversión como t1 = (float) i.

DAG: compartir el trabajo repetido

Un DAG de expresión (grafo acíclico dirigido) es como el árbol sintáctico, pero un nodo puede tener más de un padre: una subexpresión que aparece varias veces se guarda una sola vez. Antes de crear un nodo, el compilador busca un nodo existente con el mismo operador y los mismos hijos. Las hojas iguales también se comparten. Esto deja al descubierto las subexpresiones comunes, que se pueden calcular una sola vez.

(x + y) * (x + y)

árbol: 7 nodos          DAG: 4 nodos
      *                     *
     / \                   / \
    +   +                  \ /
   / \ / \                  +
  x  y x  y                / \
                          x   y

Arreglos

Con almacenamiento por filas (row-major) e índices que empiezan en 0, la dirección de A[i][j] es base + (i · n2 + j) · w. Aquí n2 es el número de columnas y w el ancho de un elemento. El número de filas no aparece, solo el número de columnas.

A tiene 5 filas, 3 columnas, w = 4 bytes, base = 200
dirección de A[2][1] = 200 + (2 * 3 + 1) * 4 = 228

Booleanos y saltos

En el código de saltos (jumping code) el valor de una expresión booleana no se guarda en una variable. Es el lugar donde termina el control. En B1 || B2, si B1 es verdadero el control salta directo a la salida verdadera; en B1 && B2, si B1 es falso salta directo a la salida falsa. Los operandos que no pueden cambiar el resultado nunca se evalúan. Esto es la evaluación en cortocircuito.

Un while se convierte en tres piezas: la prueba arriba con un salto de salida a justo después del bucle, el cuerpo y un salto incondicional de vuelta a la prueba. Un if sin else se convierte en una prueba que salta solo la sentencia controlada.

while (i < n) i = i + 1;

L1: ifFalse i < n goto L2
    i = i + 1
    goto L1
L2: ...

Backpatching

En una sola pasada, un salto se escribe antes de que exista su destino. El backpatching deja el destino en blanco y pone la instrucción en una lista: la truelist tiene los saltos que se toman cuando la condición es verdadera, la falselist los que se toman cuando es falsa. Cuando se conoce el destino, todos los saltos de la lista se rellenan de una vez. Para B1 || B2: la falselist de B1 se rellena con el inicio de B2; la truelist del conjunto es la unión de las dos truelists; la falselist del conjunto es la falselist de B2.

Entornos de ejecución: distribución de la memoria y llamadas

Mientras el programa se ejecuta, ¿dónde viven sus cosas? Piensa en tu pupitre en la escuela. Algunas cosas están pegadas a él para siempre (la etiqueta con tu nombre), otras están en una bandeja que crece y se achica en orden (los libros de hoy), y otras están en una caja grande en la esquina, de donde sacas y pones cosas en cualquier orden. Los programas tienen los mismos tres tipos de lugar.

Las cuatro áreas

dirección baja
+--------------------+
| código             |  tamaño conocido al compilar
+--------------------+
| datos estáticos    |  tamaño conocido al compilar
+--------------------+
| heap               |  crece hacia el
|               v    |  espacio libre
|  (espacio libre)   |
|               ^    |  crece hacia el
| pila               |  espacio libre
+--------------------+
dirección alta

El código y los datos estáticos tienen un tamaño conocido al compilar. La pila y el heap cambian de tamaño mientras el programa se ejecuta. Ponerlos en extremos opuestos de la misma región libre deja que cualquiera de los dos crezca mientras quede espacio entre ellos.

• Asignación estática: la dirección se elige al compilar (o al enlazar). Sirve para datos que existen exactamente una vez durante toda la ejecución, como las variables globales y las constantes.
• Pila: datos cuya vida está ligada a una llamada.
• Heap: datos cuya vida no depende de las llamadas, y datos cuyo tamaño solo se conoce al ejecutar.

Registros de activación

Cada vez que se llama a un procedimiento, se apila un registro de activación (stack frame). Cuando la llamada retorna, se desapila. Guarda los datos de esa ejecución: los parámetros reales, el valor devuelto, el enlace de control (control link), el enlace de acceso (access link), el estado guardado de la máquina (incluida la dirección de retorno), las variables locales y los temporales. Esto es lo que hace posible la recursión: cada llamada tiene sus propias variables locales.

Enlace de control y enlace de acceso

Los dos coinciden solo cuando quien llamó es el propio procedimiento que rodea. Con procedimientos anidados y ámbito estático, un nombre que pertenece a un procedimiento externo se encuentra con el par (diferencia de profundidad de anidamiento, desplazamiento en el registro). El código sigue tantos enlaces de acceso como la diferencia entre la profundidad del procedimiento que usa el nombre y la del que lo declara.

procedure main (profundidad 1): var x
  procedure a (profundidad 2)
    procedure b (profundidad 3): usa x

llamadas: main -> a -> b
b usa x, declarada en main: 3 - 1 = 2 enlaces de acceso
b --> a --> main  (luego el desplazamiento de x)

Las closures rompen la regla de la pila

La pila supone que los datos de una llamada mueren cuando la llamada retorna. Una closure rompe eso: recuerda el entorno donde se creó y se puede llamar después de que la función externa terminó.

function makeCounter() {
	let n = 0;
	return () => { n = n + 1; return n; };
}
const next = makeCounter();
next(); next();   // n tiene que seguir existiendo aquí

Por eso las variables capturadas viven en un entorno en el heap, que se libera solo cuando ninguna closure apunta a él.

Dos errores clásicos de la memoria manual

• Fuga de memoria (memory leak): olvidar liberar lo que ya no se usará. El programa sigue correcto, pero usa cada vez más memoria.
• Puntero colgante (dangling pointer): liberar lo que todavía se va a usar. El programa entonces lee o escribe en memoria que puede ya pertenecer a otro objeto.

Asignación en el heap y recolección de basura

El heap es una caja grande donde el programa pide pedazos de memoria de cualquier tamaño. Alguien tiene que recordar qué pedazos están libres y cuáles ocupados, y limpiar cuando un pedazo ya no hace falta. Veamos cómo.

Encontrar un pedazo libre

Los pedazos libres se guardan en una lista libre. El first fit toma el primer pedazo suficientemente grande. Es rápido, pero tiende a partir los pedazos grandes. El best fit toma el pedazo más pequeño que sea suficientemente grande. Guarda los pedazos grandes para pedidos grandes, pero la búsqueda es más larga y deja sobras diminutas. Los dos intentan limitar la fragmentación: el espacio libre total alcanza, pero está repartido en pedazos demasiado pequeños para usar.

lista libre: [40] -> [10] -> [25] -> [18]
pedido: 12 bytes

first fit: [40]  (primero suficientemente grande, sobran 28)
best fit:  [18]  (menor suficientemente grande, sobran 6)

Recolección de basura

Un recolector de basura (garbage collector) libera memoria automáticamente: recupera solo los objetos que ya no se pueden alcanzar, así que elimina el error del puntero colgante. Las raíces son los lugares desde los que el programa puede partir (variables de la pila, globales). Un objeto está vivo si un camino de punteros lleva hasta él desde una raíz.

Conteo de referencias

Cada objeto cuenta cuántos punteros se refieren a él. Cuando la cuenta llega a cero, el objeto se libera en el acto, y a los objetos a los que apuntaba se les reduce la cuenta, posiblemente en cadena. La debilidad clásica son los ciclos: objetos que se apuntan entre sí mantienen una cuenta positiva aunque ninguna raíz los alcance, así que se fugan. Los recolectores por trazado no tienen ese problema, porque usan la alcanzabilidad desde las raíces.

raíces: p -> A -> B
        F <-> E   (se apuntan entre sí, nadie les apunta)

p = null:  A cuenta 0 -> liberado, luego B cuenta 0 -> liberado
E y F quedan con cuenta 1 cada uno -> se fugan con conteo de referencias

Mark-and-sweep y copia

Recolección generacional

La mayoría de los objetos mueren jóvenes. Por eso un recolector generacional recolecta la generación joven con frecuencia, recuperando mucha basura con poco trabajo. Para que una recolección parcial sea segura, todo puntero que entra a la región joven desde fuera debe tratarse como raíz. El recolector mantiene un conjunto recordado (remembered set), actualizado por una barrera de escritura (write barrier), un pedacito de código que se ejecuta en cada asignación de puntero. Si un objeto viejo se cambia para apuntar a uno joven, el conjunto recordado lo registra, y el objeto joven no se libera por error.

Recolección incremental

Un recolector incremental marca un poco cada vez, mezclado con el programa en ejecución, que sigue cambiando el grafo de objetos. El peligro: el programa guarda un puntero a un objeto todavía no marcado dentro de un objeto que ya fue escaneado y quita el camino original. El objeto vivo escapa del marcado y se libera por error. Una barrera de escritura anota esas escrituras, así que el destino se marca o el objeto modificado se vuelve a escanear. El precio es un poco de basura flotante (floating garbage), objetos muertos que sobreviven un ciclo más.

Generación de código

El último gran paso: del código intermedio a instrucciones que la máquina puede ejecutar. El generador de código tiene tres tareas principales: selección de instrucciones (qué instrucciones de máquina usar), asignación de registros (qué valores quedan en registros, y en cuál) y ordenamiento de instrucciones (en qué orden). Los registros son la memoria más rápida y más escasa de la máquina, así que decidir qué queda en ellos pesa mucho en la velocidad. Encontrar la mejor asignación es NP-completo, así que en la práctica los compiladores usan heurísticas como la coloración de grafos.

Máquinas de pila y máquinas de registros

En una máquina de pila las instrucciones no nombran sus operandos. Toman los operandos del tope de la pila y apilan el resultado. El código de una expresión es su forma posfija: primero el operando de la izquierda, luego el de la derecha, luego el operador. En una máquina de registros cada instrucción nombra dónde está cada valor, como en MUL R1, R1, R2.

Bloques básicos y el grafo de flujo

Un bloque básico es una secuencia máxima de instrucciones consecutivas con una única entrada (la primera instrucción) y una única salida (la última). Dentro no hay saltos ni destinos de salto, así que las instrucciones siempre se ejecutan juntas y en orden. Para hallar los bloques, marca los líderes: la primera instrucción, toda instrucción que es destino de un salto y toda instrucción que viene justo después de un salto. Un bloque va desde un líder hasta la instrucción anterior al siguiente líder, así que el número de bloques es igual al número de líderes. Los bloques son los nodos del grafo de flujo, y las aristas dicen qué bloque puede ejecutarse después de cuál.

1: i = 0
2: if i > 9 goto 5
3: i = i + 1
4: goto 2
5: print i

líderes: 1 (primera), 2 (destino de 4), 3 (después de un salto), 5 (destino de 2)
bloques: [1] [2] [3-4] [5]  ->  4 bloques

Vitalidad dentro de un bloque

Una variable está viva en un punto si su valor ahí todavía puede usarse antes de ser sobrescrito. Dentro de un bloque, ve hacia atrás. Empieza con el conjunto vivo a la salida. Para cada instrucción x = y op z, primero quita x, luego agrega y y z. El generador usa esto para saber cuándo se puede reutilizar un registro.

vivas a la salida: {z}
3: z = y + 1      antes de 3: ({z} - z) + y = {y}
2: y = x * 2      antes de 2: ({y} - y) + x = {x}
1: x = x + 1      antes de 1: ({x} - x) + x = {x}

Un modelo de costo

Un modelo simple le da a cada instrucción su largo en palabras: 1 por la instrucción más el costo del modo de direccionamiento de cada operando. Los registros cuestan 0, las direcciones de memoria y las constantes cuestan 1 porque ocupan una palabra extra. Así la selección de instrucciones prefiere mantener los valores en registros y evitar loads y stores inútiles.

Registros: coloración y el número de Ershov

En la asignación por coloración de grafos, cada variable es un nodo, cada interferencia (dos variables vivas al mismo tiempo) es una arista, y cada registro es un color. Los vecinos necesitan colores distintos. El menor número de registros que funciona sin derramar es el número cromático del grafo. Si la máquina tiene menos registros, alguna variable se derrama (spill): vive en la memoria, con loads y stores alrededor de cada uso.

Para un árbol de expresión, el número de Ershov dice cuántos registros bastan para evaluarlo sin guardar temporales. Las hojas valen 1. Un nodo cuyos hijos tienen números distintos recibe el mayor. Si los números son iguales, recibe ese valor más 1. El truco es evaluar primero el hijo más exigente: su resultado ocupa entonces un solo registro mientras se calcula el otro hijo.

(a + b) * c        a+b: 1,1 iguales -> 2     raíz: 2 y 1 -> 2
(a + b) * (c + d)  dos hijos 2, iguales -> 3

Descriptores y peephole

El generador simple mantiene dos tablas. El descriptor de registros dice qué variables tienen su valor actual en cada registro. El descriptor de direcciones dice en qué lugares (registros, memoria) está el valor actual de cada variable. Antes de reutilizar un registro, el generador los consulta: si el registro guarda la única copia de un valor vivo, primero emite un store. Al final de un bloque, toda variable viva cuya copia en memoria está desactualizada también se guarda.

Un optimizador peephole mira por una pequeña ventana deslizante de pocas instrucciones y cambia lo que encuentra por algo más corto o más rápido. Por ejemplo, quita un load justo después de un store a la misma dirección, quita código inalcanzable, acorta un salto a un salto y cambia x * 2 por x + x. Cada mejora puede abrir espacio para otras, así que la pasada suele repetirse.

Optimizaciones independientes de la máquina

Una optimización hace el programa más rápido o más pequeño sin cambiar lo que hace. 'Independiente de la máquina' quiere decir que trabaja sobre el código intermedio, así que no depende del procesador.

Trucos locales simples

Las optimizaciones funcionan en cadena: una prepara el terreno para la siguiente.

Subexpresiones comunes

Una ocurrencia de una expresión es una subexpresión común si se calculó antes y ninguno de sus operandos cambió desde entonces. Una asignación a un operando mata la expresión. La versión local mira un bloque básico; la versión global usa el análisis de expresiones disponibles para reutilizar valores entre bloques.

(1) t1 = a + b
(2) t2 = a + b    reutiliza t1 (a, b no cambiaron)
(3) a  = t2 * 2    mata a + b
(4) t3 = a + b    hay que calcularla de nuevo

Bucles: dónde se va el tiempo

Los programas pasan la mayor parte del tiempo en bucles, así que las optimizaciones de bucle valen la pena. Una sentencia es invariante del bucle cuando sus operandos son constantes, o se definen solo fuera del bucle, o se definen por otras sentencias invariantes. El movimiento de código la lleva al preencabezado (preheader), un bloque justo antes del bucle, para que se ejecute una vez en lugar de una vez por iteración. Una variable de inducción cambia en un paso fijo en cada iteración, como i y t = i * 4. Esas se tratan con la reducción de fuerza (strength reduction), que cambia la multiplicación por una suma hecha en cada paso, y no con el movimiento de código.

antes:   L: t1 = n - 2      después: t1 = n - 2      (movido afuera)
            t2 = i * 4               L: t2 = i * 4
            ...                           ...

Análisis de flujo de datos y bucles

Para saber qué es seguro, el compilador hace preguntas sobre todo el grafo de flujo: '¿qué asignación puede llegar hasta aquí?', '¿esta variable todavía se va a usar?', '¿este valor ya se calculó en todos los caminos?'. El análisis de flujo de datos responde a estas preguntas con una receta común.

El marco de trabajo

• Una dirección: hacia adelante (desde la entrada) o hacia atrás (desde la salida).
• Funciones de transferencia: cómo cada bloque cambia la información.
• Un operador de encuentro (meet): cómo combinar la información que llega de varios caminos (unión o intersección).
• El análisis es conservador: ante la duda, asume lo peor, así que las optimizaciones que lo usan siguen siendo seguras.

La unión sirve para las preguntas 'existe algún camino'. La intersección sirve para las de 'en todos los caminos', porque la eliminación global de subexpresiones comunes solo es segura si el valor está listo por cualquier camino de llegada.

Definiciones que alcanzan

Una definición d alcanza un punto si existe un camino de d hasta él sin otra definición de la misma variable en el medio. Para cada bloque, gen guarda las definiciones del bloque que sobreviven hasta su final, y kill guarda las otras definiciones de las mismas variables. Las ecuaciones son OUT[B] = gen[B] ∪ (IN[B] − kill[B]) y IN[B] = ∪ OUT[P] sobre los predecesores P. Se resuelven repitiendo hasta que nada cambie.

B1: d1: x = 1      B2: d2: x = x + 1 ; if x < 9 goto B2     B3: d3: y = x
aristas: B1->B2, B2->B2, B2->B3

IN[B2]  = OUT[B1] ∪ OUT[B2] = {d1} ∪ {d2} = {d1, d2}
IN[B3]  = OUT[B2] = {d2}      (d2 mata a d1: misma variable x)

Variables vivas

Recorre el código hacia atrás. Para x = y op z, el conjunto antes de ella es (conjunto después − {x}) ∪ {y, z}: la definición mata x, y los usos hacen vivas a y y z. Una variable está viva a la entrada de un bloque si se lee en el bloque antes de redefinirse, o si está viva a la salida y no se redefine en él. El resultado orienta la eliminación de código muerto y la asignación de registros.

Expresiones disponibles

Una expresión está disponible en un punto si, en todo camino desde la entrada hasta él, la expresión se calculó y ningún operando se asignó después del último cálculo. El orden importa dentro de un bloque: calcular y luego matar deja la expresión no disponible a la salida.

         B1: t1 = a + b
          /           \
 B2: t2 = a + b    B3: d = t1 - c
     a = t2 * 2            |
          \           /
           B4: t3 = a + b

por B3: a + b está disponible.
por B2: a cambió después, así que fue matada.
Intersección de los dos caminos: NO disponible en B4.

Dominadores y bucles naturales

Un nodo d domina a n si todo camino desde la entrada hasta n pasa por d. Una arista de retroceso (back edge) es una arista cuyo destino domina al origen. El destino es el encabezado del bucle. El bucle natural de una arista de retroceso es el encabezado más todos los nodos que alcanzan el origen de la arista sin pasar por el encabezado, hallados caminando hacia atrás por los predecesores desde el origen. Los bloques donde el control sale del bucle no forman parte de él.

B1 -> B2 -> B3 -> B4 -> B2      (B4 -> B2 es la arista de retroceso)
      B2 -> B5

B2 domina a B4, así que el encabezado es B2.
Bucle = {B2, B3, B4}.  B5 queda afuera (la salida).

Paralelismo a nivel de instrucción y localidad

Un procesador moderno no hace una cosa a la vez. Y la memoria es mucho más lenta que el procesador, así que el lugar donde están los datos importa. El compilador ayuda con las dos cosas.

Pipelines

Un procesador con pipeline corta el trabajo de una instrucción en etapas: búsqueda, decodificación, ejecución, acceso a la memoria y escritura del resultado. Empieza la siguiente instrucción antes de que la anterior haya terminado. Este es el tipo más simple de paralelismo a nivel de instrucción.

tiempo -> 1    2    3    4    5    6
instr 1   B    D    E    M    W
instr 2        B    D    E    M    W
instr 3             B    D    E    M    W

Está limitado por las dependencias: una instrucción que necesita el resultado de la anterior, o un salto cuyo destino aún no se conoce, hace que el pipeline espere.

Dependencias de datos

Dos instrucciones dependen una de otra cuando usan el mismo lugar y al menos una de ellas lo escribe. Hay tres tipos, y cualquier planificador, en el compilador o en el procesador, solo puede reordenar o superponer instrucciones que no estén atadas por ellos, ni por dependencias de control.

Bucles e iteraciones paralelas

Una dependencia es transportada por el bucle (loop-carried) cuando dos iteraciones distintas usan el mismo lugar de memoria y al menos una de ellas escribe. Si no hay ninguna, las iteraciones son independientes y se pueden repartir entre procesadores distintos, en cualquier orden. El análisis de dependencias de datos compara los índices de las escrituras con los de las lecturas y escrituras de las otras iteraciones. Los accesos de solo lectura nunca crean una dependencia.

for (i = 1; i < n; i++) a[i] = a[i-1] + 1;   // transportada: necesita la iteración anterior
for (i = 1; i < n; i++) a[i] = b[i] + 1;     // independiente: puede ejecutarse en paralelo

Localidad

La caché trae de una vez una línea entera de memoria cercana. La localidad espacial es usar datos cercanos en la memoria en momentos cercanos, de modo que se use cada elemento traído. En C, una matriz se guarda fila por fila (row-major). Bajar por una columna da un salto largo en la memoria en cada paso. El intercambio de bucles (loop interchange) invierte los bucles anidados para que el bucle interno recorra la dimensión guardada de forma contigua.

// lento: el bucle interno salta una fila entera en cada paso
for (j = 0; j < N; j++) for (i = 0; i < N; i++) sum += m[i][j];
// rápido: el bucle interno avanza a lo largo de una fila
for (i = 0; i < N; i++) for (j = 0; j < N; j++) sum += m[i][j];

Intérpretes, máquinas virtuales y JIT

Empezamos con la diferencia entre compiladores e intérpretes. Los lenguajes reales mezclan las dos ideas, por etapas: de un intérprete simple y lento a uno rápido, y luego a una máquina que compila mientras se ejecuta.

Intérprete que recorre el árbol

Un intérprete que recorre el árbol (tree-walking) ejecuta el programa visitando recursivamente los nodos del árbol sintáctico. Es la forma más simple de implementar un lenguaje. Pero cada operación paga por seguir punteros, elegir el código según el tipo del nodo y buscar nombres en entornos.

Bytecode y máquinas virtuales

El bytecode es una lista compacta y plana de instrucciones para una máquina imaginaria, la máquina virtual (VM). Los nombres ya se cambiaron por números, lo que mejora la localidad y reduce el trabajo por operación.

En el mini-proyecto bytecode-vm de este repositorio, una VM resultó unas 2 veces más rápida que el intérprete de árbol en un bucle y de 3 a 5 veces más rápida en una función recursiva, usando unos 2 MiB de memoria contra 58 a 98 MiB. Son los resultados medidos de su ejecución registrada.

¿VM de pila o de registros?

• VM de pila: las instrucciones intercambian valores por una pila de operandos. Quien produce un valor apila, quien consume desapila. Las instrucciones son cortas y fáciles de generar desde el árbol, en posorden.
• VM de registros: cada instrucción nombra sus fuentes y el destino. Necesita menos instrucciones para el mismo trabajo, pero cada una es más grande y el compilador es más difícil de escribir.

El bytecode de pila es la expresión en posfija. Las instrucciones binarias desapilan primero el operando de la derecha, luego el de la izquierda, y apilan el resultado. Esto importa para la resta y la división.

El bucle de despacho

El núcleo de una VM es el bucle de despacho (dispatch loop): leer el opcode al que apunta el puntero de instrucción, avanzar el puntero y saltar al código que ejecuta ese opcode. Este costo fijo se paga una vez por instrucción ejecutada, no por instrucción escrita, así que domina el tiempo de los bucles. Si el cuerpo de un bucle tiene 5 instrucciones y se ejecuta 100 veces, el bucle paga ese costo 500 veces. Trucos como el threaded code y las superinstrucciones lo reducen.

Compilación JIT

Un compilador JIT (just-in-time) traduce a código de máquina, mientras el programa se ejecuta, los trozos que el perfil (profile) muestra como calientes (los más usados). Compilar también gasta tiempo. Por eso las VM usan niveles (tiers): interpretan primero, compilan rápido después y optimizan a fondo solo lo que sigue caliente. El precio es el calentamiento (warm-up): el programa empieza lento y se va volviendo más rápido. La compilación anticipada (AOT, ahead-of-time) empieza rápido, pero no conoce el comportamiento real del programa.

Especulación y desoptimización

El JIT puede apostar. Genera código rápido para el caso que el perfil mostró ser común y lo protege con guardas (guards), pruebas de la suposición. Cuando una guarda falla, la VM desoptimiza: mueve la ejecución, incluso en medio de una función, a la versión genérica, reconstruyendo el estado que esa versión espera. Así, las apuestas agresivas nunca rompen la regla de que el programa debe seguir comportándose igual.

llamada add(a, b)
   |
 [guarda: ¿los dos son enteros?] -- sí --> suma de máquina rápida
   |
   no
   v
 desoptimiza --> versión genérica (maneja strings, floats...)

Juntando todo

Viste la línea de fábrica completa. Aquí está en una sola tabla, con la salida típica de cada estación y la idea típica para recordar.

Errores que evitar

• Creer que un lexer revisa paréntesis balanceados: no lo hace, un autómata finito no cuenta sin límite.
• Olvidar la condición del FOLLOW cuando una producción puede ser vacía en la revisión LL(1).
• Mezclar el enlace de control (quién llamó) con el enlace de acceso (quién rodea en el texto).
• Usar unión donde la pregunta dice 'en todos los caminos': eso pide intersección.
• Reordenar un bucle o sentencias sin revisar las dependencias.
• Creer que el ámbito dinámico y el estático dan la misma respuesta: no la dan cuando una función se llama desde un lugar donde sus nombres tienen otro significado.

Cómo se conectan las ideas

• Una regex se vuelve un AFN, luego un AFD: la misma maquinaria ejecuta el lexer y el motor de regex.
• Una gramática da el árbol; los atributos en el árbol dan el significado; el árbol se vuelve código intermedio plano.
• El mismo grafo de flujo alimenta los análisis de flujo de datos, las optimizaciones y la asignación de registros.
• Un intérprete de árbol, una VM de bytecode y un JIT ejecutan el mismo lenguaje con costos distintos.
• La notación posfija aparece tres veces: en el traductor simple, en el código de la máquina de pila y en el bytecode de pila.