Université Moulay Ismail de Meknès

Faculté des Sciences

Département d’Informatique
SMI / S5

Module : Compilation
Prof: Abdelaaziz Hessane

Année Universitaire: 2024/2025

Plan du cours
• Chapitre 1: Généralités sur la compilation
• Chapitre 2: Analyse lexicale
• Chapitre 3: Analyse Syntaxique
• Chapitre 4: Code intermédiaire, optimisation et génération du
code cible

2
Chapitre 1 : Généralités sur la compilation
1.1 Introduction
1.2 Définitions
1.3 Phases de la compilation
1.4 Types de compilateurs
1.5 Compilation vs Interprétation
1.6 Exemple
1.7 Outils théoriques et pratiques

3
 Chapitre 1: Généralités sur les compilateurs

1.1 Introduction

Quel est le rôle d’un programmeur?

Spécifier les étapes à suivre par l’ordinateur pour
effectuer des tâches

Comment résoudre le problème de ne pas avoir

Français, Anglais…
deux entités qui ne parlent pas une langue
commune ?
On a besoin d’un Traducteur

Binaire {0,1}

4
 Chapitre 1: Généralités sur les compilateurs

1.2 Définitions
La compilation est le processus de traduction du code du programmeur (langage haut
niveau : C++, C#, etc) vers un langage compréhensible par la machine (langage bas niveau
: Assembleur, machine)

Un compilateur : Un programme qui lit un programme écrit dans un premier langage (le
langage source) et le traduit en un programme équivalent dans un autre langage (le langage
cible).
Le compilateur doit aussi vérifier que le programme a un certain sens et signaler les erreurs
qu'il détecte.

5
 Chapitre 1: Généralités sur les compilateurs

1.3 Phases de compilation: Une vue d’ensemble

Programme écrit en
langage A (code source)

Phases d'analyse
Analyse lexicale
Analyse syntaxique

Table des Analyse sémantique Gestion

symboles Génération du code Des
intermédiaire erreurs
Optimisation du code
Phases de synthèse
Génération du code objet
(Production)
Programme cible

6
 Chapitre 1: Généralités sur les compilateurs

1.3 Phases de compilation

Programme écrit en
langage A (code source)

Pour s’assurer que tous les

Former les mots du langage : mots du code source
Analyse lexicale (lexèmes) appartiennent au vocabulaire
du langage haut niveau.

Phase d’analyse Retrouver les relations entre Pour s’assurer que tous les
les lexèmes (construire
Le compilateur s’assure que Analyse Syntaxique l’arbre syntaxique)
mots construisent des
phrases correctes
le code source respecte la
syntaxiquement et respectent
syntaxe et la grammaire du Donner une signification à la grammaire du langage haut
langage haut niveau.
Analyse sémantique l’arbre syntaxique niveau.

Tenir compte des Pour s’assurer que chaque

caractéristiques/contraintes phrase a du sens.
matérielles pour générer un
code optimisé au matériel
Génération du code
ciblé (processus physique ou intermédiaire Compilateur à une passe
virtuel)…registres, piles, etc

Générer un code interne au

Phase de production Optimisation
compilateur (sans tenir en Programme cible écrit en
Selon le type de compilateur :
compte entre autres des Une ou multi passes langage B (code machine)
contraintes matérielles)..
Phase optionnelle Génération du code final
7
 Chapitre 1: Généralités sur les compilateurs

1.4 Types de Compilateurs

Compilateur à une Compilateur à

passe plusieurs passes

Compilateurs à
deux passes

8
 Chapitre 1: Généralités sur les compilateurs

1.4 Types de Compilateurs

Compilateur à une passe → Fonctionnement simultané des phases

Toutes les étapes de la

compilation sont appliquées sur
chaque unité de programme Scanne une unité
une après l’autre
Analyse une unité
Unité du programme
Vérifier une unité

Génère le code pour une unité

Une instruction Un bloc Non
d’instructions: Fin de fichier ?
• Procédure Oui
• Module
• Etc 9
 Chapitre 1: Généralités sur les compilateurs

1.4 Types de Compilateurs

Compilateur à une passe

Avantages :
• Rapides (Ne prennent pas beaucoup de mémoire) Java PC
Inconvénients:
• Optimisation du code est limité C Macintosh
• Pas de portabilité : le code généré ne fonctionne que
pour le même matériel Pascal Station SUN.
• Nombre très élevé des traductions à créer

source Code final

10
 Chapitre 1: Généralités sur les compilateurs

1.4 Types de Compilateurs

Compilateur à plusieurs passes → les étapes sont des programmes séparés qui s’exécutent
séquentiellement
→ Chaque étape est un programme qui lit à partir d’un
fichier et produit un nouveau fichier qui sera lu par le
prochain programme jusqu’à la création du code final.

Lexique Syntaxe Sémantique …

source Unités Arbre Code final

lexicales Syntaxique

11
 Chapitre 1: Généralités sur les compilateurs

1.4 Types de Compilateurs

Compilateur à deux passes

Inconvénient majeur des compilateurs à plusieurs passes :

• Longs (Occupent beaucoup de mémoire)
Solution : Compilateur à deux passes

Passe 1 Passe 2
Lexique Génération
source Syntaxique de code Code final
Sémantique Représentation
intermédiaire
Dépendant du langage Dépendant du matériel
12
 Chapitre 1: Généralités sur les compilateurs

1.4 Types de Compilateurs

Avantages :
Compilateur à deux passes • Une meilleure portabilité
• Optimisation plus simple : La représentation est faite
sur le code intermédiaire plutôt que sur le code
source
Java PC

C Macintosh

Pascal Code Station SUN.

intermédiaire

Une combinaison par langage Une combinaison par matériel

13
 Chapitre 1: Généralités sur les compilateurs

1.5 Compilation vs Interprétation

Compilation Interprétation
• Programme d’un langage A est • Une instruction du programme A est
entièrement transformé en un transformée en une instruction en langage
programme en langage B B et puis exécutée
• Compilation doit être achevée avant • Une instruction (bloc d’instruction) à la fois
l’exécution du programme • Seulement le programme en langage A
• Un code en langage B est généré existe (pas de génération d’un programme
• Ex. C, C++, etc. en langage B)
• Ex. Ruby, Perl, PHP, Python, Javascript, etc.

14
 Chapitre 1: Généralités sur les compilateurs

1.5 Compilation vs Interprétation

Avantages

Compilation Interprétation
• Détection facile et précoce des erreurs • Faciliter la programmation: résultats
syntaxiques avant l’exécution des changements dans le programme
• Exécution rapide sont immédiats
• Protection du code source (quoique la • Offrir plus de flexibilité et de
décompilation réduit cet avantage) dynamisme: l’unité atomique est une
instruction du langage
• Faciliter l’implémentation de
fonctionnalités réservées à la méta
programmation

15
 Chapitre 1: Généralités sur les compilateurs

1.5 Compilation vs Interprétation

Inconvénients

Compilation Interprétation
• Moins de flexibilité : l’unité atomique • Lenteur à l’exécution
est un programme entier • C’est le code source qui est distribué
• Méta programmation difficile (problème de protection du code)
• À chaque modification du programme,
une recompilation est nécessaire

16
 Chapitre 1: Généralités sur les compilateurs

1.5 Compilation vs Interprétation

Compilation Interprétation

17
 Chapitre 1: Généralités sur les compilateurs

1.5 Compilation vs Interprétation

Langages hybrides
=
Compilation + interprétation

Compilation Interprétation
Code source Code intermédiaire Code Machine
(Langage X) (Langage Y) (Langage Z)

18
 Chapitre 1: Généralités sur les compilateurs

Pour résumer…

19
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple
Etape 1 : L’analyseur lexical Unité lexicale Sa nature
Connu aussi sous l’appellation Scanner, l’analyseur a Identificateur de
variable
lexical a pour rôle principal la lecture du texte du code
:= Symbole
source (suite de caractères) puis la formation des unités d’affectation
lexicales (appelées aussi entités lexicales, lexèmes, b Identificateur de
variable
jetons, tokens ou encore atomes lexicaux). + Opérateur d’addition
Exemple 2 Valeur entière
Considérons l’expression d’affectation a := b + 2 * c ; * Opérateur de
multiplication
Les unités lexicales qui apparaissent dans cette c Identificateur de
expression sont : variable
; Séparateur
20
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple
Etape 2: L’analyseur syntaxique
L’analyseur syntaxique (appelé Parser en anglais) 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 (généralement exprimées par des règles récursives). Notons
que durant cette phase, des informations, telles que le type des identificateurs, sont
enregistrées dans la table des symbols

21
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Etape 2 : L’analyseur syntaxique

La représentation sous forme d’arbre syntaxique de
l’expression « a := b + 2 * c ; » est comme suit :

Dans cette structure d’arbre, les nœuds représentent

des opérateurs et les feuilles de l’arbre représentent
les valeurs et les variables sur lesquelles s’effectuent
les opérations.
Arbre abstrait de l’expression a:=b+2*c;

22
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Etape 2 : L’analyseur syntaxique

Exemple :
L'arbre syntaxique correspondant : A = B1 + B2 * 60 Remarque : L'arbre abstrait est une
forme compacte de l'arbre syntaxique.

23
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Etape 3 : L’analyseur sémantique

Il comme rôle principal le contrôle du code source, pour détecter éventuellement l’existence
d’erreurs sémantiques, et la collecte des informations destinées à la production du code
intermédiaire. Un des constituants importants de la phase d’analyse sémantique est le
contrôle du type qui consiste à vérifier si les opérandes de chaque opérateur sont conformes
aux spécifications du langage utilisé pour le code source.

24
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Etape 3 : L’analyseur sémantique

Cas Arianne 5 (1996)

• Un bug* de conversion de type a causé
l'échec du vol Arianne 5
• La fusée a explosé après 40 secondes de
vol
• Coût : environ 370 millions de dollars

[Link]
* Ce n'est pas un bug de compilation, mais un bug de conception
logicielle lié à la gestion des types et des conversions.
25
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Etape 3 : L’analyseur sémantique

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

26
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Etape 3 : L’analyseur sémantique

Exemple 2 : Si on suppose que a, b et c sont de type réel,
alors pendant l’évaluation de l’expression, l’analyse
sémantique aura comme tâche d’insérer une opération de
conversion de type pour transformer la valeur entière 2 en
valeur réelle 2.0. Cela peut être effectué sur l’arbre
syntaxique comme le montre la figure suivante. L’arbre
résultant est appelé : arbre syntaxique décoré.
Enrichissement de l’arbre syntaxique lors
de la phase d’analyse sémantique

27
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Etape 4 : Le 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.

28
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Etape 4 : Le générateur de code intermédiaire

Supposons que la machine abstraite est une machine à une adresse qui dispose d’un seul
accumulateur et dont le jeu d’instruction contient les instructions LoadValue, ConvReal, Mul,
Add et Store. Elles permettent de réaliser les opérations données dans la deuxième colonne.
Nous avons supposé aussi que a occupe la première entrée dans la table des symboles, b
occupe la deuxième et c la troisième. Ainsi, le code intermédiaire de l’expression « a := b + 2 * c
; », peut être comme suit :

29
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Etape 4 : Le générateur de code intermédiaire

30
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Etape 5 : L’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é. Il s’agit principalement de :
• Réduire le temps d’exécution et l’espace mémoire qui sera occupé par le code cible.
• Supprime, par exemple, les identificateurs non utilisés, élimine les instructions
inaccessibles, élimine les instructions non nécessaires
• Fait ressortir hors des boucles les instructions qui ne dépendent pas de l’indice de
parcours des boucles,
• etc.

31
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Etape 5 : L’optimiseur du code intermédiaire

N.B : L’optimisation risque de ralentir le processus de compilation dans son ensemble mais
elle peut avoir un effet positif considérable sur le code cible qui sera généré ultérieurement.

32
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple
Etape 5 : L’optimiseur du code
intermédiaire

On constate dans l’exemple précédent que la

valeur convertie 2.0 est stockée dans temp1 puis
récupérée et chargée dans l’accumulateur. Puisque
aucun usage n’est fait de temp1 dans le reste du
code, il est possible d’éliminer les deux instructions
en question. Le nouveau code intermédiaire est le
suivant :

33
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Etape 6 : Le 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.
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 :

34
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Etape 6 : Le générateur du code cible

35
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Le gestionnaire de 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.
L’enregistrement contient, parmi d’autres informations, le nom de l’identificateur, son type, et
l’emplacement mémoire qui lui correspondra lors de l’exécution.

36
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

Le gestionnaire de table de symbole

▪ 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
▪ lors de l’analyse sémantique, une vérification de types est opérée grâce à cet
enregistrement.

37
 Chapitre 1: Généralités sur les compilateurs

1.6 Exemple

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

38
 Chapitre 1: Généralités sur les compilateurs

Pour résumer …  Langage de haut niveau

 Langage de bas niveau

39
 Chapitre 1: Généralités sur les compilateurs

1.7 Outils théoriques et pratiques

Phase de la compilation Outils théoriques Outils pratiques

Analyse lexicale Expressions régulières Java, Rubby, C, (F)Lex,
(scanning) Automates à états finis JavaCC, SableCC
Analyse syntaxique
Phases d’analyse Grammaires
(parsing) Yacc, Bison, JavaCC,
Traduction dirigée par la SableCC
Analyse sémantique
syntaxe
Traduction dirigée par la
Phase de production Génération de code Bison, JavaCC, SableCC
syntaxe

40
 Chapitre 1: Généralités sur les compilateurs

Références

1. Compilers: Principles, Techniques, and Tools (2nd Edition), Alfred V. Aho, Monica S. Lam, Ravi Sethi,
Jeffrey D. Ullman, Addison Wesley ; 2nd edition (2007)

2. Modern Compiler Implementation in Java, 2nd ed. Andrew Appel, Cambrdige University Press
(2004).

3. Lex & yacc (2nd Edition 1992), John R. Levine, Tony Mason and Doug Brown, O'Reilly & Associates,

Inc.

4. Engineering a Compiler Second Edition, Keith D. Cooper Linda Torczon, Morgan Kaufmann, Elsevier,
Inc. (2012).

5. Programming Language, Third edition, Michael L. Scott, 2009 by Elsevier Inc.

41