Comment écrire un compilateur très basique

Intro

Un compilateur type effectue les étapes suivantes:

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

La plupart des compilateurs modernes (par exemple, gcc et clang) répètent à nouveau 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 de code initiale. Ensuite, ce langage est converti en code spécifique à la plate-forme (x86, ARM, etc.) faisant à peu près la même chose dune manière optimisée pour la plate-forme. Cela comprend par exemple lutilisation dinstructions vectorielles lorsque cela est possible, la réorganisation des instructions pour augmenter lefficacité de la prédiction des branches, et ainsi de suite.

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 nest pas une étape de compilation en soi. Dans des langages comme Java et C #, la liaison peut être totalement dynamique, effectuée par la VM au moment du chargement.

Noubliez pas les principes de base

• Faites-le fonctionner
• Rendez-le beau
• Rendez-le efficace

Cette séquence classique sapplique à tous les développements logiciels, mais 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 pourrait fonctionner.

Lisez les livres!

Lisez le Dragon Book dAho et Ullman. Ceci est classique et est encore tout à fait applicable aujourdhui.

Modern Compiler Design est également salué.

Si ce truc est trop difficile pour vous en ce moment, lisez dabord quelques intros sur lanalyse; généralement lanalyse des bibliothèques incluez des intros et des exemples.

Assurez-vous que vous êtes à laise avec les graphiques, en particulier les arbres. Ces éléments sont les éléments dont les programmes sont constitués au niveau logique.

Définissez bien votre langage

Utilisez la notation que vous voulez, mais assurez-vous davoir 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 nouveau langage comme cas de test pour le futur compilateur.

Utilisez votre langage préféré

Cest tout à fait correct décrire un compilateur en Python ou Ruby ou dans nimporte quel autre langage qui vous est facile.Utilisez des algorithmes simples que vous comprenez bien. La première version na pas besoin dêtre rapide, efficace ou complète. Il doit seulement être suffisamment correct et facile à modifier.

Il est également possible décrire différentes étapes dun compilateur dans différentes langues, si nécessaire.

Préparez-vous à écrire beaucoup de tests

Toute votre langue doit être couverte par des cas de test; en fait, elle sera définie par eux. Familiarisez-vous avec votre cadre de test préféré. Écrivez des tests dès le premier jour. Concentrez-vous sur les tests « positifs » qui acceptent le code correct, par opposition à la détection dun code incorrect.

Exécutez tous les tests régulièrement. Corrigez les tests cassés avant de continuer. Ce serait dommage de se retrouver avec un mauvais- langage défini qui ne peut pas accepter de code valide.

Créez un bon analyseur

Les générateurs danalyseurs sont nombreux . Choisissez ce que vous voulez Vous pouvez également écrire votre propre analyseur à partir de zéro, mais cela ne vaut la peine que si la syntaxe de votre langage est morte simple.

Lanalyseur doit détecter et signaler les erreurs de syntaxe. Ecrire beaucoup de cas de test, positifs et négatifs ve; réutiliser le code que vous avez écrit lors de la définition du langage.

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

Si votre langage a des modules, la sortie de lanalyseur peut être la représentation la plus simple de « code objet » que vous générez. Il existe de nombreuses façons simples de vider 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 rendre aucun sens dans certains contextes. Un exemple est une déclaration en double de la même variable ou la transmission dun paramètre dun type incorrect. Le validateur détectera ces erreurs en regardant larborescence.

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

Encore une fois, écrivez et exécutez de nombreux 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. Souvent, il est acceptable de traduire directement une construction de langage (comme une instruction if) en un modèle de code légèrement paramétré, un peu comme un modèle HTML.

Encore une fois , ignorez lefficacité et concentrez-vous sur lexactitude.

Cibler une VM de bas niveau indépendante de la plate-forme

Je suppose que vous ignorez les éléments de bas niveau à moins que vous ne soyez vivement intéressé par le matériel spécifique des détails. 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, multiplateforme; a un bon JIT.
• JVM: cible le monde Java, assez multiplateforme, a un bon JIT.

Ignorer loptimisation

Loptimisation est difficile. Loptimisation est presque toujours prématurée. Générez du code inefficace mais correct. Implémentez tout le langage avant dessayer doptimiser le code résultant.

Bien sûr, des optimisations triviales sont acceptables. Mais évitez tout truc rusé et poilu avant que votre compilateur ne soit stable.

Et alors?

Si tout cela nest pas trop intimidant pour vous, veuillez continuer! Pour un langage simple, chacune des étapes peut être plus simple que vous ne le pensez.

Voir un « Hello world » à partir dun programme que votre compilateur a créé peut en valoir la peine.

Commentaires

• Cest lune des meilleures réponses que ‘ ai encore vues.
• Je pense que vous a manqué une partie de la question … LOP voulait écrire un compilateur très basique . Je pense que vous allez au-delà du très simple ici.
• @ marco-fiset , au contraire, je pense que ‘ est une réponse exceptionnelle qui indique à lOP comment faire un compilateur très basique, tout en soulignant les pièges à éviter et en définissant des phases plus avancées.
• Cest lune des meilleures réponses Je lai déjà vu dans tout lunivers de Stack Exchange. Félicitations!
• Voir un ‘ Hello world ‘ à partir dun programme créé par votre compilateur pourrait en valoir la peine. – INDEED

Jack Crenshaw « s Let « s Build a Compiler , bien quinachevé, est une introduction et un didacticiel parfaitement lisibles.

Nicklaus Wirth » s Construction du compilateur est un très bon manuel sur les bases de la construction de compilateurs simples. Il se concentre sur la descente récursive descendante, qui, soyons honnêtes, est BEAUCOUP plus facile que lex / yacc ou flex / bison. Le compilateur PASCAL original que son groupe a écrit a été fait de cette façon.

Dautres personnes ont mentionné les différents livres Dragon.

Commentaires

• Un des avantages de Pascal, cest 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 y a beaucoup de documentation sur les composants internes ici .
• PASCAL a été spécifiquement conçu avec un- Passez à lesprit la compilation et les liens. Le livre du compilateur de Wirth ‘ mentionne les compilateurs multipass et ajoute quil connaissait un compilateur PL / I qui a pris 70 (oui, soixante-dix) passages.
• Déclaration obligatoire avant utilisation remonte à ALGOL. Tony Hoare sest fait épingler les oreilles par le comité ALGOL lorsquil a essayé de suggérer dajouter des règles de type par défaut, similaires à celles de FORTRAN. Ils connaissaient déjà les problèmes que cela pourrait créer, avec des erreurs typographiques dans les noms et des règles par défaut créant des bogues intéressants.
• Voici une version plus mise à jour et terminée du livre par lauteur original lui-même: stack.nl/~marcov/compiler.pdf Veuillez modifier votre réponse et ajouter ceci 🙂

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

• a. Lier et charger le code exécutable

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

• c. Comprendre les formats de fichier .COM (plus facile que PE)
• d. 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 les compilateurs et interprètes en C ++ comme point de départ (par Ronald Mak). Sinon, « construisons un compilateur » par Crenshaw est OK.

Si vous ne voulez pas faire cela, vous pouvez aussi bien écrire votre propre VM et écrire un générateur de code ciblé sur cette VM.

• Autre point de départ: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Great Book By Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Conseils: apprenez dabord Flex et Bison. Ensuite, construisez votre propre compilateur / VM.

Bonne chance!

Commentaires

• Je pense que cibler LLVM et non le vrai code machine est à peu près le meilleur moyen disponible aujourdhui.
• Je suis daccord, je suis LLVM depuis un certain temps maintenant et je devrais dire que cétait lune des meilleures choses que javais vues depuis des années en termes deffort de programmeur nécessaire pour le cibler!
• Quen est-il de MIPS et utilisez spim pour lexécuter? Ou MIX ?
• @MichaelT Je nai pas utilisé MIPS mais je suis sûr que ce sera bien.
• Jeu dinstructions @PrototypeStark RISC, processeur du monde réel qui est toujours utilisé aujourdhui (sachant quil sera traduisible en systèmes embarqués). Lensemble dinstructions complet se trouve sur wikipedia . En regardant sur le net, il existe de nombreux exemples et il est utilisé dans de nombreuses classes académiques comme cible pour la programmation en langage machine. Il y a un peu dactivité là-dessus à SO .

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

Commentaires

• Mais ensuite, une fois que vous avez votre compilateur BF prêt, vous devez y écrire votre code 🙁
• @ 500-InternalServerError utilisez la méthode du sous-ensemble C

Lapproche DIY pour un compilateur simple pourrait ressembler à ceci (du moins cest à quoi ressemblait mon projet uni):

1. Définissez la grammaire de la langue. Sans contexte.
2. Si votre grammaire nest pas encore LL (1), faites-le maintenant. Notez que certaines règles qui semblaient correctes en CF clair la grammaire peut savérer moche. 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 de haut en bas parseur de descente récursive pour votre grammaire, qui accepte ou rejette lentrée.
5. Ajoutez la génération darbre de syntaxe dans votre analyseur.
6. Écrivez ma générateur de code chine à partir de larbre de syntaxe.
7. Profit & Beer, vous pouvez également commencer à réfléchir à comment faire un analyseur plus intelligent ou générer un meilleur code.

Il devrait une abondance de littérature décrivant chaque étape en détail.

Commentaires

• Le 7ème point est ce sur quoi OP demande.
• 1-5 ne sont pas pertinents et ne méritent pas une telle une attention particulière. 6 est la partie la plus intéressante.Malheureusement, la plupart des livres suivent le même modèle, après le tristement célèbre livre de dragon, en accordant trop dattention à lanalyse et en laissant les transformations de code hors de portée.