Programme GIT
ENI-ABT BAMAKO 2020
SPECIFICATION ET TRADUCTION DES
LANGAGES
COMPILATION
Module1a
Chargé de cours:
Dr Yacouba GOÏTA
Tél : [Link]
Email : goita_yacouba@[Link]
WEBOGRAPHIE
❖ Algorithmique et bases de la programmation : Introduction à la
Compilation - Nicolas Delestre - INSA ROUEN
[Link]
❖ Introduction à la compilation: Cours 1 – Yann Régis-Gianas PPS –
Université Denis Diderot – Paris 7 (2010)
[Link]
❖ Introduction à la compilation Christine Paulin-Mohring – Université Paris
Sud – Master Informatique 2009-2010
[Link]
❖ Compilation – Alexis Nasr – [Link]
[Link]/~[Link]/Ens/Compilation/intro_compil.pdf
❖ Cours M Hammemi Moez - ISG de Tunis (2007)
❖ Cours Mme El Abed Lamia - ISG de Tunis (2007)
❖ Cours – Annie Corbel 1999
[Link]
2 Cours Compilation
PREREQUIS
❖Théorie des langages formels: expressions
régulières, automates, grammaires, ambiguïté
❖Langages de programmation
❖Algorithmique
3 Cours Compilation
Objectif
POURQUOI?
QUOI?
COMMENT?
4 Cours Compilation
plan
❖Définition: compilateur
❖Analyse lexicale (linéaire)
❖Analyse syntaxique (hiérarchique)
❖Analyse sémantique
❖Génération du code intermédiaire
❖Optimisation du code
❖Génération du code objet
5 Cours Compilation
POURQUOI? (1)
❖Si vous deviez écrire un programme capable
d‘évaluer (au sens de calculer) des expressions
arithmétiques qu'un utilisateur aurait saisies au
clavier
❖Par exemple : ≪ (24+45.5)/87*1.2E3 ≫
❖Comment procéder ?
6 Cours Compilation
POURQUOI? (2)
❖Ecrire des procédures et des fonctions permettant
❑De reconnaitre un entier
❑De reconnaitre un réel
❑De reconnaitre une addition
❑...
➔ C'est compliqué pour quelque chose de simple
➔ A la moindre modification tout est à
reprogrammer
7 Cours Compilation
POURQUOI? (3)
❖Il faut suivre des méthodes et des
techniques afin de résoudre ce type de
problème :
➔C'est le rôle de la COMPILATION
8 Cours Compilation
QUOI? (1)
❖C'est un programme qui traduit un
programme écrit dans un langage source
vers un langage cible en indiquant les
erreurs éventuelles que pourrait contenir le
programme source
programme programme
compilateur
source cible
messages
d'erreur
9 Cours Compilation
QUOI? (2)
❖Premier compilateur : compilateur Fortran de
J. Backus (1957)
❖Langage source : langage de haut niveau (C,
C++, Java, Pascal, Fortran...)
❖Langage cible : langage de bas niveau
(assembleur, langage machine)
10 Cours Compilation
COMMENT? (1)
Et comment ça marche ?
Comme un enfant qui apprend à lire...
❖On reconnait d'abord les mots
➔Analyse Lexicale
❖Puis, on vérifie que tous les mots sont dans le bon
ordre
➔Analyse Syntaxique
❖Enfin, on vérifie que tout ceci a un sens
➔Analyse Sémantique
11 Cours Compilation
Structure Globale
En deux parties :
❖analyse/reconnaissance
❖synthèse/transformation
Partie Partie
Texte Rep Texte
Avant Arrière
source sémantique cible
(analyse) (synthèse)
12 Cours Compilation
Les phases de la compilation
programme source
analyseur lexical
analyseur syntaxique
analyseur sémantique
gestion de la
table des symboles générateur de code intermédiaire gestion des erreurs
"optimiseur" de code
générateur de code cible
programme cible
13 Cours Compilation
Analyse lexicale (1)
❖Lit le programme source
❖Reconnaît les séquences de caractères
significatives appelées lexèmes
❖Pour chaque lexème, l’analyseur lexical émet
un couple
(type du lexème, valeur du lexème | @ dans la table de symboles)
❖Exemple : (NOMBRE, 123)
14 Cours Compilation
Analyse lexicale (2)
❖Les types de lexèmes sont des symboles, ils
constituent les symboles terminaux de la
grammaire du langage
❖ Les symboles terminaux de la grammaire (ou
types de lexèmes) constituent l’interface entre
l’analyseur lexical et l’analyseur syntaxique
Les types de lexèmes doivent être connus des
deux
15 Cours Compilation
Analyse lexicale (3)
Table de
symboles
16 Cours Compilation
Analyse lexicale (4)
❖Exemple:
position := initiale + vitesse*60
<id1,1> <aff,:=> <id2,2> <op,+> <id3,3> <op,*>
<nb,60>
Table de symboles
1 position …
2 initial …
3 rate …
17 Cours Compilation
Analyse lexicale(5)
❖Comment reconnaitre les mots?
❖Les lister : avoir un dictionnaire de mots clefs
❖Mais certains mots sont génériques :
✓ Les nombres
✓ Les identifiants des programmes (variable,
fonction/procédure, etc.)
❖Il faut avoir un outil permettant de les caractériser
expressions régulières
18 Cours Compilation
Analyse lexicale(6)
Comment on implante tout ça ?
❖La théorie montre que toute expression régulière peut
être représentée à l'aide d'un automate (et inversement)
❖Problème de différenciation entre identificateurs et
mots clés
19 Cours Compilation
Analyse syntaxique(1)
❖Vérifie que la suite des unités lexicales (lexèmes)
fournie par l’analyseur lexical est compatible avec
une grammaire et produit en sortie un arbre d'analyse
(arbre syntaxique)
❖grammaire hors contexte (ou notation BNF) qui sert à
décrire la syntaxe du langage
❖Deux types d'analyse : Ascendante ou Descendante
20 Cours Compilation
Analyse syntaxique(2)
❖ Exemple: (Arbre d’Analyse Descendante )
<id1,1> <aff,:=> <id2,2> <op,+> <id3,3> <op,*> <nb,60>
Affectation
id := expr
position expr + expr
id expr * expr
initiale id nombre
vitesse 60
21 Cours Compilation
Analyse sémantique(1)
❖Vérifie la cohérence de l'arbre d'analyse
❖Collecte d'informations destinées à la production de
code
❖L’analyse sémantique utilise l’arbre abstrait, ainsi que
la table de symboles afin d’effectuer un certain
nombre de contrôles sémantiques
l’arbre abstrait
Analyse contrôles
la table de symboles Sémantique sémantiques
22 Cours Compilation
Analyse sémantique(2)
parmi lesquels :
❖Vérifier que les variables utilisées ont bien été
déclarées
❖Au contrôle de type : le compilateur vérifie que les
opérandes d’un opérateur possèdent bien le bon type
❖conversions automatiques de types
23 Cours Compilation
Analyse sémantique(2)
❖Exemple:
:= :=
id1 + id1 +
id2 * id2 *
id3 60 id3 EntierVersReel
60
24 Cours Compilation
Génération du code intermédiaire
❖Programme pour une machine abstraite
✓Code facile à produire, à traduire en langage
cible
❖Exemple: code à 3 adresses
:=
temp1:=EntierVersReel(60)
id1 +
temp2:=id3*temp1
id2 *
temp3:=id2+temp2
id3 EntierVersReel id1:=temp3
60
25 Cours Compilation
Optimisation du code
❖Optimiser le code intermédiaire en éliminant
les opérations inutiles pour produire du code
plus efficace et pour une exécution machine
plus rapide
❖Exemple:
temp1:=EntierVersReel(60)
temp2:=id3*temp1 temp1:= id3 * 60.0
temp3:=id2+temp2 id1:= id2 + temp1
id1:=temp3
26 Cours Compilation
Génération du code machine
❖Obtention du code machine
MOVF id3, R2
MULF #60.0, R2
temp1:= id3 * 60.0 MOVF id2, R1
id1:= id2 + temp1 ADDF R2, R1
MOVF R1, id1
27 Cours Compilation
Récapitulatif...
temp1:=EntierVersReel(60)
temp2:=id3*temp1
position := initiale + vitesse * 60 Analyseur
temp3:=id2+temp2
sémantique
id1:=temp3
Analyseur lexical :=
id1 + Optimiseur de
id1 := id2 + id3 * 60 code
id2 *
Analyseur temp1:= id3 * 60.0
syntaxique id3 EntToReel id1:= id2 + temp1
60
Générateur de
:= code
Générateur code
id1 + intermédiaire MOVF id3, R2
MULF #60.0, R2
id2 * MOVF id2, R1
ADDF R2, R1
id3 60 MOVF R1, id1
28 Cours Compilation
TAF
RECHERCHE
LEX/YACC
ANTLR
29 Cours Compilation
