14/10/2015

Chapitre I

Cours de compilation

Introduction aux compilateurs

Pr. Ghizlane BENCHEIKH
A.U. 2015 - 2016

I. Quest ce quun compilateur ?

1.1) Dfinition : Un compilateur est un programme
excutable (logiciel) qui permet de :

1.2) Exemples
Exemples de langage compils :
Fortran, C, C++, Pascal, ADA,

Lire un programme crit en un langage de haut niveau

(langage source) et le traduit vers un programme crit en

un langage de plus bas niveau (langage cible).
Signaler des erreurs de syntaxe, de smantique (par
exemple via une vrification de type)
Dans certains cas, faire des optimisations qui peuvent viser
plusieurs objectifs parfois contradictoires : vitesse
dexcution, taille du code, utilisation de la mmoire, etc.
3

Exemples de compilateurs pour le langage C :

Dev C++, LCC Win32, Code block, Borland C++,

Visual C++,

Dfinition : Un arbre abstrait est constitu de nuds qui reprsentent les

oprations et les fils des nuds qui reprsentent les arguments des
oprations.

II. La structure dun compilateur

La compilation se dcompose en deux phases, contenant
chacune plusieurs modules :

Exemple : Soit l'instruction: A = B1 + B2 * 60

Son arbre abstrait est :

Une phase danalyse, qui va reconnatre les variables, les

instructions, les oprateurs, dtecter les erreurs et laborer

une reprsentation intermdiaire,
Une phase de synthse et de production qui devra produire le

code cible partir de cette reprsentation intermdiaire.

Dessiner larbre abstrait des expressions

1) A = B+C+D,
2) A = B*C*D,
3) A = B*(C+D),
4) A=B*C+2*D*E

14/10/2015

2.1.1) Analyse lexicale

2.1) Phase danalyse

Elle lit le programme source lettre par lettre et le dcompose en

units lexicales appeles lexmes (Token en anglais)

La phase danalyse, est ralise par la partie frontale du

compilateur, elle permet de :
dcouper le programme source en ses constituants
(variables, instructions, ) : Analyse lexicale;
dtecter des erreurs de syntaxe : Analyseur syntaxique;
dtecter des erreurs de smantique : Analyse smantique;
produire une reprsentation intermdiaire du programme
source : Gnrateur de code intermdiaire;
conserver dans une table des symboles diverses informations
sur les procdures et variables du programme source.
7

Spcifie la nature de chaque unit lexicale, quil sagisse

didentificateurs, de constantes relles, entires, chanes de

caractres, des oprateurs (affectation, addition), des sparateurs
(parenthses, points virgules), les mots cls du langage (if, else,
while, int, float, )
Elimine les caractres superflus (commentaires, espaces,
passages la ligne).
Exemple : considrons le code C suivant :

if ( i < a + b ) // ceci est un commentaire

x = 2 * x;

2.1.2) Analyse syntaxique

Lanalyseur lexical dterminera la suite de token :

Il s

agit de vrifier que les units lexicales sont dans le bon

ordre dfini par le langage.
Lanalyseur syntaxique sait comment doivent tre construites les
expressions, les instructions, les dclarations de variables, les
appels de fonctions,
Exemple : En C, une slection simple doit se prsenter sous la
forme : if (expression) instruction
Si lanalyseur syntaxique reoit la suite dunits lexicales
MOT_CL_IF IDENT OP_REL ENTIER
il doit signaler une erreur car il ny a pas de ( juste aprs le if

MOT_CL SPARATEUR IDENTIFICATEUR OPRATEUR_REL

IDENTIFICATEUR
OPRATEUR_ARITH
IDENTIFICATEUR
SPARATEUR IDENTIFICATEUR AFFECTATION CONSTANTE
OPRATEUR_ARITH IDENTIFICATEUR SPARATEUR

Mot_cl

identificateur identificateur
Sparateur

Op_rel

Op_arith

liminer

if ( i < a + b ) // ceci est un commentaire

x = 2 * x;

Lanalyseur syntaxique produit un arbre syntaxique abstrait

10

2.1.3) Analyse smantique

2.2) Phase de synthse

Dans cette phase, on opre certains contrles (contrles de type,

La phase de synthse est ralise par la partie finale du

par exemple) afin de vrifier que lassemblage des constituants

du programme a un sens.

compilateur, elle construit le programme cible partir de la

reprsentation intermdiaire et de la table des symboles, elle
comprend :
Optimisation du code : Il sagit damliorer le code produit afin

On ne peut pas, par exemple, additionner un rel avec une

que le programme rsultant soit plus rapide, comme

llimination de calculs inutiles (faits en double), extraction des
boucles des invariants de boucle,
Gnration de code : Il sagit de produire les instructions en
langage cible.

chane de caractres, ou affecter une variable un nombre.

11

12

14/10/2015

2.3) Rsum

Programme source

Analyse
Lexicale

Analyse

Programme source

Analyse
Syntaxique

Reprsentation
intermdiaire

Reprsentation
intermdiaire

Analyse
Smantique

Synthse

Programme cible
13

Analyse

14

Gnrateur de
code
intermdiaire

Synthse

Programme cible

Programme source

Chapitre II
Optimisateur
du code
Gnrateur
du code cible

Analyse

Analyse lexicale

Reprsentation
intermdiaire

Synthse

Programme cible
16

15

I. Introduction

Dfinitions

Lanalyseur lexical constitue la premire tape dun

Une unit lexicale est une suite de caractres qui a une

compilateur. Sa tche principale est de lire les caractres

dentre et de produire comme rsultat une suite de lexmes
que lanalyseur syntaxique aura traiter.
Il limine les caractres superflus (commentaires,
tabulations, fin de lignes, )
Il gre les numros de ligne dans le programme source pour
pouvoir associer chaque erreur rencontre par la suite la
ligne dans laquelle elle intervient

17

Pour effectuer ces analyse, on fait appel aux notions de

thorie de langage, les expressions rgulires et les
automates.

signification collective.
Exemples :
les chanes , , <, > sont des oprateurs relationnels. Lunit

lexicale est OPREL, par exemple.

Les chanes toto, ind, tab, ajouter sont des identificateurs (de

variables ou de fonctions).
Les chanes if, else, while sont des mots cls.
Les symboles ; ( ) . sont des sparateurs.

18

14/10/2015

Un lexme est une suite de caractres du programme source qui

Exemples:

concorde avec le modle d'une unit lexicale

Exemple : Lunit lexicale correspondant la chane est
OPREL, alors que le lexme est .
Un modle est une rgle associe une unit lexicale qui dcrit
lensemble des chanes du programme qui peuvent correspondre
cette unit lexicale.

L'unit lexicale IDENT (identificateurs) en C a pour modle :

toute suite non vide de caractres compose de chiffres, lettres

ou du symbole "_" et qui commencent par une lettre. Des
exemples de lexmes pour cette unit lexicale sont : max, i, a1,
ajouter_valeur ...
L'unit lexicale NOMBRE (entier sign) a pour modle : toute
suite non vide de chiffres prcde ventuellement d'un seul
caractre parmi. Comme par exemple : -12, 83204, +0

pour les caractres spciaux simples et doubles et les mots rservs,

le lexme et le modle concident,

le modle d'un nombre est une suite de chiffres, ventuellement

prcde d'un signe ,

Attributs : informations concernant le lexme (champs

Le modle d'un identificateur est une suite de lettres, de chiffres et

dans la table des symboles) ;

du caractre _ , commenant par une lettre.

19

20

On note le mot vide

II. Expressions rgulires

Si x et y sont deux mots, la concatnation de x et y, note xy, est le

Dfinitions
Un alphabet est un ensemble de symboles.

mot obtenu en crivant y immdiatement aprs x. Par exemple, la

concatnation des mots abc et le mot rst est le mot abcrst.
Si x est une chane, on dfinit

{0,1} est un alphabet

{A,T,C,G} est un alphabet
{1,M,0,5} est un alphabet

x0 =
Pour n > 0, xn = xn-1x =xxn-1.

Un mot (ou chane) sur un alphabet est une squence

On a donc x1 = x, x2 = xx, x3 = xxx, etc.

finie de symboles de .

00011011 est un mot sur {0,1}

ACCAGTTGAAGTGGACCTTT est un mot sur {A,T,C,G}.
Soit lalphabet { aa, b, c} aba nest pas un mot sur . baab, caa,

bc, aaaa sont des mots sur .

21

22

Un langage sur un alphabet est un ensemble de mots construits sur

. Exemple :
Soit lalphabet = {a,b,1}, soit L lensemble des mots qui se terminent

Exemple : On se donne les alphabets L = {A,BZ, a, b z}, ensemble

des lettres, et C ={0,1 9}, ensemble des chiffres. Dfinir les langages
suivants : L U C, LC, L4, L*, C+ et L(L U C)*.

par 1. L1 est le langage infini : {a1, b1, aa1, ab1, aaabb1, .}

Soit lalphabet franais, lensemble des mots du dictionnaire constitue un

langage sur cet alphabet.

LC est l'ensemble des chanes formes d'une lettre suivie d'un chiffre,

Les oprations sur les langages

Soient L et M deux langages, on dfinit :
Dnomination

L4 est l'ensemble des chanes de quatre lettres,

L* est l'ensemble des chanes faites d'un nombre quelconque de

Notation Dfinition
LUM

{ x | x L ou x M}

la concatnation de L et M

LM

{xy | x L et y M}

la fermeture de Kleene de L

L*

{ x1x2xn | xi L, n N et n 0}

la fermeture positive de L

L+

{ x1x2xn | xi L, n N et n >0}

l'union de L et M

23

L U C est l'ensemble des lettres et des chiffres,

lettres ; en fait partie,

C+ est l'ensemble des chanes de chiffres comportant au moins un

chiffre,

L(L U C)* est l'ensemble des chanes de lettres et chiffres commenant

par une lettre.

24

14/10/2015

Problmatique

Expression rgulire

tant donn un langage, comment dcrire tous les

Soit un alphabet. Une expression rgulire r sur est une formule

qui dfinit un langage L(r) sur , de la manire suivante :
est une expression rgulire qui dfinit le langage {} ;
Si a , alors a est une expression rgulire qui dfinit le
langage {a} ;
Soient x et y deux expressions rgulires, dfinissant les
langages L(x) et L(y). Alors

mots acceptables ?
Comment dcrire un langage ?
Comment savoir quun mot donn appartient un

langage donn?

x|y est une expression rgulire dfinissant le langage L(x) U L(y)

xy est une expression rgulire dfinissant le langage L(x)L(y)

En utilisant les expressions rgulires

25

x* est une expression rgulire dfinissant le langage (L(x))*

26

Remarques
Priorit des oprateurs : on conviendra des priorits

dcroissantes suivantes : *, concatnation, |

Exemple : ab*|c veut dire : (a(b*))|c
La concatnation est distributive par rapport |
Exemple : r(s|t) = rs|rt et (s|t)r = sr|tr
Exercice 1: Quelles sont les langages dfinies par les
expressions rgulires suivantes : (a|b)*, a|b*c, (a*|b*)*,
b*ab*ab*ab*

27

Exercice 2 : Donnez, pour chacun des langages suivants, une

expression rgulire qui permet de le dfinir (sur lalphabet
= {0, 1}) :
Toutes les chanes qui se terminent par 00.
Toutes les chanes dont le 10me symbole, compt partir de la
fin de la chane, est un 1.
3) Ensemble de toutes les chanes dans lesquelles chaque paire de 0
apparat devant une paire de 1.
1)
2)

Exercice 3 : Donnez lexpression rgulire qui permet de dfinir

un identificateur en langage C
28

EXEMPLE : Voici quelques dfinitions rgulires, et notamment

celles de identificateur et nombre, qui dfinissent les identificateurs et
les nombres du langage C :

Dfinition rgulire
Pour allger lcriture de certaines expressions rgulires, on
introduit des dfinitions rgulires qui permettent de donner des
noms certaines expressions en vue de leur rutilisation. On
crit donc
d1 r1
d2 r2

dn r n

lettre A | B | ... | Z | a | b | ... | z

chiffre 0 | 1 | ... | 9
identificateur lettre ( lettre | chiffre )*
chiffres chiffre chiffre*

On utilise la notation

rgulire c1|c2| |ck

[c1c2 ck] pour dsigner lexpression

o chaque di est une chane sur un alphabet disjoint de ,

distincte de d1, d2 di-1, et chaque r i une expression rgulire

sur U {d1, d2 di-1}.

29

30

14/10/2015

III.1. Automate fini

III. Mise en uvre dun analyseur lexical

31

Le rle dun analyseur lexical est la reconnaissance des units

lexicales. Une fois la syntaxe des tokens est spcifies de faon
formelle avec des expressions rgulires, il faut un procd
automatique. Pour cela, on utilise des automates. Les tapes sont
donc :
Ecriture dexpressions rgulires
Conversion dexpressions rgulires en automates non
dterministes finis (AFN)
Passage en automate fini (AFD)
Minimisation de lautomate
Construction du code correspondant
Pour implmenter lautomate ainsi obtenu, on utilise
souvent un tableau qui contient la fonction de transition.

Exemple 1

Un automate fini est une machine dote dun ensemble fini

dtats, et qui lit des lments dun alphabet, faisant passer la

machine dun tat un autre chaque lecture.
Un automate fini est la donne de :
un alphabet fini ;
un ensemble fini dtats Q ;
une fonction de transition : Q Q ;
un tat initial p0 ;
un ensemble dtats finaux F (reprsentant chacun la
reconnaissance dun lexmes)

32

Reprsentation matricielle

0
1
2
3

a
1
3

b
2
0

Tableau de transition
33

34

Automate fini non-dterministe

Un automate fini non-dterministe (AFN) est un automate qui
offre plusieurs changements dtat pour un mme symbole
.
Exemple, lautomate suivant, qui reconnat tous les mots composs
dau moins une lettre sur lalphabet {a,b}, offre deux possibilits
de reconnaissance dun mot partir de ltat initial gris :

Exemple 2

35

36

14/10/2015

Automate fini dterministe

Un automate fini dterministe (AFD) est un automate o dun tat
un autre il existe au plus un mouvement possible.

III. 2. Conversion dexpressions rgulires en

automates finis non dterministes (AFN)
On utilise ici une construction assez intuitive qui est lalgorithme

de Thompson. On prend des blocs de lexpression rgulire, et on

construit les morceaux dautomates requis, jusqu assembler le tout.

Exemple : Considrons lexpression rgulire reprsentant un

entier naturel suivante : chiffre chiffre*

P0

Chiffre

Cette construction produit de trs nombreuses transitions, ce qui

P1

fait que lautomate obtenu nest pas dterministe.

Chiffre

37

38

Expression
Schma correspondant
rgulire
a
ab

a|b

Exercice
Donner les automates finis non dterministe correspondants aux
expressions suivantes :
1) (a|b)*aba
2) (ab*c)|(a(b|c*))
3) Ecrire un automate reconnaissant les entiers signs. Si le
nombre comporte plusieurs chiffres, le premier ne peut pas tre
0 (pas de 007 par exemple)
4) Ecrire un automate reconnaissant les rels. Exemples : -5280,
+39.37, 1.849E-4, -.849E4

a*
39

III. 3. Automate => Expression rgulire

Transformation de lautomate en automate gnralis.
Transformation de lautomate gnralis en expression rgulire.
Un automate gnralis est un automate fini dont les transitions

sont tiquetes par des expressions rgulires et non pas

simplement des symboles ou le mot vide.
Exemple

41

40

Transformation dun automate en automate

gnralis
Ajouter un nouvel tat initial possdant une transition- vers lancien tat

initial.

ajouter un nouvel tat dacceptation vers lequel il existe une transition-

partant des anciens tat dacceptation.

Sil existe plusieurs transitions entre deux tats , elles sont remplaces par

une transition unique tiquete par lunion des tiquettes des diffrentes
transitions.
Des transitions tiquetes sont ajoutes entre les tats qui ne sont relis
par aucune transition.

42

14/10/2015

chaque itration, on diminue dun le nombre dtats de lautomate

gnralis.
A lissue du processus, on obtient un automate gnralis

comportant deux tats (ltat initial et ltat dacceptation) et une

transition entre les deux.
Lexpression rgulire tiquetant cette transition dnote le langage
de lautomate initial.

43

44

Exercice
Dessiner lautomate non dterministe dfini par :

A = (={a,b}, Q ={1,2,3,4}, , Init = {1,2}, Fin = {3,4})

Avec donne par la table :

Dcrire par une expression rgulire le langage reconnu par

A. Simplifiez ventuellement cette expression.

45