Teoría del compilador
¿Qué es un compilador?
Un compilador es un programa que traduce código escrito en un lenguaje fuente (de alto nivel) a código en un lenguaje destino (usualmente código máquina o código ensamblador). El proceso de compilación no solo traduce, sino que también verifica la corrección del programa en múltiples niveles.
La diferencia entre un compilador y un intérprete es que el compilador genera código ejecutable de forma separada, mientras que el intérprete ejecuta el programa directamente línea por línea sin generar código intermedio persistente.
¿Qué es una gramática formal?
Una gramática formal es un conjunto de reglas de producción que definen el lenguaje. Una gramática libre de contexto (CFG) tiene la forma:
A → α
Donde A es un no-terminal (símbolo abstracto) y α es una secuencia de terminales y/o no-terminales. Los terminales son los tokens del lexer. Los no-terminales representan construcciones gramaticales abstractas (sentencias, expresiones, etc.).
FIRST y FOLLOW
FIRST(A)
El conjunto FIRST de un no-terminal A es el conjunto de terminales que pueden aparecer al inicio de cualquier cadena derivable de A. Si A puede derivar la cadena vacía, ε pertenece a FIRST(A).
Algoritmo de cálculo (punto fijo):
- Si la producción es A → ε, añadir ε a FIRST(A).
- Si A → X₁X₂...Xₙ, añadir FIRST(X₁) - { ε } a FIRST(A). Si ε ∈ FIRST(X₁), añadir FIRST(X₂) - { ε }, etc.
- Si todos los Xᵢ tienen ε en su FIRST, añadir ε a FIRST(A).
- Repetir hasta que no haya cambios.
FOLLOW(A)
El conjunto FOLLOW de A es el conjunto de terminales que pueden aparecer inmediatamente después de A en alguna forma sentencial. EOF siempre está en FOLLOW del símbolo inicial.
Reglas de cálculo:
- Añadir EOF a FOLLOW(S) donde S es el símbolo inicial.
- Si existe A → αBβ, añadir FIRST(β) - { ε } a FOLLOW(B).
- Si β puede derivar ε (o B es el último símbolo), añadir FOLLOW(A) a FOLLOW(B).
- Repetir hasta que no haya cambios.
Tabla predictiva LL(1)
La tabla LL(1) M[A, a] indica qué producción usar cuando estamos intentando expandir el no-terminal A y el token actual es a.
Construcción:
- Para cada producción A → α y cada terminal a en FIRST(α): M[A, a] = A → α.
- Si ε ∈ FIRST(α), para cada b en FOLLOW(A): M[A, b] = A → α.
Si alguna celda tiene dos producciones, la gramática no es LL(1) y no puede ser analizada con un parser predictivo simple.
El parser LL(1) de pila
El parser LL(1) usa una pila explícita. Inicialmente la pila contiene [S, $] donde S es el símbolo inicial. El algoritmo:
- Si el tope de la pila es un terminal que coincide con el token actual, consumir ambos.
- Si el tope de la pila es un no-terminal A y el token actual es a, consultar M[A, a] y expandir A con esa producción (reemplazar A por la producción en la pila, en orden inverso).
- Si M[A, a] está vacío, hay un error sintáctico.
- Si la pila y la entrada son ambas $, el análisis fue exitoso.
El parser de Slang implementa este proceso usando recursión descendente, que es matemáticamente equivalente al parser de pila explícita.
Modo pánico (panic mode)
El modo pánico es una estrategia de recuperación de errores sintácticos. Cuando el parser encuentra un error, en lugar de abortar completamente:
- Registra el error con su posición y descripción.
- Descarta tokens de la entrada hasta encontrar un token ancla de sincronización.
- Los tokens ancla son puntos donde el estado del programa puede inferirse con confianza:
;,if,while,},EOF, etc. - Reanuda el análisis desde ese punto.
El resultado es que el compilador puede reportar múltiples errores en una sola ejecución, lo cual es indispensable para una experiencia de desarrollo real.
AST: Árbol de Sintaxis Abstracta
El AST es la representación en árbol de la estructura del programa, sin los detalles sintácticos redundantes (paréntesis, punto y coma, etc.). Cada nodo representa una construcción del programa:
- NodoPrograma: la raíz del árbol con todos los elementos de nivel superior.
- NodoDeclVariable: una declaración
let nombre: tipo = valor. - NodoBinario: operación binaria con operador izquierdo y derecho.
- NodoDeclFuncion: una función con parámetros, tipo de retorno y cuerpo.
- NodoIf/While/For: estructuras de control con condición y cuerpo.
- NodoLlamada: invocación de función con argumentos.
El AST es la representación que usan todas las fases posteriores: semántica, optimización e interpretación.
Tabla de símbolos
La tabla de símbolos es una estructura de datos que mapea nombres de entidades (variables, funciones) a su información semántica (tipo, alcance, parámetros, etc.).
Se implementa como una pila de diccionarios (uno por cada ámbito activo). Un alcance nuevo se crea al entrar a cada función o bloque de control. La búsqueda de un nombre recorre la pila desde el ámbito más interno hasta el global.
Fases 4, 5 y 6: Generación, Optimización y Código Máquina
Generación de código intermedio
Traduce el AST a una representación independiente de la arquitectura, como el código de tres direcciones (Three-Address Code, TAC) o el IR (Intermediate Representation) de LLVM. El TAC tiene instrucciones simples de la forma:t1 = a + b, if t1 goto L1, param a.
Esta representación separa la lógica del programa de los detalles de la arquitectura objetivo, facilitando la portabilidad y la optimización.
Optimización de código
Aplica transformaciones al código intermedio que mejoran el rendimiento sin cambiar el comportamiento del programa. Técnicas comunes:
- Propagación de constantes: reemplazar
x = 5; y = x + 3pory = 8en tiempo de compilación. - Eliminación de código muerto: remover código que nunca se ejecuta.
- Eliminación de subexpresiones comunes: calcular una expresión solo una vez si se usa varias veces.
- Desenrollar bucles: expandir el cuerpo de un bucle para reducir el overhead de la condición.
Generación de código final
Traduce el código intermedio optimizado a instrucciones reales del procesador objetivo (x86, ARM, etc.). Implica la asignación de registros (decidir qué variables van en registros del CPU), gestión del stack frame para llamadas a funciones, y emisión del binario ejecutable.
En Slang, estas tres fases son reemplazadas por el intérprete del AST, que ejecuta el programa directamente sin generar código máquina. Esto es suficiente para los propósitos educativos de esta herramienta.
El intérprete del AST de Slang
En lugar de generar código máquina, Slang implementa un intérprete que recorre el AST y evalúa cada nodo directamente:
- Los literales se evalúan a sus valores (42, "hola", true).
- Los identificadores buscan su valor en el entorno de ejecución.
- Las expresiones binarias evalúan ambos operandos y aplican el operador.
- Los bloques crean un nuevo entorno hijo para manejar el alcance.
- Las funciones crean un entorno propio, declaran los parámetros y ejecutan el cuerpo.
- El
returnusa una señal especial (SeñalReturn) para interrumpir la ejecución del bloque. print()escribe a la consola de salida de la interfaz.