Vous voulez créer un compilateur ? Il suffit de lire ces deux articles (2008)
(prog21.dadgum.com)- La plupart des manuels sur les compilateurs sont vastes et très centrés sur la théorie, ce qui rend difficile pour un débutant d’implémenter un compilateur réellement fonctionnel
- Comme ressource pratique pour surmonter cela, la série « Let’s Build a Compiler! » de Jack Crenshaw est présentée ; elle traite d’un compilateur Pascal concis à passage unique
- Ce tutoriel favorise un apprentissage expérimental grâce à la combinaison de l’analyse syntaxique et de la génération de code, à un minimum d’optimisation, ainsi qu’à des versions en C et en Forth
- Le deuxième document, l’article « A Nanopass Framework for Compiler Education », présente une architecture de compilateur modulaire composée de nombreux passes simples
- Après avoir acquis une expérience concrète d’implémentation avec ces deux ressources, on peut, si nécessaire, approfondir avec des manuels traditionnels (Dragon Book)
La réalité de l’apprentissage des compilateurs et deux articles essentiels
- Les ouvrages existants sur les compilateurs sont jugés trop volumineux et difficiles, au point qu’il est compliqué pour un débutant d’écrire un compilateur réellement opérationnel
- La plupart des livres couvrent de très nombreux sujets, comme la transformation des expressions régulières ou la théorie des grammaires, sans offrir de point de départ vraiment pratique
- Cela contribue à créer des idées reçues et des mythes selon lesquels « les compilateurs sont difficiles »
- La série « Let’s Build a Compiler! » de Jack Crenshaw est présentée comme une ressource emblématique pour casser cette perception
- Ce tutoriel, lancé en 1988, traite d’un compilateur à passage unique de niveau Turbo Pascal
- Sa structure combine l’analyse syntaxique et la génération de code, avec seulement un minimum d’optimisation
- Il a été écrit à l’origine en Pascal, et il existe ensuite une version C ainsi qu’une traduction en Forth
- La version Forth facilite l’expérimentation et la compréhension grâce aux caractéristiques interactives du langage
- La limite de la série de Crenshaw est l’absence de représentation interne du programme (arbre de syntaxe abstraite, AST)
- En Pascal, la manipulation d’arbres était complexe et a donc été omise, mais elle peut être mise en œuvre facilement dans des langages de haut niveau comme Python, Ruby, Erlang, Haskell, Lisp
- Ces langages ont précisément été conçus pour manipuler des données sous forme d’arbres
- La deuxième ressource recommandée est l’article de Sarkar, Waddell, Dybvig
« A Nanopass Framework for Compiler Education »
- L’idée centrale est qu’« un compilateur est une série de processus qui transforment progressivement la représentation interne d’un programme »
- Il propose une structure composée de dizaines à centaines de transformations (passes) simples
- Chaque transformation est maintenue aussi simple que possible, en évitant le couplage entre les transformations
- Le framework définit explicitement les entrées et les sorties de chaque passe
- Le langage d’implémentation est Scheme, avec une validation à l’exécution basée sur le typage dynamique
- Après avoir écrit un vrai compilateur grâce à ces deux ressources, on peut, si nécessaire, poursuivre avec des manuels traditionnels comme le Dragon Book
- Mais ces deux ressources suffisent déjà à acquérir une expérience pratique de création de compilateurs
1 commentaires
Commentaires sur Hacker News
The Art of Computer Programming de Donald Knuth est toujours en cours d’écriture, et il est désormais peu probable qu’il traite du sujet des compilateurs
Je ne suis pas d’accord avec l’auteur. Le chapitre 2 du Dragon Book (par Aho et al.) se suffit à lui-même comme introduction aux compilateurs
Une autre excellente introduction est Compilers de Niklaus Wirth, qui en moins de 100 pages contient le code source d’un compilateur complet avec des explications claires
C’est avec ces deux livres que j’ai appris assez pour écrire moi-même un compilateur au lycée
Je pense qu’un livre plus pratique, qui suit concrètement la construction d’un vrai compilateur, est bien meilleur
Des ressources sont regroupées dans ce lien
La 2e édition ajoute l’analyse de flot de données, mais le format SSA (Static Single Assignment), au cœur des compilateurs modernes comme GCC et LLVM, n’occupe qu’une seule page
Pour construire un backend moderne, il faut étudier la théorie SSA séparément
Voir la page officielle de TAOCP
L’article d’Abdulaziz Ghuloum An Incremental Approach to Compiler Construction
casse l’idée que « les compilateurs sont magiques » et montre qu’on peut écrire un compilateur aussi facilement qu’un interpréteur
Il décrit en détail, étape par étape, la construction d’un compilateur qui prend en charge une grande partie de Scheme et génère de l’assembleur pour Intel x86
Récemment, les techniques de compilation ont beaucoup progressé avec les méta-compilateurs, la compilation adaptative (Adaptive Compilation) et les compilateurs JIT
Le groupe de recherche VPRI d’Alan Kay s’intéresse à ces problèmes de complexité
Ressources associées : article sur Ometa, vidéo sur l’Adaptive Compilation, conférence d’Alan Kay
J’ai entendu un bon conseil pour lire des livres : un livre est accessible en accès aléatoire (random access), comme la RAM
Si on ne lit que les parties nécessaires, même un gros livre paraît moins intimidant
Cela dit, cette approche ne marche pas quand on ne sait pas encore ce qu’on ignore. D’où l’importance des introductions légères
Aujourd’hui, Crafting Interpreters est souvent recommandé
Le lien vers l’article sur Nanopass est cassé
C’est pourquoi j’ai fait une antisèche qui résume l’essentiel de Crafting Interpreters
Le livre n’est pas un simple manuel, mais un ouvrage d’apprentissage fondé sur l’expérience, où l’on sent le plaisir de l’auteur, y compris dans des choses comme le pattern visitor
En ce moment, je construis un compilateur jouet pour le plaisir
Au lieu d’une théorie du parsing complexe ou d’un DSL, j’utilise les parser combinators de Megaparsec
La logique de parsing est claire, facile à réutiliser, et évite les complications de la séparation traditionnelle lexer/parser
Il y a moins de bugs, de meilleurs diagnostics d’erreur, et la plupart des langages (C#, Rust, etc.) utilisent aussi cette approche
tree-sitter est excellent lui aussi, mais il a beaucoup de dépendances. La descente récursive permet au contraire une implémentation concise sans dépendances
L’avantage de l’approche par parser combinators est que lexer et parser peuvent tous deux être traités avec le même type de parseur
Cela permet de gérer proprement les espaces et les problèmes de tokenisation
Le lien mort vers l’article sur Nanopass est consultable ici
Ce qui m’a appris les compilateurs, c’était l’article sur le compilateur Tiny Pascal dans BYTE Magazine en 1978
J’ai appris l’optimisation dans un cours d’été donné à Stanford par Ullman et Hennessy
Mon générateur de code était une approche originale que j’avais conçue moi-même
J’ai le Dragon Book, mais je ne l’ai en réalité jamais lu
Le point essentiel de l’approche Nanopass n’est pas le nombre de passes, mais le fait de définir pour chaque passe un langage d’entrée et de sortie explicite
Cette manière de penser, très structurée, permet d’attraper beaucoup de bugs avant l’exécution
Le tutoriel de Crenshaw est excellent lui aussi, mais cette gestion des invariants du langage est ce qui fait la différence pour construire un compilateur réellement extensible
À l’époque d’UC Irvine, je me souviens avoir implémenté un compilateur optimisant dans le cours CS241 du professeur Michael Franz, élève de Niklaus Wirth
Le devoir consistait à générer du bytecode pour une machine virtuelle appelée DLX
Des ressources associées sont disponibles dans cette description de l’architecture DLX et cette image de référence sur un algorithme d’allocation de registres