Compiler von Grund auf: lexer parser type inference

Einen Compiler von Grund auf bauen: Erfahrungen eines Anfängers ohne tiefes Wissen

Ein Compiler wird in Phasen aufgebaut: Lexer, Parser, Typinferenz, Vorbereitung und Codegenerierung. Der Autor, ohne Vorerfahrung im Compilerbau, begann mit dem Studium eines Open-Source-C#-Projekts mit Semantik ähnlich zu Rust. Anstatt bestehenden Code zu modifizieren, implementierte er alles von Grund auf, während er die Grundlagen lernte. Der Prozess war nicht streng top-down oder bottom-up – Phasen wurden aufgrund von Abhängigkeiten mehrfach überarbeitet.

Der Datenfluss folgt diesem Schema: Quellcode → Tokens → AST → typisierter AST → vorbereiteter AST → LLVM IR.

Lexer und Parser: Umgang mit Mehrdeutigkeiten

Der Lexer und Parser wurden von einem externen Projekt mit einem LR(1)-Parser übernommen. Probleme traten mit Generics auf: Ausdrücke wie var a = Test < b > c; erfordern einen Vorausblick von mehr als einem Token, um Template-Parameter von Vergleichen zu unterscheiden. Standard-LR(1) kann dies ohne Kontext nicht bewältigen.

Ein komplexerer Fall ist var a = Test < b > (c);. Solche Mehrdeutigkeiten werden auf die Typinferenzphase verschoben. Der Parser erzeugt AST-Knoten mit Fehlerbehandlung, wenn Tokens nicht dem erwarteten Format entsprechen.

Typinferenz: Mehrfaches Durchlaufen des AST

Typinferenz erfordert mehrere Durchläufe über den AST aufgrund von Abhängigkeiten zwischen Deklarationen in verschiedenen Dateien. Die Abfolge:

• Verarbeitung von Top-Level-Typdeklarationen (Schreiben in den Namensraumbereich).
• Parsen von Generics-Parametern und ihren Einschränkungen.
• Behandlung von Vererbung.
• Delegates, verschachtelte Typen, Funktionen.
• Felder, Eigenschaften, Initialisierer.
• Attribute.
• Erst dann – Funktionskörper.

Generics verursachten die Hauptschwierigkeiten. Beispiel für rekursive Erzeugung:

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

Der Compiler geriet in eine Schleife und erzeugte unendlich viele Test<E>. Gelöst mit Einschränkungen: Statische Felder/Eigenschaften mit Klassen-Generics-Parametern sind verboten (public static T CoolField; ist nicht erlaubt). Dies verhindert Konflikte beim Linken.

Operationen für verschiedene Typen und virtuelle/abstrakte Methoden erforderten Verfeinerungen.

Vorbereitung von Typen für die Codegenerierung

Eine zusätzliche Phase transformiert den AST für einfachere IR-Generierung:

• Lambdas und Closures: Synthetische Klassen werden erzeugt, um Kontext zu erfassen. Beispiel:

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

Transformiert in:

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;
    }
}

• Generierung von Get/Set für Eigenschaften.
• Ersetzen von Eigenschaftszugriffen durch Aufrufe.
• Entfernung von totem Code (außer bei Bibliotheken).
• Statische Konstruktoren.
• Umwandlung von Klassen in Zeiger.
• Hinzufügen von virtuellen Tabellen (vtables).

Codegenerierung zu LLVM IR

LLVM-IR-Generierung wird durch Vorbereitung vereinfacht: Plattformspezifische Details (setjmp, va_list) werden frühzeitig gelöst. Hauptprobleme sind Linking und Generics.

Das Verbot statischer Generics-Felder ist durch Bibliotheksabhängigkeiten gerechtfertigt. Im Schema A → B(int), A → C(int) → App generiert jede Bibliothek ihr eigenes SomeType<int>. Änderungen in B sind nicht mit C synchronisiert, und der Linker weiß nicht, welches zu wählen ist.

Andere Nuancen: Unterstriche in globalen Namen für x86 Windows (gelöst durch den LLVM-Linker), vtables. Die LLVM-IR-Syntax wird nach AST-Vorbereitung schnell gemeistert.

Wichtige Erkenntnisse

• Generics erfordern sorgfältiges Design: Vorausblick im Parser, mehrfache Typinferenz, Einschränkungen bei statischen Elementen.
• Die Vorbereitungsphase vor der IR ist entscheidend für Zeiger, Lambdas und toten Code.
• LLVM vereinfacht plattformübergreifende Entwicklung, beseitigt aber nicht Linking-Konflikte.
• Parallele Entwicklung von Phasen führt zu Überarbeitungen – es ist besser, mit einer einfachen Teilmenge der Sprache zu beginnen.
• Synthetische Klassen für Closures bewahren Semantik ohne tiefes Wissen über Closures.

— Editorial Team