Compilateur - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
Un compilateur est un programme informatique qui traduit un langage, le langage source, en un autre, appelé le langage cible (ou langage objet), en préservant la signification du texte source. Ce schéma général décrit un grand nombre de programmes différents ; et ce que l'on entend par « signification du texte source » dépend du rôle du compilateur. Lorsque l'on parle de compilateur, on suppose aussi en général que le langage source est, pour l'application envisagée, de plus haut niveau que le langage cible, c'est-à-dire qu'il présente un niveau d'abstraction supérieur.
En pratique, un compilateur sert le plus souvent à traduire un code source écrit dans un langage de programmation en un autre langage, habituellement un langage d'assemblage ou un langage machine. Le programme en langage machine produit par un compilateur est appelé code objet.
Le premier compilateur, A-0 System, a été écrit en 1951 par Grace Hopper.
Structure et phases d'un compilateur
La tâche principale d'un compilateur est de produire du code objet correct. La plupart des compilateurs permettent d'optimiser le code (le code objet optimisé s'exécutera plus rapidement, ou aura une occupation mémoire moindre).
Un compilateur fonctionne par analyse-synthèse, c'est-à-dire qu'au lieu de remplacer chaque construction du langage source par une suite équivalente de constructions du langage cible, il commence par analyser le texte source pour en construire une représentation intermédiaire qu'il traduit à son tour en langage cible.
Il est donc naturel de séparer — au moins conceptuellement, mais aussi en pratique — le compilateur en une partie avant (ou frontale), parfois appelée « souche », qui lit le texte source et produit la représentation intermédiaire, et une partie arrière (ou finale), qui parcourt cette représentation pour produire le texte cible. Dans un compilateur idéal, la partie avant est indépendante du langage cible, tandis que la partie arrière est indépendante du langage source. Certains compilateurs effectuent de plus sur la forme intermédiaire des traitements substantiels, que l'on peut regrouper en une partie centrale, indépendante à la fois du langage source et de la machine cible. On peut ainsi écrire des compilateurs pour toute une gamme de langages et d'architectures en partageant la partie centrale, à laquelle on attache une partie avant par langage et une partie arrière par architecture.
Les étapes de la compilation incluent :
- l'analyse lexicale, qui coupe le texte du code source en petits morceaux appelés jetons (tokens).
Chaque jeton est une unité atomique unique de la langue (unités lexicales ou lexèmes), par exemple un mot-clé, identifiant ou nom du symbole. La syntaxe de jeton est généralement un langage régulier, donc un automate à états finis construits à partir d'une expression régulière peut être utilisé pour le reconnaître. Cette phase est aussi appelée lexing ou à balayage, et le logiciel qui effectue une analyse lexicale est appelé un analyseur lexical ou un scanner (lex, flex par exemples).
- le prétraitement, phase nécessaire pour certaines langues, par exemple, C, qui prend en charge la substitution de macro et de la compilation conditionnelle.
Généralement, la phase de prétraitement se produit avant que l'analyse syntaxique ou sémantique, par exemple dans le cas de C, le préprocesseur manipule les symboles lexicaux plutôt que des formes syntaxiques.
- l'analyse syntaxique implique l'analyse de la séquence jeton pour identifier la structure syntaxique du programme.
Cette phase s'appuie généralement sur un arbre d'analyse, qui remplace la séquence linéaire de jetons avec une structure en arbre construit selon les règles d'une grammaire formelle qui définit la syntaxe du langage. L'arbre d'analyse est souvent analysé, augmenté et transformé par des phases plus tard dans le compilateur. Yacc et Bison sont les analyseurs syntaxiques les plus utilisés.
- l'analyse sémantique, qui est la phase durant laquelle le compilateur ajoute des informations sémantiques à l'arbre d'analyse et construit la table des symboles.
Cette phase effectue des vérifications sémantiques comme la vérification de type (vérification des erreurs de type), ou objet de liaison (associant variables et des références de fonction avec leurs définitions), ou tâche définie (nécessitant toutes les variables locales doivent être initialisées avant utilisation), le rejet des programmes incorrects ou l'émission d'avertissements. L'analyse sémantique nécessite habituellement un arbre d'analyse complet, ce qui signifie que cette phase est la conséquence logique de la phase d'analyse, et précède logiquement la phase de génération de code, mais il est souvent possible de replier les phases multiples dans une passe sur le code dans une mise en œuvre de compilateur.
- la transformation du code source en code intermédiaire ;
- l'application de techniques d'optimisation sur le code intermédiaire : c'est à dire rendre le programme plus rapide, tout en gardant des délais de compilation raisonnables.
Le but de cette phase est de générer un code réduit, permises par des passes de compilation qui se greffent par dessus un compilateur existant. C’est un domaine de recherche continuel !
- la génération de code avec l'allocation de registres et la traduction du code intermédiaire en code objet, avec éventuellement l'insertion de données de débogage et d'analyse de l'exécution ;
- et enfin l'édition des liens.
Ces différentes étapes expliquent que les compilateurs fassent toujours l'objet de recherches, particulièrement dans le domaine de l'optimisation du code produit.
La plupart (mais pas tous) des compilateurs traduisent un fichier source d'un programme écrit dans un langage de programmation en un fichier objet (ou un exécutable, ou un fichier en assembleur, ou même en un autre langage).
Une implémentation (réalisation concrète) d'un langage de programmation peut être interprétée ou compilée. C'est cette réalisation qui est un compilateur ou un interpréteur, et un langage de programmation (spécification plus ou moins théorique et formalisée de sa syntaxe et de sa sémantique) peut avoir une implémentation compilée, et une autre interprétée.
