Comprendre le Compilateur : Processus et Structures Clés

Le Rôle du Compilateur

Un compilateur est un programme informatique qui traduit un programme écrit dans un langage de programmation vers un autre langage de programmation, produisant un programme équivalent que la machine sera capable d'interpréter. Habituellement, ce deuxième langage est le langage machine, mais il peut s'agir de tout autre texte. Ce processus de traduction est appelé compilation.¹

Un compilateur est un programme qui traduit le code source d'un programme en langage de haut niveau vers un niveau de langage plus faible (généralement en langage machine). De cette façon, un développeur peut concevoir un programme dans un langage beaucoup plus proche de la façon de penser d'un être humain, et ensuite le compiler vers un langage plus gérable par un ordinateur.

Le Processus de Construction

C'est le processus par lequel les instructions écrites dans un langage de programmation sont traduites en langage machine. En plus d'un traducteur, vous pourriez avoir besoin d'autres programmes pour créer un programme objet exécutable. Un programme source peut être divisé en modules stockés dans des fichiers séparés. La tâche de rassembler le programme source est souvent confiée à un programme distinct : le préprocesseur. Le préprocesseur peut développer les abréviations, les appels de macro et les états du langage source.

Habituellement, la création d'un programme exécutable (un typique .exe pour Microsoft Windows ou DOS) comporte deux étapes. La première étape est appelée compilation (en soi) et traduit le code source écrit dans un langage de programmation en un fichier stocké en code de bas niveau (généralement en code objet, pas directement en langage machine). La deuxième étape est appelée linkage (ou édition de liens) dans laquelle les liens au niveau du code de bas niveau générés pour tous les fichiers et sous-programmes qui ont été commandés pour compiler sont ajoutés, ainsi que le code de fonction se trouvant dans les bibliothèques du compilateur, pour communiquer directement avec le système d'exploitation, et enfin traduire le code objet en code machine pour générer un module exécutable.

Ces deux étapes peuvent être effectuées séparément, en stockant le résultat de la phase de compilation dans des fichiers objets (un typique .obj pour Microsoft Windows, DOS ou Unix) pour les lier plus tard, ou en créant directement l'exécutable, auquel cas la phase de compilation n'est stockée que temporairement. Un programme peut avoir des parties écrites dans des langages différents (par exemple C, C++ et Asm), qui pourraient être compilées séparément puis liées ensemble pour former un seul module exécutable.

Les Étapes du Processus

Le processus de traduction consiste en interne en plusieurs étapes ou phases, qui effectuent différentes opérations logiques. Il est utile de penser à ces phases comme des parties distinctes dans le traducteur, et elles peuvent effectivement être écrites comme des opérations codées séparément, mais dans la pratique, elles sont souvent intégrées.

Phase d'Analyse

Analyse Lexicale

Article détaillé : Lexer

L'analyse lexicale est la première étape. Ici, le programme source est lu de gauche à droite et regroupé en composantes lexicales (tokens), qui sont des séquences de caractères ayant une signification. De plus, tous les espaces, les lignes blanches, les commentaires et autres informations superflues sont retirés du programme source. Elle vérifie également que les symboles du langage (mots-clés, opérateurs,...) sont correctement orthographiés.

Comme les tâches effectuées par l'analyseur lexical sont un cas particulier de la « reconnaissance de motifs » (pattern matching), des méthodes de spécification et de reconnaissance des formes sont nécessaires. Ces méthodes sont principalement les expressions régulières et les automates finis. Toutefois, un analyseur lexical est aussi le traducteur qui gère la saisie du code source, et puisque cette tâche implique souvent une dépense de temps importante, l'analyseur lexical doit fonctionner aussi efficacement que possible.

Analyse Syntaxique

Article détaillé : Parser

À ce stade, les caractères ou les éléments lexicaux sont regroupés de façon hiérarchique en phrases grammaticales que le compilateur utilise pour synthétiser la sortie. Elle vérifie si le produit de la phase précédente est syntaxiquement correct selon la grammaire du langage. En général, les phrases grammaticales du programme source sont représentées par un arbre d'analyse.

La structure hiérarchique d'une règle est généralement exprimée en utilisant la récursivité. Par exemple, vous pouvez donner les règles suivantes dans le cadre de la définition des expressions :

• Tout identificateur est une expression.
• Tout nombre est une expression.
• Si expression₁ et expression₂ sont des expressions, alors le sont aussi :
  • expression₁ + expression₂
  • expression₁ * expression₂
  • (Expression₁)

Les règles 1 et 2 sont les règles de base (non récursives), tandis que l'article 3 définit les expressions en termes d'opérateurs appliqués à d'autres expressions.

La division entre l'analyse lexicale et syntaxique est quelque peu arbitraire. Un facteur de division pour déterminer est de savoir si une construction du langage source est de nature récursive ou non. Les constructions lexicales n'ont pas besoin de récursion, alors que les structures syntaxiques en ont souvent besoin. La récursivité n'est pas nécessaire pour reconnaître les identificateurs, qui sont généralement des chaînes de lettres et de chiffres, commençant par une lettre. Habituellement, les identifiants sont reconnus par la simple considération du flux d'entrée, dans l'espoir de trouver un caractère qui n'est ni une lettre ni un chiffre, et après avoir réuni toutes les lettres et chiffres trouvés jusqu'à ce point dans une composante lexicale appelée ID. De plus, ce type d'analyse n'est pas assez puissant pour analyser des expressions ou des propositions. Par exemple, nous ne pouvons pas correctement faire correspondre les parenthèses dans les expressions ou les mots dans les phrases sans imposer une sorte de hiérarchie ou d'imbrication à l'entrée.

Analyse Sémantique

La phase d'analyse sémantique vérifie le programme source pour essayer de trouver des erreurs sémantiques et rassemble des informations sur les types pour la phase ultérieure de la génération de code. Elle utilise la structure hiérarchique déterminée par la phase d'analyse syntaxique pour identifier les opérateurs et les opérandes des expressions et des propositions.

Un élément important de l'analyse sémantique est la vérification de type. Ici, le compilateur vérifie si chaque opérateur a des opérandes autorisés par la spécification du langage source. Par exemple, les définitions de nombreux langages de programmation exigent que le compilateur signale une erreur chaque fois que vous utilisez un nombre réel comme indice d'une matrice. Cependant, la spécification du langage peut imposer des restrictions sur les opérandes, par exemple, lorsqu'un opérateur arithmétique binaire est appliqué à un nombre entier et un nombre réel. Il vérifie que le régime a défini la bonne taille.

Phase de Synthèse de Code

Elle consiste à générer le code objet équivalent au programme source. Le code objet est généré uniquement lorsque le programme source est sans erreur d'analyse, ce qui ne signifie pas que le programme s'exécutera correctement, étant donné qu'un programme peut contenir des idées fausses ou des expressions mal calculées. Habituellement, le code objet est un code machine relocalisable ou du code assembleur. Les emplacements mémoire sont choisis pour chacune des variables utilisées par le programme. Ensuite, chacune des instructions intermédiaires est convertie en une séquence d'instructions machine qui exécute la même tâche. Un aspect essentiel est l'attribution des variables d'entrée.

Génération de Code Intermédiaire

Après l'analyse syntaxique et sémantique, certains compilateurs génèrent explicitement une représentation intermédiaire du programme source. Vous pouvez considérer cela comme une représentation intermédiaire du programme pour une machine abstraite. Cette représentation intermédiaire doit présenter deux propriétés importantes : elle doit être facile à produire et facile à traduire en programme objet.

La représentation intermédiaire peut prendre plusieurs formes. Il existe une forme intermédiaire appelée « code à trois adresses » qui ressemble au langage d'assemblage d'une machine dans laquelle chaque emplacement mémoire peut agir comme un enregistrement. Le code à trois adresses se compose d'une séquence d'instructions, dont chacune a au plus trois opérandes. Cette représentation intermédiaire a plusieurs propriétés :

• Premièrement : Chaque instruction à trois adresses possède au plus un opérateur, en plus de l'affectation. Ainsi, lorsque ces instructions sont générées, le traducteur doit décider de l'ordre dans lequel toutes les opérations sont exécutées.
• Deuxièmement : Le traducteur doit générer un nom temporaire pour stocker les valeurs calculées pour chaque énoncé.
• Troisièmement : Quelques instructions en « trois voies » ont moins de trois opérandes, par exemple, l'affectation.

Optimisation du Code

La phase d'optimisation du code vise à améliorer le code intermédiaire, afin que le code machine résultant s'exécute plus rapidement. Cette phase de l'étape de synthèse est possible, surtout si le traducteur est un compilateur (un interpréteur ou un exécuteur peut difficilement optimiser le code objet). Il existe une grande variation dans le degré d'optimisation que gèrent les différents compilateurs. Dans ceux qui effectuent beaucoup d'optimisation, appelés compilateurs d'optimisation, une partie significative du temps du compilateur est consacrée à cette phase. Cependant, il existe des optimisations simples qui améliorent considérablement le temps d'exécution sans que la compilation du programme ne soit trop lente.

Structure de Données Clés

L'interaction entre les algorithmes utilisés par les phases du compilateur et les structures de données qui soutiennent ces phases est naturellement très forte. L'auteur du compilateur s'efforce de mettre en œuvre ces algorithmes d'une manière aussi efficace que possible, sans ajouter trop de complexité. Idéalement, un compilateur devrait être capable de compiler un programme en un temps proportionnel à sa taille.

Composants ou Jetons Lexicaux

Lorsqu'un analyseur lexical rencontre les caractères formant un jeton, il représente généralement un jeton symbolique, c'est-à-dire une valeur d'un type de données énuméré qui représente l'ensemble des jetons du langage source. Il est également parfois nécessaire de conserver la chaîne ou toute autre information même qui en est dérivée, comme son nom associé à un jeton d'identification ou la valeur d'un jeton numérique.

Dans la plupart des langages, l'analyseur lexical suffit de générer un jeton à la fois. Dans ce cas, on peut utiliser une simple variable globale pour conserver les informations du jeton. Dans d'autres cas (l'exemple le plus notable est FORTRAN), vous aurez besoin d'un tableau (ou vecteur) de jetons.

Arbre de Syntaxe

Si l'analyseur génère un arbre de syntaxe, celui-ci est habituellement construit comme une structure standard basée sur des pointeurs qui est allouée dynamiquement au fur et à mesure de l'analyse. L'arbre entier peut alors être stocké comme une variable unique qui pointe vers le nœud racine. Chaque nœud de la structure est un enregistrement dont les champs représentent les données recueillies par l'analyseur, puis par l'analyseur sémantique. Par exemple, le type de données d'une expression peut être stocké comme un champ dans le nœud de l'arbre de syntaxe de l'expression.

Parfois, pour économiser de l'espace, ces champs sont alloués dynamiquement, ou stockés dans d'autres structures de données comme la table des symboles, ce qui permet une allocation et une désallocation sélectives. En fait, chaque nœud de l'arbre de syntaxe peut lui-même nécessiter différents attributs à stocker, selon le type de structure du langage qu'il représente. Dans ce cas, chaque nœud de l'arbre de syntaxe peut être représenté par une variable d'enregistrement, chaque nœud de la classe ne contenant que les informations nécessaires à ce cas.

Table des Symboles

Cette structure de données conserve les informations associées aux identifiants, fonctions, variables, constantes et types de données. La table des symboles interagit avec presque toutes les phases du compilateur : l'analyseur lexical, l'analyseur syntaxique et l'analyseur sémantique peuvent saisir les identificateurs dans le tableau, l'analyseur sémantique y ajoutera d'autres types de données et informations, et les phases de génération et d'optimisation de code utilisent les informations fournies par la table des symboles pour faire les sélections de code appropriées pour l'objet.

Puisque la table des symboles sera accédée si souvent, les opérations d'insertion, de suppression et d'accès doivent être efficaces, de préférence en temps constant. Une structure de données standard à cette fin est la table d'adressage ou de calcul de hachage, mais différentes structures arborescentes peuvent être utilisées. Parfois, plusieurs tables sont utilisées et maintenues dans une liste ou une pile.

Table des Littéraux

La recherche et l'insertion rapides sont également essentielles pour la table des littéraux, qui stocke les constantes et les chaînes de caractères utilisées dans le programme. Cependant, une table des littéraux n'a pas besoin de suppressions, car les données sont appliquées globalement au programme et une constante ou une chaîne n'apparaît qu'une seule fois dans ce tableau. La table des littéraux est importante pour réduire la taille d'un programme en mémoire en permettant la réutilisation des constantes et des chaînes. Elle est également nécessaire pour construire le générateur de code pour les adresses symboliques des littéraux et pour y entrer les définitions de données dans le fichier de code objet.

Code Intermédiaire

Selon le type de code intermédiaire (par exemple, le code à trois adresses ou le code P) et les types d'optimisations effectuées, ce code peut être stocké comme un tableau de chaînes, un fichier texte temporaire ou une liste de structures connexes. Dans les compilateurs qui effectuent des optimisations complexes, une attention particulière doit être portée à la sélection des représentations qui permettent une réorganisation facile.

Génération de Code Intermédiaire

Après l'analyse syntaxique et sémantique, certains compilateurs génèrent explicitement une représentation intermédiaire du programme source. Vous pouvez considérer cela comme une représentation intermédiaire d'un programme de machine abstraite. Cette représentation intermédiaire doit présenter deux propriétés importantes : elle doit être facile à produire et facile à traduire en programme objet.

La représentation intermédiaire peut prendre plusieurs formes. Il existe une forme intermédiaire appelée « code à trois adresses », qui ressemble au langage d'assemblage pour une machine dans laquelle chaque emplacement mémoire peut agir comme un enregistrement. Le code à trois adresses se compose d'une séquence d'instructions, dont chacune a au plus trois opérandes. Le code du programme source (1) peut apparaître en trois adresses comme suit :

 temp1: = entarea1 (60)
 temp2: = id3 * temp1 (2)
 TEMP3: = id2 + temp2
 id1: = TEMP3

Cette représentation intermédiaire a plusieurs propriétés. D'abord, chaque instruction en trois adresses possède au plus un opérateur, en plus de l'affectation. Par conséquent, lorsque ces instructions sont générées, le compilateur doit décider de l'ordre dans lequel les opérations sont exécutées ; la multiplication précède l'addition dans le programme source. Deuxièmement, le compilateur doit générer un nom temporaire pour stocker les valeurs calculées pour chaque énoncé. Troisièmement, certaines instructions en « trois voies » ont moins de trois opérandes, comme la dernière et les premières instructions.

Optimisation de Code

La phase d'optimisation du code tente d'améliorer le code intermédiaire, afin que le code machine s'exécute plus rapidement. Certaines optimisations sont triviales. Par exemple, un algorithme naturel génère le code intermédiaire (2) en utilisant une instruction par opérateur de la représentation de l'arbre après l'analyse sémantique, bien qu'il existe une meilleure façon d'effectuer les mêmes calculs en utilisant les deux états :

 Temp1: = id3 * 60.0 (3)
 Id1: = id2 + temp1

Cet algorithme est simple : rien de mal, car le problème peut être résolu dans la phase d'optimisation du code. Autrement dit, le compilateur peut déduire que la conversion du réel 60 peut être faite une fois pour toutes au moment de la compilation, de sorte que l'opération réelle puisse être supprimée. De plus, TEMP3 n'est utilisé qu'une seule fois, pour transmettre sa valeur à id1. Il est donc possible de remplacer TEMP3 par id1, ce qui rend la dernière instruction de (2) inutile, et vous obtenez le code (3).

Il existe de nombreuses variations dans le degré d'optimisation du code que gèrent les différents compilateurs. Dans ceux qui effectuent beaucoup d'optimisation, appelés « compilateurs d'optimisation », une partie significative du temps du compilateur est consacrée à cette phase. Cependant, il existe des optimisations simples qui améliorent considérablement le temps d'exécution sans que la compilation du programme ne soit trop lente.

Fichiers Temporaires

Au début, l'ordinateur n'avait pas assez de mémoire pour stocker un programme complet lors de la compilation. Ce problème a été résolu en utilisant des fichiers temporaires pour conserver les produits des étapes intermédiaires au cours de la traduction ou en compilant à la volée, c'est-à-dire en ne conservant qu'assez d'informations des parties précédentes du programme source pour permettre la traduction.

Les limites de mémoire sont maintenant un problème beaucoup plus faible, et il est possible de conserver toute l'unité de compilation en mémoire, surtout si la collection est disponible séparément dans le langage. Cependant, il est parfois utile pour les compilateurs de générer des fichiers intermédiaires au cours de certaines étapes du traitement. Typique de ces derniers est la nécessité de traiter la correction arrière lors de la génération de code.