Compilation

Adil KENZI

1
Lectures recommandées - livres
1. « Engineering a Compiler » ©, K. D. Cooper & L.
Torczon, Morgan Kaufmann 2004
2. « Introduction to Automata Theory Languages
and Computation » ©, J. E. Hopcroft, R.
Motwani, J. [Link], 2001, Addison Wesley
3. « Compilers and Compiler Generators » ©, P.D.
Terry, 2000
4. Cours, Compilation, Karim BAINA, ENSIAS,
Rabat

2
 Plan du cours
1. Introduction
2. Définitions
3. Analyseur lexical
4. Analyseur syntaxique
5. Générateurs d’analyseurs lexicaux et syntaxiques
1. Flex
2. Bison
6. Analyseur sémantique
7. Conclusion et perspectives
3
1. Introduction

4
Introduction
Les micro-processeurs sont partout
Jeux vidéo,
Ordinateurs personnels,
Téléphones portables,
Machine à laver,
Voitures,
Micro-ondes,
Lave vaisselles,
Systèmes de navigation par satellites (GPS), etc.
Pour fonctionner, tous ces micro-processeurs
nécessitent des programmes spécifiques à leur
architecture
5
Compilateur : Pourquoi ?
Programmation en langages de bas niveau (proches de la
machine)
 très difficile (complexité)
 Apprentissage lent et difficile
 Débuggage fastidieux
 très coûteuse en temps (perte de temps)
 très coûteuse en ressource humaine (budget énorme)
 Tâches manuelles
 Maintenance
 très ingrate (artisanat)
 Centrée sur les détails techniques et non sur les modèles conceptuels

6
Compilateur : Pourquoi ?
Besoin de
 Langages de haut niveau
 avec des structures et des modèles conceptuels proches de l’humain

 Programmes de génération des langages bas niveau à partir de

langages haut niveau
 Compilateurs
 Interpréteurs
 Etc.

7
2. Définitions

8
Positionnement des compilateurs
 Un compilateur est un
programme Utilitaires, BDD,
Programmes Compilateurs, etc.

Système
d’exploitation

Matériel

9
Compilateur - définition
Un compilateur est un programme (une fonction)
qui prend en entrée un programme dans un
langage source L1 et produit en sortie programme
équivalent dans un langage L2

Programme P1 Programme P2
Compilateur
en langage source L1 en langage cible L2

Messages d’erreurs
Exemple de langages compilés :
C , Ada , C++ pour Sun, Pascal,

10
Interpréteur - définition
Un interpréteur est programme qui prend en entrée
un programme dans un langage source L1 et produit
en sortie les résultats de l’exécution de ce
programme
Programme en
Interpréteur Résultats
langage source L1

Messages d’erreurs
Exemples d’interpréteurs :
Javascript, PHP, Prolog, PL/SQL, Lisp/Scheme, Basic,
Python, etc.
11
Architecture d’un compilateur(1/2)
 Un compilateur se compose principalement des briques
logicielles suivantes
 Un analyseur lexical : lit le flot de caractères qui constituent le
programme source et les regroupe en séquence de caractères
significatives
 Un analyseur syntaxique : se sert des séquences de caractères
significatives (unités lexicales) produites par l’analyseur lexical
pour créer une représentation intermédiaire arborescente qui
dépeint la structure grammaticale du flots d’unités
 Un analyseur sémantique : il vérifie que le programme est
sémantiquement correcte vis-à-vis de la définition du langage
1. Contrôle de type
2. Contrôle d’unicité
12
Architecture d’un compilateur(2/2)
 Un générateur de pseudo-code : construction des
représentations intermédiaires :
 arbres abstraits
 code à trois adresses
 Un optimisateur de code : améliorer le code
intermédiaire afin qu’il en résulte un meilleur code cible

 Un générateur de code : il prend en entrée une

représentation intermédiaire du programme source et la
réécrit dans le langage cible

13
Exemple simple de compilation

14
Alphabet
On appelle alphabet  un ensemble fini non vide.
Les éléments d’un alphabet sont appelés lettres

Exemple d’alphabets
 = {a, b,.., z}
 = {, , , .., , +, *, /, =}
 = {if, then, else, while, begin, end}

15
Langage
Soit n un entier naturel, on appelle mot de
longueur n sur l’alphabet  toute application de
{1, 2,…n} dans .
Alphabet  Mots de *
Le mot vide est noté
 = {a, b,.., z} « abab », « surf
 », « cascade »,
…
l’ensemble de tous  = {, , , .., , «  = *2+ »,
les mots sur un +, *, /, =} « + =* », …
alphabet  est noté *
 = {if, then, else, (if,then,else),
while, begin, end} (begin,begin,end)
Langage
Un langage sur , noté L() est une partie de * : L()
 *

Exemple de langages sur  = {a, b,.., z}

L0 = , L1 = {}, L2 = {awa | w  *},
L3 = {waw | w  *},
L4 = {w  * | |w|  10 }
a

La fonction |.|

x : *  IN
 calcule le nombre d’occurrence de la lettre x de  dans un mot
de *

17
Lexique et expressions régulières
Les meilleurs modèles définissant les unités
lexicales (types tokens) auxquelles appartiennent
les lexèmes (tokens) sont des langages particuliers
(langages réguliers)

Il existe plusieurs manières de décrire les langages

réguliers
les expressions régulières
Les automates d’états finis
Les grammaires linéaires

18
Expressions régulières (ER)
Soit  un alphabet, une expression régulière est
définie comme suit :
 (1) les éléments de , (2)  (mot vide) et (3) 
(ensemble vide) sont des expressions régulières.
 Si  et  sont des expressions régulières, alors
 (4) ( | ) représentant l’union de  et ,
 (5) ( ) représentant la concaténation de  et 
 (6)  * représentant la fermeture de Kleene (répétition un
nombre de fois éventuellement égal à 0)
 Sont des expressions régulières
 Nulle autre expression n’est une expression régulière

19
Expressions régulières (ER)
 est l’élément neutre par rapport à la concaténation ( )
= ( ) = 

 est l’ensemble vide de caractères, neutre par rapport à

l’union ( | ) = 

Fermeture positive : l’écriture + =  * (répétition un

nombre de fois au moins égal à 1)

20
Expressions

régulières (ER)
Exemples d’ER :
 Alphabétique = (‘a’ | ‘b’ | … | ‘z’ | ‘A’ | ‘B’ | … | ‘Z’)
 Numérique = (0 | …| 9)
 Opérateurs = (+ | - | / | * | = | <= | >= | < | >)
 Naturel = Numérique+
 Entier = (+ | - | ) Naturel
 Identificateur = (Alphabétique(Alphabétique|
Numérique)*)

21
Prouver qu’un Langage est irrégulier
 Lemme de l’étoile (pumping lemma):
 Si un langage L sur un alphabet  (L   *) est régulier,
alors  n  IN* (qui dépend de L) tel  u  L avec |u| 
n, et il existe une décomposition de u en trois parties u =
fgh telle que :
1. g
2. |fg|  n
3.  k  0, fgkh  L

22
Prouver qu’un Langage est irrégulier
 Soit l’alphabet  = {a, b}

 Le langage L = a+ est régulier (par construction) alors

  u  L, |u|  1 
 u = fgh, f=a*, g=a, h=a*, g     k  0, fgkh = a*(a)ka*  L

 Le langage L = a*b* est régulier (par construction) alors

  u  L, |u|  1 
 u = fgh, f=a*, g=ai, h=a*b*, g     k  0, fgkh = a*(ai)ka*b*  L

 Le langage L = ambm, m  IN n’est pas régulier, car

  u  L, |u| 2 
 u = fgh, f=am-i, g=ai, h=bm, g     k  0, fgkh = am-i(ai)kbm  L
 u = fgh, f=am-i, g=aibi, h=bm-j, g     k  0, fgkh = am-i(aibj)kbm-j  L
 u = fgh, f=am, g=bj, h=bm-j, g     k  0, fgkh = am(bj)kbm-j  L

23
Expressions régulières (ER)
Les expressions régulières sont beaucoup plus
puissantes que ce dont on a besoin lorsqu’on fait de
l’analyse lexicale

Chaque expression régulière R correspond à une

machine abstraite qui reconnaît L(R) le langage
définit par R

On appelle ces machines automates d’états finis

24
Automates et ER
Alphabétique =(‘a’ | … | ‘z’ | ‘A’ | … | ‘Z’)
Numérique =(0 | …| 9)
Identificateur = (Alphabétique(Alphabétique|
Numérique)*)
‘a’ .. ‘Z’ 0 .. 9

‘a’ .. ‘Z’
s0 s1
0..9
s2 s2 : état poubelle (ou trash)
de gestion d’erreur
‘a’ .. ‘Z’ 0 .. 9
Automate correspondant aux identificateurs 25
Automates d’états finis DFA -
Deterministic Finite Automata
Un automate d’états finis A est défini comme un 5-uplet
A = <S, , , s0, F > où :
 S est un ensemble d'états,
  est un alphabet (un ensemble de caractères),
  : S    S est la fonction de transition de l'automate,
 s est l'état initial de l'automate,
0
 F  S est l'ensemble des états finaux de l'automate et

Les automates sont des graphes où les états sont les noeuds du
graphe et les arcs représentent la fonction de transition.

L’ensemble des mots pouvant être acceptés par un automate A

est appelé le langage reconnu par A, noté L(A).
26
Automates d’états finis DFA - Deterministic
Finite Automata
On dit qu’un automate d’états finis A = <S, , , s ,
0
F > accepte le mot x, composé des caractères
x1x2x3 . . .xn ssi ((…
((s0, x1 ), x2 ), x3 ),…), xn-1), xn)  F

Intuitivement x x x . . .x correspond aux

1 2 3 n
étiquettes des arcs formant un chemin à travers les
transitions de l’automate, commençant par s0 et se
terminant par sk  F.
A chaque étape, x correspond à l’étiquette du ième
i
arc du chemin.
27
Analyseur lexical

28
Analyseur lexical - Plan
Introduction
Concepts
Lexème
Unité lexicale
Motif
Fonctionnement d’un analyseur lexical

29
 Analyseur lexical
 L’analyseur lexical constitue la première étape dans le
processus de compilation.
 Sa principale tâche est de lire les caractères du fichier source
et de produire la suite d’unités lexicales que le module
d’analyse syntaxique va utiliser.
 Le plus souvent l’analyseur lexical est implanté comme un
sous-programme de l’analyseur syntaxique
 il se contente de lire les caractères d’entrée jusqu’à ce qu’il
puisse identifier la prochaine unité lexicale.

30
 Analyseur lexical-Concepts
 Des notions liées à l’analyseur lexical :
Lexème (token ou jeton) : une chaîne de caractères ayant une
signification pour le langage source.
 Exemples : main, if, -125, >, a, x2 et "bonjour" sont des lexèmes.
Unité lexicale : un nom qui désigne la catégorie d’un lexème.
 Exemples : « mot clé », « opérateur », « nombre », « commentaire »,

…etc.
Modèle (règle ou motif) : définition d’une unité lexicale.

31
 Fonctionnement de l’analyseur lexical
 Interaction entre un analyseur lexical et un analyseur
syntaxique :

Unité lexicale
Caractère Analyseur Analyseur
lexical syntaxique
Get next token

Programme
source
Table des
symboles

32
Fonctionnement de l’analyseur lexical
Modèles Unité lexicale

M1 identificateur

M2 opérateur

mot clef
(Lexème) Token …
chaîne

Mn nombre
 Fonctionnement de l’analyseur lexical
 L’analyseur lexical réalise également certaines tâches
secondaires :
Élimination des caractères d’espacement : les caractères blancs
(ou espaces), les tabulations et les sauts de lignes.
Élimination des commentaires.
Liaison des messages d’erreur issus du compilateur au
programme source (indication de la ligne qui contient l’erreur).
 Certains traitements de pré-processeur peuvent être implantés
au cours de l’analyse lexical.

34
Exemple
Soit le programme C suivant
int main()
{
int x, alpha;
x==20;
}

Identifions les lexèmes et les unités lexicales

35
Exemple
lexème Unité lexicale
main Mot clé
( séparateur
) séparateur
{ séparateur
x identificateur
, séparateur
alpha identificateur
20 nombre
…… ……

36
 Analyseur lexical-Unités lexicales
 Exemples d’unités lexicales :
Mots clés (key words) : ce sont des mots réservés au langage
de programmation.
 Exemples (langage C) : if, else, while, do, for, main, char, int, float,
double, sizeof, …etc.
Identificateurs (identifiers) : un identificateur est un nom
propre donné par le programmeur pour désigner une entité de
son programme (une variable, une fonction ou une étiquette).
En C, un identificateur est une suite de caractères qui
commence par une lettre ([a…z] ou [A…Z] ou « _ ») et ne
contient que des lettres et/ou des chiffres [0…9]).

37
 Unités lexicales
 Exemples d’unités lexicales (suite) :
Symboles spéciaux ou délimiteurs : ce sont des séparateurs
d’unités lexicales.
 Exemples (langage C):
 point virgule « ; »

 caractère blanc ou espace « »

 tabulation

 saut de ligne

 accolades « { } »

 guillemets « " »

 apostrophe « ' »

38
 Unités lexicales
 Exemples d’unités lexicales (suite) :
Opérateurs : des symboles pour des opérations de base
offertes par le langage de programmation.
 Exemples (opérateurs du langage C) : +, -, *, /, %, >, >=, ==, <=, <, !
=, &, |, ^, ~, >>, <<, &&, ||, !, ?:, =, +=, -=, *=, /=, %=, &=, |=, ^=,
~=, >>=, <<=, &&=, ||=, [ ], ( ), ., ->, & (adresse), sizeof.
Nombres : suite de chiffres avec éventuellement un signe (+ ou
-), un point décimal « . ».
Commentaires : chaînes de caractères délimitées entre deux
symboles spéciaux. Un commentaire est un texte à ignorer.

39
 Unités lexicales
 Exemples d’unités lexicales (suite) :
 Exemples de commentaires :
 En C : /* Texte */

 En C++ : // Texte

 En pascal : (* Texte *) ou { Texte }

 En JavaScript : <!-- Texte -->

 En Basic : REM Texte

 En visual basic : ' Texte

40
 Construction d’analyseur lexical
Implémenter des programmes en langage C, permettant de
reconnaitre les unités lexicales suivantes :
Identificateur
Nombre
Chaine de caractère
Opérateur de relation
Opérateurs d’affectation
Les séparateurs
Les blancs
Les mots clés
etc
Définir une fonction d’extraction pour chaque unité lexicale

41
Analyseur lexical-Vue d’ensemble

42
 Extraction des unités lexicales
Variables de l’analyse lexicale :
1. on utilise un tampon de lecture : Tampon
2. On utilise deux variables :
1. Une variable (ptrDeb) qui marque le début de la
prochaine unité lexicale à extraire
2. Une variable (ptrFin) initialisé à ptrDeb qui avance
jusqu’à la reconnaissance d’un lexème. Dans ce cas le
pointeur ptrDeb rejoint le PtrFin. Dans le cas contraire le
ptrFin revient à la position initiale, c’est-à-dire PtrDeb
3. Le lexème extrait sera rangé dans la variable lexème, son
unité lexicale sera rangée dans la variable UL

43
Construction d’analyseur lexical
La fonction associée à l’analyseur lexical

int lex()
{
if(identif())return 1;
if(opR())return 1;
if(Op_arith())return 1;
if(Ch_litterale())return 1;
if(Nombre())return 1;
if(Separateur())return 1;
if(Afectation())return 1;
if(Blanc())return(lex());
erreur_lexicale();return 0;
}
44
Fonction Identif()-Voir le code dans le fichier
[Link]
La fonction Identif() est une fonction qui retourne 1
lorsqu’elle reconnait l’unite lexicale Identificateur et 0
dans le cas contraire.
Cette fonction est définie en se basant sur l’automate qui
reconnait les identificateurs suivant

‘a’ .. ‘Z’ 0 .. 9

‘a’ .. ‘Z’
0 1
0..9
-1: état poubelle (ou trash)
-1
de gestion d’erreur
‘a’ .. ‘Z’ 0 .. 9
Automate correspondant aux identificateurs 45