Comment écrire un compilateur très basique

214

Les compilateurs avancés, par exemple, gcccompilent les codes dans des fichiers lisibles par machine en fonction du langage dans lequel le code a été écrit (par exemple C, C ++, etc.). En fait, ils interprètent la signification de chaque code en fonction de la bibliothèque et des fonctions des langages correspondants. Corrige moi si je me trompe.

Je souhaite mieux comprendre les compilateurs en écrivant un compilateur très basique (probablement en C) pour compiler un fichier statique (par exemple, Hello World dans un fichier texte). J'ai essayé des tutoriels et des livres, mais tous sont des cas pratiques. Ils traitent de la compilation de codes dynamiques avec des significations liées au langage correspondant.

Comment puis-je écrire un compilateur de base pour convertir un texte statique en un fichier lisible par machine?

La prochaine étape consistera à introduire des variables dans le compilateur. imaginons que nous voulions écrire un compilateur qui ne compile que certaines fonctions d’un langage.

L'introduction de tutoriels et de ressources pratiques est très appréciée :-)

Googlebot
la source
Avez-vous essayé lex / flex et le yacc / bison?
mouviciel
15
@mouviciel: Ce n'est pas un bon moyen d'apprendre à construire un compilateur. Ces outils font un travail considérable pour vous, vous ne le faites donc jamais et vous ne savez pas comment faire.
Mason Wheeler
11
@Mat est intéressant, le premier de vos liens donne 404, alors que le second est maintenant marqué comme duplicata de cette question.
Ruslan

Réponses:

326

Intro

Un compilateur typique effectue les étapes suivantes:

  • Analyse: le texte source est converti en un arbre de syntaxe abstraite (AST).
  • Résolution des références à d'autres modules (C reporte cette étape jusqu'à la liaison).
  • Validation sémantique: élimination d'instructions syntaxiquement correctes qui n'ont aucun sens, par exemple code inaccessible ou déclarations en double.
  • Transformations équivalentes et optimisation de haut niveau: l'AST est transformé pour représenter un calcul plus efficace avec la même sémantique. Cela inclut, par exemple, le calcul précoce de sous-expressions communes et d'expressions constantes, l'élimination des affectations locales excessives (voir aussi SSA ), etc.
  • Génération de code: l'AST est transformé en code de bas niveau linéaire, avec sauts, allocation de registre, etc. Certains appels de fonction peuvent être intégrés à ce stade, certaines boucles déroulées, etc.
  • Optimisation des peepholes: le code de bas niveau est analysé pour détecter les inefficacités locales simples éliminées.

La plupart des compilateurs modernes (par exemple, gcc et clang) répètent encore une fois les deux dernières étapes. Ils utilisent un langage intermédiaire de bas niveau mais indépendant de la plate-forme pour la génération initiale du code. Ensuite, cette langue est convertie en code spécifique à la plate-forme (x86, ARM, etc.) faisant à peu près la même chose d'une manière optimisée pour la plate-forme. Cela inclut, par exemple, l'utilisation d'instructions vectorielles lorsque cela est possible, la réorganisation d'instructions pour augmenter l'efficacité de la prédiction de branche, etc.

Après cela, le code objet est prêt pour la liaison. La plupart des compilateurs de code natif savent comment appeler un éditeur de liens pour produire un exécutable, mais ce n'est pas une étape de compilation en soi. Dans des langages tels que Java et C #, la liaison peut être totalement dynamique, effectuée par la VM au moment du chargement.

Rappelez-vous les bases

  • Fais-le fonctionner
  • Le rendre beau
  • Le rendre efficace

Cette séquence classique s’applique à tous les développements logiciels, mais elle mérite d’être répétée.

Concentrez-vous sur la première étape de la séquence. Créez la chose la plus simple qui puisse fonctionner.

Lisez les livres!

Lisez le livre du dragon par Aho et Ullman. Ceci est classique et est encore tout à fait applicable aujourd'hui.

La conception du compilateur moderne est également appréciée.

Si cela vous pose trop de problèmes en ce moment, lisez d'abord quelques intros sur l'analyse; Les bibliothèques d'analyse comprennent généralement des intros et des exemples.

Assurez-vous que vous êtes à l'aise avec les graphiques, en particulier les arbres. Ces choses sont les choses dont les programmes sont faits au niveau logique.

Définissez bien votre langue

Utilisez la notation que vous voulez, mais assurez-vous d'avoir une description complète et cohérente de votre langue. Cela inclut à la fois la syntaxe et la sémantique.

Il est grand temps d'écrire des extraits de code dans votre nouvelle langue en tant que cas de test pour le futur compilateur.

Utilisez votre langue préférée

Écrire un compilateur en Python, en Ruby ou dans n’importe quel langage qui vous convient est tout à fait acceptable. Utilisez des algorithmes simples que vous comprenez bien. La première version ne doit pas nécessairement être rapide, efficace ou complète. Il doit seulement être suffisamment correct et facile à modifier.

Il est également correct d'écrire différentes étapes d'un compilateur dans différentes langues, si nécessaire.

Préparez-vous à écrire beaucoup de tests

Toute votre langue devrait être couverte par des cas de test; effectivement, il sera défini par eux. Familiarisez-vous avec votre framework de test préféré. Écrire des tests dès le premier jour. Concentrez-vous sur les tests «positifs» acceptant le code correct, par opposition à la détection de code incorrect.

Exécutez tous les tests régulièrement. Corrigez les tests brisés avant de continuer. Il serait dommage de se retrouver avec un langage mal défini qui ne puisse accepter un code valide.

Créer un bon analyseur

Les générateurs de parseurs sont nombreux . Choisissez ce que vous voulez. Vous pouvez également écrire votre propre analyseur à partir de rien, mais cela ne vaut que si la syntaxe de votre langue est extrêmement simple.

L'analyseur doit détecter et signaler les erreurs de syntaxe. Écrivez beaucoup de cas tests, à la fois positifs et négatifs; réutilisez le code que vous avez écrit en définissant la langue.

La sortie de votre analyseur est un arbre de syntaxe abstraite.

Si votre langage comporte des modules, la sortie de l'analyseur peut être la représentation la plus simple du "code objet" que vous générez. Il existe de nombreuses façons simples de déposer un arbre dans un fichier et de le recharger rapidement.

Créer un validateur sémantique

Très probablement, votre langage permet des constructions syntaxiquement correctes qui peuvent ne pas avoir de sens dans certains contextes. Un exemple est une déclaration en double de la même variable ou la transmission d'un paramètre d'un type incorrect. Le validateur détectera de telles erreurs en regardant l’arbre.

Le validateur résoudra également les références à d'autres modules écrits dans votre langue, chargera ces autres modules et les utilisera dans le processus de validation. Par exemple, cette étape s'assurera que le nombre de paramètres transmis à une fonction par un autre module est correct.

Encore une fois, écrivez et exécutez beaucoup de cas de test. Les cas triviaux sont aussi indispensables au dépannage que intelligents et complexes.

Générer du code

Utilisez les techniques les plus simples que vous connaissez. Il est souvent correct de traduire directement une construction de langage (comme une ifinstruction) en un modèle de code légèrement paramétré, semblable à un modèle HTML.

Encore une fois, ignorez l'efficacité et concentrez-vous sur la correction.

Ciblez une machine virtuelle de bas niveau indépendante de la plate-forme

Je suppose que vous ignorez les éléments de bas niveau, à moins que vous ne vous intéressiez vraiment aux détails spécifiques au matériel. Ces détails sont sanglants et complexes.

Vos options:

  • LLVM: permet une génération de code machine efficace, généralement pour x86 et ARM.
  • CLR: cible .NET, principalement sous x86 / Windows; a un bon JIT.
  • JVM: cible le monde Java, assez multiplateforme, a un bon JIT.

Ignorer l'optimisation

L'optimisation est difficile. Presque toujours, l'optimisation est prématurée. Générer un code inefficace mais correct. Implémentez l'ensemble du langage avant d'essayer d'optimiser le code résultant.

Bien sûr, des optimisations triviales sont acceptables. Mais évitez toute substance rusée et poilue avant que votre compilateur ne soit stable.

Et alors?

Si tout cela ne vous intimide pas trop, continuez! Pour un langage simple, chacune des étapes peut être plus simple que vous ne le pensez.

Voir un «bonjour» à partir d’un programme créé par votre compilateur pourrait en valoir la peine.

9000
la source
45
C'est l'une des meilleures réponses que j'ai jamais vues.
Gahooa
11
Je pense que vous avez manqué une partie de la question ... Le PO voulait écrire un compilateur très basique . Je pense que vous allez au-delà de très basique ici.
marco-fiset
22
@ marco-fiset , au contraire, je pense que c'est une réponse remarquable qui indique au PO comment faire un compilateur très basique, tout en soulignant les pièges à éviter et en définissant des phases plus avancées.
smci
6
C'est l'une des meilleures réponses que j'ai jamais vues dans l'univers de Stack Exchange. Gloire!
Andre Terra
3
Voir un «Bonjour tout le monde» à partir d’un programme créé par votre compilateur pourrait en valoir la peine. -
INDEED
27

Construisons un compilateur de Jack Crenshaw , bien qu'inachevé, est une introduction et un tutoriel extrêmement lisibles.

Nicklaus Wirth's Compiler Construction est un très bon manuel sur les bases de la construction d'un compilateur simple. Il se concentre sur la descente récursive de haut en bas, ce qui, soyons honnêtes, est BEAUCOUP plus facile que le lex / yacc ou le flex / bison. Le compilateur PASCAL original que son groupe a écrit a été réalisé de cette façon.

D'autres personnes ont mentionné les différents livres de Dragon.

John R. Strohm
la source
1
L’un des avantages de Pascal est que tout doit être défini ou déclaré avant d’être utilisé. Par conséquent, il peut être compilé en un seul passage. Turbo Pascal 3.0 en est un exemple, et il existe beaucoup de documentation sur les composants internes ici .
tcrosley
1
PASCAL a été spécialement conçu pour la compilation en un seul passage et l’établissement de liens. Le livre du compilateur de Wirth mentionne les compilateurs multipass et ajoute qu'il connaissait un compilateur PL / I qui nécessitait 70 (oui, soixante-dix) passes.
John R. Strohm
La déclaration obligatoire avant utilisation remonte à ALGOL. Le comité d’ALGOL a bien épinglé Tony Hoare en tentant de lui suggérer d’ajouter des règles de type par défaut, semblables à celles de FORTRAN. Ils connaissaient déjà les problèmes que cela pouvait créer, avec des erreurs typographiques dans les noms et des règles par défaut créant des bogues intéressants.
John R. Strohm
1
Voici une version plus mise à jour et achevée du livre par l'auteur original lui-même: stack.nl/~marcov/compiler.pdf Veuillez éditer votre réponse et ajouter ceci :)
sonnet
16

En fait, je commencerais par écrire un compilateur pour Brainfuck . C'est un langage assez obtus pour programmer, mais il n'a que 8 instructions à mettre en œuvre. C'est à peu près aussi simple que possible et il existe des instructions C équivalentes pour les commandes impliquées si vous trouvez que la syntaxe est déroutante.

Ingénieur du monde
la source
7
Mais ensuite, une fois que votre compilateur BF est prêt, vous devez écrire votre code dans celui-ci :(
500 - Erreur interne du serveur
@ 500-InternalServerError utilise la méthode du sous-ensemble C
World Engineer le
12

Si vous voulez vraiment écrire uniquement du code lisible par machine et non destiné à une machine virtuelle, vous devrez lire les manuels Intel et comprendre.

  • une. Liaison et chargement de code exécutable

  • b. Formats COFF et PE (pour Windows), sinon comprendre le format ELF (pour Linux)

  • c. Comprendre les formats de fichier .COM (plus facile que PE)
  • ré. Comprendre les assembleurs
  • e. Comprendre les compilateurs et le moteur de génération de code dans les compilateurs.

Beaucoup plus difficile que dit. Je vous suggère de lire Compilers and Interpreters en C ++ comme point de départ (par Ronald Mak). Sinon, "permet de construire un compilateur" par Crenshaw est OK.

Si vous ne le souhaitez pas, vous pouvez également écrire votre propre machine virtuelle et écrire un générateur de code destiné à cette machine virtuelle.

Conseils: Apprendre Flex et Bison EN PREMIER. Continuez ensuite à construire votre propre compilateur / VM.

Bonne chance!

Aniket Inge
la source
7
Je pense que cibler LLVM et non le code machine réel est la meilleure solution disponible à ce jour.
9000
Je suis d’accord, je suis depuis quelque temps déjà sur LLVM et je dois dire que c’est l’une des meilleures choses que j’ai vu depuis des années en termes d’effort de programmation nécessaire pour la cibler!
Aniket Inge
2
Qu'en est-il de MIPS et utiliser Spim pour l'exécuter? Ou MIX ?
@MichaelT Je n'ai pas utilisé MIPS mais je suis sûr que ce sera bien.
Aniket Inge
@PrototypeStark Jeu d'instructions RISC, processeur réel qui est encore utilisé de nos jours (sachant qu'il peut être traduit en systèmes embarqués). Le jeu complet d'instructions est à wikipedia . En regardant sur le net, il y a beaucoup d'exemples et il est utilisé dans de nombreux cours théoriques comme cible pour la programmation en langage machine. Il y a un peu d'activité à ce sujet à SO .
10

L'approche de bricolage pour un compilateur simple pourrait ressembler à ceci (du moins, c'est à ça que ressemblait mon projet uni):

  1. Définir la grammaire de la langue. Sans contexte.
  2. Si votre grammaire n'est pas encore LL (1), faites-le maintenant. Notez que certaines règles qui semblaient bien dans la grammaire simple des FC peuvent s'avérer laides. Peut-être que votre langage est trop complexe ...
  3. Écrivez Lexer qui coupe le flux de texte en jetons (mots, nombres, littéraux).
  4. Écrivez un analyseur descendant récursif de haut en bas pour votre grammaire, qui accepte ou refuse les entrées.
  5. Ajouter la génération d'arborescence de syntaxe dans votre analyseur.
  6. Écrivez le générateur de code machine à partir de l'arbre de syntaxe.
  7. Profit & Beer, sinon vous pouvez commencer à penser à un analyseur syntaxique plus intelligent ou à un meilleur code.

Il devrait y avoir beaucoup de littérature décrivant chaque étape en détail.

Mar
la source
Le 7ème point est ce que OP demande.
Florian Margaine
7
1-5 ne sont pas pertinents et ne méritent pas une telle attention. 6 est la partie la plus intéressante. Malheureusement, la plupart des livres suivent le même schéma, après le fameux livre de dragon, accordant trop d’attention à l’analyse et laissant le code se transformer hors de portée.
SK-logic le