Compilador desde cero: lexer parser type inference

Construyendo un compilador desde cero: La experiencia de un principiante sin conocimientos profundos

Un compilador se construye por etapas: lexer, parser, inferencia de tipos, preparación y generación de código. El autor, sin experiencia previa en construcción de compiladores, comenzó estudiando un proyecto de código abierto en C# con semántica similar a Rust. En lugar de modificar código existente, implementó todo desde cero mientras aprendía los conceptos básicos. El proceso no fue estrictamente descendente o ascendente: las etapas se rehicieron múltiples veces debido a interdependencias.

El flujo de datos sigue este esquema: código fuente → tokens → AST → AST tipado → AST preparado → LLVM IR.

Lexer y Parser: Manejo de ambigüedades

El lexer y parser se adaptaron de un proyecto externo con un parser LR(1). Surgieron problemas con genéricos: expresiones como var a = Test < b > c; requieren mirar más de un token hacia adelante para distinguir parámetros de plantilla de comparaciones. El LR(1) estándar no puede manejar esto sin contexto.

Un caso más complejo es var a = Test < b > (c);. Tales ambigüedades se posponen a la etapa de inferencia de tipos. El parser genera nodos AST con manejo de errores si los tokens no coinciden con el formato esperado.

Inferencia de tipos: Recorrido múltiple del AST

La inferencia de tipos requiere múltiples pasadas sobre el AST debido a dependencias entre declaraciones en diferentes archivos. La secuencia:

• Procesar declaraciones de tipos de nivel superior (escritura en ámbito de espacio de nombres).
• Analizar parámetros genéricos y sus restricciones.
• Manejar herencia.
• Delegados, tipos anidados, funciones.
• Campos, propiedades, inicializadores.
• Atributos.
• Solo entonces: cuerpos de funciones.

Los genéricos causaron las principales dificultades. Ejemplo de generación recursiva:

public class Test<T> 
{ 
    public static Test<E> GetTest<E>(); 
}

El compilador entró en bucle, creando infinitos Test<E>. Se resolvió con restricciones: campos/propiedades estáticas con parámetros genéricos de clase están prohibidos (public static T CoolField; no está permitido). Esto evita conflictos durante el enlazado.

Las operaciones para diferentes tipos y métodos virtuales/abstractos requirieron refinamientos.

Preparación de tipos para generación de código

Una etapa adicional transforma el AST para facilitar la generación de IR:

• Lambdas y Closures: Se generan clases sintéticas para capturar contexto. Ejemplo:

public class Test
{
    public Action ReturnFunction(int a, int b)
    {
        var action = () => 
        { 
            Console.WriteLine($"Result: {a + b}"); 
        };
        return action;
    }
}

Transformado en:

public class __SyntheticClass0
{
    public int a;
    public int b;
    public void Lambda0()
    {
        Console.WriteLine($"Result: {a + b}"); 
    }
}

public class Test
{
    public Action ReturnFunction(int a, int b)
    {
        __SyntheticClass0 tmpVar = new __SyntheticClass0();
        tmpVar.a = a;
        tmpVar.b = b;
        return tmpVar.Lambda0;
    }
}

• Generación de get/set para propiedades.
• Reemplazo de accesos a propiedades con llamadas.
• Eliminación de código muerto (excepto para bibliotecas).
• Constructores estáticos.
• Conversión de clases a punteros.
• Adición de tablas virtuales (vtables).

Generación de código a LLVM IR

La generación de LLVM IR se simplifica por la preparación: detalles específicos de plataforma (setjmp, va_list) se resuelven temprano. Los principales problemas son enlazado y genéricos.

Prohibir campos genéricos estáticos se justifica por dependencias de bibliotecas. En el esquema A → B(int), A → C(int) → App, cada biblioteca genera su propio SomeType<int>. Cambios en B no se sincronizan con C, y el enlazador no sabe cuál elegir.

Otros matices: guiones bajos en nombres globales para Windows x86 (resuelto por el enlazador LLVM), vtables. La sintaxis de LLVM IR se domina rápidamente después de la preparación del AST.

Conclusiones clave

• Los genéricos requieren diseño cuidadoso: mirada adelante en el parser, inferencia de tipos multipaso, restricciones en elementos estáticos.
• La etapa de preparación antes del IR es crítica para punteros, lambdas y código muerto.
• LLVM simplifica el desarrollo multiplataforma pero no elimina conflictos de enlazado.
• El desarrollo paralelo de etapas lleva a reescrituras: es mejor comenzar con un subconjunto simple del lenguaje.
• Las clases sintéticas para closures preservan semántica sin conocimiento profundo de closures.

— Editorial Team