Démarrer un simple (le plus simple peut-être) compilateur C ?

Question

Je suis tombé sur ça : Écrire un compilateur en utilisant Turbo Pascal

Je suis curieux de savoir s'il existe des tutoriels ou des références expliquant comment procéder pour créer un compilateur C simple. Je veux dire, c'est suffisant si cela me permet d'arriver à lui faire comprendre les opérations arithmétiques. Je suis devenu vraiment curieux après avoir lu cet article de Ken Thompson . L'idée d'écrire quelque chose qui se comprend lui-même semble excitante.

Pourquoi ai-je posé cette question au lieu de la poser à Google ? J'ai essayé Google et celui de Pascal était le premier lien. Les autres ne semblaient pas pertinents et se sont ajoutés à cela... Je ne suis pas diplômé en informatique (donc je dois encore apprendre ce que font tous ces outils comme yacc) et je veux apprendre par la pratique et j'espère que les personnes ayant plus d'expérience sont toujours meilleures que Google pour ces choses. Je veux lire un article écrit dans le même esprit que celui que j'ai cité plus haut, mais qui mette en évidence au moins les phases de démarrage de la construction d'un compilateur C simple.

Aussi, je ne sais pas quelle est la meilleure façon d'apprendre. Dois-je commencer par construire un compilateur C en C ou dans un autre langage ? Dois-je écrire un compilateur en C ou dans un autre langage ? Je pense qu'il est plus facile de répondre à ce genre de questions une fois que j'ai une idée de la direction à prendre. Des suggestions ?

Des suggestions ?

Answer 1

Je vous conseille ce tutoriel :

• Tutoriel LLVM

Il s'agit d'un petit exemple sur la façon d'implémenter un compilateur "petit langage". Le code source est très petit et est expliqué étape par étape.

Il existe également la bibliothèque frontale C pour la bibliothèque LLVM (Low Level Virtual Machine qui représente la structure interne d'un programme) :

• Clang

Answer 2

Un compilateur se compose de trois éléments :

1. Un analyseur syntaxique
2. Un arbre syntaxique abstrait (AST)
3. Un générateur de code d'assemblage

Il existe de nombreux générateurs d'analyseurs sympathiques qui commencent par des grammaires de langue. ANTLR serait peut-être un bon point de départ pour vous. Si vous voulez vous en tenir aux racines du C, essayez lex/yacc ou bison.

Il existe des grammaires pour le C, mais je pense que le C dans sa globalité est complexe. Vous feriez bien de commencer par un sous-ensemble du langage et de progresser.

Une fois que vous avez un AST, vous l'utilisez pour générer le code machine que vous allez exécuter.

C'est faisable, mais pas trivial.

Je consulterais également Amazon pour trouver des livres sur l'écriture de compilateurs. Le livre du Dragon est le classique, mais il en existe des plus modernes.

MISE À JOUR : Des questions similaires ont été posées sur Stack overflow, par exemple celui-ci . Consultez également ces ressources.

Answer 3

Pour ce que ça vaut, le Compilateur C miniature est un compilateur C assez complet dans un paquetage source relativement petit. Vous pourriez bénéficier de l'étude de ce code source, car il est probablement beaucoup plus facile à comprendre que d'essayer de comprendre l'ensemble des sources de GCC, par exemple.

Answer 4

C'est mon opinion (et ma conjecture) : il sera difficile d'écrire un compilateur sans comprendre les structures de données normalement couvertes dans les cours d'informatique de premier cycle (postsecondaire). Cela ne signifie pas que vous ne pouvez pas, mais vous devrez connaître les structures de données essentielles telles que les listes liées et les arbres.

Plutôt que d'écrire un compilateur complet ou conforme aux normes du langage C (du moins au début), je suggérerais de vous limiter à un sous-ensemble de base du langage, comme les opérateurs communs, le support des entiers uniquement, et les fonctions et pointeurs de base. Un exemple classique de ceci était le compilateur de Ron Cain Petit-C rendu populaire par une série d'articles écrits dans Journal du Dr Dobbs dans les années 80, je crois. Ils publient un CD avec le livre épuisé de James Hendrix, Un compilateur Small-C .

Ce que je suggérerais, c'est de suivre le tutoriel de Crenshaw, mais de l'écrire pour un compilateur de type C, et quelle que soit la cible CPU (Crenshaw cible le CPU Motorola 68000) que vous souhaitez cibler. Pour ce faire, vous aurez besoin de connaître l'assemblage de base de la cible sur laquelle vous voulez exécuter les programmes compilés. Cela peut inclure un émulateur pour un 68000 ou un MIPS, qui sont sans doute les plus performants. plus beau que le vénérable jeu d'instructions CISC de l'Intel x86 (16/32 bits).

Il existe de nombreux ouvrages susceptibles de servir de point de départ à l'apprentissage de la théorie (et de la pratique) des compilateurs et des traducteurs. Lisez le comp.compilateurs FAQ et des critiques chez divers vendeurs de livres en ligne. La plupart des livres d'introduction sont écrits en tant que manuels pour des cours d'informatique de deuxième ou de troisième cycle, et peuvent donc être lents à lire sans connaissances en informatique. Un livre plus ancien qui pourrait être plus introductif, mais plus facile à lire que " Le livre du dragon " es Introduction à la construction d'un compilateur par Thomas Parsons. Comme il est plus ancien, vous devriez pouvoir trouver un exemplaire d'occasion à un prix raisonnable auprès des libraires en ligne de votre choix.

Donc je dirais, essayez de commencer avec le livre de Jack Crenshaw. Construisons un compilateur écrivez votre propre tutoriel, en vous inspirant de ses exemples, et construisez les bases d'un site Web. simple compilateur. Une fois qu'il fonctionne, vous pouvez mieux décider où vous voulez aller à partir de ce point.

Ajouté :

En ce qui concerne le processus de bootstrapping. Puisqu'il existe des compilateurs C librement disponibles, vous n'avez pas à vous soucier de l'amorçage. Écrivez votre compilateur avec des outils distincts existants (GCC, Visual C++ Express, Mingw / djgpp, tcc), et vous pouvez vous soucier de l'autocompilation de votre projet à un stade beaucoup plus avancé. J'ai été surpris par cette partie de la question jusqu'à ce que je réalise que vous avez été amené à l'idée d'écrire votre propre compilateur en lisant le discours du prix Turing de l'ACM de Ken Thomas, Réflexions sur la confiance qui entre dans le processus d'amorçage du compilateur. C'est un sujet avancé modéré, et c'est aussi simplement beaucoup de tracas. Je trouve que même l'amorçage du compilateur C GCC sous les anciens systèmes Unix (Digital OSF/1 sur l'Alpha 64 bits) qui incluaient un compilateur C est un processus lent et fastidieux, sujet aux erreurs.

L'autre question était de savoir ce que fait réellement un compilateur comme Yacc. Yacc (Yet Another Compiler Compiler ou Bison de GNU) est un outil conçu pour faciliter l'écriture d'un analyseur de compilateur (ou de traducteur). Basé sur le grammaire formelle pour votre langue cible que vous entrez dans yacc, celui-ci génère une analyseur syntaxique qui est une partie de la conception globale d'un compilateur. Ensuite, il y a Lex (ou flex de GNU) qui est utilisé pour générer un analyseur lexical ou analyseur, qui est souvent utilisé en combinaison avec l'analyseur généré par yacc pour former le squelette du frontal d'un compilateur. Ces outils rendent l'écriture d'un frontal sans doute plus facile que d'écrire soi-même un analyseur lexical et un parseur. Le tutoriel de Crenshaw n'utilise pas ces outils, et vous n'avez pas besoin de le faire non plus, de nombreux auteurs de compilateurs ne les utilisent pas toujours. Bien sûr, Crenshaw admet que l'analyseur syntaxique du tutoriel est assez basique.

Le tutoriel de Crenshaw évite également de générer un AST (abstract syntax tree), ce qui simplifie mais limite également le compilateur du tutoriel. Il manque la plupart des optimisations, sinon toutes, et est très lié au langage de programmation spécifique et au langage d'assemblage particulier émis par le "back-end" du compilateur. Normalement, l'AST est une pièce intermédiaire où une certaine optimisation peut être effectuée, et sert à découpler le front-end et le back-end du compilateur dans la conception. Pour un débutant sans formation en informatique, je suggérerais de ne pas s'inquiéter de ne pas avoir d'AST pour votre premier compilateur (ou du moins la première version de celui-ci). Je pense que le fait de garder les choses petites et simples vous aidera à finir d'écrire un compilateur, dans sa première version, et vous pourrez décider à partir de là comment vous voulez procéder ensuite.

Answer 5

Vous pourriez être intéressé par le livre/cours Les éléments des systèmes informatiques : construire un ordinateur moderne à partir des premiers principes .

Notez qu'il ne s'agit pas de construire un "PC" à partir de matériel acheté sur Newegg. Il commence par une description des principes fondamentaux de la logique booléenne et construit un ordinateur virtuel à partir des niveaux d'abstraction les plus bas vers des niveaux d'abstraction de plus en plus élevés. Les supports de cours sont tous en ligne, et le livre lui-même est assez bon marché chez Amazon.

Dans ce cours, en plus de "construire le matériel", vous implémenterez également un assembleur, une machine virtuelle, un compilateur et un système d'exploitation rudimentaire, de manière progressive. Je pense que cela vous donnera une base suffisante pour approfondir le sujet avec certaines des ressources les plus couramment recommandées dans les autres réponses.