Kompilátor od nuly: lexer parser inferování typů

Tvorba kompilátoru od nuly: zkušenost začátečníka bez hlubokých znalostí

Kompilátor se staví postupně: lexer, parser, odvozování typů, příprava a generování kódu. Autor, bez zkušeností v tvorbě kompilátorů, začal studiem otevřeného projektu v C#, který se podobá Rustu sémantikou. Místo úprav cizího kódu musel vše implementovat od nuly, přičemž se paralelně učil základy. Proces neprobíhal striktně shora dolů nebo zdola nahoru – fáze se mnohokrát přepracovávaly kvůli vzájemným závislostem.

Tok dat následuje schématu: zdrojový kód → tokeny → AST → typované AST → připravené AST → LLVM IR.

Lexer a parser: zpracování nejednoznačností

Lexer a parser byly adaptovány z externího projektu s LR(1)-parserem. Problémy nastaly s generiky: výrazy jako var a = Test < b > c; vyžadují lookahead více než jednoho tokenu, aby se odlišily parametry šablony od porovnání. Standardní LR(1) si bez kontextu neporadí.

Složitější případ – var a = Test < b > (c);. Takové nejednoznačnosti se odkládají na fázi odvozování typů. Parser generuje AST uzly s ošetřením chyb, pokud tokeny neodpovídají očekávanému formátu.

Odvozování typů: vícefázový průchod AST

Odvozování typů vyžaduje několik průchodů AST kvůli závislostem mezi deklaracemi v různých souborech. Posloupnost:

• Zpracování deklarací typů na nejvyšší úrovni (zápis do namespace scope).
• Analýza generických parametrů a jejich omezení.
• Zpracování dědičnosti.
• Delegáty, vnořené typy, funkce.
• Pole, vlastnosti, inicializátory.
• Atributy.
• Teprve poté – těla funkcí.

Generika způsobila hlavní potíže. Příklad rekurzivní generace:

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

Kompilátor se zacyklil, vytvářejíc nekonečné Test<E>. Řešeno omezeními: statická pole/vlastnosti s generickými parametry třídy jsou zakázány (public static T CoolField; není povoleno). Tím se předejde konfliktům při linkování.

Operace pro různé typy a virtuální/abstraktní metody vyžadovaly úpravy.

Příprava typů pro generování kódu

Další fáze transformuje AST pro usnadnění generování IR:

• Lambda výrazy a uzávěry: generují se syntetické třídy pro zachycení kontextu. Příklad:

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

Transformuje se na:

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

• Generování get/set pro vlastnosti.
• Nahrazení přístupů k vlastnostem voláními.
• Eliminace mrtvého kódu (kromě knihoven).
• Statické konstruktory.
• Převod tříd na ukazatele.
• Přidání virtuálních tabulek (vtables).

Generování kódu do LLVM IR

Generování LLVM IR je zjednodušeno přípravou: platformně specifické detaily (setjmp, va_list) se řeší v raných fázích. Hlavní problémy – linkování a generika.

Zákaz statických generických polí je odůvodněn závislostmi knihoven. Ve schématu A → B(int), A → C(int) → App každá knihovna generuje svůj SomeType<int>. Změny v B se nesynchronizují s C, linker neví, který vybrat.

Další nuance: podtržítka v názvech globálů pod x86 Windows (řešeno LLVM-linkerem), vtables. Syntaxe LLVM IR se rychle osvojí po přípravě AST.

Co je důležité

• Generika vyžadují opatrný design: lookahead v parseru, vícefázové odvozování typů, omezení na statiku.
• Přípravná fáze před IR je klíčová pro ukazatele, lambda výrazy a mrtvý kód.
• LLVM zjednodušuje multiplatformnost, ale nezbavuje linkovacích konfliktů.
• Paralelní vývoj fází vede k přepisům – lepší je začít s jednoduchou podmnožinou jazyka.
• Syntetické třídy pro uzávěry zachovávají sémantiku bez hlubokých znalostí o closure.

— Editorial Team