Compilateur à partir de zéro : lexer parser inférence de type

Construire un Compilateur à Partir de Zéro : L'Expérience d'un Débutant Sans Connaissances Approfondies

Un compilateur est construit en étapes : analyseur lexical, analyseur syntaxique, inférence de types, préparation et génération de code. L'auteur, sans expérience préalable en construction de compilateurs, a commencé par étudier un projet open-source en C# avec une sémantique similaire à Rust. Plutôt que de modifier du code existant, il a tout implémenté à partir de zéro en apprenant les bases. Le processus n'était pas strictement descendant ou ascendant—les étapes ont été retravaillées plusieurs fois en raison des interdépendances.

Le flux de données suit ce schéma : code source → tokens → AST → AST typé → AST préparé → IR LLVM.

Analyseur Lexical et Syntaxique : Gérer les Ambiguïtés

L'analyseur lexical et syntaxique ont été adaptés d'un projet externe avec un analyseur LR(1). Des problèmes sont apparus avec les génériques : des expressions comme var a = Test < b > c; nécessitent une anticipation de plus d'un token pour distinguer les paramètres de template des comparaisons. Le LR(1) standard ne peut pas gérer cela sans contexte.

Un cas plus complexe est var a = Test < b > (c);. De telles ambiguïtés sont reportées à l'étape d'inférence de types. L'analyseur génère des nœuds AST avec gestion d'erreurs si les tokens ne correspondent pas au format attendu.

Inférence de Types : Parcours Multi-Pass de l'AST

L'inférence de types nécessite plusieurs passes sur l'AST en raison des dépendances entre les déclarations dans différents fichiers. La séquence :

• Traitement des déclarations de types de haut niveau (écriture dans la portée du namespace).
• Analyse des paramètres génériques et de leurs contraintes.
• Gestion de l'héritage.
• Délégués, types imbriqués, fonctions.
• Champs, propriétés, initialiseurs.
• Attributs.
• Ensuite seulement—les corps de fonctions.

Les génériques ont causé les principales difficultés. Exemple de génération récursive :

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

Le compilateur bouclait, créant un Test<E> infini. Résolu avec des contraintes : les champs/propriétés statiques avec paramètres génériques de classe sont interdits (public static T CoolField; n'est pas autorisé). Cela évite les conflits lors de l'édition des liens.

Les opérations pour différents types et les méthodes virtuelles/abstraites ont nécessité des ajustements.

Préparation des Types pour la Génération de Code

Une étape supplémentaire transforme l'AST pour faciliter la génération d'IR :

• Lambdas et Clôtures : Des classes synthétiques sont générées pour capturer le contexte. Exemple :

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

Transformé en :

public class __SyntheticClass0
{
    public int a;
    public int b;
    public void Lambda0()
    {
        Console.WriteLine($"Résultat : {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;
    }
}

• Génération de get/set pour les propriétés.
• Remplacement des accès aux propriétés par des appels.
• Élimination du code mort (sauf pour les bibliothèques).
• Constructeurs statiques.
• Conversion des classes en pointeurs.
• Ajout de tables virtuelles (vtables).

Génération de Code en IR LLVM

La génération d'IR LLVM est simplifiée par la préparation : les détails spécifiques à la plateforme (setjmp, va_list) sont résolus tôt. Les principaux problèmes sont l'édition des liens et les génériques.

L'interdiction des champs génériques statiques est justifiée par les dépendances des bibliothèques. Dans le schéma A → B(int), A → C(int) → App, chaque bibliothèque génère son propre SomeType<int>. Les changements dans B ne sont pas synchronisés avec C, et l'éditeur de liens ne sait pas lequel choisir.

Autres nuances : underscores dans les noms globaux pour Windows x86 (résolu par l'éditeur de liens LLVM), vtables. La syntaxe IR LLVM est rapidement maîtrisée après la préparation de l'AST.

Points Clés à Retenir

• Les génériques nécessitent une conception minutieuse : anticipation dans l'analyseur, inférence de types multi-pass, contraintes sur les éléments statiques.
• L'étape de préparation avant l'IR est cruciale pour les pointeurs, lambdas et le code mort.
• LLVM simplifie le développement multiplateforme mais n'élimine pas les conflits d'édition des liens.
• Le développement parallèle des étapes conduit à des réécritures—il vaut mieux commencer par un sous-ensemble simple du langage.
• Les classes synthétiques pour les clôtures préservent la sémantique sans connaissances approfondies des clôtures.

— Editorial Team