Compilation/Introduction

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Présentation de la problématique de compilation

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 : de haut niveau qui permet l’usage d’un modèle mathématique ; dont les expressions sont forgé indépendamment des instructions matérielles ; conçu avec des soucis de structuration et de modularité.	langage machine : de bas niveau ; qui reflète l'architecture matérielle au niveau binaire avec manipulation de registres.

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

On distingue quatre niveaux de langages différents :

1. langage machine ;
2. langage d'assemblage ;
3. langage de haut niveau ;
4. langage de commande.

Langage machine 

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 

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 

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

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

On peut distinguer deux types d’outils intervenant dans la chaîne de compilation :

1. 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

Initialement, un texte écrit (ou un programme) est une suite de caractères. L'analyse de ce texte se fait en trois étapes:

1. 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.
2. 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.
3. appréhender le sens du texte, c’est l'analyse sémantique.

Structure d'un compilateur

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 :

1. l'analyse lexicale ;
2. l'analyse syntaxique ;
3. l'analyse sémantique ;
4. la génération de code intermédiaire ;
5. l'optimisation de code ;
6. 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 :

1. la gestion de la table des symboles ;
2. le traitement des erreurs.

Gestion de la table des symboles

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

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

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

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

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

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

Tente d'améliorer l'efficacité du code.

Exemple temp1 := 60.0 * id3 id1 := id2 + temp1

Génération de code

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

Schéma illustrant la chaîne de compilation classique et ses regroupements

En pratique, il arrive souvent que l’on regroupe plusieurs phases :

1. en partie frontale et partie finale ;
2. ou, en passes.

Partie frontale et partie finale

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

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

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.