 Carte conceptuelle du cours

Faculté des Sciences d'Agadir Compilation

Compilation
Par Mustapha Machkour
SMI5/LPII
semestre 5
Automne 2023
Pr Mustapha Machkour

FS Agadir SMI5-LPII

Sommaire Objectifs
 Définition et concepts généraux
 Comprendre les concepts et les notions de l'analyse lexicale 1 :  Les langages de programmation
Expressions régulières  Définition d’un traducteur
 Comprendre les concepts et les notions de l'analyse lexicale 2 : Les  Schéma simple d'un traducteur
automates Chapitre 1  Structure de principe d'un compilateur
 Analyse lexicale : Transformation de l'expression régulière en automate
 Comprendre les concepts et les notions de l'analyse lexicale 4 : Définitions et concepts généraux  Analyse lexicale : lexèmes
Transformation AFND AFD  Analyse syntaxique
 Analyse syntaxique 1  Analyse sémantique
 Grammaire et dérivations  Contexte d’un compilateur : pré -processeurs, assembleur,
 Arbre syntaxique et approches d'analyse éditeur de liens
 Analyse prédictive et Grammaire LL  Compilateur croisé
 Analyse Ascendante

4 6

 Les raisons d'être du cours  Processus simplifié de traduction  Objectifs d'un traducteur
– Architecture des ordinateurs (structure de processeur) & programmation Début de l'informatique
assembleur Programmation par langage machine
– Programmation avec des langages de haut niveau (VB, C) 
Manipulation de code numérique binaire ou hexadécimal
– Lien entre les deux ?

 Un langage de programmation sert à créer des programmes destinés au
Programmation très difficile, fastidieuse et présente beaucoup
processeur
d'inconvénients.
 Processeur ne comprend que le binaire
Besoin de traducteurs

7 8 9

1
 Inconvénients de la programmation machine  Programmation assembleur  Programme assembleur
Représentation du code numérique par des symboles mnémonique plus expressifs. Programme qui traduit des instructions écrites en langage
- Forte exposée aux erreurs
mov,add… d'assemblage en code machine.
- Difficulté à détecter les erreurs Mais, la machine ne comprend que le langage machine.
- Difficulté de comprendre le programme  Naissance de traducteur : programme assembleur.
- Maintenance de programme très difficile
- Nbre de programmeurs très limité
- Manque de structures de contrôle et structures de données
- Manque de portabilité

10 11 12

FS Agadir SMI5-LPII

 Limite de la programmation assembleur  Classification des langages évolués  Langages de haut niveau ou langages évolués
- Non portable Cette classification est due à la manière d’écrire des programmes dans Ce type de langages présentent beaucoup d'avantages
ces langages. - Portabilité
- Absence de structures de contrôles
- Langages procéduraux
- Manque de structures de données - Utilisation des mots proches du langage humain
- Langages à base objets
- Utilisation des structures de contrôle et structures de données
- etc. - Langages orientés objets
- Facile à apprendre
 Naissance des langages de haut niveau ou langage évolué - Langages orientés objets pilotés par les événements
- Langages de programmation déclarative
- Présente un aspect modulaire (moins de couplage entre les
modules)
- Langages de programmation fonctionnelle
- Maintenance facile

13 14 15

 Naissance de traducteurs
 Définition d’un traducteur  Schéma simple d'un traducteur
Programme écrit en LHN ne peut être exécuté
par un processeur. Un traducteur est un programme qui
 Nécessité de traducteurs= compilateurs prend en entrée un programme écrit dans un langage A (dit
langage source : S)
et le traduit en un autre programme écrit dans un autre
langage B (dit langage cible C).
PcB doit être équivalent à PsA

16 17 18

2
 Remarque  Langages source  Langages cible
- Langage source d'un traducteur est un langage de Langage cible : langage de programmation qlq,
- Au cours de cette traduction, le traducteur doit détecter les programmation évolué ou langage intermédiaire :
erreurs dans le programme source. - pascal, C,
- Assembleur
- Le traducteur doit conserver le sens (la sémantique) du - Assembleur - Langage binaire…
programme source. - Arbre

19 20 21

FS Agadir SMI5-LPII

 Langage de traducteur  Notation  Une autre notation

Un traducteur peut être implémenté dans n'importe quel
langage de programmation: langage d'implémentation du Langage du programme source Ps |TSLC = Pc
traducteur,
TSLC Langage du programme cible

Langage du traducteur

22 23 24

 Langage du traducteur (réalisation d'un traducteur)  Exercice

 Exemples
Écrire la formule qui représente la traduction d'un programme source
- TCPascalMachine en assembleur en programme cible en langage machine avec un
- TAssMachineMachine traducteur écrit en langage assembleur.

25 26 27

3
  Exercice 2
 Réponse  Réponse
On suppose qu'on dispose d'un traducteur de la forme
PAss | TAssAssMachine TPascalCMachine|TCMachineMachine= TPascalMachineMachine
TCMachineMachine
et on veut écrire un traducteur en langage machine pour
convertir un programme pascal en programme machine.
Expliquer comment peut-on faire pour réaliser ce traducteur
(quel est le traducteur à combiner avec celui en haut pour
obtenir TPascal Machine Machine )

28 29 30

FS Agadir SMI5-LPII

 Règle générale  Définition d'un compilateur  Contexte d'un compilateur

TSL1C1 | TL1L2C2= TSC2C1 - pré processeurs permettent
Compilateur = Traducteur d'un programme source en + les macro définitions "define"
langage machine.
PB =Ps| TSLB + Inclusion des fichiers d'entête
#include<stdio.h>

+ Extensions de langages (accès aux bases de données)

31 32 33

 Structure d'un compilateur

 Contexte d'un compilateur(suite)  Contexte d'un compilateur(suite)
- Assembleurs - Chargeur et éditeur de lien
Traduction du code assembleur en code machine. + charger le programme en mémoire à partir du fichier.
+ faire le lien entre les fichiers représentant le programme
(traduction séparée)(linkage ou édition de lien).

34 35 36

4
 Analyse lexicale  Exemple  Exercice
Extraire les mots du texte du programme à partir d'une suite pour le texte Quels sont les lexèmes pour le texte suivant :
de caractères.
a=b+1 while (i>=1)
Ces mots sont dits lexèmes (instances d’unités lexicales).
on a les lexèmes suivants
a, = , b, + , 1.

37 38 39

FS Agadir SMI5-LPII

 Exemple
 Chercher les lexèmes (instances d'unités lexicales) dans  Analyse syntaxique Considérons la définition d'expression suivante (grammaire):
for i= 1 to n Dans cette analyse, le traducteur regroupe les unités lexicales obtenues - Tout nombre est une expression,
de l'analyse lexicale et vérifie si elles représentent des expressions
j=j+i syntaxiquement correctes ou non (construit un arbre syntaxique
- Tout identificateur est une expression,
next i d’analyse ou arbre d’analyse). - Si a et b sont des expressions alors
a + b est une expression,
- Si a et b sont des expressions alors
a * b est une expression.

40 41 42

 Exemple(suite)  Exemple(suite)  Exercices

Montrer que a+1 est une expression. Réponse (arbre d’analyse) - Donner l'arbre syntaxique des expressions suivantes:
(utilisation d’arbre d’analyse). a+b+1 et a*b+1,
- L'expression a*b+
a-t-elle un arbre syntaxique?

43 44 45

5
  Analyse sémantique  Exemple  Génération de code intermédiaire
Dans cette phase d'analyse le traducteur vérifie par exemple le int a,b=2,c=1; - Arbre abstrait (une représentation hiérarchique d’une expression)
type de données des variables mises en jeu dans une a=b+c; - Code à trois adresses
opération.

46 47 48

FS Agadir SMI5-LPII

 Exemple de code à trois adresses  Exercices donner le code à trois adresses de  Exemple d’arbre abstrait
La formule La formule
a=b+3*c+1;
a=b*3+c; a+3
devient d=h*2+d*3
possède l’arbre abstrait
x=b*3;
a=x+c;

49 50 51

 Donner l’arbre abstrait de  Optimisation de code  Optimisation de code (suite)

Le code suivant
- b+3*c+1; Code initial Pour i = 1 à 100 faire
- d=h*2+d*3 a=1; som=som+a*b+c+i;
Fin pour
b=2+a; Peut devenir
c=b+3; temp=a*b+c;
Pour i = 1 à 100 faire
d=c; som=som+temp+i;
Fin pour
Optimisation 
b=2+1;
d=b+3;

52 53 54

6
 Génération de code  Interpréteur  Exemples
Code écrit en langage d'assemblage. Traducteur qui ne génère pas de code machine ( programme - php
exe).
add, move… - javascript
add r1, r2, r3
mul r4, r1, r2

55 56 57

FS Agadir SMI5-LPII

 Compilateur croisé cross-compiler

Résumé
Traducteur qui s'exécute sur une machine A et
produit un code pour une machine B.  Les langages de programmation
TSAB  Définition d’un traducteur
 Schéma simple d'un traducteur Chapitre 2
Comprendre les concepts et les notions de l'analyse
 Structure de principe d'un compilateur
lexicale 1
 Contexte d'un compilateur Expressions régulières

58 59

Objectifs  Objet de l'analyse lexicale  Analyse lexicale en deux phase

 Objectifs de l’analyse lexicale - Première phase du compilateur(fait partie du front-end) Phase de Lecture + phase d'analyse lexicale proprement dite
 Analyse préliminaire - Lecture du texte caractère par caractère d'un programme
 Alphabet et langage source
 Opérations sur les langages - Regrouper les caractères pour en former des unités lexicales
 Les unités lexicales, lexèmes et modèles - Présenter les unités lexicales trouvées à l'analyseur
 Les expressions régulières syntaxique
 Opérations des expressions régulières

61 62 63

7
 Phase de lecture  Phase d'analyse lexicale  Schéma analyseur lexical
Extraction des caractères + suppression des blancs, fin de Reconnaissance des mots ou des lexèmes en utilisant
ligne, des tabulations , des commentaires = phase des modèles ou des spécifications
préliminaire

64 65 66

FS Agadir SMI5-LPII

 Analyse lexicale = phase séparée  Notion d'alphabet  Exemples d'alphabet

Pourquoi? Alphabet =Ensemble fini et non vide de A={a,b,c,d,1,2}
symboles. A={ab,c,d}
- Simplicité de la conception
On le note par A. A={0,1}
Séparation des tâches(an. lexical et an.
Un symbole peut être composé d'un ou de
syntaxique) plusieurs caractères.
- Portabilité du compilateur
- Efficacité (tâche mécanique)
- Existence des outils générateurs

67 68 69

 Notion de chaîne  Exemple  Chaîne vide

Une chaîne est suite finie de symboles de l'alphabet A. pour l'alphabet Est une chaîne composé de 0 symbole
A={a,b,c,d,1,2}, Notation
Nous avons les chaînes : ε = chaîne vide
ab, ac, bc1

70 71 72

8
 Longueur de chaîne  Exemple  Exercice
Longueur de chaîne = Le nombre d'occurrences Alphabet : A={a,c,d}
de symboles de l'alphabet dans la chaîne. Chercher la longueur des chaînes suivantes:
Chaîne : S=acda
- Notation - A={a,b,c,d,1,2} , S=ab
|S|=4
|ch| donne la longueur de ch. - A={ab,c,k,d}, S=abckd

73 74 75

FS Agadir SMI5-LPII

 Concaténation des chaînes  Exemple 1

Si X et Y sont deux chaînes alors si X=ab, Y=df alors
XY est une chaîne composée des symboles de X suivis des XY=abdf.
symboles de Y.

Opérations sur la chaînes

76 77 78

 Exercice  Exponentiation des chaînes  Notion de langage

Quelle est la valeur de XY dans les cas suivants : Soit S une chaîne. un langage = sous-ensemble de l'ensemble des chaînes
- X=ab et Y=ε par définition formées par un alphabet.
- X=ε et Y=ab S0=ε Notation
S1=S L
Sn=SSSSS…S n fois

79 80 81

9
 Exemples  Exercice  Exercice
Alphabet : A={0,1} A={0,1} A={0,1,2…9}
L={0,1,11,10} L=langage? L=langage?

82 83 84

FS Agadir SMI5-LPII

 Concaténation des langages  Exemple  Exponentiation des langages

Soit L1 et L2 deux langages alors Nous donnons L1={a,b} et L2={c} Soit L un langage.
La concaténation de L1 et L2 notée Chercher L1L2. par définition
L1L2 ou L1*L2 est donnée par L0={ε}
L1L2={XY avec X chaîne de L1 et Y chaîne de L2} L1=L
Ln=LLLL…L n fois

85 86 87

 Exemple  Exercice  Exercice

L={a,b} Soit L={a} Chercher
L2=LL={aa,ab,ba,bb} Chercher L1, L2 et L3 - L{ε}
- {ε}L

88 89 90

10
 Union des langages  Exemple  Fermeture d'un langage
Soit L1 et L2 deux langages alors Nous donnons L1={a,b} et L2={a,c} Soit L un langage, la fermeture de L est donnée par
l'union de L1 et L2 notée Chercher L1 U L2. L*= U Li avec i=0,1…
L1 U L2 est donnée par
L1 U L2={X/ X de L1 ou X de L2}

91 92 93

FS Agadir SMI5-LPII

 Exemple  Réponse  Exercice

Chercher L* sachant que L={a} L*=L0u L u L2 u L3…={ε,a, aa, aaa…} Chercher L* sachant que L={a, b}

94 95 96

 Fermeture positive d'un langage  Réponse  Remarque

Soit L un langage, la fermeture positive de L est donnée par L+=L u L2 u L3…={a, aa, aaa…} L+=L* \{ε}
L+= U Li avec i=1…
Exemple
Chercher L+ sachant que L={a}

97 98 99

11
 Exercices  Exercice  Réponse
- Chercher L+ sachant que L={ab} Soit A et L des langages / ID={id/ id de LA*}
- Chercher L+ sachant que L={a,b} A={lettres, chiffres} et L={lettres}
Donner l'expression du langage ID représentant les
identificateurs.

100 101 102

FS Agadir SMI5-LPII

 Exercices  Exercice  Exercice

Soit L={lettres} et C={chiffres} Soit L1={0} et L2={1} Soit L={0,1}
Définir les langages suivants : Définir le langage binaire à partir de L1 et L2. Définir le langage binaire à partir de L.
- L U C.
- LC.
- L2
- L*
- (L U C)*
- L(L U C)*

103 104 105

 Unité lexicale  Unités lexicales et lexèmes

 Lexèmes
Définition - Les lexèmes sont des valeurs ou instances des unités lexicales.
Considérons l'instruction suivante
Unité lexicale = mot défini dans le langage correspondant au mot ou symbole - Une unité lexicale est une classe de lexèmes
int c=1;
rencontré dans le programme. Exemples
Définition
Exemples d'unités lexicale - {12, 13} sont des lexèmes de NB.
lexème= mot ou symbole du programme : variable, constante, nom de fonction, ID,
opérateurs de comparaison, opérateurs d'affectation… - {x, x1, X_3} sont des lexèmes de ID.
NB, - {<, <=, == } sont des lexèmes OPER.
Exemples
OPER
int,
=,
c et 1;

106 107 108

12
  Expressions régulières E.R.(description des mots du langage)  Expressions régulières E.R.(description des mots du langage)
Définition
 Exercice Objectifs Soit A un alphabet, une expression régulière est donnée par :
Chercher les lexèmes et les unités lexicales dans  Une E.R. est une notation utilisée pour spécifier ou décrire un - ε est une E.R. qui désigne le langage {ε}
langage.
le programme suivant : - si a est un élément de A alors a est une E.R. qui désigne {a}
 Une E.R. est donnée à base d'un alphabet. - si X est une E.R. qui désigne L alors (X)* est une E.R. qui désigne L*
int max(int i,int j)  Une E.R. décrit les unités lexicales d'un langage. - si X est une E.R. qui désigne L alors (X)+ est une E.R. qui désigne L+
{ - si X et Y sont des E.R. qui désignent Lx et Ly alors (X)|(Y) désigne Lx u Ly.
- si X et Y sont des E.R. qui désignent Lx et Ly alors (X)(Y) désigne LxLy
return i>j?i:j;
}

109 110 111

FS Agadir SMI5-LPII

 Exemples  Chercher les langages désignés par chacune des E.R. suivantes :  Réponses
Soit A={a,b} un alphabet - a* - a*  L={ε, a, aa, aaa, …}
- a(a)* - a(a)*  L={a, aa, aaa, …}
- (a|b)*
- a|b - a|b  L={a, b}
- (a*|b*)*
- a|ba* - a|ba*  L={a, b, ba, baa, …}
- (a)|((b)*(c))=a|b*c - (aa)*a - (aa)*a  L={a, aaa, aaaaa, …}

112 113 114

 Définition régulière  Exemple : cas du langage C

 Définition régulière : pourquoi?
Le nom affecté à une expression régulière. - Lettre  a|b|…|z|A|B…|Z
Réutiliser et simplifier les expressions régulières.
Exemples - Chiffre  0|1…|9
- Lettre  a|b|…|z|A|B…|Z - Id Lettre(Lettre|Chiffre)*
- Chiffre  0|1…|9

115 116 117

13
 Opérations sur les E.R.  Écrire une expression régulière qui décrit les  Réponses
Soit X, Y, Z des E. R. alors on a les propriétés lexèmes suivants, nous prenons A={a,b}: 1) b(a|b)*
algébriques suivantes: : 1) les mots qui commencent par b. 2) (b|a)*a
- X|Y=Y|X 3) (b|a)a+
2) les mots qui se terminent par a.
- X|(Y|Z)=(X|Y)|Z 4) (b|a)*b(aa)+
- X(YZ)=(XY)Z 3) les mots qui se terminent par un nombre qlq de a. 5) b*ab*ab*
- X(Y|Z)=XY|XZ 4) les mots qui se terminent par un nombre pair de a. 6) (a|b)*a(a|b)*a (a|b)*
- (X|Y)Z=XZ|YZ 5) les mots contenant exactement 2a.
- Xε= εX=X 6) les mots contenant au moins 2a.

118 119 120

FS Agadir SMI5-LPII

 Remarque  Remarque (utilisation des définitions)  Exercice

On peut utiliser les définitions régulière dans les Pour la question 6, on a aussi la réponse Écrire une expression régulière qui décrit les
réponses aux questions 5 et 6.
(b|a)*a(b|a)*a|a (b|a)* a (b|a)* nombres binaires.
Pour la question 5, on a aussi la réponse suivante
b*ab*a|ab*ab* on peut aussi écrire
On peut aussi écrire E1 (b|a)*a(b|a)*a
E1b*ab*a E2a (b|a)* a (b|a)*
E2ab*ab* EE1|E2
EE1|E2

121 122 123

 Réponse  Extensions des expressions régulières  Exercice

(0|1)+ - r?=r|ε 1) Donner l'expression régulière qui représente les
- a|x|w=[axw] chiffres.
- a|b|c|…|z=[a-z] 2) Donner l'expression régulière qui représente les lettres
A…Z.
3) Donner l'expression régulière qui représente les lettres.

124 125 126

14
  Exercices
 Réponse  Remarques
1) Chercher l'expression régulière étendue pour les
1) [0-9] Dans l'écriture des expressions régulières, on doit
identificateurs.
2) [A-Z]
2) Chercher l'expression régulière étendue pour les prendre en considération la priorité et
3) [a-zA-Z] nombres entiers. l'associativité (à droite) des opérateurs
- *, +
- ?
- |

127 128 129

FS Agadir SMI5-LPII

 Exemple  Exercice  Réponse

L'expression (a)(b)*|(cd) peut s'écrire Simplifier les expressions suivantes: Simplifier les expressions suivantes:
ab*|cd 1) b(c)*a 1) bc*a
2) ((a|b)|c)|(d)+c 2) (a|b|c)|d+c=[a-c]|d+c

130 131 132

Objectifs
Résumé
 Objectifs de l’analyse lexicale  Automate
 Analyse préliminaire  Automate fini déterministe
Chapitre 3
 Alphabet et langage  Implémentation d'un automate
Comprendre les concepts et les notions de l'analyse
 Opérations sur les langages lexicale 2
 Les unités lexicales, lexèmes et modèles Les automates
 Les expressions régulières
 Opérations des expressions régulières

133 135

15
  Liens automate/E.R./langage
 Exemple Nous considérons le schéma suivant
 Les automates finis A.F.
Soit L un langage défini par une E.R. Langage des identificateurs est défini par la
Soit x une chaîne. définition régulière ID donnée par
Est ce que x appartient à L? ID  Lettre(Lettre|Chiffre)+
Est ce que les chaînes suivantes font partie du
 Moyen pour reconnaître les chaînes de L?
lexique de ID?
 Automates finis =A.F.
- surface
- x1
- 1y

136 137 138

FS Agadir SMI5-LPII

 Automate fini : AF
AF = 5-uplets (E, A, T, I, F), avec  Exemple
 Représentation graphique d’un automate

- E=ensemble fini d'éléments appelés des états; - E={e1, e2, e3} =ensemble composé de 3 états État initial : 3 façons

- A=ensemble de symboles qui forment les mots ou les - A={a1, a2} =alphabet avec 2 symboles
chaînes=Alphabet; - I={e1} est l'état initial Nom état initial

- T=fonction de transitions qui associe à chaque paire de E x A - La fonction de transitions est définie par
un élément de E T(e1, a1)= {e2} 0
T: E x A  E T(e1,a2)={e3}
- I=état initial appartenant à E (début de l'automate);
- F={e2,e3} ensembles des états terminaux. i
- F=ensemble non vide des états terminaux ou finaux
(terminaison de l'automate).

139 140 141

 Représentation graphique d’un automate

 Représentation graphique d’un automate  Représentation graphique d’un automate
État final

État intermédiaire Transition

Nom état final symbole

Nom intermédiaire

142 143 144

16
  Remarque
 Exemple de représentation graphique  Donner la représentation graphique de l'automate
l'automate suivant : suivant :
-E={e1, e2, e3} =ensemble composé de 3 états
-A={a1, a2} =alphabet avec 2 symboles -E={e1, e2, e3} =ensemble composé de 3 états
-I={e1} est l'état initial -A={a, b} =alphabet avec 2 symboles
-I={e1} est l'état initial
-La fonction de transitions est définie par -La fonction de transitions est définie par
T(e1,a1)= {e2} T(e1, a) = {e2}
T(e1,a2)={e3} T(e1,b) = {e3}
-F={e2,e3} ensembles des états terminaux T(e2,b) = {e3}
Représentation graphique permet de reconnaître les chaînes a1 et a2. -F={e2,e3} ensembles des états terminaux.
 Quelles sont les chaînes reconnues par cet
automate?

145 146 147

FS Agadir SMI5-LPII

 Donner la représentation graphique de l'automate suivant :  Donner la représentation graphique de l'automate suivant :

 Donner la représentation graphique de l'automate -E={e1, e2, e3} =ensemble composé de 3 états -E={e1, e2, e3} =ensemble composé de 3 états
suivant : -A={a, b} =alphabet avec 2 symboles -A={a, b} =alphabet avec 2 symboles
-I={e1} est l'état initial -I={e1} est l'état initial
-E={e1, e2, e3} =ensemble composé de 3 états -La fonction de transitions est définie par -La fonction de transitions est définie par
-A={a, b} =alphabet avec 2 symboles T(e1, a) = {e2} T(e1, a) = {e2}
T(e1,b) = {e3} T(e1,b) = {e3}
-I={e1} est l'état initial T(e2,b) = {e3}
-La fonction de transitions est définie par
T(e1, a) = {e2}

148 149 150

 Donner la représentation graphique de l'automate suivant :  Donner la représentation graphique de l'automate suivant :  Donner la représentation graphique de l'automate suivant :

-E={1, 2, 3} =ensemble composé de 3 états -E={1, 2, 3} =ensemble composé de 3 états -E={1, 2, 3} =ensemble composé de 3 états
-A={a, b} =alphabet avec 2 symboles -A={a, b} =alphabet avec 2 symboles -A={a, b} =alphabet avec 2 symboles
-I={1} est l'état initial -I={1} est l'état initial -I={1} est l'état initial
-La fonction de transitions est définie par -La fonction de transitions est définie par -La fonction de transitions est définie par
T(1, a) = {2} T(1, a) = {2} T(1, a) = {2}
T(1,b) = {3} T(2,b) = {3} T(2,b) = {3}
T(3,b) = {3} T(3,b) = {3} T(3,a) = {2}
-F={2,3} états terminaux. -F={3} état terminal. -F={3} état terminal.
 Quelles sont les chaînes reconnues par cet automate?  Quelles sont les chaînes reconnues par cet automate?  Quelles sont les chaînes reconnues par cet automate?

151 152 153

17
  Donner la représentation graphique de l'automate suivant :

-E={1, 2, 3} =ensemble composé de 3 états

 Exercice  Réponse
-A={a, b} =alphabet avec 2 symboles Proposer un automate pour ((a|b)*cb)
-I={1} est l'état initial
-La fonction de transitions est définie par b
T(1, a) = {2} c 1 b
T(1,a) = {3}
T(3,b) = {3} 0 2
-F={2,3} états terminaux.
a
 Quelles sont les chaînes reconnues par cet automate?

154 155 156

FS Agadir SMI5-LPII

 Cas d'un identificateur  Cas d'un identificateur  Exercice

Lettre|chiffre Lettre|chiffre Proposer un automate pour le cas d'un entier.
lettre 1 lettre 1
0 0

blanc

157 158 159

buffer=&Buffer[0];
while(1) {
 Cas d'un entier c = lireChar();
switch(etat){
 Implémentation d'un A.F. case: 0
switch(type(c)){
chiffre - Programme buffer*=c;buffer++;
case ALPHA: etat=1;break;
- Matrice de transitions case NUMER: etat=2;break;
case OPARITH-{/}: etat=3; break;
chiffre 1 case '<': etat=4; break;
case '>': etat=6; break;
0 case '=': etat=8; break;
case ':': etat=9; break;
blanc case ';': etat=11; break;
case '/': etat=12; break;
default: erreur;
}
break;
case 1:
if (type(c) == ALPHA ou type(c) == NUMER) {
buffer*=c;buffer++;
etat=1;
}
else {
buffer*='\0'; remettreCar();
return(ajouter_token(Buffer,TYPE_IDENT));
}
break;
160 161 162

18
 break;  Automate avec un programme
case 2:
if (type(c) == NUMER){  Cas d'une matrice de transitions buffer=&Buffer[0];
buffer*=c;buffer++; while(1) {
etat=2; a e2 c = lireChar();
} switch(etat){
e1
else { case: 0
b e3
buffer*='\0';remettreCar(); switch(c){
return(ajouter_token(Buffer,TYPE_NUMER));
} case 'a': etat=1;break;
break; case 'b': etat=2;break;
case 3: états a b default: erreur;
return(ajouter_token(Buffer,TYPE_OPER)); break; }
case 4:
if (c == '=') {
e1 e2 e3 break;
case 1:
buffer*=c;buffer++;
etat = 5; e2 return(ajouter_token("a"));
} else {
remettreCar(); case 2:
return(est-dans("<")); e3 return(ajouter_token("b"));
} …
…
163 164 165

FS Agadir SMI5-LPII

Résumé
Objectifs
 Automate
 Automate fini déterministe
 Automate fini déterministe
 Automate fini non déterministe
 Implémentation d'un automate Chapitre 4
 Transformation d'une expression
Transformation de l'expression régulière en
régulière en automate fini non
automate
déterministe

166 167 168

 Automate fini déterministe : AFD

 Définition de ε-transition Un automate fini est dit déterministe s'il ne  Contre-exemple (AFND)
ε-transition est une transition par le symbole ε contient pas de
entre deux états. ε-transition b
et 1 b
a
si pour chaque couple 0 2

(état , symbole) il y a au plus une a

transition étiqueté symbole partant de

état.

169 170 171

19
  Exercice
 Contre-exemple (AFND)  Exemple ((a|b)*cb) Chercher un automate pour
b (a|b)*abb
c 1 b
b
0 2
a 1 b
0 2 a

172 173 174

FS Agadir SMI5-LPII

 Algorithme de passage d'une ER en AFND  Algorithme de passage d'une ER en AFND

Algorithme Algorithme
 Passage des E.R aux automates finis Entrées : une ER r sur un alphabet A
Comment? Sortie : un AFND N qui reconnaît L(r).
On considère le schéma Début Construire pour chaque a de A
Construire un AFND pour ε. soit

175 176 177

 Algorithme de passage d'une ER en AFND

Algorithme
Construire pour l'expression XY l'automate défini par - construire pour l'expression X* l'automate défini par
ε

N(Y) N(X) f
N(X) f i ε ε
i
Construire pour l'expression X|Y l'automate défini par ε

fin algo.
ε N(X) ε
i f
ε N(Y) ε

178 179 180

20
 ou bien pour X*
ε
 Exercices  Exercices
- Construire un AFND correspondant à l'ER - Construire un automate fini pour le langage
i ε N(X) f X=abb. binaire.
fin algo. ε - Construire AFND pour l'ER a|b. - Chercher un automate qui décrit l'E.R. (ab|ba)*
- Chercher l’AFND de a+ - Chercher un automate qui décrit l'E.R. (ab|ba)+
- Construire AFND pour l'ER Y=(a|b)*. - Chercher un automate pour les nombres
- Construire AFND pour l'ER Z=XY. binaires où chaque 1 est suivi directement de 0;

181 182 183

FS Agadir SMI5-LPII

Résumé
 Travail à faire
 Automate fini déterministe
Suite du micro compilateur de C:  Automate fini non déterministe
Reconnaissance des id , des constantes  Transformation d'une expression régulière en automate Chapitre 5
numériques (commencer par les constantes fini non déterministe
entières) et des opérateurs. Comprendre les concepts et les notions de l'analyse
lexicale 4
Transformation AFND AFD

184 185

 Rappel
Objectifs
 Transformation d'automate non déterministe en automate  AFD & AFND
déterministe Comment peut-on passer d’un AFND à un AFD?
 Générateur d’analyseur lexical Notion de ε-fermeture
Soit x0 un état
ε-fermeture(x0) est l'ensemble des états que l'on peut atteindre à
partir de x0 en utilisant des transitions ε.
x0 peut être composé de plusieurs états.

187 188 189

21
 Exemple 1  Exemple 1(réponse)  Exemple 2
b b b

ε 1 b ε 1 b ε 1 b
0 2 0 2 0 2
ε
a a a

ε-fermeture(0)? ε-fermeture(0) ={0,1} ε-fermeture(0) ?

190 191 192

FS Agadir SMI5-LPII

 AFD & AFND

algorithme AFND_to_AFD
entrée X AFND
 Exercice sortie Y AFD
début
 Exemple 2(réponse) Chercher ε-fermeture(0) soit x0 l'état initial de l’ AFND X alors
y0=ε-fermeture(x0); // y0 est l’état initial de l’AFD Y.
b ε Soit Q les états de Y et A l'alphabet de Y ;
Q={y0}; // formation des états
ε 1 b Tant qu’il y a un état S non marqués dans Q faire
b 2 3
0 ε 1 b Marquer S
0 2
pour tout a de A faire
ε
ε T={ens d'états cibles de transitions à partir d'un état si de S}
a
Y=ε-fermeture(T);
SI Y est non dans Q alors ajouter Y non marqué
ajouter une transition a de S à Y.
fin pour
ε-fermeture(0) ={0,1,2} Fin tant que
Un état de Y est un terminal s'il contient au moins un état final de X.
fin.

193 194 195

Résumé
 Exemple  Transformation d'automate non déterministe en automate
Transformer l'AFND en AFD  Réponse déterministe
ε 2 a S2 b
 Générateur d’analyseur lexical
1 5 S1 a S3
a b a b
a

a a
3 4 S4
b

196 197 198

22
 Objectifs  Définition de la syntaxe(rappel)
 Analyse syntaxique L'analyse syntaxique (parsing) est une tâche fondamentale d'un
 Grammaire non contextuelle compilateur, ses objectifs incluent:
 Terminaux - Réception des mots (lexèmes) fournis par l’analyseur lexical
 Non Terminaux - Rassemblement de ces mots en phrases (instructions) ;
Chapitre 6  Productions - Vérification de la syntaxe de ces phrases ;
Analyse syntaxique 1  Axiome - Construction des représentations de ces phrases (paires d'unités lexicales
et lexèmes) correctes en termes d'arbres syntaxiques ou arbres d'analyse.

200 201

FS Agadir SMI5-LPII

 Syntaxe et analyseur syntaxique  Schéma simplifié d’un analyseur syntaxique  Remarque

Pour vérifier la syntaxe d'une phrase on utilise un analyseur L’arbre syntaxique s'appelle aussi arbre de dérivation.
syntaxique = parser.

202 203 204

 Différence arbres syntaxique et abstrait  Analyseur syntaxique et grammaire

 Remarque
Pour construire un analyseur syntaxique (parser) d'un langage, on doit
L’arbre syntaxique n’est pas l’arbre abstrait  Arbre de syntaxique  Arbre abstrait décrire la syntaxe de ce langage de manière précise.
 Utilisation d'une grammaire
expression
+

+ a 1
expression expression

ID INT

a 1

205 206 207

23
 Objectifs d'une grammaire  Pourquoi une grammaire? (1/3)  Pourquoi une grammaire?(2/3)
Une grammaire est un ensemble de règles pour décrire la manière de (1) Spécification
former des phrases (instructions) et des programmes dans un langage.
(1) Spécification

et
- Spécification précise de la syntaxe du langage de programmation

(2) Reconnaissance
- Spécification compréhensible et claire de la syntaxe du langage de
programmation

208 209 210

FS Agadir SMI5-LPII

 Exemple introductif de grammaire  Grammaire hors contexte=GHC

 Pourquoi une grammaire?(3/3)
Considérons la grammaire suivante : La syntaxe d’un langage de programmation est définie par une
(2) Reconnaissance
expr→ expr + expr grammaire dite Grammaire Hors Contexte (GHC).
expr→ expr - expr
- Correction de la syntaxe (reconnaissance des chaînes syntaxiques)
conformément à la spécification déjà définie en (1). expr→ expr * expr GHC=Grammaire qui ne dépend pas de sens ou de la sémantique
expr→ ID - Context-Free Grammar = CFG
- Traduction du langage (arbre abstrait). expr→ INT - Backus-Naur Form = BNF

211 212 213

- Grammaire hors contexte (GHC) (1)  Remarque

 Exercice Les éléments d’une GHC :
Recherche sur Backus et Naur Un terminal est un lexème ou unité
Terminaux (T), Non-terminaux (NT), Productions (P) et axiomes (S)
lexicale.
GHC=Ensemble G de la forme
G=(T,NT,S,P) avec
- T=ensemble des mots du langage (mots)= Terminaux
Exemples
+, *, ID, INT, if, else, while…

214 215 216

24
 Exemple  Remarque  Exercice
Dans la grammaire suivante : Dans une grammaire les terminaux ne figurent pas à gauche Préciser les terminaux de la grammaire suivante :
expr→ expr + expr des règles. S → (L) | a
expr→ expr - expr L → L,S | S
expr→ expr * expr
expr→ ID
expr→ INT
les terminaux sont :
T = {+, - , *, ID, INT}

217 218 219

FS Agadir SMI5-LPII

 Réponse - Grammaire hors contexte (GHC) (2)  Remarque

T={ ( ) a , } Les éléments d’une GHC : Dans une grammaire un non terminal figure au moins une fois à
Terminaux (T), Non terminaux (NT), Production(P) et Axiomes gauche d’une règle.
(S)
- NT=ensembles des symboles Non Terminaux générés par la grammaire (des
phrases ou catégories syntaxiques)
Exemples
expr→ expr + expr
instr→ if (expr) instr else instr

220 221 222

- Grammaire hors contexte (GHC) (3)

 Exercice
 Réponse Terminaux(T), Non-Terminaux(NT), Production(P) et Axiomes (S)
Préciser les non terminaux de la grammaire suivante : - P=Ensemble des règles qui servent à générer les phrases du langage
NT={ S , L}
S → (L) | a On les appelle aussi des productions ou règles
d'écriture
L → L,S | S
Ces règles ont la forme :
s → s1 s2 s3…
avec si des terminaux ou de non terminaux
( i.e. les si appartiennent T U NT)
Pour produire s il faut avoir ou produire s1…

223 224 225

25
 - Grammaire hors contexte (GHC) (4)
 Utilisation des règles  Exemples de règles
- La règle : expr→ expr + expr
s → s1 s2 s3… expr→ ID Terminaux(T), Non-Terminaux(NT),
Signifie que, pour produire la syntaxe s il faut expr→ INT Production(P) et Axiomes (S)
avoir ou produire s1 suivi de s2…
- Axiome (S)=Symbole de départ non terminal
- On peut aussi dire que s se dérive (de gauche à droire) en s1 s2…
représentant le langage (figurant à gauche de la
- ou encore
première production) =S
s1 s2 s3 … se réduit (de droite à gauche) en s

226 227 228

FS Agadir SMI5-LPII

 Exemple d’axiome  On considère la grammaire suivante :  Réponse

Dans la grammaire suivante : S (L)|a S={ S }
expr→expr + expr LL,S | S
expr→expr - expr Chercher l’axiome.
expr→expr * expr
expr→ID
expr→INT

l’axiome est : S ={expr}

229 230 231

 Exercice de GHC  Exemple de GHC(suite)  Une autre façon de représenter les productions
Considérons la grammaire définie par les productions La représentation suivante, par
T={ ID, NB, +, -, *}
expr→expr + expr factorisation de expr:
NT={expr} expr→ expr+expr | expr – expr | expr*expr | ID | INT
expr→expr - expr
expr→expr * expr S={expr} remplace
expr→ID
expr→expr + expr
expr→INT expr→expr - expr
expr→expr * expr
Chercher les T,NT et S. expr→ID
expr→INT

232 233 234

26
 Résumé Objectifs
 Analyse syntaxique  Analyseur syntaxique et grammaire
 Grammaire non contextuelle  Dérivations
 Terminaux  Sentence
 Non Terminaux Chapitre 7  Forme sententielle
 Productions Grammaire et dérivations
 Axiome

235 237

FS Agadir SMI5-LPII

 Analyseur syntaxique et grammaire  Dérivation

 Définition de la dérivation
Définition d'un langage à partir d'une grammaire
Un analyseur syntaxique (parser) peut être construit à base Soit a, b des chaînes et A un NT.
Notion de dérivation
d'une grammaire. si A→c est une production alors on peut faire la dérivation suivante :
Comment ? c.a.d. aAb═>acb (GHC).
Appliquer les productions plusieurs fois, à partir du symbole initial(axiome),
pour dériver ou générer les phrases du langage : Transformer les non terminaux "═>" est le symbole de dérivation (différent de "→") .
en terminaux.
aAb ═>acb est lue comme suit:
"aAb dérive ou génère acb" ou bien
"acb est une phrase dérivée de aAb".

238 239 240

 Exemple de dérivation  Dérivations en plusieurs étapes  Exemple de dérivation

Si a1═> a2 ═>a3 ═>…═>an alors on dit que Considérons la grammaire
expr ═> ID est une dérivation correcte,
a1 dérive an en n étapes. expr→-expr|(expr)|expr+expr|expr–expr|expr*expr |ID |INT
car, on a la production
- On a aussi A partir des productions ci-dessus, on peut faire la dérivation suivante :
expr→ID. a ═> a pour toute chaîne a.
- On utilise aussi le symbole ═>* pour dire se dérive en 0, 1 ou expr ═> -expr
plusieurs étapes.

- Le symbole ═>+ veut dire se dérive en une ou plusieurs étapes.

241 242 243

27
 Exemple de dérivation  Exemple  Exemple
Considérons la grammaire Considérons la grammaire Considérons la grammaire
expr→-expr|(expr)|expr+expr|expr–expr|expr*expr |ident |nbre expr→-expr|(expr)|expr+expr|expr–expr|expr*expr |id|int expr→-expr|(expr)|expr+expr|expr–expr|expr*expr |ID |INT
A partir des productions ci-dessus, on peut faire la dérivation suivante : A partir des productions ci-dessus, on peut faire la dérivation suivante : A partir des productions ci-dessus, on peut faire la dérivation suivante :
expr ═> -(id) ? expr ═> ID+INT ?
expr ═> (expr) car car
expr ═> -expr expr ═> expr+expr
═> -(expr) ═> ID+expr
═> -(id) ═> ID+INT

244 245 246

FS Agadir SMI5-LPII

 Exercice 1  Exercice 2  Sentences

expr→-expr|(expr)|expr+expr|expr–expr|expr*expr |ID |INT Montrer que l'on peut dériver l'expression suivante Une sentence est une chaîne (dérivée) composée uniquement de
-(-id+ INT) ? terminaux.

Montrer la dérivation suivante à partir de la grammaire des expressions suivante :

expr ═>* INT + INT expr→-expr|(expr)|expr+expr|expr–expr|expr*expr |ID |INT
expr => expr+expr
=> Int+expr expr => -expr => -(expr)
=> int+int sentence => -(expr+expr)
=>-(-expr+expr)
=> -(-id+expr)
=> -(-id+int) sentence
247 248 249

 Exemple de sentence  Remarque  Formes sententielles

expr ═> expr+expr L(G(S))={sentences}= {X/ S ═>+ X avec X composée uniquement Une forme sententielle est une chaîne (dérivée) composée de
═> ID+expr d'éléments de T (terminaux)}
terminaux et de non terminaux.
═> ID+INT L(G(S)) représente les phrases du langage L de grammaire G et
d’axiome S.
ID+INT est une sentence.

250 251 252

28
 Exemple de forme sententielle : FS  Remarque  Dérivation la plus à gauche et la plus à droite
expr ═> expr+expr FS X une est chaîne en FS si S ═ >+ X et X peut contenir des éléments de Processus de dérivation
═>ID+expr FS NT U T.  présence peut être de plus d'un symbole non terminal.
═> ID+INT S  choix du symbole à développer
Les expressions en couleur verte sont des formes sententielles  le plus à gauche ou le plus à droite.
- Choix du symbole le plus à gauche  dérivation la plus à gauche.
- Choix du symbole le plus à droite 
dérivation la plus à droite.

253 254 255

FS Agadir SMI5-LPII

 Exemples  Réponse : dérivation à gauche  Réponse : dérivation à droite

On considère les productions suivantes liste → liste+liste | liste-liste | 0 | 1…| 9 liste → liste+liste | liste-liste | 0 | 1…| 9
liste → liste+liste | liste-liste | 0 | 1…| 9
liste ═> liste+liste liste ═>liste+liste
Donner la suite de dérivation de l'expression ═> liste-liste +liste ═> liste+1
2-3+1 dans les deux cas suivants : ═> 2-liste+liste ═> liste-liste+1
a) De gauche à droite de l'expression. ═> 2-3+liste ═> liste-3+1
b) De droite à gauche de l'expression. ═> 2-3+1 ═> 2-3+1

256 257 258

 Exercice  Soit la grammaire suivante : Résumé

Soit la grammaire hors contexte suivante : S→ABC  Analyseur syntaxique et grammaire
s → s s + |s s* | a A→a  Sentence
Montrer que l'on peut dériver la chaîne B→b  Forme sententielle
aa+a* Cε  Dérivation gauche
à partir de cette grammaire. Dérivation de ab?  Dérivation droite
dérivation gauche: S =>ABC
s=>ss*=>ss+s*=>as+s*=>aa+s*=>aa+a* =>aBC
dérivation droite =>abC
s=>ss*=>sa*=>ss+a*=>sa+a*=>aa+a* =>ab

259 260 261

29
 Objectifs
 Arbre syntaxique ou de dérivation (parse tree)
 Arbre syntaxique
Définition
 Analyse ascendante
Arbre syntaxique est un arbre
 Analyse descendante
- de racine axiome,
Chapitre 8  Factorisation de grammaire
Arbre syntaxique et approches d'analyse - de feuilles des symbole grammaticaux
 Grammaire récursive (terminaux) ou ε .
- de nœuds des non terminaux.

263 264

FS Agadir SMI5-LPII

 Exemple
 Exemple d’arbre syntaxique  Arbre syntaxique ou de dérivation (parse tree)
Soit la grammaire :
expr→ expr+expr | expr – expr | expr*expr | ID | INT Objectifs : liste→liste+liste|liste-liste|0|1…|9
L’expression ID + INT obtenue par les dérivations :
Donner l'arbre syntaxique de 2+6-1 relativement à cette grammaire.
expr ═> expr+expr ═> ID+expr ═> ID+INT
(1) Montre comment un axiome se dérive en une phrase ou
a l’arbre syntaxique
instruction du langage.
expr (axiome)

(2) Sert à vérifier si une chaîne est conforme à la grammaire

+ expr(NT) déjà définie.
expr(NT)

ID(T) INT(T)

265 266 267

 Exemple  Exercice 1
Réponse  Réponse (suite) Soit la grammaire suivante :
On commence par faire les dérivations de l’axiome liste jusqu’à liste s → s s + |s s* | a
obtenir la phrase 2 + 6 -1
Donner l'arbre de syntaxe de la chaîne
liste ═> liste-liste liste aa+a*
═> liste+liste -liste
liste
liste liste
═> 2+liste-liste
═> 2+6-liste
nbre nbre nbre
═> 2+6-1
L'arbre syntaxique de cette expression est 2 + 6 - 1

268 269 270

30
 Exercice 2  Processus d'analyse syntaxique  Analyse descendante
Soit la grammaire : Deux approches: On construit l'arbre syntaxique en partant de l'axiome
expr→-expr|(expr)|expr+expr|expr–expr|expr*expr |ID |INT - Analyse syntaxique descendante jusqu'aux feuilles en utilisant des dérivations.
Donner l'arbre syntaxique de la chaîne INT*INT+INT. - Analyse syntaxique ascendante

271 272 273

FS Agadir SMI5-LPII

 Exemple : analyse descendante de 2+6-1  Analyse ascendante

 Exemple : analyse descendante de 2+6-1
On construit l'arbre syntaxique en partant de la phrase (les feuilles)
liste ═> liste-liste de l’axiome
jusqu'à la racine.
═> liste+liste -liste liste

═> 2+liste-liste
═> 2+6-liste liste

═> 2+6-1 on obtient l’instruction liste

liste liste

On peut schématiser ceci dans l’arbre de dérivation affiché à la 2 + 6 - 1

page suivante.

274 275 276

 Exemple : analyse ascendante de 2+6-1  Exemple : analyse descendante de 2+6-1  Exercice

Donner les étapes qui permettent la reconnaissance de la chaîne INT*INT dans les cas
2+6-1 on part de l’instruction suivants
liste+6-1 liste
a) analyse descendante
liste+liste-1 b) analyse ascendante
liste-1 liste Utiliser la grammaire suivante:
liste-liste liste expr→-expr|(expr)|expr+expr|expr–expr|expr*expr |ID |INT
liste liste
exp=>expr* expr=>int*expr=>inr*int
liste(axiome) pour atteindre l’axiome en faisant des réductions et des
int*int
décalages. 2 + 6 - 1
expr*int
La diapositive suivante schématise ce processus.
expr*expr
expr(axiome)

277 278 279

31
  Analyse syntaxique descendante (top-down)  Analyse descendante & backtracking  Analyse descendante & backtracking(suite)
Une chaîne d'unités lexicales w respecte la syntaxe du - Exemple
langage L(S) si on les dérivations suivantes : Soit la grammaire G définie par :
s s
(1) S → cAd
(2) A → ab|a ═> échec
S ═> A1 c
Soit l'ensemble des terminaux T={c, d, a, b}. c
A d A d
═> A2
Montrons que la chaîne "cad" est une phrase du langage défini par
… G. a b
═> w

═> backtracking

280 281 282

FS Agadir SMI5-LPII

 Analyse descendante & backtracking(suite)  Élimination du backtracking  Factorisation

 Factorisation Considérons la grammaire suivante
A→ DB|DC
s s
Quelle production faut-il choisir quand on rencontre A lors du
═> succès
processus de dérivation d'une chaîne?
c
A d
c
A d  Factorisation

283 284 285

 Factorisation (suite)  Exercice  Réponse

A → DB|DC  A → D(B|C) Factoriser la grammaire suivante: Factoriser la grammaire suivante:
On peut alors remplacer S → cAd S → cAd
A → DB|DC par A → ab|a A → ab|a
A → DA’ et A’ → B|C On a A → ab|a devient A → a(b|ε)
en ajoutant un nouveau non terminal A' et le nombre de productions Donner la dérivation gauche cad dans cette grammaire. On pose B→ b|ε et on obtient A → aB. La grammaire devient
devient 3 au lieu de 2. alors
S → cAd
A → aB
B→ b|ε
Donner la dérivation gauche cad dans cette grammaire.
286 287 288

32
 Réponse  Récursivité à gauche  Exemple de récursivité gauche
Donner la dérivation gauche cad dans cette grammaire. Soit G une grammaire. Soit la grammaire G définie par
G est dite récursive à gauche si elle contient un non terminal A tel que
S → cAd (1) l → l+chiffre
A =>+ A C
A → aB (2) l → chiffre
La récursivité à gauche peut entraîner une boucle infinie.
B→ b|ε (3) chiffre→0|1|2…
La dérivation s'obtient par Cherchons à dériver la chaîne suivante :
S ═> cAd 2+3+1
═>caBd
═>cad

289 290 291

FS Agadir SMI5-LPII

 Réponse  Élimination de la récursivité à gauche  Exercice

Cherchons à dériver la chaîne suivante : Comment ? Donner la dérivation gauche de
2+3+1
Transformer la RG en RD 2+3+1 dans la nouvelle grammaire
l => l+chiffre
A travers un exemple l → chiffre l1
=> l+chiffre+chiffre
(1) l → l+chiffre l1 → +chiffre l1 | ε
l => l+chiffre+chiffre+chiffre…
(2) l → chiffre
 récursivité infinie lorsque on veut faire des dérivations 
gauches, l → chiffre l1
l1 → +chiffre l1 | ε

292 293 294

 Élimination de la récursivité à gauche  Exercice  Réponse

Éliminer la récursivité gauche de la
- Règle générale Éliminer la récursivité gauche de la grammaire suivante
Si on a une récursivité grammaire suivante E → E op nbre
E → nbre
A→AC|D E → E op nbre op → +
Alors elle devient E → nbre op → -
op → *
A → D A' op → + op → /
op → - La récursivité concerne les deux premières règles et qui vont devenir :
A' → C A' | ε
E → nbre E'
op → * E' → op nbre E' | ε
op → /
L'arbre syntaxique de nbre*nbre+nbre s'obtient à partir des dérivations de
Donner dans cette grammaire l'arbre de syntaxe la diapositive suivante.
associé à la chaîne nbre*nbre+nbre
295 296 297

33
 Dérivations de nbre*nbre+nbre  Exercice  Réponse (exercice )
Éliminer la récursivité gauche de la grammaire E→TE'
E → nbre E' suivante E'→+TE'|ε
E' → op nbre E' | ε E → E+T T→FT'
op → + | - | * | / E→T T'→*FT'|ε
E => nbre E' T → T*F F→(E) | nbre|id
=> nbre op nbre E' T→F
=>nbre * nbre E' F →(E)|nbre|id
=>nbre * nbre op nbre E'
=>nbre * nbre + nbre E'
=> nbre * nbre + nbre
298 299 300

FS Agadir SMI5-LPII

 Exercice  Exercice  Cas général

Montrer que la chaîne suivante fait partie du langage généré par la Transformer la grammaire suivante La grammaire suivante
grammaire de la planche précédente: A→AB A → AC1 | AC2…|ACn
x+y*2 A→AC A → D1|D2…|Dm
A→D se transforme en grammaire
en grammaire non récursive à gauche A → D1A'|D2A'…|DmA'
AAH (B|C) A' → C1A'|C2A'…|CnA'| ε
AD
ADA1
A1HA1|↋

301 302 303

 Exercice  Cas de récursivité indirecte

 Exercice
Éliminer la récursivité gauche dans la grammaire suivante Exemple
considérons la grammaire Éliminer la récursivité gauche de la grammaire suivante:
liste → liste+chiffre | liste-chiffre
liste → chiffre S → Ab A→ Bc
chiffre → 0|1… A → Sa | ε B→ Aad | ε
On peut avoir les dérivations
Montrer comment peut-on dériver la sentence 1+2-1 dans la S=>Ab =>Sab  récursivité directe
nouvelle grammaire? Et S=> Ab=>b
liste chiffre l1 On obtient alors
l1+chiffre l1 |-chiffrel1| ε S → Sab
S→b
Donc on applique la première règle
S → bA'
304
A' → abA'| ε 305 306

34
 Exercice Résumé
Éliminer la récursivité gauche de la grammaire suivante:  Arbre syntaxique
A→ Ac | Aad | bd
 Analyse ascendante
 Analyse descendante
 Factorisation de grammaire Chapitre 9
 Grammaire récursive Analyse prédictive et Grammaire LL

307 308 309

FS Agadir SMI5-LPII

 Analyse sans recul  Notion de premier(A)(First(A))

Objectifs
Considérons les productions Définition
 Grammaire LL A→A1|A2 …|An premier(A) est l’ensemble des terminaux qui
 Analyse prédictive Rencontrer A dans une chaîne à analyser, laquelle des Ai apparaissent en première place (de la gauche) dans
 Notion de premier (productions) à choisir?
par exemple
les sentences dérivées de A.
 Notion de suivant S → abd | aAb premier(A)={a є T/ A =>* aB} u {ε si A =>* ε}
 Table d'analyse prédictive A→ d|c et
 Grammaire à descente récursive la phrase adb.
Analyse sans recul :
 Introduction des concepts premier et suivant.

310 311 312

 Exemple 1 de calcul de premier  Exemple 2  Réponse

Soit la grammaire : Calcul de premier de S premier(S)={c,b}
S → aAb | cd
S→Ab
A→d
Calculons premier(S) et premier(A) A→cd|ε
S => aAb
S=> cd
premier(S)={a,c}. S=>Ab=>cdb
premier(A)={d} S=>Ab=>εb=b

313 314 315

35
 Exemple 2  Réponse  Exemple 3
Calcul de premier de A premier(A)={c, ε} Calcul de premier de S
S→Ab S→AB
A→cd|ε A→cd|ε
B→b|ε
S=>AB=>cdB;
S=>AB=>εB=B
S=>AB=>εB=ε

316 317 318

FS Agadir SMI5-LPII

 Algorithme de calcul de premier

premier(X)
début
 Réponse  Remarque si X є T alors
premier(S)={c,b,ε} S→AB sinon
premier(X)={X};

si X є NT alors
premier (S) comprend premier(A) premier(X)=Ø;
si X→aA est une prod alors premier(X)={a} u premier(X)
si X→a est une prod alors premier(X)={a} u premier(X)
si X→ε est une prod alors premier(X)={ε} u premier(X)
si X→Y1Y2…YK est une prod (appliquée aussi à une chaîne) alors
premier(X)=(premier(Y1)-{ε}) u premier(X)
si ε є premier(Yi) i=1→ k-1 alors
premier(X)=(premier (Yi+1)-{ε}) u premier(X)
si ε є premier(Yk) alors
premier(X)={ε} u premier(X)

fin.
319 320 321

 Exemple d’application  Réponse symbole premier

Chercher premier(X) pour la grammaire suivante : S→ABc
a a  Réponse symbole premier
S→ABc A→a | ε
b b S→ABc a {a}
A→a | ε B→b | ε
A→a | ε
B→b | ε c c b {b}
B→b | ε
A a,ε  Exercice c {c}
B b,ε Calculer premier(Bc). A {a,ε}
S a,b,c B {b,ε}
S {a,b,c}

322 323 324

36
  Exercice  Réponse symbole premier
 Réponse symbole premier Chercher premier pour les symboles de la grammaire S→aSe
S→ABc suivante: S a, b, c, d
a {a} S→B
A→a | ε S→aSe B b, c, d
b {b}
B→bBe
B→b | ε S→B
B→C C c, d
 Exercice c {c} B→bBe
C→cCe
Calculer premier(Bc). A {a,ε} B→C
C→d
 Réponse B {b,ε}
C→cCe
premier(Bc)={b,c} C→d
S {a,b,c}

325 326 327

FS Agadir SMI5-LPII

 Notion de suivant(A)(follow(A))  Exemple 1  Réponse

suivant(A)={ensemble des terminaux qui viennent Calcul de suivant suivant(A)={b}.
juste après le symbole A dans des formes Soit la grammaire :
sententielles} S → aAb
suivant(A)={aє T/ S=>+…Aa…} u {ε si S=>+…A sinon Ø} A→d
Calculons suivant(A)

328 329 330

 Exemple 2  Réponse  Exemple 3

Calcul de suivant Calcul de suivant(A) Calcul de suivant
Soit la grammaire : suivant(A)={d}. Soit la grammaire :
S → aAB S → aABC
B→d B → d|ε
Calculer suivant(A) C→c
Calculer suivant(A)

331 332 333

37
  Réponse  Algorithme de calcul de suivant
 Exemple d’application
suivant(X)
suivant(A)={d,c}. début Chercher suivant(X) pour la grammaire suivante :
si X=S(axiome) alors S→ABc
suivant(X)={ε} //initialisation A→a | ε
sinon B→b | ε
suivant(X)=Ø //initialisation
si A→…XB est une prod alors
suivant(X)=suivant(X) u premier(B)
si A→…X est une prod alors
suivant(X)=suivant(X) u suivant(A)
Fin.
334 335 336

FS Agadir SMI5-LPII

 Exemple d’application
 Réponse symbole suivant Chercher suivant(X) pour la grammaire suivante :  Réponse symbole suivant
S→ABc A b, c S→ABC S→ABC A b, c, ε
A→a | ε A→a | ε A→a | ε
B c B c, ε
B→b | ε B→b | ε B→b | ε
S ε C→c | ε C→ c | ε S ε
C ε

337 338 339

 Exercice  Construction d’une table d’analyse d’une grammaire

Une table d’analyse M est définie par
Chercher suivant pour les symboles de la  Réponse symbole suivant M: NT x T→ productions u {erreur}
grammaire suivante: S→aSe Exemple
B ε,e
S→aSe S→B M[A][t] désigne la production à développer quand on a A(non
S ε,e terminal) et le terminal t sinon erreur.
S→B B→bBe
M[A][t] permet de prédire la production à utiliser.
B→bBe B→C C ε,e Comment construire la table d’analyse
B→C C→cCe  besoin de la fonction de prédiction : prédic on(A→X1X2…Xn)
C→d prédiction(A→X1X2…Xn)=
C→cCe
-premier(X1…Xn)-{ε} u suivant(A) si ε є premier(X1…Xn)
C→d -premier(X1X2…Xn) sinon.

340 341 342

38
  Exemple de calcul de la table d’analyse M
 Exemple symbole premier suivant M[NT][t]="NT→X1X2…" si t є prédic on(NT→X1…)
(1) S→ABc A a,ε b,c  Calcul de la table d’analyse M
NT/T a b c
(2) A→a M[NT][t]=ordre(NT→X1X2…) si t є prédic on(NT→X1…)
B b,ε c S S→ABc S→ABc S→ABc
(3) A→ε
S a,b,c ε ou bien A A→a A→ε A→ε
(4) B→b (5) B →ε
B B→b B →ε
production prédiction M[NT][t]="NT→X1X2…" si t є prédic on(NT→X1…) prod prédiction
(1) S→ABc premier(ABc)={a,b,c}
(1) S→ABc premier(ABc)={a,b,c}
(2) A→a premier(a)={a}
(2) A→a premier(a)={a}
(3) A→ε (premier(ε)-{ε}) u suivant(A)=suivant(A)={b,c}
(3) A→ε (premier(ε)-{ε}) u suivant(A)=suivant(A)={b,c}
(4) B→b premier(b)={b}
(4) B→b premier(b)={b}
(5) B →ε (premier(ε)-{ε}) u suivant(B)=suivant(B)={c} (5) B →ε (premier(ε)-{ε}) u suivant(B)=suivant(B)={c}
343 344 345

FS Agadir SMI5-LPII

 Exemple de calcul de la table d’analyse M

M[NT][t]=ordre(NT→X1X2…) si t є prédic on(NT→X1…)
 Analyseur syntaxique prédictif  Programme contrôleur
NT/T a b c algorithme PC
Analyseur basé sur la table d’analyse début
S (1) (1) (1) initialiser pile par $S.
Schéma d’analyseur prédictif répéter
A (2) (3) (3) X=symbole au sommet de pile
a=symbole de chaîne
B (4) (5) si X est un terminal ou $ (dans pile) alors
si X==a(dans entrée) alors
prod prédiction Table
dépiler( X) ; et avancer le pointeur d’entrée(dans entrée);
d’analyse
sinon retourner erreur;
(1) S→ABc premier(ABc)={a,b,c} sinon (X est non terminal)
entrée$ Programme contrôleur Arbre si M[X][a]=X→Y1…Yn alors //dans la table d’analyse
(2) A→a premier(a)={a} syntaxique ou dépiler(X);
(3) A→ε (premier(ε)-{ε}) u suivant(A)=suivant(A)={b,c} erreur empiler(Yn);empiler(Yn-1)…empiler(Y1);
sinon retourner erreur;
(4) B→b premier(b)={b} p jusqu’ à X=‘$’; //pile vide
il fin.
(5) B →ε (premier(ε)-{ε}) u suivant(B)=suivant(B)={c} e

346 347 348

 Exemple 1 d’analyse pile entrée M[X][a]

 Exemple 2 d’analyse  Réponse
Faire l’analyse de la chaîne pile entrée M[X][a]
abc. $S abc$ S→ABc Analyse de la chaîne abb.
Faire l’analyse de la chaîne abb. $S abb$ S→ABc
S =>Abc $cBA abc$ A→a
=>aBc $cBa abc$ $cBA abb$ A→a
=>abc $cBa abb$
$cB bc$ B→b
$cb bc$ $cB bb$ B→b
NT/T a b c $c c$ $cb bb$
S S→ABc S→ABc S→ABc $ $ $c b$
A A→a A→ε A→ε
B B→b B →ε

349 350 351

39
  Exercice  Les symboles lookahead  Les grammaires LL(1)
Analyser les chaînes Le choix d'une production pour avancer dans L= left to right scanning
- ac l'analyse de la chaîne d'entrée exige un L=leftmost derivation
- bc symbole de cette chaîne d'entrée. 1=un seul symbole d’entrée pour la prévision à
Ces symboles sont appelés des lookahead. chaque étape.
Puisqu’on se contente d’un seul symbole, on une grammaire de type LL(1) a une table
parle de lookahead (1) d’analyse sans entrée multiple.

352 353 354

FS Agadir SMI5-LPII

 Caractéristiques des grammaires LL(1)  Caractéristiques des grammaires LL(1)  Caractéristiques des grammaires LL(1)
- Une grammaire RAG n’est pas LL(1). - Une grammaire RAG n’est pas LL(1). - Une grammaire ambiguë n’est pas LL(1).
- Une grammaire ambiguë n’est pas LL(1). Liste Liste +Nb S S + S
- Une grammaire est LL(1) SI Liste Nb S S * S
pour toute A→B|C Nb [0-9] S a
- B et C ne se dérivent pas tous les deux en Dérivation de la chaîne a*a+a
chaînes commençant par un même terminal a.
- Soit B, soit C se dérive en ε
- Si B=>*ε alors C ne se dérive pas en une chaîne
commençant par un terminal de suivant(A).

355 356 357

 Caractéristiques des grammaires LL(1)  Caractéristiques des grammaires LL(1)  Caractéristiques des grammaires LL(1)
- Une grammaire est LL(1) SI - Une grammaire RAG n’est pas LL(1). - Une grammaire est LL(1) SI
pour toute A→B|C - Une grammaire ambiguë n’est pas LL(1). pour toute A→B|C
- B et C ne se dérivent pas tous les deux en - Une grammaire est LL(1) SI - Soit B, soit C se dérive en ε
chaînes commençant par un même terminal a. pour toute A→B|C S A|B
- B et C ne se dérivent pas tous les deux en AbA|Ɛ
S aA|a chaînes commençant par un même terminal a. BƐ
AbA|b - Soit B, soit C se dérive en ε
- Si B=>*ε alors C ne se dérive pas en une chaîne
commençant par un terminal de suivant(A).

358 359 360

40
 Caractéristiques des grammaires LL(1)  Exercice
- Une grammaire est LL(1) SI  Exercice
La grammaire suivante est-elle LL(1)? La grammaire suivante est-elle LL(1)?
pour toute A→B|C
S→Ab S→Ab
- Si B=>*ε alors C ne se dérive pas en une chaîne
commençant par un terminal de suivant(A). A→a A→a
Aε|c
A→aB A→B
AaAc A→ε
A→ε
B→b B→b
B→ε. B→ε.

361 362 363

FS Agadir SMI5-LPII

 Analyse à descente récursive

 Exercice  Travail à faire Une procédure pour chaque non terminal.
Exemple
La grammaire suivante est-elle LL(1)? Construire un analyseur syntaxique pour les A aB | CD |ε
expressions arithmétiques. trouverA
S→ABBA { si (mot==a) alors
A→a E→E+T|E-T|T {mot=prochainmot();
retourner trouverB();
A→ε T→T*F|T/F|F sinon si (mot in (premier(C)-{ε})) alors
retourner(trouverC() et trouverD());
B→b F→(E)|nbre|ident sinon si (mot in suivant(A)) alors
retourner true;
B→ε. sinon retourner false;
}
trouverC{…}
…

364 365 366

 Travail à faire Résumé

Écrire un analyseur syntaxique à descente  Grammaire LL
récursive pour les expressions arithmétiques.
 Analyse prédictive
 Notion de premier
 Notion de suivant Chapitre 10
Analyse Ascendante
 Table d'analyse prédictive
 Grammaire à descente récursive

367 368 369

41
Objectifs  Exemple
 Analyse ascendante
 Analyse ascendante Considérons la grammaire suivante :
On part des feuilles de l’arbre syntaxique pour listeliste+liste|liste-liste|0|1…|9
 Décalage et réduction retrouver la racine=axiome. Faisons l'analyse ascendante de 2+6-1.
 Analyse LR Comment? 2+6-1
 Schéma d'analyseur LR Remplacer la partie droite d’une production par sa liste+6-1
 Tabla action et successeur partie gauche. liste+liste-1
liste-1
liste-liste
liste (axiome).
 Analyse décalage-réduction ou shift-reduce

370 371 372

FS Agadir SMI5-LPII

 Exemple (suite)  Exercice

 Réponse
liste
En utilisant une analyse ascendante, donner le processus de Reconnaissance de la chaîne abbcd dans la grammaire suivante
reconnaissance de la chaîne abbcd dans la grammaire S → aAB
liste
suivante A → Abc|b
S → aAB B→d
liste
liste liste Processus de décalage-réduction
A → Abc|b abbcd
2 + 6 - 1 B→d aAbcd
aAd
aAB
S (axiome)
373 374 375

 Construction de dérivation droite inverse Reverse Right Derivation

Considérons de nouveau la chaîne 2+6-1.  Réponse
2+6-1  Exercice Reconnaissance de la chaîne abbcd dans la grammaire suivante
2+6-1 S → aAB
Donner la dérivation droite inversée de la chaine abbcd dans
liste+6-1 A → Abc|b
liste+liste-1
la grammaire suivante B→d
liste-1 S → aAB Processus de décalage-réduction
liste-liste A → Abc|b abbcd
liste (axiome). aAbcd
B→d aAd
Ce processus peut être compris comme l’inverse d’une dérivation droite :
aAB
Liste=>liste-liste=>liste-1=>liste+liste-1=>liste+6-1 =>2+6-1
S
 Analyse Reverse-Right Derivation
Si on part de S, on obtient
S => aAB => aAd => aAbcd => abbcd
376 377 378

42
  Recherche des productions lors du processus de  Schéma d’un analyseur syntaxique LR
 Analyse LR(0) reconnaissance de phrases
- L : lecture de gauche à droite de la chaîne (Left to right scan) Comme dans l’analyse LL(1), nous avons besoin d’un moyen
Table Table
- R: construction d’une dérivation droite inverse (Reverse- pour choisir les productions à utiliser pour avancer l’analyse. action successeur
Rightmost derivation)  Table action et table goto ou successeur.
- Pas de symbole de prévision (lookahead). Entrée$ Programme moteur Arbre
syntaxique ou
Cette analyse est appelée aussi shift-reduce parsing. erreur

P
i
Composée d’états
l
e

379 380 381

FS Agadir SMI5-LPII

 Structure de la table Action  Structure de la table Successeur ou Branchement  Exemple de table action et successeur
Action[état][T] prend l’une des valeurs suivantes Soit la grammaire suivante
Successeur[état][NT] prend l’une des valeurs suivantes
- di : décaler(dans entrée) et empiler l’état i (1)EE+T
- état à empiler
(2)ET
- ri : réduire en utilisant la production i - vide pour indiquer erreur
(3)TT*F
- vide pour indiquer erreur
(4)TF
- accepter(la chaîne est correcte et fin d'analyse)
(5)F(E)
(6)Fid
les tables action et successeur de cette grammaire sont données par
la suite.

382 383 384

 Programmeur moteur d’analyse

pm()
 Exemple d’analyse
 Tables action et successeur états Action Succ début Soit la grammaire suivante
Considérons la chaîne à analyser id + * ( ) $ E T F empiler(0) //état initial et pile vide
0 d5 d4 1 2 3 répéter (1)EE+T
: id*id+id
1 d6 ac si action[s][a]=di alors //s sommet de pile (2)ET
empiler(i); liremotsuivant();
2 r2 d7 r2 r2
sinon (3)TT*F
3 r4 r4 r4 r4
4 d5 d4 8 2 3
si action[s][a]=ri alors (4)TF
soit la production i définie par
5 r6 r6 r6 r6 XX1X2…Xn (5)F(E)
6 d5 d4 9 3 dépiler (n fois); (6)Fid.
7 d5 d4 10 empiler(j) avec successeur[s][X]=j
sinon Construire le processus de reconnaissance de la chaîne id*id+id
8 d6 d11
si action[s][a]=accepter alors
9 r1 d7 r1 r1 retourner true;
10 r3 r3 r3 r3 sinon
11 r5 r5 r5 r5 retourner ‘erreur ’;
fin répéter
fin.
385 386 387

43
T Entrée$ S P A E Action Suc
T Entrée$ S P A
0 id*id+id$ 0 d5 id + * ( ) $ ET F
0 id*id+id$ 0 d5
E Action Suc  Remarque
5 *id+id$ 0,5 r6 0 d5 d4 1 2 3
(1)EE+T 5 *id+id$ 0,5 r6
id + * ( ) $ ET F
La partie s de la table de reconnaissance contient les
3 *id+id$ 6 0,3 r4 1 d6 ac
(2)ET 0 d5 d4 1 2 3
2 *id+id$ 6,4 0,2 d7 2 r2 d7 r2 r2
(3)TT*F
3 *id+id$ 6 0,3 r4
1 d6 ac productions du processus de dérivation droite inversée.
7 Id+id$ 6,4 0,2,7 d5 3 r4 r4 r4 r4 2 *id+id$ 6,4 0,2 d7

5 +id$ 6,4 0,2,7,5 r6 4 d5 d4 8 2 3

(4)TF 7 Id+id$ 6,4 0,2,7 d5
2 r2 d7 r2 r2

10 +id$ 6,4,6 0,2,7,10 r3 5 r6 r6 r6 r6

(5)F(E) 5 +id$ 6,4 0,2,7,5 r6
3 r4 r4 r4 r4
4 d5 d4 8 2 3
2 +id$ 6,4,6,3 0,2 r2
(6)Fid. 10 +id$ 6,4,6 0,2,7,10 r3
6 d5 d4 9 3 5 r6 r6 r6 r6
1 +id$ 6,4,6,3,2 0,1 d6 2 +id$ 6,4,6,3 0,2 r2
7 d5 d4 1
6 Id$ 6,4,6,3,2 0,1,6 d5 1 +id$ 6,4,6,3,2 0,1 d6 6 d5 d4 9 3
0
5 $ 6,4,6,3,2 0,1,6,5 r6 6 Id$ 6,4,6,3,2 0,1,6 d5 7 d5 d4 1
8 d6 d1
5 $ 6,4,6,3,2 0,1,6,5 r6 0
3 $ 6,4,6,3,2, 0,1,6,3 r4 1
6 3 $ 6,4,6,3,2, 0,1,6,3 r4 8 d6 d1
9 r1 d7 r1 r1
6 1
9 $ 6,4,6,3,2, 0,1,6,9 r1 10 r3 r3 r3 r3
6,4 9 $ 6,4,6,3,2, 0,1,6,9 r1 9 r1 d7 r1 r1
11 r5 r5 r5 r5
1 $ 6,4,6,3,2, 0,1 ac 6,4 10 r3 r3 r3 r3
6,4,1 1 $ 6,4,6,3,2, 0,1 ac 11 r5 r5 r5 r5
388 389 390
6,4,1

FS Agadir SMI5-LPII

T entrée S P A E Action Suc

0 id+id$ 0 d5 id + * ( ) $ ET F  Comment construire les tables action et successeur?
 Exercice 5 +id$ 0,5 r6 0 d5 d4 1 2 3
3 +id$ 6 0,3 r4 1 d6 ac
Chercher le processus d’analyse des chaînes 2 +id$ 6,4 0,2 r2 2 r2 d7 r2 r2
1 +id$ 6,4,2 0,1 d6 3 r4 r4 r4 r4
- id+id 6 id$ 6,4,2 0,1,6 d5 4 d5 d4 8 2 3

- id+id *id 5 $ 6,4,2 0,1,6,5 r6 5 r6 r6 r6 r6

3 $ 6,4,2,6 0,1,6,3 r4
6 d5 d4 9 3
9 $ 6,4,2,6,4 0,1,6,9 r1
7 d5 d4 1
1 $ 6,4,2,6,4,1 0,1 ac 0
8 d6 d1
1
9 r1 d7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
391 392 393

 Notion d’item ou de configuration  Notion d’item (suite)  Exercice

Considérons la production suivante - Le premier item E.E+T veut dire que l’analyse attend un E Chercher les items relatifs à la production suivante :
E E+T suivi de + suivi de T.
A cette production est associée les quatre items suivants: E E* T
- L’item E E.+T veut dire que l’analyse a reconnu le symbole
E.E+T E et attend un + suivi de T.
E E.+T
- Donc les items décrivent les différents états de l’analyse.
E E+.T
E E+T.
Un item est une production à laquelle on a ajoutée un point dans
la partie droite.

394 395 396

44
  Fermeture d’un ensemble d’items
 Réponse Considérons l’ensemble d’items suivant :
Chercher les items relatifs à la production suivante : I={E E+.T}
 Remarque
E E* T La fermeture de I noté fermeture(I) est l'ensemble d’items
l’item associé à la production A ε est obtenu comme suit :
Les items associés à E E+T
A. i. initialiser fermeture(I) par I={EE+.T}
E .E+T
ii. rechercher les productions avec partie gauche contenant
E E.+T T, par exemple T0|1;
E E+.T iii. ajouter les items T.0 et T.1 à fermeture(I);
E E+T. iv. répéter les op ii) et iii) avec les items ajoutés à
fermeture(I) jusqu’aucun item ne soit ajouté (ensemble
fermé).

397 398 399

FS Agadir SMI5-LPII

 Fermeture d’un ensemble d’items(suite)  Exercice 1  Exercice 1 : Réponse

Donc la fermeture de I est : Soit la grammaire Soit la grammaire
fermeture({E E+.T})={E E+.T, T.0 , T.1 } E E+T E E+T
E E*T E E*T
E T E T
T 0|1 T 0|1
Chercher la fermeture de {E E*.T}. Chercher la fermeture {E E*.T}.
fermeture({E E*.T})={E E*.T, T .0, T .1 }

400 401 402

 Exercice 2  Exercice 2 : réponse  Remarque

Soit la grammaire suivante Soit la grammaire suivante Les ensembles d’items fermés que l’on obtient représentent les états de
(1)EE+T (1)EE+T l’analyseur syntaxique (les colonnes T et P).
(2)ET (2)ET
(3)TT*F (3)TT*F
(4)TF (4)TF
(5)F(E) (5)F(E)
(6)Fid (6)Fid
1)Chercher la fermeture de l’item E E+.T 1)fermeture(E E+.T)={E E+.T, T .T*F, T .F, F.(E), F.id}
2)Chercher la fermeture de l’item E .E+T 2)fermeture(E.E+T)={E.E+T, E.T, T.T*F, …}

403 404 405

45
  Exemple  Transitions entre les ensembles d’items
Soit la grammaire G Grammaire G’ augmentée Les ensembles d’items forment les états d’un automate fini dont les
 Grammaire augmentée (0)S E transitions sont étiquetées par les terminaux et les non terminaux.
(1)E E+T
Soit G une grammaire d’axiome E. (1)E E+T Automate fini  état initial
A partir de la grammaire G on développe une autre grammaire G’ dite
(2)E E*T (2)E E*T
état initial i=fermeture({S.E}).
grammaire augmentée, en lui ajoutant (3)E T (3)E T
la production : S E. (4)T 0
(4)T 0 (5)T1
S représente l’axiome de la nouvelle grammaire(G’).
(5) T1

406 407 408

FS Agadir SMI5-LPII

 Exemple  Exemple  Transition entre les états

i=fermeture({S .E})= {S .E,
Cas de la grammaire Cas de la grammaire Cherchons maintenant les états que l’on peut atteindre à partir de
E .E+T,
(0)S E (0)S E l’état initial i.
E .E*T,
(1)E E+T (1)E E+T E.T,
Comment?
1. Chercher dans i (état initial) un item(ou plusieurs) contenant un
(2)E E*T (2)E E*T T.0,
symbole (a par exemple) précédé d’un point.
T.1}
(3)E T (3)E T 2. Déplacer dans ces items le point après le symbole a.
(4)T 0 (4)T 0 3. Rassembler les items obtenus dans un même ensemble.
(5)T1 (5)T1 4. Calculer la fermeture de cet ensemble = nouvel état de l’automate:
T(i,a).
5. Répéter 1-4 pour tous les symboles.

409 410 411

 Exemple 1  Exercice 1  Réponse

Prenons l’état i défini par Cherchons d’autres ensembles de C. T(i,1)={T1.} =état 2 à ajouter à C
i=fermeture({S .E})= {S .E, E .E+T,E .E*T,E.T,
Prenons toujours l’état i défini par T(i,T)={E T.}=état 4 à ajouter à C
T.0, T.1}
i=fermeture({S .E})= {S .E, E .E+T,E .E*T,E.T, T.0, T.1}
Cherchons un item avec un symbole figurant après le point, par exemple T.0 et le
symbole est 0. 1)Chercher T(i,1).
Calculons T(i,0)=fermeture({T 0.})={T 0.} 2)Chercher T(i,T).
T(i,0) désigne un état nommée par exemple 1. T(i,0) est un ensemble qui fait partie
de la collection canonique d’ensembles d’items notée C.

412 413 414

46
  Exercice 2  Recherche d’autres états  Recherche d’autres états
Prenons l’état i défini par
Si on prend les ensembles des items (états) obtenus: Si on prend les ensembles des items (états) obtenus:
i=fermeture({S .E})= {S .E, E .E+T,E .E*T,E.T,
T(i,0)={T 0.}=état 1 T(i,0)={T 0.}=état 1
T.0, T.1} T(i,1)={T1.} =état 2
T(i,1)={T1.} =état 2
et T(i,E)={S E., EE.+T, EE.*T}=état 3
T(i,E)={S E., EE.+T, EE.*T}=état 3
calculons T(i,E)=fermeture({S E., EE.+T, EE.*T}) T(i,T)={E T.}=état 4
T(i,T)={E T.}=état 4
={S E., EE.+T, EE.*T} Recherchons des états à partir de 3:
T(i,E) désigne un état nommée par exemple 3 à ajouter à C. T(3,+)=fermeture({EE+.T})=
{EE+.T, T.0, T.1}=état 5 à ajouter à C.

415 416 417

FS Agadir SMI5-LPII

 Recherche d’autres états(suite)

 Recherche d’autres états(suite)  Recherche d’autres états(suite)
T(i,0)={T 0.}=état 1
T(i,0)={T 0.}=état 1 T(i,0)={T 0.}=état 1
T(i,1)={T1.} =état 2 T(i,1)={T1.} =état 2
T(i,1)={T1.} =état 2 T(i,E)={S E., EE.+T, EE.*T}=état 3 T(i,E)={S E., EE.+T, EE.*T}=état 3
T(i,E)={S E., EE.+T, EE.*T}=état 3 T(i,T)={E T.}=état 4 T(i,T)={E T.}=état 4
T(i,T)={E T.}=état 4 T(3,+)={EE+.T, T.0, T.1}=état 5
T(3,+)={EE+.T, T.0, T.1}=état 5
toujours à partir de 3: T(3,*)={EE*.T, T.0, T.1}=état 6 T(3,*)={EE*.T, T.0, T.1}=état 6
T(3,*)=fermeture({EE*.T})= maintenant à partir de 5 et de 6:
maintenant à partir de 5 et de 6: T(5,0)=fermeture({T0.})=état 1 figure déjà dans C.
{EE*.T, T.0, T.1}=état 6 à ajouter à C. T(5,1)=fermeture({T 1.})=état 2
T(5,T)=fermeture({EE+T.})={EE+T.}=état 7 à ajouter à C
T(6,T)=fermeture({EE*T.})={EE*T.}=état 8

418 419 420

 Exemple
 Construction des tables d’analyse action et successeur i= {S .E, E +T,E.E*T,E.T, T.0,
Algorithme  Exemple T.1}=état 0 é * + 0 1 $ E T
entrée : grammaire augmentée G’
sortie : tables action et successeur i= {S .E, E.E+T,E.E*T,E.T, T.0, T.1}=état 0 T(i,0)={T 0.}=état 1
d1 d2 3 4
T(i,1)={T1.} =état 2 0
début T(i,0)={T 0.}=état 1
construire une matrice M vérifiant : T(i,E)={S E., EE.+T, EE.*T}=état 3 1 r4 r4 r4 r4 r4
la première colonne est formé des états de C avec état 0 formé à partir de fermeture({S.E}) T(i,1)={T1.} =état 2
T(i,T)={E T.}=état 4 r5 r5 r5 r5 r5
la première ligne est composée : T(i,E)={S E., EE.+T, EE.*T}=état 3 2
T(3,+)={E E+.T,T.0, T.1}=état 5
- des symboles terminaux + $ pour action d6 d5 a
T(i,T)={E T.}=état 4 3
- Et des symboles non terminaux pour successeur. T(3,*) = {EE*.T, T.0,T.1}=état 6
Pour action T(3,+)={E E+.T,T.0, T.1}=état 5 4 r3 r3 r3 r3 r3
T(5,T)={EE+T.}=état 7
Si T(i,a)=ek alors M(i,a)=dK T(3,*)= {EE*.T, T.0,T.1}=état 6 T(6,T)={EE*T.}=état 8 5 d1 d2 7
Si un état i contient A d. alors M(i,a)=rk (pour tout a) avec k=ordre(Ad) pour A <> S.
Si un état i contient SE. alors M(i,$)=acc. T(5,T)={EE+T.}=état 7 T(6,T)={EE*T.}=état 8 (0)S E d1 d2 8
Pour successeur (1)E E+T 6
Si T(i,A)=ej alors M(i,A)=j (2)E E*T 7 r1 r1 r1 r1 r1
fin
(3)E T 8 r2 r2 r2 r2 r2
(4)T 0
(5)T1
421 422 423

47
  Recherche des états
 Exercice  Réponse état 0
Soit la grammaire G suivante : état 0= fermeture({S.E})={S.E, E.E+T, E.T, T.id, T.(E)}.
(0)S E
état 1=T(0,E)=ferm({SE., E E.+T})=
EE+T
(1)EE+T {SE., E E.+T}
E T état 2=T(1,+)=ferm({EE+.T})
Tid (2)E T ={EE+.T, T.id, T.(E)}
T(E) (3)Tid état 3=T(2,T)=ferm({EE+T.})={EE+T.}
état 4=T(2,id)=ferm({Tid.})={Tid.}
1)Donner la grammaire G’ augmentée associée à G. (4)T(E) état 5=T(2,()=ferm({T(.E)})={T(.E),E.E+T,
2)Chercher la collection C des ensembles d’items. E.T, T.id, T.(id)}
3)Donner les tables d’analyse. état 6 =T(5,E)=ferm({T(E.),EE.+T})={T(E.),EE.+T}
état 7=T(6,))=ferm({T(E).})={T(E).}
état 8=T(5,T)=ferm({E T.})={ET.}

424 425 426

FS Agadir SMI5-LPII

 Exercice  Réponse Résumé

Calculer  Analyse ascendante
T(0,T), T(0,(), T(0,id), T(5,id), T(6,+) T(0,T)=7  Décalage et réduction
T(0,()=5  Analyse LR
T(0,id)=4  Schéma d'analyseur LR
T(5,id)=4  Tabla action et successeur
T(6,+)=3

427 428 429

48