COMPILATION

ET
THÉORIE DES LANGAGES

Dr. Abdelali El Gourari

 Dr. Abdelali El Gourari
Doctor of Computer Science specializing in Artificial Intelligence and Embedded Systems at Cadi Ayyad University,
Morocco. His primary research interests are applying artificial intelligence to adaptive education systems,
particularly remote-controlled experiments.

mail
[email protected]
[email protected]

Websites
ai-labs.uca.ma
elgourari.com

Présentez vous
 Plan

• Introduction • Langages d’assemblage

• Les objectives du Cours • Assemblage
• L'environnement d'un compilateur • Langages machines
• Cousins des compilateurs • Structure d’un compilateur
▪ Interpréteurs • Analyse lexicale
▪ Préprocesseurs • Analyse syntaxique
▪ Langages Intermédiaire ou P-code • Analyse sémantique
▪ Éditeur de liens
• Génération de code
▪ Le Chargeur
• Optimisation de code
 Introduction
Un compilateur est un logiciel particulier qui traduit un programme écrit dans
un langage de haut niveau (par le programmeur) en instructions exécutables
(par un ordinateur). C'est donc l'instrument fondamentale à la base de tout
réalisation informatique.

Programme Compilateur Programme

source Cible

Messages
d'erreur
 Introduction

• Premier compilateur : compilateur

Fortran de J. Backus (1957)

• Langage source : langage de haut

niveau (C, C++, Java, Pascal,…

• Langage cible : langage de bas niveau

(assembleur, langage machine)
 Introduction
• La compilation est la traduction d'un langage de programmation de haut
niveau vers un autre langage de programmation de haut niveau.

• Une traduction de Pascal vers C, ou de Java vers C++, on parle plutôt de

traducteur
• La différence entre traducteur et compilateur : dans un traducteur, il n'y a pas
de perte d'informations (on garde les commentaires, par exemple), alors que
dans un compilateur il y a perte d'informations.
• La traduction d'un langage de programmation de bas niveau vers un autre
langage de programmation de haut niveau. Par exemple pour retrouver le code
C à partir d'un code compilé (piratage, récupération de vieux logiciels, ...)
 Les objectives du Cours

Le but de ce cours est de présenter les principes de base inhérents à la

réalisation de compilateurs.
 Les objectives du Cours

• Les principes de base inhérents à la réalisation de compilateurs : analyse

lexicale, analyse syntaxique, analyse sémantique, génération de code.
• Les outils fondamentaux utilisés pour effectuer ces analyses : Grammaires,
Automates à état fini, méthodes algorithmiques d'analyse...
• Comprendre comment est écrit un compilateur permet de mieux
comprendre les contraintes imposées par les différents langages lorsque
l'on écrit un programme dans un langage de haut niveau.
L'environnement d'un compilateur
Programme Source
Code machine absolu
Chargeur
Préprocesseur
Bibliothèque Code Relogeable

Programme source prétraité éditeur de Liens

Compilateur Code relogeable

Assembleur

Programme cible en langage d'assemblage

Cousins des compilateurs

• Interpréteurs

• Préprocesseurs

• Langages Intermédiaire ou P-code

• Éditeur de liens

• Le chargeur
 Interpréteurs
• L'interpréteur  analyse une
instruction après l'autre puis
l'exécute.

• Un compilateur  Il travaille
simultanément sur le
programme et sur les données.

Exemples de langages
interprétés : Python, BASIC,
Perl, Prolog…
 Préprocesseurs  .cpp
Le préprocesseur est un programme qui analyse votre code source et y
effectue des modifications avant la compilation.

https://www.google.com/url?sa=i&url=https%3A%2F%2Fyard.onl%2Fsitelycee%2Fcours%2Fc%2FC
ompilationSeparee.html&psig=AOvVaw0SKl4NAbvHgsrmRJPyX302&ust=1728408833048000&sourc
e=images&cd=vfe&opi=89978449&ved=0CBcQjhxqFwoTCNDojPfm_IgDFQAAAAAdAAAAABAb
 Langages Intermédiaire ou P-code

• Les langages P-code ou langages intermédiaires sont à mi-chemin de

l'interprétation et de la compilation.
• Le code source est traduit (compilé) dans une forme binaire compacte (du
pseudo-code ou p-code) qui n'est pas encore du code machine. Ce P-code est
interprété pour exécuter le programme.
• Par exemple en Java, le code source est compilé pour obtenir un fichier
(.class) ''byte code'' qui sera interprété par une machine virtuelle.
 L'édition des liens (Linker)

• L'édition des liens consiste à relier les codes de chaque fonction de bibliothèque
utilisée avec le programme.

• Le résultat de l'édition des liens est un programme exécutable,

 Le Chargeur

• Le programme objet, obtenu après l’édition de liens, doit encore être chargé en
mémoire centrale pour être exécuté. Le chargeur s’occupe de cette tâche.

• Dans les anciens systèmes (comme DOS), on pouvait fixer les adresses à
l’avance et charger le programme à l’endroit spécifié. On utilisait donc un
chargeur absolu.

• Aujourd'hui, les chargeurs s’occupent de reloger les programmes en mémoire

centrale. Ce sont des chargeurs relogeables (transformable).
 Structure d’un compilateur
programme source analyseur lexical

analyseur syntaxique
gestion de la gestion des erreurs
analyseur sémantique
table des symboles
générateur de code
intermédiaire

"optimiseur" de code
générateur de code
cible programme cible
 Analyse lexicale(Scanning)

Appelée aussi Analyse linéaire

• Reconnaître les types des mots lus. Pour cela, on lit le programme source de
gauche à droite et les caractères sont regroupés en unités lexicales.
• Se charger d’éliminer les caractères superflus (commentaires, espaces, ...)
• Identifier les parties du texte qui ne font pas partie à proprement parler du
programme mais sont des directives pour le compilateur .
 Analyse lexicale(Scanning)
Outils théoriques utilisés : expressions régulières et automates à états finis

position = initial + vitesse * 60

[id, 1] [=] [id, 2] [+] [id, 3] [*] [60]

Les identificateurs rencontrés sont placés dans la table des symboles.

Les blancs et les commentaires sont éliminés.
 Analyse syntaxique

• Appelée aussi analyse grammaticale

• Il s'agit de regrouper les unités lexicales en structures grammaticales, de
découvrir la structure du programme.
• L'analyseur syntaxique sait comment doivent être construites les
expressions, les instructions, les déclarations de variables, les appels de
fonctions, ...
 Analyse syntaxique
On reconstruit la structure syntaxique de la suite d’unités lexicales fournie
par l'analyseur lexical.
Instruction d'affectation
Arbre de dérivation

identificateur expression
position =

expression + expression

expression * expression
identificateur
initial

identificateur nombre
vitesse 60
 Analyse syntaxique

while (b != 0) {
if (a > b)
a = a - b; Donner l’arbre de
else dérivation?
b = b - a;
}
return a;
Analyse syntaxique

?
 Analyse Sémantique

Appelée aussi analyse contextuelle

• Dans cette phase, on opère certains contrôles (contrôles de type, par

exemple) afin de vérifier que l'assemblage des constituants du
programme a un sens.

• On ne peut pas, par exemple, additionner un réel avec une chaîne de

caractères, ou affecter une variable à un nombre, ...

• Outil théorique utilisé : schéma de traduction dirigée par la syntaxe

 Analyse Sémantique
De point de vue des types, le fragment analysé est
correct; il faut noter toute fois la conversion de
<affectation > l’entire 60 vers le réel 60.0 et le fait que les
opérations étiquetant l’arbre abstrait sont des
opérations flottantes.
<somme>
Id_1

Id_2 <mult>

Id_3 Conv-ent

60
 Génération de code
<affectation >

<somme>
Id_1
Code à trois adresses
A1 := inttoreal(60) Id_2 <mult>
A2 := id3 * A1
A3 := id2 + A2 Id_3 Conv-ent

id1 := A3
60
 Optimisation de code

Elimination des opérations inutiles pour produire du code plus efficace.

A1 := inttoreal(60) A1 := id3 *60.0
Les variables A2 et A3 sont éliminées
A2 := id3 * A1 id1 := id2 + A1
A3 := id2 + A2
id1 := A3
● La constante est traduite en réel flottant à la compilation, et non à
l'exécution
 Génération de code cible

• La dernière phase produit du code en langage d'assemblage

• Un point important est l'utilisation des registres
MULF #60.0, R2
A1 := id3 * 60.0 MOVF id3, R2
id1 := id2 + A1 MOVF id2,R1
ADDF R2, R1
MOVF R1, id1
• F = flottant.
• La première instruction transfère le contenu de id3 dans le registre R2
• La seconde multiplie le contenu du registre R2 par la constant 60.0
 Gestion de la table des symboles

• La table des symboles est la structure de données utilisée servant à stocker

les informations qui concernent les identificateurs du programme source.

• Le remplissage de cette table (collection des informations) a lieu lors des

phases d'analyse.

• Les informations contenues dans la table des symboles sont nécessaires

lors des analyses syntaxique et sémantique, ainsi que lors de la génération
de code.
 Gestion des erreurs

• Chaque phase peut rencontrer des erreurs. Il s'agit de les détecter et

d'informer l'utilisateur le plus précisément possible : erreur de syntaxe,
erreur de sémantique, erreur système, erreur interne.
• Détecte des erreurs Lexicales:
 Identificateurs trop longs ou illégaux
 Caractères ou nombres illégaux.
• Détecte des erreurs syntaxiques:
 Parenthèses non fermées,
 Manque de délimiteurs
 Quelques problématiques

• Analyse lexicale : est-ce que mon programme utilise les mots de base du
langage ?
• utilisation d’automates dans les compilateurs.
• Analyse syntaxique : est-ce que les mots/phrases de mon programme sont
correctement construits ?
• utilisation de grammaires dans les compilateurs.
• Analyse sémantique :est-ce que le programme fait ce que je veux ?
• indécidable.
• preuve à la main dans de nombreux cas !
 Qualités d’un compilateur

• Correction : le programme compilé doit avant tout correspondre au même

calcul que le programme original
• Optimisation : le programme généré doit être rapide
• Efficacité : le compilateur lui-même doit être rapide
• Productivité : le compilateur doit signaler les erreurs et les risques de
manière compréhensible
• Portabilité : le compilateur doit être extensible facilement à de nouveaux
langages source et architectures cibles
• Prévisibilité : les optimisations doivent être cohérentes et prévisibles
 Un langage ?

• Pour nous, un langage est simplement un ensemble de suites de lettres…

• Un langage formel = un ensemble de mots.

• on dit aussi: chaînes de caractères

 Exemples

• {0, 01, 10, 00, 11, 000, 001, 010, 100, 011, 101, 110, 111} est un langage
• {la, lala, lalala, lalalala, lalalalala, …, lalalala…la, ….} est un langage
• {T, ₢T, ₢ ₢ T, ₢ ₢ ₢ T, …} est un langage
• L’ensemble des mots définis dans un dictionnaire.
• L’ensemble des phrases que l’on peut écrire en français.
 Alphabet

• Alphabet (vocabulaire, lexique) : est un ensemble fini de symboles.

• alphabet = lettres, espace et symboles de ponctuation, . . .

Remarque:

• On note A* l'ensemble des mots sur A. ???

 Exemples

• A={0, 1}  l’alphabet binaire

• B={a, b, c…..z, é, ç, …..}  l’alphabet de la langue français
• C={int, if, else, printf}  un alphabet du langage C
• C={BONJOUR,ab, ça, 20, $}  un alphabet de 5 symboles

sont des alphabets couramment utilisés

 Mots

Un mot est une suite finie de symboles :

–> 0010111100 est un mot sur {0, 1}
–>aaabbb est un mot sur {a, b}
–> acababbc est un mot sur {a, b, c}
–> BONJOUR est un mot sur {A, …, Z}
–> μξπρςστυ est un mot sur {α, …, ξ}
 Longueur d’un mot

• BONJOUR est un mot de longueur 7

• La longueur d’un mot w, notée |w|, est simplement le nombre de
symboles qui le composent.
 Stratification

Parmi tous les mots sur A, il y a:

– Les mots de longueur nulle, formant l’ensemble {ε}
– Les mots de longueur 1, donnant simplement l’ensemble A
– Les mots de longueur 2, formant 𝑨𝟐
–Les mots de longueur n, formant 𝑨𝒏
Mot
Mot
 Concaténation

• Soit deux mots S et S’ sur A

• S’ils sont définis par : S = 𝑺𝟏 … 𝑺𝒏 et S’ = 𝑺′𝟏 … 𝑺′𝒎 ,
• On peut définir un nouveau mot, qu’on notera S.S’ (ou SS’) par:
• S.S’ = 𝑺𝟏 …𝑺𝒏 𝑺′𝟏 …𝑺′𝒎
• Il s’agit de la concaténation de S et de S’
 Exemple

• Sur X={a, b, c}, S=abbac est un mot, qui est désigné par S
• S’=bcca est un autre mot, qui est désigné par S’
• On vérifiera que leur concaténation S.S’ correspond au mot abbacbcca
 Propriétés

La concaténation est associative…mais non commutative...

• Un élément neutre : ε
ε.x = x. ε = x
• Conséquence : la concaténation d’une suite vide de mots est le mot
vide
 Propriétés

• Lemme de décomposition:
Soit U la langueur de ‘av’.
Soit il existe un symbole ‘a’ et un mot ‘v’ de longueur |U|-1 tels que
U=av
ex: U=XML avec a=X et v=ML
• Puissance: w, n≥ 𝟎
– 𝒘𝟎 = ε
– 𝒘𝒏+𝟏 = 𝒘𝒏 𝒘
 Stratification
D’où la formule:

A* = {ε} ∪ A ∪ 𝑨𝟐 ∪ 𝑨𝟑 ... ∪ 𝑨𝒏 …

Ou:
𝐴∗ = ‫∞ڂ‬
𝑛=0 𝐴
𝑛

avec 𝑨𝟎 = {ε}
 Langages Formels

Un langage formel sur un alphabet A sera défini simplement comme une

partie de A*
Donc parmi les langages possibles sur A:

–∅ ---(langage vide)
– {ε} ---(langage réduit au mot vide)
– A* --- (langage plein)
Puissance d’un mot
Factorisation d’un mot
Factorisation d’un mot
Inverse d’un mot ou miroir
Relation d’ordre
Langage
Les opérations sur les langages
Les opérations sur les langages
Les opérations sur les langages
Les opérations sur les langages
Les opérations sur les langages
Les opérations sur les langages
Exercice
Solution
 Grammaire

 Introduction
Grammaire
Grammaire
Grammaire
Grammaire
Dérivation
Exemple
Exemple
Langage engendré par une grammaire
Grammaire équivalentes
Classification des grammaire
Classification des grammaire
Classification des grammaire
Classification des grammaire
Arbre Syntaxique
Arbre Syntaxique
Classification des grammaire
Classification des grammaire
Classification des grammaire
Classification des grammaire
Classification des langages
Classification des langages
Classification des langages
Exercice 1 et 2
Sol_Exercice_1
Sol_Exercice_2
 Exercice 3
Soient les grammaires Gi = ({a, b, c} , {S, A, B, R, T} , S , Pi), (i=1,..,6) ; où les Pi sont
:
1) P1 : S → aA | bB ; A → a | ab ; B → b | cb
2) P2 : S → bA ; A → aA | ε
3) P3 : S → aSc | A A → bA | b
4) P4 : S → aSbS | ε
5) P5 : S → aRbc | abc ; R → aRTb | aTb ; Tb → bT ; Tc → cc
6) P6 : S → aAb | ε A → aSb ; Ab → ε

 Pour chacune des grammaires Gi (i=1,..,6) ; donner le type de celle-ci, puis trouver
le langage engendré par chacune d’elles.
 Vérifier que G2 n’est pas de type 1 ; mais que L(G2) est de type 1.
 Montrer que L(G6) est de type 2 en trouvant une grammaire de type 2 qui
l’engendre.
 Exercice 4
Soit la grammaire G dont les règles de production sont :
S → RD
R → aRb | A
Ab → bbA
AD → ε
1) Déterminer L(G).
2) Construire une grammaire de type 2 équivalente à G.
 Sol_Exercice_3
II) G2 n’est pas de type 1 car elle contient la règle : A → ε ; or dans les grammaires
de type 1, le seul symbole qui peut produire la chaîne vide est S. Cependant, on peut
écrire une grammaire de type 1 équivalente à G2 : G2’ a pour règles de production :
S → Sa | b ; ce qui veut dire que L(G2) est de type 1.
III) Une grammaire de type 2 équivalente à G6 : G6’ a pour règles de production : S
→ aaSbb | a | ε
 Sol_Exercice_4
1) L(G) = { anb2n / n > 0} ;
2) Grammaire de type 2 équivalente à G : G’ = ({a, b}, {S}, S, P’)
où P’ : S → aSbb | ε