Revisiter Let’s Build a Compiler

• Le projet réimplémente le tutoriel « Let’s Build a Compiler » de Jack Crenshaw, publié entre 1988 et 1995, en Python et WebAssembly.
• L’original utilisait Pascal et l’assembleur Motorola 68000, mais ce travail le transforme en code exécutable dans un environnement moderne.
• Le cœur du tutoriel est la mise en œuvre directe d’un analyseur descendant récursif (recursive-descent parser) et une approche qui génère du code assembleur réel dès les premières étapes.
• La méthode de Crenshaw repose sur la traduction dirigée par la syntaxe (syntax-directed translation), mais montre ses limites au stade du traitement des types.
• Cette réimplémentation est notable car elle restaure ce classique sous une forme que les développeurs modernes peuvent exécuter et expérimenter directement.

---

Contexte du tutoriel classique

• Le « Let’s Build a Compiler » de Jack Crenshaw, publié entre 1988 et 1995, est un guide d’initiation à la construction de compilateurs qui reste fréquemment cité aujourd’hui.
  • Le texte original est rédigé en Pascal et produit du code assembleur Motorola 68000.
  • Même en 2025, 35 ans plus tard, il continue d’être régulièrement évoqué, notamment sur Hacker News.
• L’auteur de l’article l’a découvert en 2003 et en a été impressionné; en 2025, il l’a ensuite remis en forme en Python et WebAssembly.

Réécriture en Python et WebAssembly

• Plutôt qu’une simple lecture, le compilateur du tutoriel a été traduit en Python et implémenté pour générer de la WebAssembly (WASM).
• Le résultat est publié dans le dépôt GitHub (eliben/letsbuildacompiler).
  • Le fichier TUTORIAL.md explique comment chaque partie de l’original est mappée vers du code Python.
  • Les lecteurs peuvent tester du code directement exécutable tout en suivant le tutoriel original.

Exemple de langage KISS et génération WASM

• Il présente le résultat de la compilation, avec le compilateur Python, d’un programme exemple du langage KISS conçu par Crenshaw.
  • L’exemple inclut procedure, des boucles while ainsi que le passage par valeur et par référence.
• Le texte WASM généré contient une logique de gestion des paramètres passés par référence (by-reference parameter), avec très peu d’optimisations appliquées.
• La partie où la variable globale X est renvoyée implicitement depuis la fonction main constitue un dispositif pratique pour les tests.
• Le code WASM généré est utilisé dans des tests de validation des résultats attendus par exécution réelle.

Atouts du tutoriel

• Le tutoriel de Crenshaw construit progressivement un analyseur descendant récursif, en mettant l’accent sur la génération de code réellement opérationnel plutôt que sur une théorie trop complexe.
  • À l’époque, lex et yacc étaient considérés comme des standards, mais la simplicité et la clarté d’un parseur écrit à la main ont eu un impact majeur.
  • Par la suite, pendant 20 ans, l’auteur est devenu adepte des analyseurs descendants récursifs faits à la main.
• Alors que la plupart des cours de l’époque se concentraient sur l’analyse syntaxique, Crenshaw abordait la génération de code assembleur dès les premières phases.

Limites et améliorations possibles

• Le tutoriel utilise la traduction dirigée par la syntaxe (syntax-directed translation) pour générer directement le code pendant l’analyse syntaxique.
  • Cette approche est utile pour l’apprentissage, mais elle a la limite que, sans disposer au préalable des informations de type, il est difficile d’optimiser.
• À partir de la partie 14, où sont introduits les types, il apparaît qu’une approche structurée basée sur une représentation intermédiaire (IR) ou un AST est nécessaire.
• Il n’est pas précisé pourquoi Crenshaw a interrompu le tutoriel après la partie 14, mais une relation possible avec cette limite est évoquée.
• L’auteur considère qu’une approche où la partie 14 sert de pivot, avec génération d’un AST suivie de la vérification des types et de la génération de code, serait plus adaptée.

Conclusion

• Le tutoriel original conserve une lisibilité et une utilité remarquables comme introduction à la construction de compilateurs.
• Cette version Python/WASM complète l’implémentation pour permettre aux développeurs modernes d’apprendre sans dépendre de technologies obsolètes.
• Mise à disposition via le dépôt GitHub, elle permet à chacun de faire des essais et est saluée comme une réinterprétation moderne offrant une expérience concrète de la structure d’un compilateur.

[GN⁺]

Discussions sur Hacker News

• J’aime ce tutoriel qui ne s’enlise pas dans les détails du frontend et génère dès le départ du code assembleur fonctionnel
  L’approche de Ghuloum est particulièrement séduisante : partir d’une toute petite portion du langage, puis étendre progressivement l’ensemble
  Un bon livre que j’ai découvert récemment est celui-ci ; même si C et x86 ne sont pas des cibles idéales pour les débutants, c’était une excellente ressource pour construire un premier compilateur
  À noter que l’article de Ghuloum se trouve ici

  • C’est un cas rare, mais je pense que c’est un exemple où l’approche académique ne correspond pas vraiment à la pratique
    Autrefois, le parsing était la partie la plus importante, donc les cursus étaient construits autour de ça ; aujourd’hui, ce qui compte davantage, c’est la manière d’implémenter les fonctionnalités du langage
    Même si on écrit soi-même un compilateur, on vit désormais à une époque où il suffit de dire : « Claude, génère-moi un parser en descente récursive pour cette grammaire », et on obtient presque le bon résultat du premier coup
  • J’y ai senti la différence entre chercheurs académiques et développeurs en production
    Les premiers ont tendance à raisonner en couches (layers), les seconds en pipeline (pipes)
    L’approche en couches donne du code qui se compile, mais difficile à exécuter, tandis que l’approche en pipeline s’exécute facilement mais manque de structure
    Au final, l’essentiel est de découper le développement en unités minimales exécutables

• Je trouve que ce texte vise vraiment juste
  Je m’intéressais déjà aux compilateurs avant l’université, et cette ressource était l’introduction la plus accessible que j’aie trouvée
  À 17 ans, en construisant moi-même un parser en descente récursive, j’ai compris que même un problème qui paraît complexe devient simple si on le découpe en primitives adaptées

  • « Découper un problème en primitives adaptées » est le vrai cœur de la programmation
    On trouve beaucoup de ressources sur les algorithmes, mais très peu sur la manière d’aborder un problème à travers ses primitives
  • La descente récursive n’est pas seulement une manière d’écrire un parser, c’est aussi une leçon de conception logicielle
    Autrefois, les parsers à base de tables comme yacc dominaient, mais aujourd’hui la descente récursive est plus pratique et plus flexible
    La génération de code par les LLM a encore facilité cette approche
    Pour un compilateur jouet à vocation pédagogique, on peut tout à fait ignorer l’AST, l’IR et les optimisations, et passer directement à la génération de code
    Dans le passé, en entreprise, quand nous avions créé un outil de test prenant en charge un sous-ensemble de C, nous faisions retourner au parser une structure de données exécutable au lieu de générer du code
    Par exemple, une classe ForLoopStatement contenait testExpression, puis sa méthode Execute() l’appelait directement
  • L’article de 1971 de Niklaus Wirth, Program Development by Stepwise Refinement, est un classique fondateur de cette manière de penser
    C’est aussi un article important, cité dans The Mythical Man-Month de Fred Brooks
  • De nos jours, dès que j’ai besoin de parsing, j’utilise des parser combinators
    C’est conceptuellement très naturel et élégant

• L’explication selon laquelle le tutoriel de Jack Crenshaw utilise une approche de syntax-directed translation m’a intrigué
  Je me demande si cela signifie simplement compilateur en un seul passage, ou s’il s’agit d’un concept plus précis
  Je comprends qu’il soit difficile de faire des optimisations fondées sur les types dans un langage statiquement typé, mais j’aimerais savoir s’il y a aussi des limites au niveau de la vérification de types

  • Si le langage cible suit une règle de déclaration avant utilisation et n’a pas d’inférence de types complexe, on peut faire des optimisations fondées sur les types ou du constant folding
    En revanche, sans IR, des optimisations avancées comme LICM, CSE ou GVN sont impossibles
    Personnellement, je préfère une compilation en 2 passes par fonction : on construit d’abord l’IR, puis on génère immédiatement le code avant de jeter l’état, ce qui donne un résultat rapide et efficace
  • syntax-directed translation est un concept un peu plus précis : cela désigne le fait de générer le code au fur et à mesure de la lecture du code source
    Même un compilateur en un seul passage peut séparer les étapes et ne faire la génération de code qu’à la fin

• Le tutoriel de Crenshaw n’atteint pas un niveau vraiment pratique, mais il devient bien plus utile si on l’étend avec la technique de precedence climbing
  Un bon article sur le sujet est disponible ici

• J’ai revisité d’anciens fils sur « Let’s Build a Compiler »
  Il y a eu plusieurs passages sur HN entre 2007 et 2023
  En particulier, l’interview de Jack Crenshaw était très intéressante à lire, même s’il n’y avait pas de commentaires

  • Le quatrième lien n’est pas un texte de Crenshaw mais un autre article portant le même titre
  • L’interview de Crenshaw était vraiment excellente

• Petite présentation / promo d’un projet perso : cwerg.org
  Il utilise Python et la descente récursive pour le parsing, et sépare frontend et backend via un IR
  Il génère des binaires ELF pour x86 et ARM, avec un objectif d’usage réel
  En revanche, c’est complexe et pas du tout au format tutoriel

• J’ai aussi un souvenir nostalgique d’avoir appris le tutoriel de Jack Crenshaw sur le newsgroup USENET comp.compilers
  Pour info, ce groupe est toujours actif

• Pour une approche moderne des compilateurs, je recommande cet article de blog de Cornell

  • Grâce à LLVM, créer un compilateur est devenu étonnamment facile
    À chaque utilisation, j’ai l’impression d’ajouter quelques pierres au sommet d’une pyramide
  • Mais LLVM est aussi une approche indirecte, avec ses limites
    Les langages qui l’utilisent comme backend ont en commun des temps de compilation lents
    Zig en est conscient et développe son propre backend, tandis que Rust reste encore prisonnier de compilations lentes
    LLVM donne l’illusion que la complexité garantit la qualité et je pense que c’est une technologie qui affaiblit l’autonomie des développeurs
    Cela me rappelle aussi d’autres technologies populaires aux initiales similaires

• Pour des raisons proches, j’ai moi aussi écrit un tutoriel appelé tiny-optimizing-compiler
  C’est un exemple concis qui ne couvre que les étapes intermédiaires et le backend d’un compilateur
  Lien GitHub

  • Ce serait amusant de l’implémenter en Lean

• Quand j’étais jeune, j’avais imprimé ce tutoriel pour l’emporter partout et le lire
  Voir un compilateur se construire en si peu de temps était vraiment formidable
  Des ressources comme Beej’s Guide font partie des documents les plus précieux de la formation en informatique, mais elles ne sont pas reconnues à leur juste valeur