Los compiladores utilizan árboles y grafos para representar sintaxis, flujo de control, llamadas y dependencias. Estas estructuras permiten validar, optimizar y ordenar el trabajo de construcción.
Un compilador transforma código fuente mediante varias representaciones intermedias. Cada una expone relaciones distintas: jerarquía sintáctica, posibles saltos, uso de valores o llamadas entre funciones.
Los mismos conceptos sirven para analizar dependencias entre módulos y automatizar construcciones incrementales.
El AST representa la estructura gramatical relevante y omite detalles como separadores o paréntesis redundantes.
Es un árbol cuando cada nodo tiene un único padre; referencias posteriores pueden convertir la representación completa en un grafo.
Un recorrido en preorden resulta útil para inspección; el postorden procesa primero operandos y luego operaciones.
Los visitantes separan las operaciones —validar tipos, generar código o formatear— de las clases de nodos sintácticos.
La tabla de símbolos registra declaraciones, ámbitos, tipos y ubicaciones. Cada uso de un nombre se conecta conceptualmente con su declaración.
Estas relaciones permiten detectar nombres inexistentes, usos antes de inicializar y capturas entre ámbitos.
Un CFG divide una función en bloques básicos. Las aristas representan los saltos posibles durante la ejecución.
Condicionales crean bifurcaciones y bucles crean ciclos.
Ejecuta el orden topológico una tarea por vez. Agrega la dependencia codegen → parser para formar un ciclo y observar cómo queda vacía la cola de tareas disponibles.
Tareas disponibles
Orden producido
Acción actual
Un bloque d domina a n si todo camino desde la entrada hasta n pasa por d. El dominador inmediato organiza los bloques en un árbol.
Los dominadores son fundamentales para detectar bucles, ubicar cálculos y construir la forma SSA.
Cada bloque transforma información que circula por el CFG. El análisis repite ecuaciones hasta alcanzar un punto fijo.
Así se calculan variables vivas, definiciones alcanzables y expresiones disponibles.
En Static Single Assignment cada variable se define una sola vez. Las funciones φ combinan valores procedentes de caminos de control diferentes.
SSA facilita propagación de constantes, eliminación de código muerto y otras optimizaciones.
Los vértices son funciones y una arista f → g indica que f puede llamar a g.
Permite analizar alcanzabilidad, recursión, propagación interprocedimental e impacto de cambios. Las llamadas dinámicas pueden obligar a sobreaproximar destinos.
Si B necesita que A esté disponible primero, se crea A → B. La dirección debe mantenerse consistente.
Cuando el grafo es acíclico dirigido, un orden topológico proporciona una secuencia válida.
function ordenTopologico(vertices, aristas) {
const entrada = calcularGradosEntrada(vertices, aristas);
const disponibles = vertices.filter(v => entrada[v] === 0);
const orden = [];
while (disponibles.length) {
const u = disponibles.shift();
orden.push(u);
for (const v of dependientes[u]) {
entrada[v]--;
if (entrada[v] === 0) disponibles.push(v);
}
}
return orden.length === vertices.length ? orden : null;
}Un ciclo significa que ninguna tarea del ciclo puede comenzar antes que las demás. Kahn lo detecta cuando la cola queda vacía sin procesar todos los vértices.
DFS también detecta una arista hacia un vértice gris de la pila activa.
En un grafo dirigido, cada componente fuertemente conexa con más de un vértice identifica un grupo de dependencias mutuamente circulares.
Contraer las componentes produce un DAG que resume el orden posible entre grupos.
Cuando cambia un archivo, el sistema recorre aristas hacia sus dependientes transitivos y reconstruye solo lo afectado.
Hashes de contenido evitan recompilar cuando la salida relevante no cambió.
Todas las tareas con grado de entrada cero pueden ejecutarse en paralelo. Al finalizar una, se liberan nuevos trabajos.
El camino crítico del DAG establece un límite inferior para el tiempo total, incluso con recursos ilimitados.
Los gestores de paquetes resuelven versiones, dependencias transitivas y conflictos. El grafo puede contener varias versiones posibles antes de elegir una solución.
Una dependencia circular entre paquetes no siempre es ilegal en todos los entornos, pero complica instalación, inicialización y mantenimiento.
En el CFG, un bloque no alcanzable desde la entrada nunca se ejecuta. En el grafo de llamadas, una función no alcanzable desde puntos de entrada puede ser candidata a eliminación.
El análisis conservador debe considerar reflexión, callbacks y llamadas indirectas antes de borrar código.
Los compiladores utilizan distintas estructuras porque cada una responde preguntas diferentes. Árboles describen sintaxis; grafos capturan control, datos, llamadas y dependencias.
En el próximo tema revisaremos bibliotecas y herramientas para representar, analizar y visualizar grafos.