Kompilator od zera: lexer parser wnioskowanie typów

Tworzenie kompilatora od zera: doświadczenia początkującego bez głębokiej wiedzy

Kompilator buduje się etapami: lekser, parser, wnioskowanie typów, przygotowanie i generowanie kodu. Autor, nie mając doświadczenia w tworzeniu kompilatorów, zaczął od analizy otwartego projektu w C#, podobnego semantycznie do Rusta. Zamiast modyfikować cudzy kod, musiał zaimplementować wszystko od podstaw, równolegle ucząc się podstaw. Proces nie przebiegał ściśle odgórnie ani oddolnie — etapy były wielokrotnie przerabiane z powodu wzajemnych zależności.

Przepływ danych przebiega według schematu: kod źródłowy → tokeny → AST → typowane AST → przygotowane AST → LLVM IR.

Lekser i parser: obsługa niejednoznaczności

Lekser i parser zostały zaadaptowane z zewnętrznego projektu z parserem LR(1). Problemy pojawiły się z generykami: wyrażenia typu var a = Test < b > c; wymagają lookahead większego niż jeden token, aby odróżnić parametry szablonowe od porównań. Standardowy LR(1) nie radzi sobie bez kontekstu.

Bardziej złożony przypadek — var a = Test < b > (c);. Takie niejednoznaczności są odkładane na etap wnioskowania typów. Parser generuje węzły AST z obsługą błędów, jeśli tokeny nie pasują do oczekiwanego formatu.

Wnioskowanie typów: wieloetapowe przechodzenie AST

Wnioskowanie typów wymaga kilku przejść przez AST z powodu zależności między deklaracjami w różnych plikach. Sekwencja:

• Przetwarzanie deklaracji typów wysokiego poziomu (zapis w zakresie namespace).
• Analiza parametrów generycznych i ich ograniczeń.
• Obsługa dziedziczenia.
• Delegaty, typy zagnieżdżone, funkcje.
• Pola, właściwości, inicjalizatory.
• Atrybuty.
• Dopiero potem — ciała funkcji.

Generyki sprawiły najwięcej trudności. Przykład rekurencyjnej generacji:

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

Kompilator zapętlał się, tworząc nieskończone Test<E>. Rozwiązano ograniczeniami: statyczne pola/właściwości z parametrami generycznymi klasy są zabronione (public static T CoolField; niedopuszczalne). Zapobiega to konfliktom podczas linkowania.

Operacje dla różnych typów oraz metody wirtualne/abstrakcyjne wymagały dopracowania.

Przygotowanie typów do generowania kodu

Dodatkowy etap przekształca AST dla ułatwienia generowania IR:

• Lambdy i domknięcia: generowane są syntetyczne klasy do przechwytywania kontekstu. Przykład:

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

Przekształcane w:

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

• Generacja get/set dla właściwości.
• Zastępowanie odwołań do właściwości wywołaniami.
• Eliminacja martwego kodu (oprócz bibliotek).
• Konstruktory statyczne.
• Przekształcanie klas na wskaźniki.
• Dodawanie tablic wirtualnych (vtables).

Generowanie kodu w LLVM IR

Generowanie LLVM IR jest uproszczone przez przygotowanie: szczegóły specyficzne dla platformy (setjmp, va_list) są rozwiązywane na wczesnych etapach. Główne problemy — linkowanie i generyki.

Zakaz statycznych pól generycznych uzasadniono zależnościami bibliotek. W schemacie A → B(int), A → C(int) → App każda biblioteka generuje swój SomeType<int>. Zmiany w B nie są synchronizowane z C, linker nie wie, który wybrać.

Inne niuanse: podkreślenia w nazwach globalnych pod x86 Windows (rozwiązane przez linker LLVM), vtables. Składnia LLVM IR jest szybko przyswajana po przygotowaniu AST.

Co jest ważne

• Generyki wymagają ostrożnego projektowania: lookahead w parserze, wieloetapowe wnioskowanie typów, ograniczenia na statykę.
• Etap przygotowawczy przed IR jest kluczowy dla wskaźników, lambd i martwego kodu.
• LLVM ułatwia wieloplatformowość, ale nie eliminuje konfliktów linkowania.
• Równoległe rozwijanie etapów prowadzi do przepisywania — lepiej zacząć od prostego podzbioru języka.
• Syntetyczne klasy dla domknięć zachowują semantykę bez głębokiej wiedzy o closure.

— Editorial Team