Un aperçu bref et dynamique de l'architecture du compilateur

La plupart des compilateurs ont l'architecture suivante:



Dans cet article, je vais détailler cette architecture en détail, élément par élément.
Nous pouvons dire que cet article est un ajout à l'énorme quantité de ressources existantes sur le sujet des compilateurs. C'est une source autonome qui vous permettra de comprendre les bases de la conception et de l'implémentation des langages de programmation.

Le public cible de l'article est constitué de personnes dont l'idée du travail des compilateurs est extrêmement limitée (le maximum est qu'ils participent à la compilation). Cependant, je m'attends à ce que le lecteur comprenne les structures de données et les algorithmes.

L'article n'est en aucun cas consacré aux compilateurs de production modernes avec des millions de lignes de code - non, il s'agit d'un court cours «compilateurs pour les nuls» pour vous aider à comprendre ce qu'est un compilateur.

Présentation

Je travaille actuellement sur le langage du système Krug inspiré de Rust and Go. Dans l'article, je ferai référence à Krug comme exemple pour illustrer mes pensées. Krug est en cours de développement, mais est déjà disponible sur https://github.com/krug-lang dans les référentiels caasper et krug . Le langage n'est pas tout à fait typique par rapport à l'architecture de compilation habituelle, ce qui m'a en partie inspiré à écrire un article - mais plus à ce sujet plus tard.

Je m'empresse de vous informer que je ne suis en aucun cas un spécialiste des compilateurs! Je n'ai pas de doctorat et je n'ai suivi aucune formation formelle - j'ai moi-même étudié tout ce qui est décrit dans l'article pendant mon temps libre. Je dois également dire que je ne décris pas la véritable approche, juste pour créer un compilateur, mais plutôt, je présente les méthodes de base appropriées pour créer un petit compilateur "jouet".

Frontend

Revenons au diagramme ci-dessus: les flèches à gauche dirigées vers le champ frontal sont des langages bien connus et aimés comme C. Le frontal ressemble à ceci: analyse lexicale -> analyseur.

Analyse lexicale

Quand j'ai commencé à étudier les compilateurs et la conception de langages, on m'a dit que l'analyse lexicale était la même que la tokenisation. Nous utiliserons cette description. L'analyseur prend les données d'entrée sous la forme de chaînes ou d'un flux de caractères et reconnaît les modèles en eux, qu'il coupe en jetons.

Dans le cas d'un compilateur, il reçoit un programme écrit en entrée. Il est lu dans une chaîne à partir d'un fichier et l'analyseur tokenise son code source.

enum TokenType { Identifier, Number, }; struct Token { std::string Lexeme; TokenType type; // ... // It's also handy to store things in here // like the position of the token (start to end row:col) }; 

Dans ce fragment, écrit dans un langage en forme de C, vous pouvez voir la structure contenant le lexème susmentionné, ainsi que TokenType, qui sert à reconnaître ce jeton.

Remarque: l'article n'est pas une instruction pour créer un langage avec des exemples - mais pour une meilleure compréhension, je vais insérer de temps en temps des extraits de code.

Les analyseurs sont généralement les composants de compilation les plus simples. L'ensemble du frontend, en fait, est assez simple par rapport au reste des pièces du puzzle. Bien que cela dépende beaucoup de votre travail.

Prenez le morceau de code C suivant:

 int main() { printf("Hello world!\n"); return 0; } 

Après l'avoir lu d'un fichier sur une ligne et effectué un scan linéaire, vous pourrez peut-être découper des jetons. Nous identifions les jetons de manière naturelle - vu que int est un "mot", et 0 dans la déclaration de retour est un "nombre". L'analyseur lexical exécute la même procédure que nous - plus tard, nous examinerons ce processus plus en détail. Par exemple, analysez les chiffres:

 0xdeadbeef — HexNumber ( ) 1231234234 — WholeNumber ( ) 3.1412 — FloatingNumber (   ) 55.5555 — FloatingNumber (   ) 0b0001 — BinaryNumber ( ) 

Définir des mots peut être difficile. La plupart des langues définissent un mot comme une séquence de lettres et de chiffres, et un identifiant doit généralement commencer par une lettre ou un trait de soulignement. Par exemple:

 123foobar := 3 person-age := 5 fmt.Println(123foobar) 

Dans Go, ce code ne sera pas considéré comme correct et sera analysé dans les jetons suivants:

 Number(123), Identifier(foobar), Symbol(:=), Number(3) ... 

La plupart des identifiants rencontrés ressemblent à ceci:

 foo_bar __uint8_t fooBar123 

Les analyseurs devront résoudre d'autres problèmes, par exemple, avec les espaces, les commentaires multilignes et unifilaires, les identifiants, les nombres, les systèmes de numérotation et la mise en forme des nombres (par exemple, 1_000_000) et les encodages (par exemple, la prise en charge d'UTF8 au lieu d'ASCII).

Et si vous pensez que vous pouvez recourir à des expressions régulières - mieux vaut ne pas la peine. Il est beaucoup plus facile d'écrire un analyseur à partir de zéro, mais je recommande fortement de lire cet article de notre roi et dieu Rob Pike. Les raisons pour lesquelles Regex ne nous convient pas sont décrites dans de nombreux autres articles, je vais donc omettre ce point. De plus, écrire un analyseur est beaucoup plus intéressant que de vous tourmenter avec de longues expressions verbeuses téléchargées sur regex101.com à 5 h 24. Dans ma première langue, j'utilisais la fonction split(str) pour la tokenisation - et je n'allais pas loin.

Analyse

L'analyse est un peu plus compliquée que l'analyse lexicale. Il existe de nombreux analyseurs et générateurs d'analyseurs - ici, le jeu commence de manière spectaculaire.

Les analyseurs dans les compilateurs prennent généralement des entrées sous forme de jetons et construisent un arbre spécifique - un arbre de syntaxe abstraite ou un arbre d'analyse. De par leur nature, ils sont similaires, mais présentent quelques différences.

Ces étapes peuvent être représentées comme des fonctions:

 fn lex(string input) []Token {...} fn parse(tokens []Token) AST {...} let input = "int main() { return 0; }"; let tokens = lex(input); let parse_tree = parse(tokens); // .... 

En règle générale, les compilateurs sont construits à partir de nombreux petits composants qui prennent des entrées, les modifient ou les convertissent en différentes sorties. C'est l'une des raisons pour lesquelles les langages fonctionnels sont bien adaptés à la création de compilateurs. D'autres raisons sont une excellente analyse comparative et des bibliothèques standard assez étendues. Fait amusant: la première implémentation du compilateur Rust était sur Ocaml.

Je vous conseille de garder ces composants aussi simples et autonomes que possible - la modularité facilitera grandement le processus. À mon avis, on peut en dire autant de nombreux autres aspects du développement logiciel.

Les arbres

Analyser l'arbre

Qu'est-ce que c'est que ça? Également connu sous le nom d'arbre d'analyse, cet arbre épais sert à visualiser le programme source. Ils contiennent toutes les informations (ou la plupart) sur le programme d'entrée, généralement les mêmes que celles décrites dans la grammaire de votre langue. Chaque nœud d'arbre sera en fin ou non en fin, par exemple, NumberConstant ou StringConstant.

Arbre de syntaxe abstraite

Comme son nom l'indique, l'ASD est un arbre de syntaxe abstraite . L'arbre d'analyse contient beaucoup d'informations (souvent redondantes) sur votre programme, et dans le cas d'un ASD, il n'est pas nécessaire. ASD n'a pas besoin d'informations inutiles sur la structure et la grammaire, ce qui n'affecte pas la sémantique du programme.

Supposons que votre arbre ait une expression comme ((5 + 5) -3) +2. Dans l'arbre d'analyse, vous le stockeriez complètement, avec les crochets, les opérateurs et les valeurs 5, 5, 3 et 2. Mais vous pouvez simplement vous associer à l'ASD - nous n'avons besoin que de connaître les valeurs, les opérateurs et leur ordre.

L'image ci-dessous montre l'arbre de l'expression a + b / c.


L'ASD peut être représenté comme suit:

 interface Expression { ... }; struct UnaryExpression { Expression value; char op; }; struct BinaryExpression { Expression lhand, rhand; string op; // string because the op could be more than 1 char. }; interface Node { ... }; // or for something like a variable struct Variable : Node { Token identifier; Expression value; }; 

Cette vue est assez limitée, mais j'espère que vous pourrez voir comment vos nœuds seront structurés. Pour l'analyse, vous pouvez recourir à la procédure suivante:

 Node parseNode() { Token current = consume(); switch (current.lexeme) { case "var": return parseVariableNode(); // ... } panic("unrecognized input!"); } Node n = parseNode(); if (n != null) { // append to some list of top level nodes? // or append to a block of nodes! } 

J'espère que vous obtiendrez l'essentiel de la façon dont l'analyse pas à pas des nœuds restants se déroulera, en commençant par les constructions de langage de haut niveau. Comment exactement un analyseur avec une descente récursive est mis en œuvre, vous devez vous étudier.

La grammaire

L'analyse dans un ADS à partir d'un ensemble de jetons peut être difficile. Habituellement, vous devriez commencer par la grammaire de votre langue. En substance, la grammaire détermine la structure de votre langue. Il existe plusieurs langages pour définir des langages qui peuvent se décrire (ou s'analyser) eux-mêmes.

Un exemple de langage pour déterminer les langues est une forme étendue de Backus-Naur (RBNF). Il s'agit d'une variante du BNF avec moins de supports d'angle. Voici un exemple RBNF d'un article de Wikipedia:

 digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; digit = "0" | digit excluding zero ; 

Des règles de production sont définies: elles indiquent quel modèle de terminal est «non terminal». Les terminaux font partie de l'alphabet, par exemple, le jeton if ou 0 et 1 dans l'exemple ci-dessus sont des terminaux. Les non-terminaux sont leur contraire, ils sont du côté gauche des règles de production, et ils peuvent être considérés comme des variables ou des «pointeurs nommés» vers des groupes de terminaux et de non-terminaux.

De nombreuses langues ont des spécifications qui contiennent de la grammaire. Par exemple, pour Go , Rust et D.

Analyseurs de descente récursive

La descente récursive est la plus simple des nombreuses approches d'analyse.

Analyseurs de descente récursive - descendants, basés sur des procédures récursives. Il est beaucoup plus facile d'écrire un analyseur, car votre grammaire n'a pas laissé de récursivité . Dans la plupart des langues "jouets", cette technique est suffisante pour l'analyse. GCC utilise un analyseur descendant manuscrit, bien que YACC ait été utilisé auparavant.

Cependant, l'analyse de ces langues peut entraîner des problèmes. En particulier, C, où

 foo * bar 

peut être interprété comme

 int foo = 3; int bar = 4; foo * bar; // unused expression 

ou comment

 typedef struct { int b; } foo; foo* bar; bar.b = 3; 

L'implémentation Clang utilise également un analyseur de descente récursive:

Comme il s'agit de code C ++ normal, une descente récursive permet aux débutants de le comprendre facilement. Il prend en charge des règles personnalisées et d'autres choses étranges requises par C / C ++ et vous aide à diagnostiquer et à corriger facilement les erreurs.

Il convient également de prêter attention à d'autres approches:

• LL décroissant, descente récursive
• ascendant LR, décalage, descente ascendante

Générateurs d'analyseurs

Un autre bon moyen. Bien sûr, il y a aussi des inconvénients - mais cela peut être dit de tout autre choix que les programmeurs font lors de la création de logiciels.

Les générateurs d'analyseurs fonctionnent très rapidement. Il est plus facile de les utiliser que d'écrire votre propre analyseur et d'obtenir un résultat de qualité - bien qu'ils ne soient pas très conviviaux et n'affichent pas toujours des messages d'erreur. De plus, vous devrez apprendre à utiliser le générateur d'analyseur et lors de la promotion du compilateur, vous devrez probablement dérouler le générateur d'analyseur.

Un exemple de générateur d'analyseur est ANTLR , il y en a beaucoup d'autres.

Je pense que cet outil convient à ceux qui ne veulent pas passer du temps à écrire un frontend, et qui préfèrent écrire le milieu et le backend du compilateur / interprète et analyser quoi que ce soit.

Application d'analyse

Si vous ne vous comprenez toujours pas. Même le frontend du compilateur (lex / parse) peut être utilisé pour résoudre d'autres problèmes:

• coloration syntaxique
• Analyse HTML / CSS pour le moteur de rendu
• transpilers: TypeScript, CoffeeScript
• linkers
• REGEX
• analyse des données d'interface
• Analyse d'URL
• des outils de formatage comme gofmt
• Analyse SQL et plus encore.

Mid

Analyse sémantique! L'analyse de la sémantique du langage est l'une des tâches les plus difficiles lors de la création d'un compilateur.

Vous devez vous assurer que tous les programmes d'entrée fonctionnent correctement. Dans mon langage Krug, les aspects liés à l'analyse sémantique n'ont pas encore été inclus, et sans cela, le programmeur devra toujours écrire le bon code. En réalité, cela est impossible - et nous écrivons, compilons, parfois exécutons, corrigeons toujours les erreurs. Cette spirale est sans fin.

De plus, la compilation de programmes est impossible sans une analyse de l'exactitude de la sémantique au stade approprié de la compilation.

Une fois, je suis tombé sur un graphique sur le pourcentage de front-end, mid -land et backend. Ensuite, ça ressemblait

 F: 20% M: 20%: B: 60% 

Aujourd'hui, c'est quelque chose comme

 F: 5% M: 60% B: 35% 

L'interface concerne principalement le générateur, et dans les langages sans contexte qui n'ont pas la dualité de grammaire, ils peuvent être complétés assez rapidement - une descente récursive aidera ici.

Avec la technologie LLVM, la plupart des travaux d'optimisation peuvent être téléchargés dans le framework, qui présente un certain nombre d'optimisations prêtes à l'emploi.

L'étape suivante est l'analyse sémantique, une partie essentielle de la phase de compilation.

Par exemple, dans Rust, avec son modèle de gestion de la mémoire, le compilateur agit comme une grande machine puissante qui effectue divers types d'analyses statiques sur les formulaires d'introduction. Une partie de cette tâche consiste à convertir les données d'entrée sous une forme plus pratique pour l'analyse.

Pour cette raison, l'analyse sémantique joue un rôle important dans l'architecture du compilateur, et le travail préparatoire exténuant comme l'optimisation de l'assemblage généré ou la lecture des données d'entrée dans l'ASD est fait pour vous.

Passages sémantiques

Au cours de l'analyse sémantique, la plupart des compilateurs effectuent un grand nombre de «passages sémantiques» sur le SDA ou une autre forme abstraite d'expression de code. Cet article fournit des détails sur la plupart des passes effectuées dans le compilateur .NET C #.

Je ne considérerai pas chaque passage, d'autant plus qu'ils varient en fonction de la langue, mais plusieurs étapes sont décrites ci-dessous dans Krug.

Annonce de niveau supérieur

Le compilateur passera par toutes les annonces "de haut niveau" dans les modules et sera conscient de leur existence. Il n'ira pas plus loin dans les blocs - il déclarera simplement quelles structures, fonctions, etc. sont disponibles dans l'un ou l'autre module.

Résolution du nom / symbole

Le compilateur parcourt tous les blocs de code dans les fonctions, etc. et les résout - c'est-à-dire, trouve les personnages qui nécessitent une autorisation. Il s'agit d'un passage commun, et c'est d'ici que l'erreur No such symbol XYZ survient généralement lors de la compilation du code Go.

L'exécution de cette passe peut être très difficile, surtout s'il existe des dépendances circulaires dans votre diagramme de dépendances. Certaines langues ne les autorisent pas, par exemple, Go lancera une erreur si l'un de vos packages forme une boucle, comme ma langue Krug. Les dépendances cycliques peuvent être considérées comme un effet secondaire d'une mauvaise architecture.

Les boucles peuvent être déterminées en modifiant DFS dans le diagramme de dépendance, ou en utilisant l'algorithme Tarjan (comme l'a fait Krug) pour définir des boucles (multiples).

Inférence de type

Le compilateur parcourt toutes les variables et affiche leurs types. L'inférence de type dans Krug est très faible; elle génère simplement des variables en fonction de leurs valeurs. Ce n'est en aucun cas un système bizarre, comme ceux que vous pouvez trouver dans des langages fonctionnels comme Haskell.

Les types peuvent être dérivés en utilisant le processus «unification» ou «unification de type». Pour les systèmes de type plus simple, une implémentation très simple peut être utilisée.

Les types sont implémentés dans Krug comme ceci:

 interface Type {}; struct IntegerType : Type { int width; bool signed; }; struct FloatingType : Type { int width; }; struct ArrayType : Type { Type base_type; uint64 length; }; 

Vous pouvez également avoir une inférence de type simple, dans laquelle vous affectez un type aux nœuds d'expression, par exemple, IntegerConstantNode peut être de type IntegerType (64). Et puis vous pouvez obtenir la fonction unify(t1, t2) , qui sélectionnera le type le plus large qui peut être utilisé pour déduire le type d'expressions plus complexes, disons, les expressions binaires. Il s'agit donc d'affecter une variable à gauche aux valeurs des types donnés à droite.

J'ai écrit une fois un simple casting de type sur Go, qui est devenu une implémentation de prototype pour Krug.

Pass Mutabilité

Krug (comme Rust) est par défaut un langage immuable, c'est-à-dire que les variables restent inchangées sauf indication contraire:

 let x = 3; x = 4; // BAD! mut y = 5; y = 6; // OK! 

Le compilateur passe en revue tous les blocs et fonctions et vérifie que leurs «variables sont correctes», c'est-à-dire que nous ne changeons pas ce qui ne suit pas, et que toutes les variables passées à certaines fonctions sont constantes ou modifiables si nécessaire.

Cela se fait à l'aide d'informations symboliques qui ont été collectées lors des passes précédentes. Une table de symboles basée sur les résultats de la passe sémantique contient des noms de jetons et des signes de variabilité variable. Il peut contenir d'autres données, par exemple, en C ++, une table peut stocker des informations sur si un symbole est externe ou statique.

Tables de caractères

Une table de caractères, ou «stab», est une table pour trouver les caractères utilisés dans votre programme. Une table est créée pour chaque étendue, et toutes contiennent des informations sur les caractères présents dans une étendue particulière.

Ces informations incluent des propriétés telles que le nom, le type, le signe de mutabilité du symbole, la présence d'une communication externe, l'emplacement dans la mémoire statique, etc.

Portée

Il s'agit d'un concept important dans les langages de programmation. Bien sûr, votre langue ne doit pas permettre de créer des étendues imbriquées, tout peut être placé dans un même espace de noms!

Bien que la représentation de la portée soit une tâche intéressante pour l'architecture du compilateur, dans la plupart des langages de type C, la portée se comporte (ou est) comme une structure de données de pile.

Habituellement, nous créons et détruisons des étendues, et elles sont généralement utilisées pour gérer les noms, c'est-à-dire qu'elles nous permettent de masquer (l'observation) des variables:

 { // push scope let x = 3; { // push scope let x = 4; // OK! } // pop scope } // pop scope 

Il peut être représenté différemment:

 struct Scope { Scope* outer; SymbolTable symbols; } 

Un petit hors-sujet, mais je recommande de lire la pile de spaghettis . Il s'agit d'une structure de données utilisée pour stocker des zones de visibilité dans les nœuds ASD des blocs opposés.

Systèmes de typage

Beaucoup des sections suivantes peuvent être développées dans des articles séparés, mais il me semble que ce titre mérite le plus. Aujourd'hui, de nombreuses informations sont disponibles sur les systèmes de types, ainsi que sur les variétés des systèmes eux-mêmes, autour desquelles de nombreuses copies se brisent. Je ne m'attarderai pas sur ce sujet, laissez simplement un lien vers l' excellent article de Steve Klabnik .

Un système de type est ce qui est fourni et défini sémantiquement dans le compilateur à l'aide des représentations du compilateur et de l'analyse de ces représentations.

Possession

Ce concept est de plus en plus utilisé dans la programmation. Les principes de la sémantique de la propriété et du mouvement sont ancrés dans la langue Rust , et j'espère qu'ils apparaîtront dans d'autres langues. Rust effectue différents types d'analyses statiques, qui vérifient si l'entrée satisfait à un ensemble de règles concernant la mémoire: qui possède quelle mémoire, quand la mémoire est détruite et combien de références (ou emprunts) existent à ces valeurs ou à la mémoire.

La beauté de Rust réside dans le fait que tout cela se fait pendant la compilation, à l'intérieur du compilateur, afin que le programmeur n'ait pas à gérer le garbage collection ou le comptage de liens. Toutes ces sémantiques sont affectées au système de types et peuvent être fournies avant même que le programme ne soit présenté sous la forme d'un fichier binaire complet.

Je ne peux pas dire comment tout cela fonctionne sous le capot, mais tout cela est le résultat d'une analyse statique et de merveilleuses recherches de l'équipe Mozilla et des participants au projet Cyclone .

Graphiques de flux de contrôle

Pour représenter les flux de programme, nous utilisons des graphiques de flux de contrôle (CFG), qui contiennent tous les chemins que l'exécution du programme peut suivre. Ceci est utilisé dans l'analyse sémantique pour exclure les sections de code inactives, c'est-à-dire les blocs, les fonctions et même les modules qui ne seront jamais atteints pendant l'exécution du programme. Les graphiques peuvent également être utilisés pour identifier les cycles qui ne peuvent pas être interrompus. Ou pour rechercher un code inaccessible, par exemple, lorsque vous appelez une «panique» (appelez une panique), ou que vous revenez dans une boucle, et que le code en dehors de la boucle ne s'exécute pas. L'analyse du flux de données joue un rôle important pendant la phase sémantique du compilateur, je vous recommande donc de lire les types d'analyses que vous pouvez effectuer, leur fonctionnement et les optimisations possibles.

Backend

La dernière partie de notre schéma d'architecture.

Nous avons fait la plupart du travail de génération de binaires exécutables. Cela peut être fait de différentes manières, dont nous discuterons ci-dessous.

- , . , , «».

, . , , . , , , . , .

, . , ++ — Cfront — C.

JavaScript. TypeScript , , , , .

«» , , , , « » . — , , .

LLVM

LLVM: Rust, Swift, C/C++ (clang), D, Haskell.

« », , . , LLVM . , . , , , , 1, 4, 8 16-. , , - .

-

— , — , .

Go — , LLVM ( ). Go , Windows, Linux MacOS. , Krug -.

. , LLVM, , , LLVM , .

, , , LLVM, IR, , , , ( ).

. , , , . IR ( ) «» fprintf . 8cc .

. — Java: , JVM , , Kotlin.

, Java . , . , .
, JVM JIT , JIT-, .

, ! , , . - , , . Godbolt — , , . , , .

, , (strip the debug symbols), , GCC. , - .

. . , . production-.

rwmj , 8 , 80% . 1971-! , Rust.

IR

(intermediate representation, IR) , . , , .

IR . , , , .

IR, «», IR . , SSA — Static Single Assignment, , .

Go IR SSA. IR LLVM SSA, .

SSA , , (constant propagation), ( ) .

, . , , , , . ( 16 32), , (spill to the stack).

— ( ). , , .

:

• (graph colouring) — (NP- ). , (liveness ranges) .
  
• — .
  

. , . , , .

( Name Mangling )

-, , . , .

 fn main() int { let x = 0; { let x = 0; { let x = 0; } } return 0; } 

, ( - :) ) , . , .

LLDB DWARF . LLVM , DWARF GNU-. , , , .

(Foreign Function Interface, FFI )

libc , , . , ?

— . , ( .s/.asm)? ? , Jai . , .

(CaaS)

API-. , Krug-, . , , .

, , , . , API-.

production- CaaS. Microsofts Roslyn, , . , , , , API-, , , Rust RLS .

Krug — — Caasper CaaS-.

Caasper (, , ), , krug, . , , (bootstrap) , .

Krug JavaScript, Go*, , , Krug. JavaScript , yarn/npm.

* Go () , JS.

Caasper . Github Krug, D LLVM. YouTube- .

Krug () .

Liens utiles

• Jack Crenshaw — .
  
• Crafting Interpreters
  
• LLVM ( Go) — !
  
• PL/0
  
• The Dragon Book — , .
  
• 8cc