Compilation
Cours et Travaux Pratiques
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
1
Objectifs
Introduire les méthodes d'analyse syntaxique et d'analyse sémantique, dans le cadre de
la construction de compilateurs et de traduction d'un formalisme en un autre.
Comprendre le cheminement d'un Comprendre les étapes du processus de
programme (texte) source vers un compilation d’un langage évolué
programme (code).
FONDAMENTAUX
Comprendre les méthodes et techniques Se familiariser, en TP, avec des outils de
utilisées en analyse lexicale, syntaxique génération d’analyseurs lexicaux et
et sémantique. syntaxiques (LEX et YACC).
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
2
Contenu (1/2)
Chapitre 1 : Introduction à la Compilation
• Différentes étapes de la Compilation
• Compilation, Interprétation, Traduction
Chapitre 2 : Analyse lexicale
• Expressions régulières
• Grammaires
• Automates d’états finis
• Un exemple de générateur d’analyseurs lexicaux : LEX
Chapitre 3 : Analyse syntaxique
• Définitions : grammaire syntaxique, récursivité gauche,
factorisation d’une grammaire, grammaire e-libre.
• Calcul des ensembles des débuts et suivants.
• Méthodes d’analyse descendantes : la descente récursive, LL(1).
• Méthodes d’analyse ascendantes : LR(1), SLR(1), LALR(1),
(méthode des items).
Mr. Jean Marius
IBARA KIEBE KANIMBOET • Un exemple de générateur d’analyseur syntaxique : YACC
Doctorant PhD en IA
3
Contenu(2/2)
Chapitre 4 : Traduction dirigée par la syntaxe (Analyse
sémantique)
Chapitre 5 : Formes intermédiaires
• Forme postfixée
• Forme quadruplés
• Triplés directs et indirects
• Arbre abstrait
Chapitre 6 : Allocation – Substitution- Organisation des
données à l’exécution
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
4
Prérequis
• Introduction à l’algorithme et à la programmation C/C++
• Théorie des langages (automates et langages).
Modalités de contrôle des connaissances
• Examen final : 50%
• TD : 25% (50% : présence et participation et 50% : micro interrogation)
• TP : 25% (50% : présence et participation et 50% : évaluations sur machine)
Références bibliographiques
• 1. Aho A., Sethi R., Ullman J., « Compilateurs : Principes, techniques et outils », Inter-
éditions, 1991 et Dunod, 2000
• 2. Drias H., « Compilation: Cours et exercices », OPU, 1993
• 3. Wilhem R., Maurer D., « Les compilateurs: Théorie, construction, génération », Masson,
1994
• Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullmann « Compilateurs principes,
Mr. Jean Marius techniques et outils », 2ème édition.
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
5
Chapitre 1
Introduction à la compilation
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
1.1 Définitions
▪ Un compilateur est un programme :
1. qui a comme entrée un code source écrit en langage de haut niveau (langage évolué), appelé
langage source.
2. et produit comme sortie un code cible en langage de bas niveau (langage d’assemblage ou
langage machine), appelé le langage cible.
▪ Un compilateur est donc un traducteur de langage évolué qu’on ne doit pas confondre avec un
interpréteur qui est un autre type de traducteur.
▪ Le rôle du compilateur se limitera à produire en sortie des messages d’erreurs.
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Figure 1.1 : Rôle d’un compilateur
Doctorant PhD en IA
7
1.1 Définitions
Interpréteur & Compilateur
▪ Un interpréteur, au lieu de produire un programme cible comme dans le cas d’un compilateur,
exécute lui-même au fur et à mesure les opérations spécifiées par le programme source. Il
analyse une instruction après l’autre puis l’exécute immédiatement. Un compilateur travaille
simultanément sur le programme et sur les données.
▪ L’interpréteur doit être présent sur le système à chaque fois que le programme est exécuté, ce
qui n’est pas le cas avec un compilateur, ce qui n’est pas le cas avec un compilateur.
Avantage et inconvénient
Avantage Inconvénient
Interpréteurs Processus de développement simple Processus de traduction peu efficace
(en particulier débogage) et vitesse d’exécution lente
Transmet au processeur l’intégralité Toute modification du code nécessite
Compilateurs du code machine prêt à l’emploi et une nouvelle traduction (correction
Mr. Jean Marius exécutable des erreurs, extension du logiciel, etc.)
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
8
1.1 Définitions
Langages interprétés & langages compilés
▪ Un langage compilé est plus adapté à un programme qui évolue rarement mais est souvent
exécuté, dans un environnement informatique stable.
Exemple : C, C++, Pascal
▪ Un langage interprété est plus adapté à une utilisation interactive et à un programme qui
évolue souvent, mais n’est pas exécuté dans son ensemble de façon répétitive.
Exemple : PHP, Perl, Python, Ruby, BASIC, R, MATLAB, etc.
Avantages et inconvénients
Langages Avantage Inconvénient
Fonctionnent sur toutes les plateformes et Tout opérateur doit être examiné par
Interprétés
code est plus léger, plus simple à écrire. l’interpréteur
Mr. Jean Marius Code compilé dépends de la
IBARA KIEBE KANIMBOET Compilés Plus rapides que les langages interprétés
plateforme
Doctorant PhD en IA
9
1.2 Structure générale d’un compilateur
Mr. Jean Marius
Figure 1.2 : Phases et modules de compilation
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
10
1.2 Structure générale d’un compilateur
1.2.1 Analyseur lexical
L’analyseur lexical a pour rôle principal la lecture du texte du code source puis la formation des
unités lexicales.
Objectifs :
1. Vérifier que le texte fourni en entrée peut se découper en mots, de sorte que chaque
mot appartienne au langage utilisé.
2. Découper le texte en unités lexicales, appelées également lexèmes ou tokens, de sorte
que chaque token représente un mot du langage. Ce découpage sera utilisé dans la
phase suivante.
3. Élimination des informations inutiles pour l’obtention du code cible, le stockage des
identificateurs dans la table des symboles et la transmission d’une entrée à l’analyseur
syntaxique. Il s’agit généralement du caractère espace et des commentaires.
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
11
1.2 Structure générale d’un compilateur
1.2.1 Analyseur lexical
Exemple : Considérons l’expression d’affectation a := b + 2 *c ; Les unités lexicales qui
apparaissent dans cette expression sont :
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
12
1.2 Structure générale d’un compilateur
1.2.2 Analyse syntaxique
Il a pour rôle principal la vérification de la syntaxe du code en regroupant les unités lexicales
suivant des structures grammaticales qui permettent de construire une représentation syntaxique
du code source. Cette dernière a souvent une structure en arbre. Notons que durant cette phase,
des informations, telles que le type des identificateurs, sont enregistrées dans la table des
symboles.
Objectifs :
1. Vérifier que le flux de tokens forme une succession de phrases conforme à la syntaxe
du langage utilisé.
2. Transformer le flux de tokens en un arbre appelé arbre de syntaxe abstraite (ASA).
Cet arbre sera utilisé dans la phase suivante.
Exemple : Considérons l’expression d’affectation a := b + 2 *c ; Les unités lexicales qui
apparaissent dans cette expression sont :
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
13
1.2 Structure générale d’un compilateur
1.2.2 Analyse syntaxique
Exemple : La représentation sous forme d’arbre syntaxique de l’expression « a := b + 2 * c »
est donnée par :
Figure 1.3 : Arbre syntaxique et parcours d’évaluation
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
14
1.2 Structure générale d’un compilateur
1.2.3 Analyse sémantique
Objectif : Vérifier que toutes les phrases décrites dans l’ASA ont un sens (elles veulent
dire quelque chose) dans le langage utilisé.
Exemple : Dans l’analyse sémantique de « a := b + 2 * c ; », il faut vérifier que, si « a » est
de type entier, alors « b » et « c » le sont aussi, sinon il faut signaler une erreur.
Mr. Jean Marius
IBARA KIEBE KANIMBOET Figure 1.4 : Enrichissement de l’arbre syntaxique lors de
Doctorant PhD en IA la phase d’analyse sémantique
15
1.2 Structure générale d’un compilateur
1.2.4 Générateur de code intermédiaire
Certains compilateurs construisent explicitement une représentation intermédiaire du code source
sous forme d’un code intermédiaire qui n’est pas directement exécutable par une machine
spécifique. C’est plutôt un code généré pour une machine abstraite (virtuelle), qui a la double caractéristique
d’être, à la fois, facile à produire, à partir de l’arbre syntaxique, et facile à convertir pour une machine réelle
donnée.
Exemple : le code intermédiaire de l’expression « a := b + 2 * c ; », peut être comme
suit :
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
16
1.2 Structure générale d’un compilateur
1.2.5 Optimiseur du code intermédiaire
Lors de la phase d’optimisation, le code intermédiaire est changé pour améliorer les performances
du code cible qui en sera généré.
Objectifs :
1. Réduire le temps d’exécution et l’espace mémoire qui sera occupé par le code cible.
2. Supprimer, par exemple, les identificateurs non utilisés
3. Éliminer les instructions inaccessibles, les instructions non nécessaires et faire
ressortir hors des boucles, les instructions qui ne dépendent pas de l’indice de
parcours des boucles, etc.
Exemple : Le nouveau code intermédiaire de « a := b + 2 * c ; », est le suivant :
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
17
1.2 Structure générale d’un compilateur
1.2.6 Générateur du code cible
C’est la phase finale d’un compilateur qui consiste à produire du code cible dans un langage
d’assemblage ou un langage machine donné. Le code généré est directement exécuté par la machine
en question ou alors il l’est après une phase d’assemblage.
Exemple : Considérons une machine à deux adresses qui dispose de deux registres de calcul
R1 et R2. Nous supposons que les variables a, b et c de la table des symboles ont comme
adresses de cellules mémoires correspondantes ad1, ad2 et ad3. Le code cible qui sera généré
pour cette machine est donné dans le tableau suivant :
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
18
1.2 Structure générale d’un compilateur
1.2.6 Générateur du code cible
C’est la phase finale d’un compilateur qui consiste à produire du code cible dans un langage
d’assemblage ou un langage machine donné. Le code généré est directement exécuté par la machine
en question ou alors il l’est après une phase d’assemblage.
Exemple : Considérons une machine à deux adresses qui dispose de deux registres de calcul
R1 et R2. Nous supposons que les variables a, b et c de la table des symboles ont comme
adresses de cellules mémoires correspondantes ad1, ad2 et ad3. Le code cible qui sera généré
pour cette machine est donné dans le tableau suivant :
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
19
1.2 Structure générale d’un compilateur
1.2. 7 Gestionnaire de la table de symbole
Les phases logiques de compilation échangent des informations par l’intermédiaire de la table des
symboles : c’est une structure de données (généralement une table) contenant un enregistrement
pour chaque identificateur utilisé dans le code source en cours d’analyse.
▪ A chaque fois que l’analyseur lexical rencontre un identificateur pour la première fois, le
gestionnaire de la table des symboles insère un enregistrement dans la table et l’initialise avec
les informations actuellement disponibles (le nom).
▪ Lors de l’analyse syntaxique, le gestionnaire associera le type à l’identificateur, alors que, lors
de l’analyse sémantique, une vérification de types est opérée grâce à cet enregistrement.
1.2. 8 Gestionnaire des erreurs
Son rôle est de signaler les erreurs qui peuvent exister dans le code source et qui sont détectées
lors des différentes phases logiques de la compilation. Il doit produire, pour chaque erreur, un
diagnostic clair et sans ambiguïté qui permettra la localisation et la correction de l’erreur par
l’auteur du code source.
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
20
1.3 Outils de construction des compilateurs
▪ Suite au développement des premiers compilateurs, on s’est très vite rendu compte que
certaines tâches liées au processus de compilation peuvent être automatisées, ce qui facilite
grandement la construction des compilateurs. La notion d’outils de construction de
compilateurs est alors apparue.
▪ La première catégorie est représentée par des outils généraux appelés Compilateurs de
Compilateurs, Générateurs de Compilateurs ou Systèmes d’écriture de traducteurs. Les outils
de cette catégorie se sont souvent orientés vers un modèle particulier de langages et ne sont
adaptés qu’à la construction de compilateurs pour des langages correspondant à ce modèle.
▪ La deuxième catégorie correspond à des outils spécialisés dans la construction automatique
de certaines phases d’un compilateur, tels que :
• Les constructeurs ou générateurs automatiques d’analyseurs lexicaux à partir d’une
spécification contenant des expressions régulières
• Constructeurs ou générateurs automatiques d’analyseurs syntaxiques à partir d’une
spécification basée sur une grammaire non contextuelle et en utilisant des algorithmes
d’analyse puissants mais difficile à mettre en œuvre manuellement.
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
21
1.4 Outils de construction des compilateurs
▪ Suite au développement des premiers compilateurs, on s’est très vite rendu compte que
certaines tâches liées au processus de compilation peuvent être automatisées, ce qui facilite
grandement la construction des compilateurs. La notion d’outils de construction de
compilateurs est alors apparue.
▪ La première catégorie est représentée par des outils généraux appelés Compilateurs de
Compilateurs, Générateurs de Compilateurs ou Systèmes d’écriture de traducteurs. Les outils
de cette catégorie se sont souvent orientés vers un modèle particulier de langages et ne sont
adaptés qu’à la construction de compilateurs pour des langages correspondant à ce modèle.
▪ La deuxième catégorie correspond à des outils spécialisés dans la construction automatique
de certaines phases d’un compilateur, tels que :
• Les constructeurs ou générateurs automatiques d’analyseurs lexicaux à partir d’une
spécification contenant des expressions régulières
• Constructeurs ou générateurs automatiques d’analyseurs syntaxiques à partir d’une
spécification basée sur une grammaire non contextuelle et en utilisant des algorithmes
d’analyse puissants mais difficile à mettre en œuvre manuellement.
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA
22
Chapitre 2
Analyse lexicale
Mr. Jean Marius
IBARA KIEBE KANIMBOET
Doctorant PhD en IA