GUÍA 25-11-26 Teoría de la Computación

NE111 · miércoles 25/11/2026 · 16:00-17:15 · Sesión 30

Generación de código · Cierre del curso

ÚLTIMA SESIÓN

Hoy, 25 de noviembre, cierra el curso. Los exámenes finales se aplican del 1 al 8 de diciembre.

CÓDIGO INTERMEDIO

Antes de generar código máquina se produce una representación intermedia, independiente tanto del lenguaje fuente como de la arquitectura destino. Eso permite reutilizar el mismo optimizador para varios lenguajes y varias máquinas.

• Código de tres direcciones: t1 = a + b, t2 = t1 * c.
• Notación postfija, que se evalúa directamente con una pila.
• Grafos de flujo de control, para el análisis y la optimización.

DE ÁRBOL A CÓDIGO DE TRES DIRECCIONES

Se recorre el árbol sintáctico abstracto en postorden generando una instrucción por nodo interno y un temporal para cada resultado parcial. El recorrido postorden aparece por tercera vez en el curso, y siempre por la misma razón: hay que resolver los hijos antes que el padre.

OPTIMIZACIONES HABITUALES

• Plegado de constantes: 2 + 3 se sustituye por 5 en tiempo de compilación.
• Eliminación de subexpresiones comunes.
• Eliminación de código muerto.
• Extracción de invariantes de ciclo.
• Desenrollado de ciclos.

GENERACIÓN DE CÓDIGO OBJETIVO

• Selección de instrucciones: qué instrucción de la máquina corresponde a cada operación.
• Asignación de registros: qué valores viven en registros y cuáles en memoria. Es un problema de coloreo de grafos, que es NP-completo, así que en la práctica se usan heurísticas.
• Planificación de instrucciones: reordenar para aprovechar la segmentación del procesador.

DOS HILOS DEL CURSO QUE SE CIERRAN AQUÍ

La asignación de registros es NP-completa: el bloque de complejidad reaparece en la última fase del compilador, y es la razón de que los compiladores usen heurísticas en lugar de buscar el óptimo.

Y decidir si una optimización es correcta en general —si dos programas hacen lo mismo— es indecidible por el teorema de Rice. Por eso los compiladores solo aplican transformaciones que pueden probar seguras en casos particulares.

RECORRIDO DEL CURSO

• Introducción — disciplinas de la computación y desarrollo histórico.
• Máquinas de Turing y recursión — el modelo de cómputo y la máquina universal.
• Complejidad computacional — recursos, problema de Halting, P y NP.
• Expresiones regulares y autómatas — modelos restringidos y análisis léxico.
• Gramática y lenguajes — gramáticas libres de contexto y autómatas de pila.
• Compiladores — parsers, intérpretes y generación de código.

LO QUE TE LLEVAS

Un mapa de lo que una máquina puede y no puede hacer, y la capacidad de reconocer a qué nivel de la jerarquía pertenece un problema antes de intentar resolverlo. En la práctica eso se traduce en saber cuándo un problema exige una expresión regular, cuándo una gramática, y cuándo no hay solución algorítmica y hay que cambiar de estrategia.

«Those who can imagine anything, can create the impossible.» — Alan Turing