Question Apprendre à écrire un compilateur [fermé]


Langues préférées: C / C ++, Java et Ruby.

Je cherche des livres / tutoriels utiles sur la façon d'écrire votre propre compilateur simplement à des fins éducatives. Je suis très familier avec C / C ++, Java et Ruby, donc je préfère les ressources qui impliquent l'un de ces trois, mais toute bonne ressource est acceptable.


699


origine


Réponses:


Grande liste de ressources:

Légende:

  • ¶ Lien vers un fichier PDF
  • $ Lien vers un livre imprimé

1024



C'est une question assez vague, je pense; juste à cause de la profondeur du sujet en cause. Un compilateur peut être décomposé en deux parties distinctes, cependant; une moitié supérieure et une inférieure. La moitié supérieure prend généralement le langage source et le convertit en une représentation intermédiaire, et la moitié inférieure prend en charge la génération de code spécifique à la plate-forme.

Néanmoins, une idée pour un moyen facile d'aborder ce sujet (celui que nous avons utilisé dans ma classe de compilateurs, au moins) est de construire le compilateur dans les deux pièces décrites ci-dessus. Plus précisément, vous aurez une bonne idée de l'ensemble du processus en construisant simplement la moitié supérieure.

Le fait de faire la moitié supérieure vous permet d'avoir l'expérience de l'écriture de l'analyseur lexical et de l'analyseur et d'aller générer du «code» (cette représentation intermédiaire que j'ai mentionnée). Donc, il prendra votre programme source et le convertira en une autre représentation et fera une certaine optimisation (si vous voulez), qui est le cœur d'un compilateur. La moitié inférieure prendra alors cette représentation intermédiaire et générera les octets nécessaires pour exécuter le programme sur une architecture spécifique. Par exemple, la moitié inférieure prendra votre représentation intermédiaire et génèrera un exécutable PE.

Certains livres sur ce sujet que j'ai trouvé particulièrement utiles Principes et techniques des compilateurs (ou le livre du dragon, en raison du dragon mignon sur la couverture). Il a une bonne théorie et couvre définitivement les grammaires sans contexte d'une manière vraiment accessible. De plus, pour construire l'analyseur et l'analyseur lexical, vous utiliserez probablement les outils * nix lex et yacc. Et sans intérêt, le livre appelé "lex et yacc"ramassé là où le livre du Dragon s'est arrêté pour cette partie.


69



je pense Implémentation du compilateur moderne en ML est le meilleur compilateur d'introduction à l'écriture de texte. Il y a un Version Java et un Version C aussi, l'un ou l'autre pourrait être plus accessible compte tenu de vos antécédents linguistiques. Le livre contient beaucoup de matériel de base utile (analyse et analyse syntaxique, analyse sémantique, enregistrements d'activation, sélection d'instructions, génération de code natif RISC et x86) et divers sujets "avancés" (compilation de langages OO et fonctionnels, polymorphisme, garbage collection, optimisation et formulaire d'affectation statique unique) dans relativement peu d'espace (~ 500 pages).

Je préfère l'implémentation du compilateur moderne au livre du Dragon car l'implémentation du compilateur moderne étudie moins le domaine - au lieu de cela il a une couverture vraiment solide de tous les sujets dont vous auriez besoin pour écrire un compilateur sérieux et décent. Après avoir travaillé sur ce livre, vous serez prêt à vous attaquer directement aux documents de recherche pour plus de profondeur si vous en avez besoin.

Je dois avouer que j'ai un faible pour Niklaus Wirth Construction de compilateur. C'est disponible en ligne en format PDF Je trouve l'esthétique de la programmation de Wirth simplement belle, mais certaines personnes trouvent son style trop minimal (par exemple, Wirth préfère les analyseurs de descente récursifs, mais la plupart des cours CS se concentrent sur les outils générateurs d'analyseurs syntaxiques). des idées de base de Wirth, donc si vous aimez son style ou pas ou non, je vous recommande fortement de lire ce livre.


54



Je suis d'accord avec la référence du livre Dragon; OMI, c'est le guide définitif pour la construction de compilateur. Préparez-vous à une théorie hardcore, cependant.

Si vous voulez un livre qui est plus léger sur la théorie, Maîtrise des scripts de jeu pourrait être un meilleur livre pour vous. Si vous êtes un débutant total à la théorie du compilateur, il fournit une introduction plus douce. Il ne couvre pas les méthodes d'analyse plus pratiques (optant pour une descente récursive non prédictive sans discuter de l'analyse LL ou LR), et si je me souviens bien, il ne discute même pas de théorie de l'optimisation. De plus, au lieu de compiler en code machine, il se compile en un bytecode censé s'exécuter sur une machine virtuelle que vous écrivez également.

C'est toujours une lecture décente, surtout si vous pouvez le ramasser pour pas cher sur Amazon. Si vous voulez seulement une introduction facile dans les compilateurs, Game Scripting Mastery n'est pas un mauvais choix. Si vous voulez faire du hardcore à l'avance, alors vous devriez vous contenter de rien de moins que le livre du dragon.


46



"Construisons un compilateur" C'est génial, mais c'est un peu démodé. (Je ne dis pas que cela le rend un peu moins valide.)

Ou consultez ARGOT. Ceci est similaire à "Construisons un compilateur" mais est une bien meilleure ressource surtout pour les débutants. Cela vient avec un didacticiel pdf qui prend une approche en 7 étapes pour vous enseigner un compilateur. Ajout du lien quora car il a les liens vers tous les différents ports de SLANG, en C ++, Java et JS, aussi des interpréteurs en python et java, écrits à l'origine en utilisant C # et la plateforme .NET.


28



Si vous cherchez à utiliser des outils puissants et de haut niveau plutôt que de construire tout vous-même, en passant par les projets et les lectures pour ce cours est une très bonne option. C'est un cours de langues par l'auteur du moteur d'analyse syntaxique Java ANTLR. Vous pouvez obtenir le livre pour le cours en format PDF à partir de les programmeurs pragmatiques.

Le cours passe en revue les choses standard du compilateur que vous verriez ailleurs: l'analyse syntaxique, la vérification des types et des types, le polymorphisme, les tables de symboles et la génération de code. À peu près la seule chose qui n'est pas couverte est des optimisations. Le projet final est un programme qui compile un sous-ensemble de C. Parce que vous utilisez des outils comme ANTLR et LLVM, il est possible d'écrire le compilateur entier en un seul jour (j'en ai une preuve d'existence, bien que je parle de ~ 24 heures). C'est lourd sur l'ingénierie pratique en utilisant des outils modernes, un peu plus léger en théorie.

LLVM, d'ailleurs, est simplement fantastique. Dans de nombreuses situations où vous pourriez normalement compiler jusqu'à l'assemblage, vous feriez mieux de compiler Représentation intermédiaire de LLVM au lieu. C'est un niveau supérieur, une plateforme croisée, et LLVM est assez bon pour générer un assemblage optimisé.


24



Si vous avez peu de temps, je recommande "Compiler Construction" de Niklaus Wirth (Addison-Wesley 1996), un minuscule petit livret que vous pouvez lire en un jour, mais il explique les bases (y compris comment implémenter des lexers, des analyseurs de descente récursifs et vos propres machines virtuelles basées sur des piles). Après cela, si vous voulez une plongée profonde, il n'y a pas moyen de contourner le livre Dragon comme le suggèrent d'autres commentateurs.


20



Vous pourriez vouloir regarder dans Lex / Yacc (ou Flex / Bison, peu importe ce que vous voulez les appeler). Flex est un analyseur lexical, qui va analyser et identifier les composants sémantiques ("jetons") de votre langage, et Bison sera utilisé pour définir ce qui se passe quand chaque jeton est analysé. Cela pourrait être, mais n'est pas limité à, l'impression de code C, pour un compilateur qui compilerait en C, ou exécuterait les instructions de manière dynamique.

Cette FAQ devrait vous aider, et ce tutoriel semble très utile.


17



De manière générale, il n'y a pas de tutoriel de cinq minutes pour les compilateurs, car c'est un sujet compliqué et écrire un compilateur peut prendre des mois. Vous devrez faire votre propre recherche.

Python et Ruby sont généralement interprétés. Peut-être que vous voulez commencer avec un interprète aussi. C'est généralement plus facile.

La première étape consiste à écrire une description formelle du langage, la grammaire de votre langage de programmation. Ensuite, vous devez transformer le code source que vous voulez compiler ou interpréter selon la grammaire en un arbre de syntaxe abstraite, une forme interne du code source que l'ordinateur comprend et peut utiliser. Cette étape est généralement appelée analyse et le logiciel qui analyse le code source s'appelle un analyseur. Souvent, l'analyseur est généré par un générateur d'analyseur qui transforme une grammaire formelle en code source ou code machine. Pour une bonne explication non-mathématique de l'analyse syntaxique, je recommande Parsing Techniques - A Practical Guide. Wikipedia a une comparaison des générateurs d'analyseur à partir de laquelle vous pouvez choisir celui qui vous convient. Selon le générateur d'analyseur que vous avez choisi, vous trouverez des didacticiels sur Internet et pour les générateurs d'analyseurs très populaires (comme GNU bison), il existe également des livres.

Ecrire un analyseur pour votre langue peut être très difficile, mais cela dépend de votre grammaire. Je suggère donc de garder votre grammaire simple (contrairement à C ++); un bon exemple pour cela est LISP.

Dans la deuxième étape, l'arbre de syntaxe abstraite est transformé d'une structure arborescente en une représentation intermédiaire linéaire. Comme un bon exemple pour ce bytecode de Lua est souvent cité. Mais la représentation intermédiaire dépend vraiment de votre langue.

Si vous construisez un interprète, vous devrez simplement interpréter la représentation intermédiaire. Vous pouvez également le compiler juste à temps. Je recommande LLVM et libjit pour une compilation juste-à-temps. Pour rendre la langue utilisable, vous devrez également inclure des fonctions d'entrée et de sortie et peut-être une petite bibliothèque standard.

Si vous allez compiler la langue, ce sera plus compliqué. Vous devrez écrire des backends pour différentes architectures informatiques et générer du code machine à partir de la représentation intermédiaire dans ces backends. Je recommande LLVM pour cette tâche.

Il y a quelques livres sur ce sujet, mais je ne peux en recommander aucun pour un usage général. La plupart d'entre eux sont trop académiques ou trop pratiques. Il n'y a pas de "Apprendre le compilateur à écrire en 21 jours" et ainsi, vous devrez acheter plusieurs livres pour avoir une bonne compréhension de tout ce sujet. Si vous effectuez une recherche sur Internet, vous trouverez des livres en ligne et des notes de cours. Il y a peut-être une bibliothèque universitaire près de chez vous où vous pouvez emprunter des livres sur des compilateurs.

Je recommande également de bonnes connaissances de base en informatique théorique et en théorie des graphes, si vous voulez rendre votre projet sérieux. Un diplôme en informatique sera également utile.


16