Compilation/Introduction
Présentation de la problématique de compilation
[modifier | modifier le wikicode]Même en informatique, humains et machines n'utilisent pas le même langage. Toute la problématique d’une chaîne de compilation est de relier la commodité d’expression d’un langage humain, c’est-à-dire qui permet de construire des w:discours facilitant l’entendement humain, avec une série d’instructions machines dont l’exécution réalise automatiquement les objets décrits par le discours. De plus on souhaite généralement que la suite d’instructions soit optimisée de manière à diminuer les ressources temporelles et énergétiques nécessaires à l’exécution.
| Caractéristiques des langages utilisés par les humains | Caractéristiques des langages utilisés par les ordinateurs |
|---|---|
langage de programmation :
|
langage machine :
|
Il existe donc un grand fossé entre ces deux types de langages qui amène à développer des outils de traduction d’un langage source vers un langage cible.
Les différents niveaux de langages
[modifier | modifier le wikicode]On distingue quatre niveaux de langages différents :
- langage machine ;
- langage d'assemblage ;
- langage de haut niveau ;
- langage de commande.
Langage machine
[modifier | modifier le wikicode]C'est une suite binaire directement interprétable par les micro-programmes de la machine. Les opérations et opérandes de chaque instruction dans le jeu d'instruction de la machine sont spécifiés par un code machine. C’est-à-dire qu’à chaque instruction on attribue un nombre, qui est généralement représenté sous forme binaire. Les processeurs ne manipulent pas, à proprement parler, des 0 et des 1. Ces deux symboles sont eux-même des représentations commodes pour l’esprit humain (toute proportion gardée). Toutefois, pour ce qui concerne le domaine logiciel, nous pouvons nous permettre cet abus de langage et réduire la problématique à des codes binaires qui spécifient des numéros d’instruction et leurs opérandes numériques.
Par exemple, en supposant un codage sur un octet où 0000 0001 code l’addition (dont le résultat sera sauvegardé dans un registre quelconque), le code 0000 0001 0000 0001 0000 0010 pourrait coder l’addition du contenu des registre 0000 0001 et 0000 0010, soit l’addition du registre un et deux.
Langage d'assemblage
[modifier | modifier le wikicode]Il est proche du langage machine mais les instructions sont représentés par des symboles mnémoniques, c'est-à-dire plus facile à retenir que le code machine.
Par exemple : ADDF R1, R2
Son exécution nécessite une traduction, ce traducteur est appelé assembleur.
Langage de haut niveau
[modifier | modifier le wikicode]Il est fondé sur un modèle mathématique bien adapté à l’expression des algorithmes et des structures de données. Son exécution nécessite une traduction dont la complexité est proportionnelle au niveau du langage.
Le traducteur de ce type de langage est nommé compilateur.
Les langages tel que C et java appartiennent à cette catégorie.
Langage de commande
[modifier | modifier le wikicode]Il permet de communiquer avec le système d'exploitation. Son rôle essentiel est de permettre de lancer l'exécution de codes exécutables en langage machine.
Des exemples courant sont les shells et les fichiers batch.
Les différents outils de traduction
[modifier | modifier le wikicode]On peut distinguer deux types d’outils intervenant dans la chaîne de compilation :
- le traducteur
- programme qui prend en entrée le code d'un programme écrit dans un langage source et qui produit en sortie un code écrit en langage objet.
- l'assembleur
- c’est un traducteur dont le langage source est un langage d'assemblage. Un compilateur est un traducteur dont le langage source est un langage de haut niveau.
Note : un code objet écrit en langage objet ou code objet contient du code machine et d'autres informations nécessaires à l'édition de lien et au débogage.
Un troisième type peut être dégagé :
- l'interpréteur
- il prend en entrée un programme écrit dans un langage source analyse les instructions du programme source et exécute immédiatement chacune d'elles. Cela signifie qu’il n'y a pas de production de code objet.
Note : les langages semi-compilé comme java utilisent un traducteur et un interpréteur, le traducteur traduit le programme source sous une forme intermédiaire (le bytecode) qui est ensuite interprété par une machine virtuelle.
Les différents niveaux de compréhension d'un texte
[modifier | modifier le wikicode]Initialement, un texte écrit (ou un programme) est une suite de caractères. L'analyse de ce texte se fait en trois étapes:
- reconnaître les mots du texte (déterminer si chaque groupe de caractères appartient à un certain lexique). On transforme une suite de caractères en une suite de mots, c’est l'analyse lexicale.
- exhiber la structure du texte, c'est-à-dire déterminer s'il est conforme à une syntaxe ou une grammaire. On transforme la suite de mots en une structure hiérarchique, c’est l'analyse syntaxique.
- appréhender le sens du texte, c’est l'analyse sémantique.
Structure d'un compilateur
[modifier | modifier le wikicode]La compilation est une tâche complexe. Conceptuellement, cette tâche peut se composer en plusieurs sous-tâches interconnectées. Certaines de ces sous-tâches sont appelés phases. Une phase prend en entrée une représentation intermédiaire du programme source et produit en sortie une autre représentation du même programme source.
Une décomposition typique d'un compilateur comporte six phases :
- l'analyse lexicale ;
- l'analyse syntaxique ;
- l'analyse sémantique ;
- la génération de code intermédiaire ;
- l'optimisation de code ;
- la génération de code (en langage machine/cible).
Les trois premières phases forment le cœur de la partie analyse d'un compilateur et correspondent aux différent niveaux de compréhension d'un texte.
En plus de ces six phases, deux autres sous-tâches qui interagissent avec les six premières :
- la gestion de la table des symboles ;
- le traitement des erreurs.
Gestion de la table des symboles
[modifier | modifier le wikicode]Cette tâche essentielle mémorise les identificateurs utilisés dans le programme source et collecte les informations associées à ces identificateurs, comme le type, la portée (région du programme dans laquelle l'identification est valide, etc.).
La table des symboles est une structure de données qui contient un enregistrement pour chaque identificateur muni de champs permettant de stocker les informations relatives à ces identificateurs. Cette structure est conçue de façon à accéder rapidement à ces informations.
Traitement des erreurs
[modifier | modifier le wikicode]Chaque phase peut rencontrer une erreur qui doit être traitée de façon à ce que la compilation puisse continuer et que d'autres erreurs puissent être détectées. En effet un compilateur qui s'arrête dès la première erreur n’est pas très pratique.
Analyse lexicale
[modifier | modifier le wikicode]Cette phase transforme un flot de caractère en un flot d'unités lexicales (tokens en anglais) dont chacune représente une suite de caractères. Une unité lexicale peut être un mot-clef, une constante, un identificateur, un opérateur ou un séparateur.
Exemple :
position
|
:=
|
initiale
|
+
|
vitesse
|
*
|
60
|
| ID | AFF | ID | PLUS | ID | MULT | CST |
- ID
- identificateur
- AFF
- affection
- CST
- constante
Certaines unités lexicales comme par exemple les identificateurs ou les constantes ont une valeur lexicale qui est la suite de caractères qu'elle représente.
Exemple : (ID, "position") AFF (ID, "initiale") PLUS (ID, "vitesse") MULT (CST, 60)
Note : lorsqu'un identificateur est rencontré il est entré dans la table des symboles, s'il n'y est pas déjà.
Analyse syntaxique
[modifier | modifier le wikicode]Elle détermine si la suite de tokens forme une construction permise, c'est-à-dire qu'elle est conforme à la grammaire définissant le langage source.
Exemple : CST AFF PLUS MULT ID ID ID est une construction incorrecte.
L’analyse syntaxique rend également explicite la structure hiérarchique. On peut pour cela par exemple utiliser des parenthèses pour délimiter les structures imbriqués.
Exemple : ID AFF (ID PLUS (ID MULT CST) )
L'analyse syntaxique définit un arbre de syntaxe abstraite.
Note : on parle de syntaxe abstraite par opposition à la syntaxe concrète que l'utilisateur emploie lors de la saisie du code.
AFF │ │ ├──PLUS │ │ │ ├──MULT │ │ │ │ │ ├──CST │ │ │ │ │ └──ID │ └──ID │ └──ID
Analyse sémantique
[modifier | modifier le wikicode]Elle vérifie la cohérence des types et enrichit (on dit aussi « décore ») l'arbre de syntaxe abstraite par exemple par des opérations de conservations de type.
Ainsi l'arbre :
AFF │ │ ├──PLUS │ │ │ ├──MULT │ │ │ │ │ ├──CST │ │ │ │ │ └──ID │ └──ID │ └──ID
peut donner une fois traité :
AFF │ │ ├──PLUS │ │ │ ├──MULT │ │ │ │ │ ├──EntierVersRéel │ │ │ │ │ │ │ └──CST │ │ │ │ │ └──ID │ └──ID │ └──ID
Génération de code intermédiaire
[modifier | modifier le wikicode]Construit une représentation intermédiaire du programme source c'est-à-dire un code pour une machine abstraite. Cette dernière est une machine dont les instructions sont plus évoluées que celles d'une machine standard.
Ce code peut prendre plusieurs formes. Une forme possible est un code à trois adresses, c'est-à-dire une séquence d'instructions à au plus trois opérandes.
Exemple :
temp1 := EntierVersRéel(60)
temp2 := id3 * temp1
temp3 := id2 + temp2
id1 := temp3
Optimisation de code
[modifier | modifier le wikicode]Tente d'améliorer l'efficacité du code.
Exemple
temp1 := 60.0 * id3
id1 := id2 + temp1
Génération de code
[modifier | modifier le wikicode]Cette phase produit du code objet :
- choisissant les emplacements mémoires pour les données ;
- sélectionnant le code machine pour implémenter les instructions du code intermédiaire ;
- allouant les registres.
Exemple : en utilisant les registres R1 et R2
MOVF id3, R2
MULF #600, R2
MOVF id2, R1
ADDF R2, R1
MOVF R1, id1
Regroupement de phases
[modifier | modifier le wikicode]
En pratique, il arrive souvent que l’on regroupe plusieurs phases :
- en partie frontale et partie finale ;
- ou, en passes.
Partie frontale et partie finale
[modifier | modifier le wikicode]Les différentes phases sont souvent réunies en une phase frontale ((en)front end) indépendante de la machine et une partie finale ((en)back end) dépendante de la machine.
La phase frontale comprend les cinq premières phases de la compilation (l'analyse lexicale, l'analyse syntaxique, l'analyse sémantique, la génération de code intermédiaire, l'optimisation de code), et la phase finale celle restante (la génération de code).
Passes
[modifier | modifier le wikicode]On implémente habituellement plusieurs phases en une seule passe qui comprends alors une lecture de la représentation intermédiaire en entrée plus une écriture de la représentation intermédiaire en sortie.
Il est préférable d’avoir peu de passe pour réduire le temps de compilation.
Par exemple :
- l'analyseur syntaxique peut directement faire appel à l'analyseur lexicale au fur et à mesure lorsqu’il a besoin d'une nouvelle unité lexicale ;
- l'analyseur sémantique peut directement produire du code intermédiaire.
On peut ainsi souvent regrouper les quatre premières phases en une seule passe.
Objectifs du cours
[modifier | modifier le wikicode]Le cours vise à étudier et maîtriser la construction d'un compilateur.
Cette construction s'appuie sur des résultats en théorie des langages et nécessite pour être abordé :
- comprendre et savoir écrire des expressions régulières et des automates (pour l'analyse lexicale) ;
- connaître la grammaire algébrique et les automates à piles (pour l'analyse sémantique) ;
- connaître la grammaire attribuée (pour la génération de code intermédiaire).
Il existe des outils pour aider à la construction d'un compilateur :
- Lex pour l'analyse lexicale ;
- Yacc pour l'analyse syntaxique ;
- LLVM pour une infrastructure complète de compilateur.
