Ministre de l’enseignement supérieur et de la recherche scientifique

Université Abderrahmane Mira Bejaia

Faculté des sciences exactes
Département d’informatique

Cours de Compilation

M1 RS – S2
Nadia TASSOULT
[Link]@[Link]

1
 Plan du cours
I. Introduction à la compilation
• Les différents étapes de la compilation
• Compilation, interprétation, traduction
II. Analyse lexicale
• Principe et rôle d'un analyseur lexical
• Terminologies
• Rappel sur les Expressions Régulières, Langages, Grammaires et Automates
• Méthodes d’analyse lexicale : à la main et par automates
III. Analyse syntaxique
• Récursivité à gauche et factorisation d’une grammaire.
• Méthodes d’analyse descendante et ascendante.
2
 Le rôle d'un analyseur lexical
La tache principale d’un analyseur lexical consiste à :

✓ Lire le texte d'entrée, caractère par caractère, de la

gauche vers la droite.

✓ Produire en sortie des unités lexicales (lexèmes ) qui sont

traitées par l’analyseur syntaxique.

3
 Le rôle d'un analyseur lexical
L’analyseur lexical doit aussi assurer certaines tâches
secondaires comme :
✓ Eliminer les blancs (espaces, tabulations, fin de lignes) et
les commentaires.
✓ Construire et gérer la table des symboles.
✓ Détecter les erreurs et associer des messages d'erreurs.
4
 Le rôle d'un analyseur lexical
L’interaction entre l’analyseur lexical et l’analyseur syntaxique peut
être schématisée comme suit:
Table des
Symboles

Unité Lexicale et ces

Texte Analyse Analyse
Attributs Reste
d’entrée Lexicale Prochaine Unité Syntaxique
Lexicale

Traitements
des Erreurs
 Le principe d'un analyseur lexical
L’analyseur lexical consiste à partir d’un programme qui est une suite
de caractères séparés par des blancs (ou des séparateurs) à:
• Spécifier les différentes entités lexicales (les mots) du langage.
• Éliminer les blancs, ainsi que les commentaires.
• Codifier les différentes entités lexicales.
• Construire la table des symboles.
• Gérer les erreurs Lexicales

6
 Le principe d'un analyseur lexical
Les unités lexicales les plus courantes:
• Les mots-clés : des mots réservés par le langage ( while, do, if, else,
for, repeat ...etc).
• Les identificateurs : les noms des variables, types, fonctions, tableaux.
• Les opérateurs : arithmétiques, logiques et de comparaison (*,+, -, /,
=, <, >, and, or, …etc ).
• Les nombres : entiers ou réels.
• Les chaînes de caractères : séquence de caractères alphanumériques.
• Les séparateurs : ( ) [ ] { } ... etc.
• Les délimiteurs : espace, tabulation et retour à la ligne.
7
 Le principe d'un analyseur lexical
L’analyseur lexical peut être vu comme une fonction ProchaineUnitéLexicale() de l’analyse
syntaxique.

• Chaque fois qu’elle est appelée, lit le programme source caractère par caractère, jusqu’à
ce qu’elle puisse reconnaitre une unité lexicale qu’elle retourne à l’analyseur syntaxique.

• La fonction ProchaineUnitéLexicale() commence la lecture par le caractère suivant la

dernière unité lexicale reconnue.

• Dans certains cas la fonction est appelée à faire des reculs pour recommencer la
reconnaissance de la prochaine unité lexicale.
8
 Spécification des unités lexicales
Lorsque l’analyseur lexical reconnaît une unité lexicale, il la transmet à
l‘analyseur syntaxique avec ses différents attributs (Type, adresse, portée, …)

• Chaque unité lexicale corresponde à une expression régulière qui spécifie

formellement son modèle.

• Les expressions régulières, correspondant aux différentes unités lexicales

reconnaissables par un langage, forme la grammaire du langage.

• La grammaire distingue un nombre fini de classes d’unités lexicales qui

représentent les symboles terminaux de la grammaire.

9
 Spécification des unités lexicales
Exemple : Soit la grammaire des instructions conditionnelles suivante:
• L’axiome de la grammaire représente
Inst → if (Exp) then Inst son point de départ et doit désigner
| if (Exp) then Inst else Inst l’ensemble du texte à analyser

• Les terminaux (unités lexicales) de cette

Exp → Terme oprel Terme grammaire sont: if , then , else , ( , ) ,
|Terme oprel , id et nb .

Terme → id • Pour les reconnaître, il faut d'abord

|nb donner les définitions régulières
associées.

10
 Terminologies
• Unité lexicale (token): une suite de caractères qui a une
signification collective : identificateur, entier, opérateur etc. C’est
un symbole terminal de la grammaire du langage.
• Modèle: est une règle associée à une unité lexicale qui décrit
l’ensemble des chaînes qui peuvent correspondre à cette unité
lexicale: expression régulière.
• Lexème: est une suite de caractères du texte d'entrée qui
concorde avec le modèle d’une unité lexicale.
Exemple 1: 10 est un lexème qui appartient à l'unité lexicale Entier.
11
 Terminologies
Exemple 2:
Soit le pseudo code Pascal suivant:
begin
Y:= (X*5)-1;
If (y<0 ) then
Y:=0;
end.
• Déterminer les Tokens (les unités lexicales) et les
lexèmes correspondants. 12
 Terminologies
Tokens Lexèmes Modèles
Mot clé Begin , end Suite de lettres qui appartient à l’ensemble des mots
, if , then clés : 𝐿+ ∈ (𝑚𝑜𝑡𝑠 𝑐𝑙é𝑠)
Identificateur Y, X Suite de lettres qui n’appartient pas à l’ensemble des
mots clés : L(𝐿+𝐶)* ∉ (𝑚𝑜𝑡𝑠 𝑐𝑙é𝑠)
Entier 5 , 0 Suite de chiffres : C+
Opérateur - ,* Ensemble d’opérateurs ∈ : {′+′ , ′*′ , ′-′ , ′/′, …}
Arithmétique (OpA)
Opérateur de < Ensemble d’opérateurs ∈ :
Comparaison(Opco {′<′ , ′>′ , ′=′ , ′≥′ , ′≤′ , ‘!=‘ …}
Parenthèses ( , ) Ensemble de symboles ∈ { ′(′ , ′)′ , ′{′ , ′}′ , ′[′ , ′]′ , …}
Séparateur ; . Ensemble de symboles ∈ {′:′ , ′,′ , ′.′ , ′;′ , …}
Affectation := Symbole d’affectation { := }
13
 Terminologies
Exemple 3: Pour reconnaitre les unités lexicales du code: I:= 2; nous devons faire 4
appels à la fonction ProchaineUnitéLexicale().
Numéro d’appel à la fonction Prochain caractère Action
ProchaineUnitéLexicale() à lire

1 I Avancer
: Reconnaitre l’identificateur I et reculer un car
: Avancer
2 = Avancer
2 Reconnaitre le symbole := et reculer car

2 Avancer
; Reconnaitre le nombre 2 et reculer d’un car
3
4 ; Avancer
Blanc (espace) Reconnaitre séparateur ; et pas de recul
(ignore l’espace)
14
 Langages et Expressions Régulières
Définitions:
• Alphabet: un ensemble A fini de symboles appelé caractères.
Exemple :
Pour décrire des nombres binaires, on utilise l’alphabet A = {0, 1}.
4. Rappels sur les Langages & Expressions Régulières
Les symboles les plus couramment utilisés sont :
• Les lettres : a, b, ..., z, A, B, ..., Z
• Les chiffres : 0, 1, ... , 9
• Les symboles mathématiques : +, - , *, / , =, > ,<, ...
15
 Langages et Expressions Régulières
• Mot: une chaine de caractères M=c1c2 ... Cn sur un alphabet A.
C’est une suite finie et ordonnée de caractères (c1 … cn).

✓ La longueur l du mot M est le nombre n de symboles contenus

dans M . On le note par |M|.

✓ La longueur de la chaîne vide notée  ∈ A est noté par ||= 0.

Exemple:
✓ 1101101 est un mot sur l’alphabet A = {0, 1} de longueur 7.
16
 Opérations sur les mots
On peut définir plusieurs opérations sur les mots.

• Egalité : deux mots m1 et m2 sur un même alphabet A sont égaux, si et

seulement si |m1| = |m2| = l
• Concaténation : la concaténation de m1 et m2 qui s’écrit m1m2, est le
mot formé en joignant les symboles de m1 et m2.
• Miroir : le miroir d’un mot m = a1a2...an est le mot m¯ = an...a2a1
obtenu en inversant les symboles de m.
Exemple:
La concaténation de m1 = 1101 et m2= 010 est le mot m1m2 = 1101010.
17
 Opérations sur les mots
Remarques:

✓La concaténation n’est pas commutative mais elle est associative:

m1(m2m3) = (m1m2)m3 = m1m2m3.

✓|m1m2| = |m1| + |m2|= l (même longueur).

✓| m¯| = |m|.

✓Le mot vide est neutre pour la concaténation: w  =  w = w

18
 Parties d’un mot
• Préfixe d’une chaîne s : chaîne obtenue en supprimant un nombre
quelconque (éventuellement 0) de symboles à la fin de s.
• Suffixe d’une chaîne s : chaîne obtenue en supprimant un nombre
quelconque (éventuellement 0) de symboles au début de s.
• Sous-chaîne d’une chaîne : chaîne obtenue en supprimant un préfixe et un
suffixe .

Exemple: soit le mot m = 1110 sur l’alphabet A = {0 1}.

• Préfixes : ,1, 11, 111, et 1011
• Suffixes :  , 110, 10, 0 et 1110
• Sous-mot :  , 0, 1, 11, 111, 10 et 1111
19
 Langages et Expressions Régulières
• Langage : un langage L sur un alphabet A est un ensemble fini ou
infini de mots sur A.
Exemple: Le langage des nombres binaires de longueur 4 est formé des
mots suivants : 0000, 0001, 0100, 1100, 1001, …
Remarques:
• Une unité lexicale est un langage sur un alphabet particulier A.
• Le langage de tous les mots sur l'alphabet A est noté A*.
• Une chaîne s est un mot sur un alphabet A, si et seulement si s ∈ A*.
• L est un langage sur un alphabet A, si et seulement si L  A*.
20
 Opérations sur les langages

• Nous pouvons appliquer les opérations ensemblistes aux

langages : réunion, intersection et complémentaire.

• Pour l’analyse lexicale, on s’intéresse principalement aux

trois opérations suivantes : réunion, concaténation,
fermeture.

21
 Opérations sur les langages
• La réunion de deux langages L et K sur un même alphabet A notée L ꒤
K, est définie par :
L ꒤ K = {  m  A* | m  L ou m  K}
• La concaténation de deux langages L et K sur un même alphabet A
notée LK, est définie par :
LK = {  ms  A* | m  L et s  K}
• La fermeture de Kleene (l’étoile) d’un langage L sur A, notée L*, est le
langage obtenu par la réunion de toutes les puissances de L :
i=∞ 0
L* = ꒤ L0 ꒤ L1 ꒤ L2 ꒤ … / L = {}
i=0
i=∞
• Fermeture positive de L notée L+ +
: L = ꒤i=1 Li
 Opérations sur les langages
Exemples:
Soit L = {A,B,...,Z} U {a, b, ... , z} et C = {0 ,1 ,... 9}
A partir de L et C, nous pouvons produire d'autres langages:
✓ L U C : ensemble des lettres et chiffres.
✓ LC : ensemble des chaînes constituées d'une lettre suivie d'un chiffre.
✓ L3 : ensemble des chaînes constituées de 3 lettres.
✓ C+ : ensemble des entiers naturels.
✓ L(LUC)* : ensemble des chaînes constituées d'une lettre suivie
d'une chaîne de lettres et de chiffres ou d'une chaîne vide.
23
 Les Expressions Régulières
• Le modèle des lexèmes d’une unité lexicale peut être décrit de manière
informelle dans le manuel du langage.

Exemple:

Pour le langage C, un identificateur est une suite de lettres, de chiffres et de

caractères de soulignement ( ‘_’ ) qui commence par une lettre ou le caractère
‘_’ et qui ne soit pas un mot-clé du langage.

➔ Description insatisfaisante pour le compilateur.

24
 Les Expressions Régulières
• Pour l’analyse lexicale, la spécification des unités lexicales est décrite en
utilisant une expression régulière (notation algébrique compacte).

➔ Notation simple à comprendre et à utiliser par les programmeurs humains

➔Manipulable d’une manière simple par un programme informatique.

Exemple : l’expression régulière de l’identificateur en c:

(Lettre|’_’ )(lettre|chiffre |’_’)* ∉ (𝑚𝑜𝑡𝑠 𝑐𝑙é𝑠)

25
 Langages et Expressions Régulières
Soit deux expressions r et s et leurs langages L(r) et L(s) sur un
alphabet A quelconque. Nous définissons les expressions suivantes:
•  est une expression régulière qui dénote le langage vide .
•  est une expression régulière qui dénote le langage {} (mot
vide). {} ≠ .
• a est une expression régulière qui dénote le langage {a} (Pour
tout a  l’alphabet A ).
26
 Langages et Expressions Régulières

• r|s est une expression régulière qui dénote la réunion des deux
langages L(r) ou L(s) : L (r|s) = L(r) ꒤ L(s)

• rs est une expression régulière qui dénote la concaténation des

deux langages L(r) et L(s): L(rs) = L(r)L(s)

• r* est une expression régulière qui dénote la fermeture de

Kleene du langage L(r) : L(r)* = (L(r))*

27
 Langages et Expressions Régulières
Les langages dénotés par les expressions régulières sont appelés langages
réguliers.
Exemple :
✓ a|b*c : les chaînes constituées, soit d'un a, ou d'un nombre quelconque,
éventuellement nul, de la lettre b suivie de la lettre c.
✓ a|b = {a,b}
✓ (a|b)(a|b) = {aa,ab,ba,bb}
• Si deux expressions r et s dénotent le même langage ➔ r et s sont
équivalentes(r=s). Par exemple, (a|b) = (b|a)
28
 Langages et Expressions Régulières
• Certains raccourcis sont utiles, par convention, à utiliser.
Exemples:
Chiffres: [0−9] au lieu de 0 | 1 | 2| 3 | 4 | 5 | 6 | 7 | 8 | 9
Lettres (minuscules et majuscules ): [A − Za − z]
+ : est un opérateur unaire qui veut dire un ou plusieurs occurrence.
* : est un opérateur unaire qui veut dire zéro, un ou plusieurs
occurrence.
? : est un opérateur unaire qui veut dire zéro ou une occurrence d’un
symbole. Nous écrivons s? au lieu de (s | ).
29
 Langages et Expressions Régulières
Exemples d’expressions régulières:
• Mots-clés: le mot-clé « while » est décrit par l’expression régulière while .

• Identificateur: consiste en une séquence de lettres, chiffres et le caractère de

soulignement ’_’ et doit commencer par une lettre :

lettre (lettre | chiffre | _ )* = [a − zA − Z ][a − zA − Z 0 − 9_ ]*

• Nombre entier. Un entier commence par un signe ’−/+ ‘ (facultatif), et suivie

d’une séquence non vide de chiffres, :

(−|+)? [Chiffres ]+ = (−|+)? [0 −9]+ ( [0 − 9][0 − 9]* = [0 − 9]+ )

30
 Langages et Expressions Régulières
Définitions régulières:
Notations (suite de règles) utilisées pour définir des expressions régulières en
utilisant des noms comme s’ils étaient des symboles.

d1 → r1 ✓ Chaque di est un nom distinct.

d2 → r2 ✓ Chaque ri est une expression régulière
•
• sur A ꒤ {d1, d2, ..., dn}.
•

dn → rn ✓ A : un alphabet de base.
31
 Les Expressions Régulières
Exemples:
•

32
 Les automates d’états finis
• Les expressions régulières sont un formalisme algébrique pour
spécifier les langages réguliers.
• Les automates finis sont un formalisme graphique pour la
reconnaissance de ces langages et la représentation graphique
des expressions régulières.
Nous distinguons deux catégories :
[Link] AFND (automates finis non-déterministes)
[Link] AFD (automates finis déterministes)
✓ produisent des reconnaisseurs plus rapides que les AFND. 33
 Les automates finis déterministes
• Un AFD permet de vérifier si un mot m appartient à un langage L (m  L ?)
Partons de l’état initial q0 de l’automate. À chaque fois, on lit un caractère de
m, puis on change l’état courant en suivant une transition étiquetée par ce
caractère.
• Deux cas peuvent se présenter :
1. Tous les caractères de m ont été lus .
✓ Si dernier état est final ➔ m  L (Chaine Acceptée)
✓ Sinon ➔ m  L (Erreur).
2. Se bloquer sur un caractère donné.
✓pas de transition avec ce caractère ➔ m  L (Erreur).

34
 Les automates finis déterministes
Un AFD, est un 5-uplet M = (E, A, δ, q0, F) où :
• E : un ensemble fini d’états.
• A : l’alphabet d’entrée.
• δ : fonction de transition définie de E × A vers E.
• q0  E : l’état initial.
• F  E : l’ensemble des états finaux.
35
 Les automates finis déterministes

Représentation d’un AFD :

Un AFD est représenté par un graphe orienté étiqueté.
• Les états : les sommets du graphe (cercles portant des noms).
• Les transitions : les arcs du graphe (flèche reliant deux états).
• Les étiquettes : les caractères de l’alphabet.
• Etat final : deux cercles concentriques.
• Etat initial : marqué par une flèche qui pointe sur son cercle.
36
Les automates finis déterministes

Représentation graphique d’un AFD.

37
 Les automates finis déterministes
Exemple : Automate de reconnaissance des identificateurs

Identificateur : lettre( lettre|chiffre)* = [a-zA-Z][a-zA-Z0-9]*

S0
Lettre|chiffre
lettre
S1 autre
S2 retourne un id
(état d’acceptation avec recul)

Remarque: autre veut dire, autre que lettre et chiffre.

38
 Reconnaissance des unités lexicales
Comment l’analyseur lexical reconnait-il les unités lexicales du
programme à compiler?

✓ Etant donné un mot m, et un langage L, engendré par une Grammaire

G, Un reconnaisseur pour un langage L sur un alphabet A est un
programme qui prend en entrée un mot (chaîne) m ∈ A* et répond :

”oui” si m ∈ L et ”non” si m ∉ L.
39
 Réalisation d’un Analyseur Lexical
03 Approches

Approche manuelle Approche semi

Approche Automatique
Construction à la automatique
Utilisation d’outils:
main en utilisant un Basée sur les
générateurs d’analyseur
langage évolué (java, Automates
lexicaux ( LEX, FLEX…)
c, pascal, …) d’Etats finis

40
 Réalisation d’un Analyseur Lexical
1. Construction à la main

À partir du 1er caractère d’un mot (lexème), on se branche à

un algorithme particulier. Il s’agit d’écrire la fonction
ProchaineUnitéLexicale().

Exemple:

Écrire un analyseur lexical à la main qui reconnait les mots

suivants : L={a, aa, aaa, aaaa,…., an}
41
 Réalisation d’un Analyseur Lexical
Début
Tc 1ercaractère;
Si (Tc = ‘a’) alors // le 1er a
TcTs;
TQ ( Tc=‘a’ ) faire // Pour a* S0
TcTs;
FTQ
Si (Tc= ‘#’) alors // # : marque de fin de la chaine. a
Chaine Acceptée
Sinon a
Erreur S1
finsi
Sinon
Erreur
Finsi;
Fin.
42
 Réalisation d’un Analyseur Lexical
Exemple 2:

Un analyseur lexical qui

reconnait les mots
suivants: L= {𝒂𝒂𝒃,𝒂𝒃}

Fin. 43
 Réalisation d’un Analyseur Lexical

Exercice d’application :

Soit le langage suivant : a*ba*

Ecrire un analyseur lexical à la main pour ce langage.

44
 Réalisation d’un Analyseur Lexical
2. Approche par Automates
Les étapes de réalisation de l’analyseur lexical qui utilise un automate sont comme suit:

• Représentation de l’automate : on représente l’automate par une matrice de

transition.
✓ les lignes représentent les états de l’automate,
✓ les colonnes représentent l’alphabet,
✓ un élément de la matrice correspond à une transition.
✓ Les cases vides sont remplies par -1 représentant une erreur
• Représentation des états finaux : la représentation des états finaux se fait dans un
vecteur associer à la matrice.
45
 Réalisation d’un Analyseur Lexical
Exemple 1: soit le langage suivant : 𝐿1={𝑎+𝑏}
L’automate correspond au langage 𝐿1 est comme suit :
Remarque : L’automate doit être simple et déterministe.

S0
Table (matrice) de transition
a b a a

S0 S1 -1 S1 S2
S1 S1 S2 b
Etat initial : S0
S2 -1 -1 Vecteur des états finaux 𝑽𝒇={𝑺𝟐}
46
 Réalisation d’un Analyseur Lexical
Algorithme d’analyse
𝒕𝒄∶ 𝒕𝒆𝒓𝒎𝒆 𝒄𝒐𝒖𝒓𝒂𝒏𝒕; S0
a
𝒕𝒔∶ 𝒕𝒆𝒓𝒎𝒆 𝒔𝒖𝒊𝒗𝒂𝒏𝒕; a
𝑬𝒄∶ 𝑬𝒕𝒂𝒕 𝒄𝒐𝒖𝒓𝒂𝒏𝒕;
𝑴∶ 𝒎𝒂𝒕𝒓𝒊𝒄𝒆 𝒅𝒆 𝒕𝒓𝒂𝒏𝒔𝒊𝒕𝒊𝒐𝒏; S1 b S2
𝑽∶ 𝒗𝒆𝒄𝒕𝒆𝒖𝒓 𝒅𝒆𝒔 é𝒕𝒂𝒕𝒔 𝒇𝒊𝒏𝒂𝒖𝒙;
𝒅𝒆𝒃𝒖𝒕 M: matrice de transition
𝒕𝒄←𝟏𝒆𝒓𝒄𝒂𝒓𝒂𝒄𝒕è𝒓𝒆;
𝑬𝒄←𝑳′é𝒕𝒂𝒕 𝒊𝒏𝒊𝒕𝒊𝒂𝒍; a b
𝑻𝒂𝒏𝒕𝒒𝒖𝒆(𝒕𝒄≠ ′#′ 𝒆𝒕 𝑴[𝑬𝒄,𝒕𝒄]≠ −𝟏) 𝒇𝒂𝒊𝒓𝒆
𝑬𝒄←𝑴[𝑬𝒄,𝑻𝒄]; 𝒕𝒄←𝒕𝒔; S0 S1 -1
𝑭𝒊𝒏𝒕𝒂𝒏𝒕𝒒𝒖𝒆
𝑺𝒊 (𝒕𝒄=′#′ 𝒆𝒕 𝑬𝒄 ∈ 𝑽) 𝒂𝒍𝒐𝒓𝒔 𝑪𝒉𝒂𝒊𝒏𝒆 𝒂𝒄𝒄𝒆𝒑𝒕é𝒆
S1 S1 S2
𝒔𝒊𝒏𝒐𝒏 𝒆𝒓𝒓𝒆𝒖𝒓 S2 -1 -1
𝑭𝒊𝒏𝒔𝒊.
fin Vecteur des états finaux 𝑽={𝑺𝟐}
47
 Réalisation d’un Analyseur Lexical

Exercice d’application:

Ecrire un analyseur lexical par automate pour

reconnaitre les entiers, les réels, les opérateurs
relationnels, et les identificateurs.

48
 Réalisation d’un Analyseur Lexical
3 . Approche Automatique
Utilise un outil informatique pour générer automatiquement le
code exécutable de l’analyseur à partir d’une description
(expressions régulières) .

Exemple: l’utilitaire LEX génère automatiquement un analyseur

lexical écrit en langage C. Il accepte en entrée des spécifications
d’unités lexicales sous forme d’expressions régulières et produit en
sortie un programme (l’analyseur lexical) une fois compilé
reconnait ces unités lexicales.
49
 Plan du cours
I. Introduction à la compilation
• Les différents étapes de la compilation
• Compilation, interprétation, traduction
II. Analyse lexicale
• Principe et rôle d'un analyseur lexical
• Terminologies
• Rappel sur les expressions régulières, Langages, Grammaires et automates
• Méthodes d’analyse lexicale : à la main et par automates
III. Analyse syntaxique
• Récursivité à gauche et factorisation d’une grammaire.
• Méthodes d’analyse descendante et ascendante.
50