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

NE111 · lunes 23/11/2026 · 16:00-17:15 · Sesión 29

Intérpretes y compiladores

LAS DOS ESTRATEGIAS

• Compilador — traduce el programa completo a otro lenguaje, típicamente código máquina, y después se ejecuta el resultado.
• Intérprete — recorre el programa y ejecuta cada construcción sobre la marcha, sin producir un ejecutable.

COMPARACIÓN

• El compilado es más rápido en ejecución, porque el análisis se hace una sola vez.
• El interpretado es más rápido de desarrollar, porque no hay ciclo de compilación.
• El compilado detecta errores antes de ejecutar; el interpretado, solo cuando llega la línea.
• El interpretado es más portátil: basta llevar el intérprete.

LOS ENFOQUES HÍBRIDOS

Casi ningún sistema real es puro. Java y C# compilan a un código intermedio que una máquina virtual interpreta, y esa máquina compila a código nativo las partes calientes en tiempo de ejecución. Python compila a bytecode y lo interpreta.

La compilación en tiempo de ejecución tiene una ventaja que la estática no puede tener: conoce los datos reales y puede optimizar en función de ellos.

LAS FASES DEL COMPILADOR

1. Análisis léxico — de caracteres a tokens. Autómatas finitos.

2. Análisis sintáctico — de tokens a árbol. Gramáticas y autómatas de pila.

3. Análisis semántico — tipos, declaraciones, ámbitos. Tabla de símbolos.

4. Generación de código intermedio.

5. Optimización.

6. Generación de código objetivo.

LAS TRES PRIMERAS SON ESTE CURSO

El análisis léxico usa el nivel 3 de la jerarquía de Chomsky y el sintáctico el nivel 2. El semántico no cabe en ninguno de los dos: verificar que una variable esté declarada antes de usarse no es libre de contexto, y por eso se resuelve con estructuras auxiliares y no con la gramática.

EL ÁRBOL SINTÁCTICO ABSTRACTO

El árbol de derivación contiene detalles irrelevantes para la ejecución, como los paréntesis y los nodos de un solo hijo. El árbol sintáctico abstracto conserva solo la estructura significativa, y es sobre él que operan las fases posteriores.

UN INTÉRPRETE DE ÁRBOL

La forma más simple de intérprete recorre el árbol sintáctico abstracto en postorden y evalúa cada nodo con los valores de sus hijos. Es exactamente el recorrido postorden de un árbol de expresión, y en dos páginas de código se tiene una calculadora funcional.

EJERCICIO

Escribir un intérprete de expresiones aritméticas que construya el árbol y lo evalúe recursivamente.