Analyse Syntaxique

Théorie des langages

INFO1
2024/2025
 CH5. Analyse syntaxique

Sommaire
➢ Rôle de l’analyseur syntaxique
➢ Définition d’une grammaire hors contexte
➢ Comment écrire une GHC ?
➢ Dérivation
➢ Langage généré par une GHC
➢ Arbres de dérivation et GHC ambiguës
➢ Langages hors contexte
➢ Précédence d’opérateurs
ESPRIM Khouja Med Khairallah 2
 CH5. Analyse syntaxique

Sommaire

➢ Autres sources d’ambiguïté

➢ Les techniques d’analyse syntaxique
➢ Analyse syntaxique descendante
➢ Analyse syntaxique prédictive
➢ GHC récursive à gauche
➢ GHC factorisable à gauche
➢ Analyse prédictive non récursive

ESPRIM Khouja Med Khairallah 3

 CH5. Analyse syntaxique

Sommaire

➢ Construction de la table d’analyse

prédictive
➢ Grammaires LL(1)
➢ Analyse syntaxique ascendante

ESPRIM Khouja Med Khairallah 4

 CH5. Analyse syntaxique

Rôle de l'analyseur
syntaxique

ESPRIM Khouja Med Khairallah 5

 CH5. Analyse syntaxique

Rôle de l’analyseur syntaxique

➢ Analyseur lexical et analyseur syntaxique :
✓ Le but de l'analyseur lexicale (scanner) est de
scinder le fichier source en jetons (lexèmes ou
tokens).
✓ L’objectif de l'analyseur syntaxique (parseur)
consiste à recombiner ces jetons.
✓ Les jetons fournis par l’analyseur lexical seront
regroupés par l’analyseur syntaxique pour de
construire des unités syntaxiques.
ESPRIM Khouja Med Khairallah 6
 CH5. Analyse syntaxique

Rôle de l’analyseur syntaxique

Flot de Analyseur
caractères lexical

Fichier
jetons
source

Place de l’analyseur Analyseur Unités

syntaxique syntaxique syntaxiques

ESPRIM Khouja Med Khairallah 7

 CH5. Analyse syntaxique

Rôle de l’analyseur syntaxique

➢ Analyseur lexical et analyseur syntaxique :
✓ Dans un compilateur, l’analyseur syntaxique
reçoit le programme sous la forme d’une suite de
lexèmes produits par l’analyseur lexical.

✓ Le rôle de l'analyseur syntaxique est de déduire,

de cette séquence, la structure syntaxique d’un
programme.

ESPRIM Khouja Med Khairallah 8

 CH5. Analyse syntaxique

Rôle de l’analyseur syntaxique

➢ Analyseur lexical et analyseur syntaxique :
✓ Dans les langages de programmation impératifs,
les unités syntaxiques sont :
▪ Les variables et les constantes.

▪ Les expressions.

▪ Les instructions et les blocs d’instructions.

▪ Les déclarations.

▪ Les définitions de fonctions.

ESPRIM Khouja Med Khairallah 9

 CH5. Analyse syntaxique

Rôle de l’analyseur syntaxique

➢ Arbre syntaxique :
✓ L’analyseur syntaxique reconnaît la structure
syntaxique d’un programme et la représente de
manière appropriée à un traitement ultérieur par
d’autres modules du compilateur.
✓ Une représentation possible est un arbre
syntaxique qui peut être décoré ou transformé et
finalement traduit dans un langage assembleur
ou autre.
ESPRIM Khouja Med Khairallah 10
 CH5. Analyse syntaxique

Rôle de l’analyseur syntaxique

➢ Arbre syntaxique :
✓ Un arbre syntaxique possède un nœud racine,
des nœuds intérieurs et des feuilles (nœuds
terminaux).
✓ Les feuilles d’un arbre syntaxique sont les jetons
trouvés par l’analyseur lexicale.
✓ Si on lit ces feuilles de gauche à droite, on trouve
une séquence identique au texte saisi dans le
fichier source.
ESPRIM Khouja Med Khairallah 11
 CH5. Analyse syntaxique

Rôle de l’analyseur syntaxique

➢ Arbre syntaxique :
✓ Deux choses sont importantes pour former un
arbre syntaxique :
▪ Savoir comment les feuilles seront combinées
pour former la structure complète de l'arbre.
▪ Savoir comment les nœuds intérieurs seront
étiquetés.

ESPRIM Khouja Med Khairallah 12

 CH5. Analyse syntaxique

Rôle de l’analyseur syntaxique

➢ Détection des erreurs de syntaxe :
✓ En plus de découvrir la structure arborescente du
texte source, l’analyseur syntaxique doit aussi
détecter les portions de textes invalides en
signalant des erreurs de syntaxe.
✓ Exemples d’erreurs syntaxiques dans C :

▪ Oubli d’un point virgule.

▪ Oubli du parenthèse ouvrante après le for.

▪ Manque d’une expression après l’opérateur *.

ESPRIM Khouja Med Khairallah 13
 CH5. Analyse syntaxique

Rôle de l’analyseur syntaxique

➢ Détection des erreurs de syntaxe :

✓ Illustrons quelques exemples d’erreurs
syntaxiques en C :
▪ a = 5 + 6 // " ; " point virgule manquant

▪ for i = 5; i < 12; i++) // " ( " manquante

▪ a = b + c - 5 *; // expression manquante

▪ = 12 + 5; // identificateur manquant

▪ a = = 3; // expression invalide

ESPRIM Khouja Med Khairallah 14

 CH5. Analyse syntaxique

Rôle de l’analyseur syntaxique

➢ Outils pour l’analyse syntaxique :

✓ L’analyseur lexical se base sur les expressions
régulières et les automates finis déterministes
pour rechercher les jetons à partir du fichier
source.
✓ L’analyseur syntaxique utilise la grammaire du
langage pour combiner les jetons en unités
syntaxiques.
ESPRIM Khouja Med Khairallah 15
 CH5. Analyse syntaxique

Rôle de l’analyseur syntaxique

➢ Grammaires des langages de programmation :
✓ Les grammaires des langages de programmation
sont simples par rapport aux grammaires des
langages naturels.
✓ Les grammaires naturelles sont très sensibles au
contexte. Ce sont des grammaires contextuelles.
✓ Les grammaires des langages de programmation
sont caractérisées par le fait qu’elles sont « hors
contexte » (GHC).
ESPRIM Khouja Med Khairallah 16
 CH5. Analyse syntaxique

Rôle de l’analyseur syntaxique

➢ Grammaires hors contexte :

✓ Une grammaire hors contexte est une notation
récursive permettant de décrire des ensembles
de jetons et d’imposer une structure sur de tels
jetons.
✓ Cette notation peut, dans certains cas, se
traduire presque directement en programmes
récursifs.
ESPRIM Khouja Med Khairallah 17
 CH5. Analyse syntaxique

Rôle de l’analyseur syntaxique

➢ Grammaires hors contexte :
✓ Mais, le plus souvent, il convient d’utiliser un
automate à pile (analyseur syntaxique).
✓ Un automate à pile est identique à un automate,
sauf qu’il dispose d'une pile qui peut être utilisée
pour mémoriser certaines informations.
✓ La puissance de calcul des automates à piles
correspond aux langages hors contexte, soit
ceux qui peuvent être décrits par une GHC.
ESPRIM Khouja Med Khairallah 18
 CH5. Analyse syntaxique

Rôle de l’analyseur syntaxique

➢ Analyse des grammaires hors contexte :
✓ Nous allons voir deux façons différentes pour la
génération des automates à pile.
✓ Le premier d'entre eux, dite l’analyse LL (1), est
relativement simple, mais ne fonctionne que pour
une certaine catégorie restreinte de grammaires.
✓ L’analyse SLR, que nous présentons plus tard,
est plus complexe, mais accepte une large
classe de grammaires.
ESPRIM Khouja Med Khairallah 19
 CH5. Analyse syntaxique

Définition d'une grammaire

hors contexte

ESPRIM Khouja Med Khairallah 20

 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte
➢ Définition d’une GHC :
✓ Une grammaire hors contexte est un quadruple
G = (V, T, P, S) où :
▪ V est l’alphabet des "non terminaux";

▪ T est l’alphabet des "terminaux". V  T = .

▪ P est l’ensemble des "règles syntaxiques" ou

"règles de production";
▪ S est "l’axiome" (S  V).

ESPRIM Khouja Med Khairallah 21

 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte
➢ Explication de la définition d’une GHC :
✓ Une GHC permet de définir d’une manière
récursive plusieurs formes de phrases d’un
langage.
✓ Chaque forme de phrases est désignée par un
nom, appelé un "non terminal".
✓ Exemple : Dans la langue arabe, une phrase
peut être une phrase nominale (‫ )جملة إسمية‬ou une
phrase verbale (‫)جملة فعلية‬.
ESPRIM Khouja Med Khairallah 22
 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte
➢ Explication de la définition d’une GHC :
✓ L’alphabet V est donc un "méta-alphabet" : il
permet de décrire les formes de phrases.
✓ C’est pourquoi la condition "V  T = " est
imposée dans la définition.
✓ L'un des non terminaux est choisi pour désigner
le langage décrit par la grammaire.
✓ C'est ce qu'on appelle "l’axiome" ou "le symbole
de départ" de la grammaire. Il est noté "S".
ESPRIM Khouja Med Khairallah 23
 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte
➢ Explication de la définition d’une GHC :
✓ Les terminaux permettent de décrire les mots du
langage. Leur ensemble est noté T.
✓ Les formes de phrases du langage sont décrites
par un certain nombre de règles syntaxiques ou
règles de production. Leur ensemble est noté P.
✓ Une règle de production a la forme suivante :

A → X1…Xn
ESPRIM Khouja Med Khairallah 24
 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte

➢ Explication de la définition d’une GHC :

✓ Dans la règle « A → X1…Xn » :
▪ « A » est un "non terminal" : A  V.

▪ « Xi » est soit un "terminal", soit un "non

terminal" : Xi  V  T.
▪ La chaîne X1…Xn est alors un mot du langage
(V  T)*.

ESPRIM Khouja Med Khairallah 25

 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte
➢ Explication de la définition d’une GHC :
✓ La notation « A → X1…Xn » signifie que
l'ensemble dénoté par A contient les chaînes qui
peuvent être obtenues par la concaténation des
chaînes de l'ensemble dénoté par X1, …Xn.
✓ En absence de toute confusion probable, nous
allons assimiler un symbole non terminal avec
l'ensemble des chaînes qu‘il dénote.
ESPRIM Khouja Med Khairallah 26
 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte
➢ Explication de la définition d’une GHC :
✓ Exemples de règles de production :
▪ ‫فعل فاعل مفعول به → جملة فعلية‬

▪ ‫ضرب | صافح → فعل‬

▪ ‫عمر | زيد → فاعل‬

▪ ‫عمرا | زيدا → مفعول به‬

✓ On peut construire les phrases suivantes :

▪ ‫صافح زيد عمرا‬

ESPRIM Khouja Med Khairallah 27
 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte
➢ Explication de la définition d’une GHC :
‫صافح زيد زيدا‬
▪

▪ ‫ضرب عمر زيدا‬

✓ Les phrases suivantes sont incorrectes :

▪ ‫ضرب ضرب زيدا‬

▪ ‫زيد صافح زيدا‬

▪ ‫ضرب عمرا زيد‬

ESPRIM Khouja Med Khairallah 28

 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte

➢ Convention d’écriture :
✓ Les symboles "non terminaux" seront désignés
par des lettres majuscules : A, B, ... etc.
✓ Les symboles "terminaux" seront désignés par
des lettres minuscules : a, b, ... etc.
✓ L’axiome sera désigné par la lettre S.

ESPRIM Khouja Med Khairallah 29

 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte
➢ Exemples de grammaires :
✓ La production :
▪ S→a

génère l’ensemble {a}.

✓ Les deux productions :

▪ S→a

▪ S → aS

génère l’ensemble {a, aa, aaa, …} = a+.

ESPRIM Khouja Med Khairallah 30
 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte
➢ Exemples de grammaires :
✓ Les deux productions :
▪ S→

▪ S → aS

génère l’ensemble {, a, aa, aaa, …} = a*.

✓ Les GHC sont plus forts que les expressions
régulière.
✓ En fait, on a vu que le langage {anbn; n entier} ne
peut pas être décrit par une expression régulière.
ESPRIM Khouja Med Khairallah 31
 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte
➢ Exemples de grammaires :
✓ Ce pendant ce langage peut être décrit en
utilisant une GHC.
✓ Les deux productions :

▪ S→

▪ S → aSb

génère l’ensemble {, ab, a2b2, a3b3, …}.

✓ La GHC précédente permet donc d’engendrer le
langage {anbn; n entier}.
ESPRIM Khouja Med Khairallah 32
 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte
➢ Exemples de grammaires :
✓ Écrivons une GHC pour le langage {anbman; n et
m non nuls}.
✓ Les productions de cette grammaire sont :

▪ S → aSa

▪ S→M

▪ M→b

▪ M → bM

ESPRIM Khouja Med Khairallah 33

 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte
➢ Exemples de grammaires :
✓ Une notation simplificatrice est utilisée lorsque
toutes les parties droites d’un ensemble de
productions sont issues d’un même "non
terminal".
✓ Ces parties sont combinées dans une règle
unique, en utilisant le symbole de l’alternatif « | »
afin de les séparer.

ESPRIM Khouja Med Khairallah 34

 CH5. Analyse syntaxique

Définition d’une grammaire

hors contexte

➢ Exemples de grammaires :
✓ Dans cette notation, la grammaire précédente
serait écrite sous la forme suivante :
▪ S → M | aSa

▪ M → b | bM

ESPRIM Khouja Med Khairallah 35

 CH5. Analyse syntaxique

Comment écrire une grammaire

hors contexte

ESPRIM Khouja Med Khairallah 36

 CH5. Analyse syntaxique

Comment écrire une

grammaire hors contexte ?
➢ GHC pour langages réguliers :
✓ Comme a été évoqué ci-dessus, une ER peut
être réécrit en utilisant une GHC.
✓ Une ER nécessite une ou deux règles de
productions.
✓ La construction est montrée dans le tableau
suivant (voir page qui suit).
✓ Par conséquent, tout langage régulier peut être
décrit en utilisant une GHC.
ESPRIM Khouja Med Khairallah 37
 CH5. Analyse syntaxique

Comment écrire une

grammaire hors contexte ?

Forme de l’ER Productions

 S→
a S→a
uv S → UV
u+v S→U|V
u* S →  | US
u+ S → U | US
ESPRIM Khouja Med Khairallah 38
 CH5. Analyse syntaxique

Comment écrire une

grammaire hors contexte ?
➢ GHC pour langages non réguliers :
✓ Cependant, comment écrire une GHC pour un
langage non régulier ?
✓ Exemple :

▪ Langages d'expressions arithmétiques.

✓ Voici une GHC pour un tel langage :

▪ Exp → Exp + Exp

▪ Exp → Exp - Exp

ESPRIM Khouja Med Khairallah 39
 CH5. Analyse syntaxique

Comment écrire une

grammaire hors contexte ?

➢ GHC pour langages non réguliers :

✓ Exp → Exp * Exp
✓ Exp → Exp / Exp

✓ Exp → Number

✓ Exp → (Exp)

✓ Exp → - Exp

ESPRIM Khouja Med Khairallah 40

 CH5. Analyse syntaxique

Comment écrire une

grammaire hors contexte ?
➢ GHC pour langages non réguliers :
✓ La plupart des constructions de langages de
programmation sont facilement exprimées par
des GHC.
✓ Lors de la rédaction d'une grammaire pour un
langage de programmation, on commence
normalement par diviser les constructions du
langage en différentes "catégories syntaxiques".
ESPRIM Khouja Med Khairallah 41
 CH5. Analyse syntaxique

Comment écrire une

grammaire hors contexte ?
➢ GHC pour langages non réguliers :
✓ Une catégorie syntaxique est un sous langage
qui définit un concept particulier. Exemples :
▪ Les expressions : utilisées pour exprimer des
calculs.
▪ Les instructions : utilisées pour exprimer des
séquences d’actions.
▪ Les déclarations : utilisées pour exprimer des
propriétés des identificateurs du programme.
ESPRIM Khouja Med Khairallah 42
 CH5. Analyse syntaxique

Comment écrire une

grammaire hors contexte ?
➢ GHC pour langages non réguliers :
✓ Chaque catégorie syntaxique est désignée par
un "non terminal principal".
✓ Par exemple, "Exp" pour les expressions, "Instr"
pour les instructions et "Decl" pour les
déclarations.
✓ La description d’une catégorie syntaxique peut
nécessiter un ou plusieurs "non terminal
secondaires".
ESPRIM Khouja Med Khairallah 43
 CH5. Analyse syntaxique

Comment écrire une

grammaire hors contexte ?
➢ GHC pour langages non réguliers :
✓ Exemple du Français :
▪ GN → Article Nom | Nom

▪ Article → Le | La | L’ | Les | Un | Une

▪ Nom → stylo | crayon | table | pomme | âme

✓ Des phrases possibles :

▪ Le stylo, Le crayon, La table, Les jeux, Une

pomme, Un crayon, L’âme, Un âme, …etc.
ESPRIM Khouja Med Khairallah 44
 CH5. Analyse syntaxique

Comment écrire une

grammaire hors contexte ?
➢ GHC pour langages non réguliers :
✓ En outre, les productions pour une catégorie
syntaxique peuvent se référer à des "non
terminaux" d’autres catégories syntaxiques.
✓ Par exemple, une déclaration peut contenir une
expression.
✓ Il est alors possible que certaines productions
pour les instructions utilisent le "non terminal"
principal pour les expressions.
ESPRIM Khouja Med Khairallah 45
 CH5. Analyse syntaxique

Comment écrire une

grammaire hors contexte ?

➢ GHC pour langages non réguliers :

✓ Prenons comme exemple, quelques instructions
du Turbo Pascal :
▪ Instr → Ident := Exp

▪ Instr → Instr ; Instr

▪ Instr → IF Exp THEN Instr

▪ Instr → IF Exp THEN Instr ELSE Instr

ESPRIM Khouja Med Khairallah 46

 CH5. Analyse syntaxique

Dérivation

ESPRIM Khouja Med Khairallah 47

 CH5. Analyse syntaxique

Dérivation

➢ La notion de dérivation :
✓ L'idée de dérivation est de considérer les
productions comme des "règles de réécriture".
✓ Chaque fois qu’on a un "non terminal", on peut le
remplacer par un terme figurant dans la partie
droite de toute production dans laquelle le non
terminal apparaît sur le côté gauche.

ESPRIM Khouja Med Khairallah 48

 CH5. Analyse syntaxique

Dérivation
➢ La notion de dérivation :
✓ On peut faire ceci n'importe où dans une suite de
symboles (terminaux ou non terminaux) et on le
répète jusqu’à n’avoir que des terminaux dans la
partie gauche.
✓ La séquence de terminaux est une suite de mots
du langage défini par la GHC.
✓ Formellement, on défini la dérivation  par les
trois règles suivantes :
ESPRIM Khouja Med Khairallah 49
 CH5. Analyse syntaxique

Dérivation
➢ La notion de dérivation :
▪    s’il existe une production  → 
▪   
▪    s’il existe une dérivation    et une
dérivation   
✓ Les symboles ,  et  sont des mots sur (V  T)*.
✓ La première règle stipule que l'utilisation d'une
production comme une règle de réécriture est une
dérivation (en une étape).
ESPRIM Khouja Med Khairallah 50
 CH5. Analyse syntaxique

Dérivation
➢ La notion de dérivation :
✓ La deuxième règle indique que la dérivation est
une relation réflexive, c-à-d qu’une suite dérive
d’elle-même.
✓ La troisième règle exprime la transitivité de la
dérivation, c-à-d qu’une séquence de dérivations
est également une dérivation.
✓ On peut utiliser la dérivation pour définir
formellement le langage généré par une GHC.
ESPRIM Khouja Med Khairallah 51
 CH5. Analyse syntaxique

Dérivation

➢ Définition formelle de la dérivation :

✓ Soit G = (V, T, P, S) une GHC.
✓ Une "Forme" sur G est un élément  de (V  T)*.

✓ Étant données deux formes  et ’ sur G.

✓ On dit que la forme ’ "dérive en une étape" de la

forme , et l’on écrit   ’, si :
▪  (A → )  P (une production);
▪  u, v  (V  T)* tels que :  = uAv et ’ = uv.
ESPRIM Khouja Med Khairallah 52
 CH5. Analyse syntaxique

Dérivation
➢ Définition formelle de la dérivation :
✓ On dit que la forme ’ "dérive en k étapes" de la
forme , et l’on écrit  k ’, si  (k + 1) formes
0, …, k telles que :
▪ 0 = .

▪ k = ’.

▪  i  {0, …, k - 1} : i  i+1.

✓ On écrit aussi  * ’, si l’on ne veut pas

préciser le nombre d’étapes de dérivation.
ESPRIM Khouja Med Khairallah 53
 CH5. Analyse syntaxique

Dérivation

➢ Explication de la dérivation :
✓ La forme « ’ » "dérive en une étape" de la forme
«  » si et seulement, il existe une règle de
production « A →  », telle que la substitution du
symbole « A » par la forme «  » dans la forme
«  » produit exactement la forme « ’ ».
✓ La dérivation en plusieurs étapes découle de la
répétition un certain nombre de fois du processus
de dérivation en une seule étape.
ESPRIM Khouja Med Khairallah 54
 CH5. Analyse syntaxique

Dérivation

➢ Exemple :
✓ Considérons la GHC G sur {a, b, c} définie par les
productions suivantes :
▪ S → R | aSc

▪ R →  | RbR

✓ S, R, aSc, aRc, RbR et  sont des formes sur G.

✓ La forme « aRc » dérive en une étape de la

forme « aSc ».
ESPRIM Khouja Med Khairallah 55
 CH5. Analyse syntaxique

Dérivation

➢ Exemple (suite) :
✓ La forme « aaaacccc » dérive en 5 étapes de la
forme « aSc ». En effet :
▪ aSc  aaScc (S → aSc)

▪ aaScc  aaaSccc (S → aSc)

▪ aaaSccc  aaaaScccc (S → aSc)

▪ aaaaScccc  aaaaRcccc (S → R)

▪ aaaaRcccc  aaaacccc (R → )

ESPRIM Khouja Med Khairallah 56

 CH5. Analyse syntaxique

Dérivation

➢ Dérivation la plus à gauche et dérivation la plus

à droite :
✓ Une dérivation dans laquelle on réécrit toujours le
non terminal le plus à gauche est appelée
"dérivation la plus à gauche".
✓ De même, une dérivation dans laquelle on réécrit
toujours le non terminal le plus à droite est dite
"dérivation la plus à droite".

ESPRIM Khouja Med Khairallah 57

 CH5. Analyse syntaxique

Dérivation
➢ Dérivation la plus à gauche et dérivation la plus
à droite :
✓ Exemple :

▪ Soit la GHC sur {a, b, c } dont les productions

sont :
❖ S → aBc | aCb | aAc

❖ A → BC

❖ B → aS | cS | 

❖ C → aB | bB | 
ESPRIM Khouja Med Khairallah 58
 CH5. Analyse syntaxique

Dérivation
➢ Dérivation la plus à gauche et dérivation la plus
à droite :
✓ Dérivation la plus à gauche du mot w = acabbc :

▪ S  aBc (S → aBc)
▪ aBc  acSc (B → cS)
▪ acSc  acaCbc (S → aCb)
▪ acaCbc  acabBbc (C → bB)
▪ acabBbc  acabbc (B → )
ESPRIM Khouja Med Khairallah 59
 CH5. Analyse syntaxique

Dérivation
➢ Dérivation la plus à gauche et dérivation la plus
à droite :
✓ Dérivation la plus à droite du mot w = acabbc :

▪ S  aAc (S → aBc)
▪ aAc  aBCc (A → BC)
▪ aBCc  aBbBc (C → bB)
▪ aBbBc  aBbc (B → )
▪ aBbc  acSbc (B → cS)
▪ acSbc  acaCbbc (S → aCb)
ESPRIM Khouja Med Khairallah 60
 CH5. Analyse syntaxique

Dérivation
➢ Dérivation la plus à gauche et dérivation la plus
à droite :
✓ Dérivation la plus à droite du mot w = acabbc :

▪ acaCbbc  acabbc (C → )

ESPRIM Khouja Med Khairallah 61

 CH5. Analyse syntaxique

Langage généré
par une GHC

ESPRIM Khouja Med Khairallah 62

 CH5. Analyse syntaxique

Langage généré par une GHC

➢ Définition :
✓ Soit G = (V, T, P, S) une GHC.
✓ Le "langage généré par G" est formé par tous les
mots de T* dérivables en plusieurs étapes à partir
de l’axiome S de G.
✓ On note ce langage par L(G).
✓ Formellement, L(G) = {w  T* | S * w}.

ESPRIM Khouja Med Khairallah 63

 CH5. Analyse syntaxique

Langage généré par une GHC

➢ Exemples :
✓ Soient les GHC suivantes :
▪ G1 définie sur T = {a} par les productions :
S →  et S → aS.
▪ G2 définie sur T = {a, b} par les productions :
S → aSb | .
▪ G3 définie sur T = {a, b} par les productions :
S → aSb | bSa | SS | ab | ba | .
ESPRIM Khouja Med Khairallah 64
 CH5. Analyse syntaxique

Langage généré par une GHC

➢ Exemples :
✓ On a :
▪ L(G1) = {, a, aa, aaa, …} = {an; n entier}.

▪ L(G2) = {an bn; n entier}.

▪ L(G3) = {w  {a, b}*; |w|a = |w|b}.

ESPRIM Khouja Med Khairallah 65

 CH5. Analyse syntaxique

Arbres de dérivation et
grammaires ambiguës

ESPRIM Khouja Med Khairallah 66

 CH5. Analyse syntaxique

Arbres de dérivation et GHC

ambiguës
➢ Arbre de dérivation :
✓ On appelle "arbre de dérivation" ou "arbre
syntaxique", tout arbre tel que :
▪ La racine est l'axiome S;

▪ Les feuilles sont des terminaux ou ;

▪ Les noeuds internes sont des non terminaux;

▪ Les fils d'un nœud N sont 0, …, k si et

seulement si «N → 0…k» est une production.

ESPRIM Khouja Med Khairallah 67

 CH5. Analyse syntaxique

Arbres de dérivation et GHC

ambiguës
➢ Arbre de dérivation :
✓ Le parcours préfixe d’un tel arbre donne un mot
du langage généré par la GHC considérée.
✓ Exemple : soit la GHC dont les productions sont :

▪ S → aTb

▪ S→c

▪ T → cSS

▪ T→S

ESPRIM Khouja Med Khairallah 68

 CH5. Analyse syntaxique

Arbres de dérivation et GHC

ambiguës
➢ Arbre de dérivation :
✓ Un arbre de dérivation pour le mot accacbb est :

ESPRIM Khouja Med Khairallah 69

 CH5. Analyse syntaxique

Arbres de dérivation et GHC

ambiguës
➢ GHC ambiguë :
✓ Définition :
▪ Une GHC G est dite "ambiguë", s'il existe un
mot w de L(G) ayant plusieurs arbres de
dérivation distincts.
✓ Exemple :

▪ La grammaire définie par les productions :

E → a | b | c, E → E + E et E → E * E est une
GHC ambiguë.
ESPRIM Khouja Med Khairallah 70
 CH5. Analyse syntaxique

Arbres de dérivation et GHC

ambiguës
➢ GHC ambiguë :
E

E + E

a E * E

b c

Un arbre syntaxique
pour a + b * c
ESPRIM Khouja Med Khairallah 71
 CH5. Analyse syntaxique

Arbres de dérivation et GHC

ambiguës
➢ GHC ambiguë :
E

E * E

E + E c

a b
Un autre arbre syntaxique
pour a + b * c
ESPRIM Khouja Med Khairallah 72
 CH5. Analyse syntaxique

Arbres de dérivation et GHC

ambiguës
➢ Dérivabilité et arbre de dérivation :
✓ Soit G une grammaire hors contexte définie sur
l’alphabet A.
✓ Un mot w de A* est dérivable à partir de l’axiome
S en n étapes, si et seulement s’il existe un arbre
de dérivation de w dans G.
✓ Par conséquent, L(G) est l’ensemble des mots w
pour lesquels il y a un arbre de dérivation dans
G.
ESPRIM Khouja Med Khairallah 73
 CH5. Analyse syntaxique

Langages
hors contexte

ESPRIM Khouja Med Khairallah 74

 CH5. Analyse syntaxique

Langages hors contexte

➢ Définition :
✓ Un langage est dis "hors contexte" ou
"algébrique", s’il est généré par une grammaire
hors contexte.
✓ Autrement dis, L est algébrique si et seulement, il
existe une GHC G telle que L = L (G).
✓ Exemples :
▪ {an, n entier}, {anbn, n entier} et {w  {a, b}*,
|w|a = |w|b} sont des langages algébriques.

ESPRIM Khouja Med Khairallah 75

 CH5. Analyse syntaxique

Langages hors contexte

➢ Théorème 1 :
✓ Tout langage régulier est algébrique.
✓ La réciproque est fausse : il existe des langages
algébriques non réguliers.

ESPRIM Khouja Med Khairallah 76

 CH5. Analyse syntaxique

Langages hors contexte

➢ Théorème 2 :
✓ La classe des langages hors contexte est stable
par les opérations régulières :
▪ Réunion.

▪ Concaténation.

▪ Étoile (fermeture de Kleene).

ESPRIM Khouja Med Khairallah 77

 CH5. Analyse syntaxique

Precedence
d'opérateurs

ESPRIM Khouja Med Khairallah 78

 CH5. Analyse syntaxique

Précédence d’opérateurs
➢ Ambiguitë des grammaires d’opérateurs :
✓ La grammaire de la page 70 est une grammaire
d’opérateurs ambiguë.
✓ Un moyen possible de résoudre l'ambiguïté est
d'utiliser des règles de priorité au cours de
l’analyse syntaxique pour pouvoir effectuer un
choix parmi les arbres de dérivation possibles.
✓ De nombreux générateurs d’analyseurs
syntaxiques optent pour cette approche.
ESPRIM Khouja Med Khairallah 79
 CH5. Analyse syntaxique

Précédence d’opérateurs

➢ Ambiguitë des grammaires d’opérateurs :

✓ Cependant, certaines méthodes d’analyse
syntaxique exigent des grammaires non
ambiguës.
✓ Pour que ces méthodes soient appliquées, il faut
leur donner des grammaires non ambiguës.
✓ Cela est possible en exprimant les priorités des
opérateurs dans la grammaire elle-même.

ESPRIM Khouja Med Khairallah 80

 CH5. Analyse syntaxique

Précédence d’opérateurs
➢ Quelques concepts sur les opérateurs :
✓ Un opérateur  est "associatif à gauche", si
l'expression « a  b  c » doit être évaluée de
gauche à droite : a  b  c = (a  b)  c.
✓ Un opérateur  est "associatif à droite", si
l'expression « a  b  c » doit être évaluée de
droite à gauche : a  b  c = a  (b  c).
✓ Un opérateur  est "non associatif", si les
expressions de la forme a  b  c sont illégales.
ESPRIM Khouja Med Khairallah 81
 CH5. Analyse syntaxique

Précédence d’opérateurs
➢ Exemples :
✓ Dans le langage C :
▪ +, -, *, /, %, sont associatifs à gauche.

▪ Les opérateurs d’affectation et ?: sont

associatifs à droite.
✓ Dans le langage pascal, l’opérateur < est non
associatif (on ne peut pas écrire a < b < c).
✓ En python et C, l’opérateur < est associatif.

ESPRIM Khouja Med Khairallah 82

 CH5. Analyse syntaxique

Précédence d’opérateurs

➢ Associativité des opérateurs :

✓ Étant donnée une grammaire d’opérateurs de la
forme suivante :
▪ Expr → Expr  Expr

▪ Expr → Const | Ident

✓ Elle est ambiguë (l’expression « 2  3  4 » a

deux arbres de dérivation distincts).
✓ Comment la rendre non ambiguë ?

ESPRIM Khouja Med Khairallah 83

 CH5. Analyse syntaxique

Précédence d’opérateurs

➢ Associativité des opérateurs :

✓ Premier cas : l’opérateur  est associatif à
gauche.
✓ On transforme les productions comme suit :

▪ Expr → Expr  Expr’

▪ Expr → Expr’

▪ Expr’ → Const | Ident

ESPRIM Khouja Med Khairallah 84

 CH5. Analyse syntaxique

Précédence d’opérateurs
➢ Associativité des opérateurs :
✓ Exemple : comment analyser 2 + 3 + 4 ?

ESPRIM Khouja Med Khairallah 85

 CH5. Analyse syntaxique

Précédence d’opérateurs

➢ Associativité des opérateurs :

✓ Deuxième cas : l’opérateur  est associatif à
droite.
✓ On transforme les productions comme suit :

▪ Expr → Expr’  Expr

▪ Expr → Expr’

▪ Expr’ → Const | Ident

ESPRIM Khouja Med Khairallah 86

 CH5. Analyse syntaxique

Précédence d’opérateurs
➢ Associativité des opérateurs :
✓ Exemple : comment analyser a = b = c ?
E

E’ = E

a E’ = E

b E’

c
ESPRIM Khouja Med Khairallah 87
 CH5. Analyse syntaxique

Précédence d’opérateurs

➢ Associativité des opérateurs :

✓ Troisième cas : l’opérateur  est non associatif.
✓ On transforme les productions comme suit :

▪ Expr → Expr’  Expr’

▪ Expr → Expr’

▪ Expr’ → Const | Ident

ESPRIM Khouja Med Khairallah 88

 CH5. Analyse syntaxique

Précédence d’opérateurs
➢ Associativité des opérateurs :
✓ Exemple : voyons si l’on peut analyser
l’expression 2 < 3 < 4 ?

E
Échec de l’analyse
E’ < E’ syntaxique
2 3

ESPRIM Khouja Med Khairallah 89

 CH5. Analyse syntaxique

Précédence d’opérateurs

➢ Priorité des opérateurs :

✓ Le mélange d’opérateurs de même priorité et de
même associativité ne pose aucun problème.
✓ Exemple :
▪ Considérons les opérateurs + et – binaires.
▪ Ils ont la même priorité et ils sont associatifs à
gauche.
▪ Construisons une GHC non ambiguë pour ces
deux opérateurs.
ESPRIM Khouja Med Khairallah 90
 CH5. Analyse syntaxique

Précédence d’opérateurs

➢ Priorité des opérateurs :

✓ Une GHC non ambiguë est la suivante :
▪ Expr → Expr + Expr1
▪ Expr → Expr - Expr1
▪ Expr → Expr1
▪ Expr1 → Const | Ident
✓ Les opérateurs de même priorité doivent avoir la
même associativité, sinon la grammaire serait
ambiguë.
ESPRIM Khouja Med Khairallah 91
 CH5. Analyse syntaxique

Précédence d’opérateurs

➢ Priorité des opérateurs :

✓ Exemple :
▪ Expr → Expr + Expr1
▪ Expr → Expr1  Expr
▪ Expr → Expr1
▪ Expr1 → Const | Ident
✓ Cette grammaire est ambiguë si les opérateurs 
et + ont une même priorité et des associativités
différentes.
ESPRIM Khouja Med Khairallah 92
 CH5. Analyse syntaxique

Précédence d’opérateurs

➢ Priorité des opérateurs :

✓ On ne peut même dériver le mot 2 + 2  2 si par
exemple l’opérateur + est associatif à gauche et
l’opérateur  est associatif à droite (ou l’inverse).
✓ En général, il n’existe pas une solution évidente
pour rendre de telles grammaires non ambiguës.
✓ C’est pourquoi les langages de programmation
imposent que les opérateurs de même priorité
doivent avoir la même associativité.
ESPRIM Khouja Med Khairallah 93
 CH5. Analyse syntaxique

Précédence d’opérateurs

➢ Priorité des opérateurs :

✓ On a également besoin de manipuler des
opérateurs de priorités différentes.
✓ Pour confectionner une grammaire qui répond à
de telles situations, on utilise un non terminal
pour chaque niveau de priorité.

ESPRIM Khouja Med Khairallah 94

 CH5. Analyse syntaxique

Précédence d’opérateurs

➢ Priorité des opérateurs :

✓ L'idée est que si une expression utilise un
opérateur d'un certain niveau de priorité, alors
ses sous-expressions ne peuvent pas utiliser les
opérateurs de moindre priorité (à moins que
ceux-ci sont écrites entre parenthèses).
✓ Ainsi, 2 + 3 * 4 sera reconnu comme 2 + (3 * 4) si
* est plus prioritaire à +.

ESPRIM Khouja Med Khairallah 95

 CH5. Analyse syntaxique

Précédence d’opérateurs
➢ Priorité des opérateurs :
✓ Par conséquent, les règles de productions issues
d’un non terminal et correspondant à un niveau
de priorité se réfèrent seulement à des non
terminaux qui correspondent à la même priorité
ou aux niveaux de priorité supérieurs.
✓ Exemple : construisons une grammaire hors
contexte pour les 4 opérateurs arithmétiques
usuels +, -, * et /.
ESPRIM Khouja Med Khairallah 96
 CH5. Analyse syntaxique

Précédence d’opérateurs
➢ Priorité des opérateurs :
✓ On aura :
▪ Un non terminal pour + et -.

▪ Un non terminal pour * et /.

▪ Un non terminal pour les parenthèses.

✓ Ordre de priorité croissante : « + - », « * / » puis

les parenthèses.
✓ Associativité des opérateurs : gauche.

ESPRIM Khouja Med Khairallah 97

 CH5. Analyse syntaxique

Précédence d’opérateurs
➢ Priorité des opérateurs :
✓ Une GHC non ambiguë pour les 4 opérateurs
arithmétiques usuels est donc :
▪ Expr → Expr + Expr1 | Expr - Expr1 | Expr1

▪ Expr1 → Expr1 * Expr2 | Expr1 / Expr2 | Expr2

▪ Expr2 → ( Expr2 ) | Const | Ident

✓ Donnons l’arbre syntaxique de l’expression

arithmétique « 2 + 3 * 4 ».

ESPRIM Khouja Med Khairallah 98

 CH5. Analyse syntaxique

Précédence d’opérateurs

Arbre de
dérivation
pour 2+3*4

ESPRIM Khouja Med Khairallah 99

 CH5. Analyse syntaxique

Autres sources
d'ambiguitë

ESPRIM Khouja Med Khairallah 100

 CH5. Analyse syntaxique

Autres sources d’ambiguïté

➢ Problème de if-then-else :
✓ Considérons la GHC suivante (Pascal) :
▪ Instr → Ident := Expr

▪ Instr → Instr ; Instr

▪ Instr → IF Expr THEN Instr ELSE Instr

▪ Instr → IF Expr THEN Instr

✓ Considérons l’instruction suivante :

▪ IF p THEN IF q THEN S1 ELSE S2

ESPRIM Khouja Med Khairallah 101

 CH5. Analyse syntaxique

Autres sources d’ambiguïté

➢ Problème de if-then-else :
✓ L’instruction précédente a deux arbres de
dérivation distincts :
✓ Première dérivation :
▪ Instr  IF Expr THEN Instr  IF p THEN Instr
 IF p THEN IF Expr THEN Instr ELSE Instr 
IF p THEN IF q THEN Instr ELSE Instr  IF p
THEN IF q THEN S1 ELSE Instr  IF p THEN
IF q THEN S1 ELSE S2
ESPRIM Khouja Med Khairallah 102
 CH5. Analyse syntaxique

Autres sources d’ambiguïté

➢ Problème de if-then-else :
✓ Deuxième dérivation :
▪ Instr  IF Expr THEN Instr ELSE Instr  IF p
THEN Instr ELSE Instr  IF p THEN IF Expr
THEN Instr ELSE Instr  IF p THEN IF q THEN
Instr ELSE Instr  IF p THEN IF q THEN S1
ELSE Instr  IF p THEN IF q THEN S1 ELSE
S2
ESPRIM Khouja Med Khairallah 103
 CH5. Analyse syntaxique

Autres sources d’ambiguïté

➢ Problème de if-then-else :
✓ Comment peut-on faire pour rendre une telle
grammaire non ambiguë ?
✓ On peut pouvons traiter « si-alors-sinon » comme
des opérateurs associatifs à droite, ceci pour
faire correspondre un « sinon » au « si-alors » le
plus proche sans correspondant.

ESPRIM Khouja Med Khairallah 104

 CH5. Analyse syntaxique

Autres sources d’ambiguïté

➢ Problème de if-then-else :
✓ Toutefois, les transformations indiquées dans la
section « Précédence des opérateurs » ne
peuvent être appliquées directement à la
grammaire précédente, car les productions n’ont
pas la bonne forme.
✓ Mais, quand un « si » et un « sinon » se
correspondent, tous les « si » qui apparaissent
entre ce « si-sinon », doivent avoir des « sinon ».
ESPRIM Khouja Med Khairallah 105
 CH5. Analyse syntaxique

Autres sources d’ambiguïté

➢ Problème de if-then-else :
✓ Par conséquent, on fera deux non terminaux :
▪ Un non terminal pour les conditionnelles avec
un « sinon ».
▪ Un non terminal pour les conditionnelles sans
« sinon ».
▪ Le résultat est montré dans la grammaire
suivante.
ESPRIM Khouja Med Khairallah 106
 CH5. Analyse syntaxique

Autres sources d’ambiguïté

➢ Problème de if-then-else :
▪ Instr → Instr1 ; Instr | Instr1
▪ Instr1 → InstrAvec | InstrSans
▪ InstrAvec → IF Expr THEN InstrAvec ELSE
InstrAvec
▪ InstrAvec → Ident := Expr
▪ InstrSans → IF Expr THEN InstrAvec ELSE
InstrSans
▪ InstrSans → IF Expr THEN Expr1
ESPRIM Khouja Med Khairallah 107
 CH5. Analyse syntaxique

Autres sources d’ambiguïté

➢ Problème de if-then-else :
✓ Cette grammaire résout également l'associativité
de la virgule (droite) et la priorité de « si » sur la
virgule.
✓ Une alternative à la réécriture des grammaires
pour résoudre l'ambiguïté est d'utiliser une
grammaire ambiguë, puis résoudre les conflits en
utilisant des règles de priorité au cours de la
phase de l'analyse syntaxique.
ESPRIM Khouja Med Khairallah 108
 CH5. Analyse syntaxique

Autres sources d’ambiguïté

➢ Problème de if-then-else :
✓ Tous les cas d'ambiguïté doivent être traités avec
soin : il ne suffit pas d’éliminer l'ambiguïté, mais
on doit le faire d'une manière à aboutir à la
structure de dérivation souhaitée.
✓ Les deux exemples de grammaires pour les
opérateurs arithmétiques et les « si-alors-sinon »,
nous ont montré qu’en général, les structures de
dérivation sont très différentes.
ESPRIM Khouja Med Khairallah 109
 CH5. Analyse syntaxique

Les techniques
d'analyse syntaxique

ESPRIM Khouja Med Khairallah 110

 CH5. Analyse syntaxique

Les techniques d’analyse

syntaxique
➢ Techniques d’analyse syntaxique :
✓ On peut construire un analyseur syntaxique à
partir de n’importe quelle grammaire.
✓ Cependant, les grammaires utilisées en pratique
ont une forme spéciale.
✓ Pour toute grammaire hors contexte, il existe un
analyseur syntaxique qui prend un temps d’au
plus O(n3) pour analyser une chaîne formée de n
unités lexicales (Algorithme d’Early).
ESPRIM Khouja Med Khairallah 111
 CH5. Analyse syntaxique

Les techniques d’analyse

syntaxique
➢ Techniques d’analyse syntaxique :
✓ Dans le cadre des langages de programmation,
les analyseurs syntaxiques réalisent presque
toujours un parcours gauche-droite du texte
d’entrée et prennent leurs décisions en
considérant une seule unité lexicale.
✓ La majorité des méthodes d’analyse syntaxique
tombent dans une des deux classes appelées
"descendante" et "ascendante".
ESPRIM Khouja Med Khairallah 112
 CH5. Analyse syntaxique

Les techniques d’analyse

syntaxique
➢ Techniques d’analyse syntaxique :
✓ Dans une méthode d’analyse syntaxique
descendante, la construction de l’arbre de
dérivation débute à la racine et descend vers les
feuilles, c’est-à-dire, de l’axiome aux lexèmes.
✓ Dans une méthode d’analyse syntaxique
ascendante, la construction de l’arbre de
dérivation commence des feuilles et remonte à la
racine, donc, des lexèmes à l’axiome.
ESPRIM Khouja Med Khairallah 113
 CH5. Analyse syntaxique

Les techniques d’analyse

syntaxique
➢ Avantages et inconvénients des tachniques :
✓ Les analyseurs descendants sont très faciles à
implémenter par des programmes récursifs, mais
ne manipulent qu’une classe restreinte de
grammaires hors contexte.
✓ Les analyseurs ascendants manipulent une
classe plus large de grammaires hors contexte,
mais un peu difficile à implémenter à la main.
Cependant, il existe des outils logiciels pour
réaliser automatiquement de tels analyseurs.
ESPRIM Khouja Med Khairallah 114
 CH5. Analyse syntaxique

Analyse syntaxique
descendante

ESPRIM Khouja Med Khairallah 115

 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Exemple :
✓ Considérons la GHC suivante :
▪ S → aSbT (1)
▪ S → cT (2)
▪ S→d (3)
▪ T→c (4)
▪ T → bS (5)

ESPRIM Khouja Med Khairallah 116

 CH5. Analyse syntaxique

Analyse syntaxique
descendante

➢ Exemple :
✓ Prenons le mot « w = accbbadbc ».
✓ Nous allons calculer la dérivation la plus à
gauche du mot w.
✓ On part de l’arbre contenant la racine étiqueté
par l’axiome de la grammaire « S ».

ESPRIM Khouja Med Khairallah 117

 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Paramètres de l’algorithme d’analyse :
✓ L’algorithme manipule trois entités :
▪ Une "forme" représentant en quelques sortes
"une approximation possible de l’analyse".
▪ La "chaîne d’entrée".

▪ Deux "pointeurs" : pf qui pointe vers la forme

et pt qui pointe vers la chaîne d’entrée.

ESPRIM Khouja Med Khairallah 118

 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Initialisations :
✓ Au départ, la forme est l’axiome « S » de la
grammaire auquel on ajoute à la fin un marquer
de fin de « $ ». On partira donc de l’état initial :
▪ Forme = « S$ ».

▪ Chaîne = « accbbadbc$ ».

▪ pf pointe vers Forme et pt pointe Chaîne.

ESPRIM Khouja Med Khairallah 119

 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Itération (1) :
✓ On lit le premier caractère dans la chaîne
d’entrée : « a ».
✓ On développe le symbole non terminal « S » :

▪ La S-production qui débute avec un « a » est

la production (1) qui est « S → aSbT ».
✓ On crée les fils de « S » : 4 nœuds étiquetés
respectivement par « a », « S », « b » et « T ».
ESPRIM Khouja Med Khairallah 120
 CH5. Analyse syntaxique

Analyse syntaxique
descendante

pf
S$
accbbadbc$
a S b T
pt

ESPRIM Khouja Med Khairallah 121

 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Itération (2) :
✓ On lit le deuxième caractère dans la chaîne
d’entrée : « c ».
✓ On cherche le non terminal le plus à gauche
parmi les fils qui viennent d’être crées : « S ».
✓ La S-production qui débute avec un « c » est la
production (2) qui est « S → cT ».
✓ On crée les fils de « S » : 2 nœuds étiquetés
respectivement par « c » et « T ».
ESPRIM Khouja Med Khairallah 122
 CH5. Analyse syntaxique

Analyse syntaxique
descendante
pf
S$
accbbadbc$
a S b T
pt
c T

ESPRIM Khouja Med Khairallah 123

 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Itération (3) :
✓ On lit le 3 ème caractère dans la chaîne d’entrée :
« c ».
✓ On cherche le non terminal le plus à gauche
parmi les fils qui viennent d’être crées : « T ».
✓ La T-production qui débute avec un « c » est la
production (4) qui est « T → c ».
✓ On crée le fils de « T » : un nœud étiqueté par la
lettre « c ».
ESPRIM Khouja Med Khairallah 124
 CH5. Analyse syntaxique

Analyse syntaxique
descendante

S$
pf
accbbadbc$
a S b T
pt
c T

c
ESPRIM Khouja Med Khairallah 125
 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Itération (4) :
✓ On lit le 4 ème caractère dans la chaîne d’entrée :
« b ».
✓ Pas de terminal parmi les fils qui viennent d’être
crées, donc on cherche un non terminal parmi les
ancêtres du nœud fils : il y en a un qui est « T ».
✓ Mais, avant ce « T », il y a un terminal « b » qui
concorde avec le caractère couramment lu.
✓ On avance à la fois les deux pointeurs pf et pt.
ESPRIM Khouja Med Khairallah 126
 CH5. Analyse syntaxique

Analyse syntaxique
descendante

pf S$
accbbadbc$
a S b T
pt
c T

c
ESPRIM Khouja Med Khairallah 127
 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Itération (5) :
✓ On lit le 5 ème caractère dans la chaîne d’entrée :
« b ».
✓ On développe le non terminal « T ».

✓ La T-production qui débute avec un « b » est la

production (5) : « T → bS ».
✓ On crée les fils de « T » : 2 nœuds étiquetés
respectivement par « b » et « S ».

ESPRIM Khouja Med Khairallah 128

 CH5. Analyse syntaxique

Analyse syntaxique
descendante

S$
pf accbbadbc$
a S b T
pt
c T
b S
c
ESPRIM Khouja Med Khairallah 129
 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Itération (6) :
✓ On lit le 6 ème caractère dans la chaîne d’entrée :
« a ».
✓ On développe le non terminal « S » (le fils
immédiat de « T » le plus à gauche).
✓ La S-production qui débute avec un « a » est la
production (1) : « S → aSbT ».
✓ On crée les fils de « S » : 4 nœuds étiquetés
respectivement par « a », « S », « b » et « T ».
ESPRIM Khouja Med Khairallah 130
 CH5. Analyse syntaxique

Analyse syntaxique
descendante
S$
pf
a S b T accbbadbc$

c T
pt
b S
c
a S b T
ESPRIM Khouja Med Khairallah 131
 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Itération (7) :
✓ On lit le 7 ème caractère dans la chaîne d’entrée :
« d ».
✓ On développe le non terminal « S » (le fils
immédiat de « S » le plus à gauche).
✓ La S-production qui débute avec un « d » est la
production (3) : « S → d ».
✓ On crée les fils de « S » : un nœud étiqueté par
« d ».
ESPRIM Khouja Med Khairallah 132
 CH5. Analyse syntaxique

Analyse syntaxique
descendante
S$
pf
a S b T
accbbadbc$
c T
b S pt
c
a S b T

ESPRIM d Khouja Med Khairallah 133

 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Itération (8) :
✓ On lit le 8 ème caractère dans la chaîne d’entrée :
« b ».
✓ Pas de terminal parmi les fils qui viennent d’être
crées, donc on cherche un non terminal parmi les
ancêtres du nœud fils : il y en a un qui est « T ».
✓ Mais, avant ce « T », il y a un terminal « b » qui
concorde avec le caractère couramment lu.
✓ On avance à la fois les deux pointeurs pf et pt.
ESPRIM Khouja Med Khairallah 134
 CH5. Analyse syntaxique

Analyse syntaxique
descendante
pf S$

a S b T
accbbadbc$
c T
b S pt
c
a S b T

ESPRIM d Khouja Med Khairallah 135

 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Itération (9) :
✓ On lit le 9 ème caractère dans la chaîne d’entrée :
« c ».
✓ On développe le non terminal « T ».

✓ La T-production qui commence par un « c » est

(4) « T → c ».
✓ On crée les fils de « T » : un seul nœud étiqueté
par « c ».
ESPRIM Khouja Med Khairallah 136
 CH5. Analyse syntaxique

Analyse syntaxique
descendante
S$
pf

a S b T
accbbadbc$
c T
b S pt
c
a S b T

ESPRIM d Khouja Med Khairallahc 137

 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Fin de l’algorithme :
✓ On arrive à la fin de la chaîne de caractères
(lecture du marqueur « $ »).
✓ L’algorithme se termine.

✓ Le résultat de l’analyse est l’arbre de dérivation

du mot « w = accbbadbc ».
✓ Le mot est donc reconnu par le langage dénoté
par la grammaire hors contexte G.
ESPRIM Khouja Med Khairallah 138
 CH5. Analyse syntaxique

Analyse syntaxique
S descendante

a S b T
Arbre syntaxique du
c T mot "accbbadbc"
b S
c
a S b T

d c
ESPRIM Khouja Med Khairallah 139
 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Algorithme d’analyse syntaxique descendante :
✓ On part de la racine étiqueté par l’axiome de la
grammaire.
✓ On réalise d’une manière répétitive les deux
étapes ci-dessous :
▪ Étape 1 : au nœud n, étiqueté par le non
terminal « A », choisir une des productions
issues de « A » et construire les fils de n avec
les symboles en partie droite de la production.
ESPRIM Khouja Med Khairallah 140
 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Algorithme d’analyse syntaxique descendante :
Étape 2 : déterminer le prochain nœud où un
▪
sous-arbre doit être construit.
✓ Pour certaines grammaires, les deux étapes
précédentes peuvent être implantées au cours
d’un seul parcours gauche-droite de la chaîne
d’entrée.
✓ L’unité lexicale qui vient d’être reconnue dans le
flot d’entrée est souvent appelé "symbole de
prévision" (lookahead).
ESPRIM Khouja Med Khairallah 141
 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Algorithme d’analyse syntaxique descendante :
✓ Quand les fils sont ajoutés à un nœud, on prend
d’abord en compte le fils le plus à gauche.
✓ Quand le nœud en cours de développement dans
l’arbre syntaxique correspond à un terminal, et
que ce terminal concorde avec le symbole de
prévision, on progresse à la fois dans l’arbre
syntaxique et dans l’entrée.
ESPRIM Khouja Med Khairallah 142
 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Algorithme d’analyse syntaxique descendante :
✓ En général, la sélection d’une production pour un
non terminal, est un processus "d’essai avec
possibilité de retour en arrière" (backtraking).
✓ Dans un tel processus, on commence par
essayer une production, puis si cette production
ne convient pas, on peut rebrousser chemin pour
essayer une autre production différente.

ESPRIM Khouja Med Khairallah 143

 CH5. Analyse syntaxique

Analyse syntaxique
descendante
➢ Algorithme d’analyse syntaxiques descendante :
✓ Une production ne convient pas si, après
utilisation de cette production, on n’arrive pas à
compléter l’arbre syntaxique pour que son mot
des feuilles coïncide avec la chaîne d’entrée.
✓ Cependant, il existe une situation particulière très
importante, appelée "analyse syntaxique
prédictive", dans lequel le rebroussement n’est
pas nécessaire.

ESPRIM Khouja Med Khairallah 144

 CH5. Analyse syntaxique

Analyse syntaxique
prédictive

ESPRIM Khouja Med Khairallah 145

 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Analyse syntaxique prédictive :
✓ L’analyse syntaxique prédictive est une technique
particulière de l’analyse syntaxique descendante.
✓ Dans une telle technique, le symbole de prévision
détermine de manière non ambiguë la production
à appliquer pour chaque non terminal.
✓ La suite des productions appliquées au cours du
traitement de l’entrée définit implicitement l’arbre
de dérivation de l’entrée.
ESPRIM Khouja Med Khairallah 146
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Implémentation d’un analyseur syntaxique
prédictive :
✓ L’analyse prédictive est caractérisée par la
simplicité de son implémentation.
✓ Un analyseur syntaxique prédictif se programme
comme un ensemble de procédures récursives
qui coopèrent pour traiter l’entrée.
✓ L’idée est très simple : à chaque non terminal, on
définit une procédure récursive.
ESPRIM Khouja Med Khairallah 147
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Implémentation d’un analyseur syntaxique
prédictive :
✓ On définit une procédure « Accepter(Lexème) »
pour simplifier le code des autres procédures.
✓ Cette procédure consiste à avancer jusqu’à la
prochaine unité lexicale de l’entrée si son
argument concorde avec le symbole de prévision.
✓ L’analyse syntaxique débute par un appel à la
procédure correspondant à l’axiome.
ESPRIM Khouja Med Khairallah 148
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Écriture d’une procédure pour une production :
✓ À chaque production, on fait correspondre une
procédure.
✓ Pour simplifier l’implémentation, le nom de la
procédure est celui du non terminal dans la partie
gauche de la production.
✓ Chaque terminal en partie droite est comparé au
symbole de prévision et chaque non terminal en
partie droite conduit à un appel de sa procédure.
ESPRIM Khouja Med Khairallah 149
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Exemple :
✓ Considérons la grammaire :
▪ S → aSbT (1)
▪ S → cT (2)
▪ S→d (3)
▪ T→c (4)
▪ T → bS (5)
✓ Cette grammaire peut très bien être analysée par
un analyseur syntaxique prédictive.
ESPRIM Khouja Med Khairallah 150
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Programme C de l’analyseur prédictif :
#include <stdio.h>
char entree [ ] = "accbbadbc$";
int indice = 0;
char symbole_prevision;
void Accepter(char);
void S();
void T();
void Erreur();
ESPRIM Khouja Med Khairallah 151
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Programme C de l’analyseur prédictif :

void Accepter(char lexeme)

{
if(symbole_prevision == lexeme)
symbole_prevision = entree[++indice];
else Erreur();
}
ESPRIM Khouja Med Khairallah 152
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Programme C de l’analyseur prédictif :
void S() {
switch(symbole_prevision) {
case 'a' : Accepter('a');
S();
Accepter('b');
T();
break;
ESPRIM Khouja Med Khairallah 153
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Programme C de l’analyseur prédictif :
case 'c' :
Accepter('c');
T();
break;
case 'd' : Accepter('d');
break;
default : Erreur(); } /* fin switch */
} /* fin procédure S() */
ESPRIM Khouja Med Khairallah 154
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Programme C de l’analyseur prédictif :
void T() {
switch(symbole_prevision) {
case 'b' : Accepter('b');
S();
break;
case 'c' : Accepter('c');
break;
ESPRIM Khouja Med Khairallah 155
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Programme C de l’analyseur prédictif :
default : Erreur(); } /* fin switch */
} /* fin procédure T() */
void Erreur()
{
printf("Erreur syntaxique : %c attendu\n",
symbole_prevision);
}
ESPRIM Khouja Med Khairallah 156
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Programme C de l’analyseur prédictif :
main() {
symbole_prevision = entree[indice];
S();
if(symbole_prevision == '$')
Accepter('$');
else
Erreur();
}
ESPRIM Khouja Med Khairallah 157
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Conditions sur l’analyse syntaxique prédictive :
✓ L’analyse prédictive se base sur la connaissance
des premiers symboles qui peuvent être
engendrés par la partie droite d’une production.
✓ On peut connaître de tels symboles en utilisant
une fonction spéciale : la fonction "Premier".
✓ Pour une forme , Premier() est l’ensemble des
unités lexicales qui apparaissent comme premier
symbole dans une ou plusieurs chaînes
dérivables à partir de .
ESPRIM Khouja Med Khairallah 158
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Conditions sur l’analyse syntaxique prédictive :
✓ Pour la grammaire de l’exemple, on a :
▪ Premier(S) = {a, c, d}.

▪ Premier(T) = {b, c}.

✓ Une première condition pour effectuer une

analyse syntaxique prédictive est que les
ensembles « Premier » sont deux à deux
disjoints pour les non terminaux.
ESPRIM Khouja Med Khairallah 159
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Conditions sur l’analyse syntaxique prédictive :
✓ Supposons qu’il existe deux productions issues
d’un même non terminal A :
▪ A→

▪ A→

✓ Alors, l’analyse syntaxique prédictive n’est

possible que si « Premier()  Premier() =  »
est vérifiée.
ESPRIM Khouja Med Khairallah 160
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Conditions sur l’analyse syntaxique prédictive :

✓ Le symbole de prévision peut alors être utilisé
pour décider de la production à appliquer :
▪ Si le symbole de prévision est dans
Premier(), alors utiliser « A →  ».
▪ Si le symbole de prévision est dans
Premier(), alors utiliser « A →  ».

ESPRIM Khouja Med Khairallah 161

 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Conception d’un analyseur prédictif :

✓ Un analyseur prédictif est un programme
comprenant une procédure pour chaque non
terminal de la grammaire.
✓ Chaque procédure réalise deux traitements :
▪ Décider de la production à utiliser en
examinant le symbole de prévision.
▪ Utiliser une production en interprétant la partie
droite.
ESPRIM Khouja Med Khairallah 162
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Conception d’un analyseur prédictif :

✓ La production dont la partie droite est la forme 
sera choisie, si le symbole de prévision est dans
Premier().
✓ S’il y a un conflit entre deux parties droites pour
un symbole de prévision particulier, cette
technique ne peut pas être utilisée pour la
grammaire de départ.
ESPRIM Khouja Med Khairallah 163
 CH5. Analyse syntaxique

Analyse syntaxique prédictive

➢ Conception d’un analyseur prédictif :
✓ Un non terminal résulte en un appel à la
procédure associée, et une unité lexicale
concordant avec le symbole de prévision résulte
en la lecture de la prochaine unité lexicale de la
chaîne d’entrée (avancement de l’analyse).
✓ Si à un point quelconque, l’unité lexicale de la
production ne concorde pas avec le symbole de
prévision, une erreur de syntaxe est alors
détectée.
ESPRIM Khouja Med Khairallah 164
 CH5. Analyse syntaxique

Grammaires
récursives à gauche

ESPRIM Khouja Med Khairallah 165

 CH5. Analyse syntaxique

Grammaires récursives à
gauche
➢ Définitions :
✓ Une GHC est dite "immédiatement récursive à
gauche", si elle contient une production de la
forme « A → A ».
✓ Une GHC est dite "indirectement récursive à
gauche", si elle contient un symbole non terminal
« A » tel qu’il existe une dérivation d’au moins
une étape de la forme « A + A » où «  » une
forme quelconque de la grammaire.
ESPRIM Khouja Med Khairallah 166
 CH5. Analyse syntaxique

Grammaires récursives à
gauche
➢ Exemples :
✓ Soit G la GHC suivante :
▪ S → ScA | B

▪ A → Aa | 

▪ B → Bb | d | e

✓ G est immédiatement récursive à gauche, à

cause des productions :
▪ S → ScA, A → Aa et B → Bb
ESPRIM Khouja Med Khairallah 167
 CH5. Analyse syntaxique

Grammaires récursives à
gauche
➢ Exemples :
✓ Soit G la GHC suivante :
▪ S → Aa | b

▪ A → Bc

▪ B → Sb | 

✓ G est indirectement récursive à gauche, à cause

de la dérivation suivante :
▪ S  Aa  Bca  Sbca (donc S + Sbca).
ESPRIM Khouja Med Khairallah 168
 CH5. Analyse syntaxique

Grammaires récursives à
gauche
➢ Grammaires récursives à gauche et analyse
descendante :
✓ Avec une grammaire récursive à gauche, on ne
peut pas faire une analyse syntaxique
descendante.
✓ Un analyseur descendant d’une grammaire
récursive à gauche peut provoquer des boucles
infinies.

ESPRIM Khouja Med Khairallah 169

 CH5. Analyse syntaxique

Grammaires récursives à
gauche
➢ Grammaires récursives à gauche et analyse
descendante :
✓ Prenons la production « A → Ab ».

✓ Supposons que la procédure pour « A », décide

d’utiliser cette production.
✓ La partie droite débute par « A », ce qui fait que
la procédure est appelée récursivement, et donc
que l’analyseur boucle indéfiniment.

ESPRIM Khouja Med Khairallah 170

 CH5. Analyse syntaxique

Grammaires récursives à
gauche
➢ Grammaires récursives à gauche et analyse
descendante :
✓ Notons que le symbole de prévision ne change
que lorsqu’un terminal de la partie droite est
accepté.
✓ Comme la production commence par le non
terminal « A », aucun changement dans l’entrée
n’intervient entre les appels récursifs, ce qui
engendre une boucle infinie.
ESPRIM Khouja Med Khairallah 171
 CH5. Analyse syntaxique

Grammaires récursives à
gauche
➢ Grammaires récursives à gauche et analyse
descendante :
✓ Il est donc impossible de réaliser un analyseur
syntaxique descendant avec de telles
grammaires.
✓ Cependant, en procédant par un nettoyage de la
grammaire, on peut arriver à réaliser un
analyseur syntaxique pour une grammaire
récursive au départ.
ESPRIM Khouja Med Khairallah 172
 CH5. Analyse syntaxique

Grammaires récursives à
gauche
➢ Algorithme d’élimination de la récursivité à
gauche immédiate :
✓ Remplacer toute règle de production de la forme
« A → A |  » par les deux règles suivantes :
▪ A → A’

▪ A’ → A’ | 

✓ La grammaire ainsi obtenue reconnaît le même

langage que la grammaire initiale RG.
ESPRIM Khouja Med Khairallah 173
 CH5. Analyse syntaxique

Grammaires récursives à
gauche
➢ Exemple :
✓ Prenons la GHC immédiatement récursive à
gauche :
▪ S → ScA | B

▪ A → Aa | 

▪ B → Bb | d | e

✓ Éliminons les récursivités à gauche immédiates

de cette grammaire :
ESPRIM Khouja Med Khairallah 174
 CH5. Analyse syntaxique

Grammaires récursives à
gauche
➢ Exemple :
✓ On obtient la grammaire :
▪ S → BS’

▪ S’ → cAS’ | 

▪ A → A’

▪ A’ → aA’ | 

▪ B → dB’ | eB’

▪ B’ → bB’ | 
ESPRIM Khouja Med Khairallah 175
 CH5. Analyse syntaxique

Grammaires récursives à
gauche
➢ Algorithme d’élimination de la récursivité à
gauche indirecte :
✓ Ordonner les « non terminaux » de la grammaire
considérée : A1, A2, …, An.
✓ Pour i := 1 à n Faire :
▪ Pour j := 1 à (i -1) Faire :

❖ Remplacer chaque production de la forme

« Ai → Aj » où « Aj → 1 | … | k », par la
production « Ai → 1 | … | k ».
▪ FinPour {j}
ESPRIM Khouja Med Khairallah 176
 CH5. Analyse syntaxique

Grammaires récursives à
gauche

➢ Algorithme d’élimination de la récursivité à

gauche indirecte :
▪ Éliminer les récursivités immédiates à gauche
des Ai-productions (productions issues de Ai).
✓ FinPour {i}

➢ La grammaire ainsi obtenue reconnaît le même

langage que la grammaire initiale RG.

ESPRIM Khouja Med Khairallah 177

 CH5. Analyse syntaxique

Grammaires récursives à
gauche
➢ Exemple :
✓ Considérons la GHC récursive à gauche :
▪ S → Aa | b

▪ A → Ac | Sd | 

✓ Éliminons les récursivités à gauche contenues

dans cette grammaire :
▪ On ordonne les non terminaux : S, A.

▪ i = 1 : pas de récursivité immédiate dans les

productions S → Aa | b.
ESPRIM Khouja Med Khairallah 178
 CH5. Analyse syntaxique

Grammaires récursives à
gauche
➢ Exemple :
i = 2 et j = 1. On obtient : A → Ac | Aad | bd | 
▪

❖ On élimine la récursivité immédiate :

A → bdA’ | A’
A’ → cA’ | adA’ | 
✓ Donc, on a obtenu la grammaire suivante :

▪ S → Aa | b

▪ A → bdA’ | A’

▪ A’ → cA’ | adA’ | 
ESPRIM Khouja Med Khairallah 179
 CH5. Analyse syntaxique

Grammaires
factorisables à gauche

ESPRIM Khouja Med Khairallah 180

 CH5. Analyse syntaxique

Grammaires factorisables à
gauche
➢ Factorisation à gauche :
✓ La factorisation à gauche est une transformation
grammaticale utile pour obtenir une grammaire
convenant à l’analyse syntaxique prédictive.
✓ L’idée de base est que, pour développer un non
terminal « A », quand il n’est pas évident de
choisir l’alternative à utiliser, on doit réécrire les
A-productions, de manière à différer la décision
jusqu’à ce que suffisamment de texte ait été lu,
pour faire le bon choix.
ESPRIM Khouja Med Khairallah 181
 CH5. Analyse syntaxique

Grammaires factorisables à
gauche
➢ Exemple :
✓ Considérons la GHC suivante :
▪ S → abcdeaTca | abcdfXy

✓ Au départ, pour savoir s'il faut choisir la

production « S → abcdeaTca » ou la production
« S → abcdfXy », il faut avoir lu la 4ième lettre du
mot (qui est soit un « e », ou soit un « f »).
✓ On ne peut donc pas dès le départ savoir quelle
production prendre.
ESPRIM Khouja Med Khairallah 182
 CH5. Analyse syntaxique

Grammaires factorisables à
gauche
➢ Algorithme de factorisation à gauche :
✓ Pour chaque non terminal « A », Faire :
▪ Trouver le plus long préfixe «  » commun à
deux de ses alternatives ou plus.
▪ Si   , Remplacer « A → 1|…|n|1|…|p »
(où les i ne commencent pas par ), par les
deux productions :
❖ A → A’ | 1 | … | p
❖ A’ → 1 | … | n
✓ Recommencer jusqu'à ne plus en trouver.
ESPRIM Khouja Med Khairallah 183
 CH5. Analyse syntaxique

Grammaires factorisables à
gauche
➢ Exemple :
✓ Soit G la GHC suivante :
▪ S → iEtS | iEtSeS | a
▪ E→b
✓ On factorise G à gauche :
▪ S → iEtSS’ | a
▪ S’ → eS | 
▪ E→b

ESPRIM Khouja Med Khairallah 184

 CH5. Analyse syntaxique

Grammaires factorisables à
gauche
➢ Définitions :
✓ Une grammaire est dite "non factorisée à
gauche", si elle contient au moins une alternative
de la forme « A → X | Y ».
✓ Lorsqu’on applique l’algorithme de la factorisation
à gauche sur une grammaire, on obtient une
grammaire équivalente à celle de départ, et l’on
dit que cette grammaire est "factorisée à
gauche".
ESPRIM Khouja Med Khairallah 185
 CH5. Analyse syntaxique

Exercice
Considérer la grammaire G=<N,T,P,S> dont les productions sont données ci-après :
P :<Instruction>→ if <Condition> then <Instruction> else <Instruction> |
if<Condition> then <Instruction> | begin <LI> end | i <Condition>→ c
<LI>→<LI> ; i | i
a) Montrer que la grammaire G précédente est ambiguë en donnant deux arbres
syntaxiques pour le fragment de programme suivant :
if c then if c then i else i
b) Comment pourra-t-on faire une analyse syntaxique "déterministe" pour ce type
d'instructions (instructions conditionnelles if).

ESPRIM Khouja Med Khairallah 186

 CH5. Analyse syntaxique

a)

ESPRIM Khouja Med Khairallah 187

 CH5. Analyse syntaxique

a)

ESPRIM Khouja Med Khairallah 188

 CH5. Analyse syntaxique

b)

➢ Il est possible d'imbriquer les instructions

if.
➢ Pour lever l'ambiguïté, en l’absence de
parenthèses bien placées, le langage C
par exemple associe toujours le else au
if sans else le plus proche.

ESPRIM Khouja Med Khairallah 189

 CH5. Analyse syntaxique

Analyse prédictive
non récursive

ESPRIM Khouja Med Khairallah 190

 CH5. Analyse syntaxique

Analyse prédictive non

récursive

➢ Analyse prédictive récursive :

✓ L’analyse syntaxique prédictive récursive est
dirigée par un ensemble de procédures
récursives représentant les non terminaux.
✓ Les appels récursifs déterminent les règles de
productions à appliquer pour construire l’arbre de
dérivation d’un mot donné.

ESPRIM Khouja Med Khairallah 191

 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Analyse prédictive non récursive :
✓ La technique d’analyse prédictive récursive peut
être remplacée par une analyse qui se base sur
l’utilisation d’une pile au lieu des appels récursifs.
✓ Cette méthode est basée sur l’utilisation d’une
table, dite "table d’analyse", qui nous dit :
▪ Quand on lit tel lexème et qu’on est à dériver
tel symbole non terminal, alors on applique
telle règle de production, puis on avance »
ESPRIM Khouja Med Khairallah 192
 CH5. Analyse syntaxique

Analyse prédictive non

récursive

➢ Analyse prédictive non récursive :

✓ L’analyse prédictive non récursive manipule :
▪ Un tampon d’entrée.

▪ Une pile.

▪ Une table d’analyse.

▪ Un flot de sortie.

ESPRIM Khouja Med Khairallah 193

 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Schéma d’un analyseur prédictif non récursive :
Tampon
d’entrée a c c d $

Analyseur Syntaxique
b Prédictive
S
$ Flot de sortie
Pile Table d’analyse
ESPRIM Khouja Med Khairallah 194
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Analyse prédictive non récursive :
✓ Le tampon d’entrée contient la chaîne à analyser
terminée par un marqueur de fin « $ ».
✓ La pile contient une suite de symboles de la
grammaire, avec « $ » au fond de la pile.
✓ La table d’analyse est un tableau à deux
dimensions M[A, a], où « A » est un non terminal
et « a » un symbole terminal ou le symbole « $ ».
ESPRIM Khouja Med Khairallah 195
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Comportement de l’analyse prédictive non
récursive :
✓ Initialement, la pile contient au sommet l’axiome
de la grammaire et le symbole « $ » au fond.
✓ Le programme d’analyse considère « X », le
symbole en sommet de pile et « a », le symbole
courant dans l’entrée.
✓ Ces deux symboles déterminent l’action de
l’analyseur.
ESPRIM Khouja Med Khairallah 196
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Comportement de l’analyse prédictive non
récursive :
✓ Il y a trois cas possibles :

▪ Si X = a = $. L’analyseur s’arrête et annonce la

réussite de l’analyse.
▪ Si X = a  $. L’analyseur dépile X et avance
son pointeur d’entrée sur le symbole suivant.
▪ Si X est un non terminal, le programme fait une
consultation de la table d’analyse.
ESPRIM Khouja Med Khairallah 197
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Comportement de l’analyse prédictive non
récursive :
✓ Consultation de la table d’analyse :

▪ Le programme détermine M[X, a] qui est soit

une « X-production », soit « Erreur ».
▪ Si M[X, A] est une X-production de la forme
« X → UVW », alors l’analyseur remplace le
symbole dépilé « X » par UVW dans l’ordre
inverse (« U » est au sommet).
ESPRIM Khouja Med Khairallah 198
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Comportement de l’analyse prédictive non
récursive :
✓ Consultation de la table d’analyse :

▪ Si M[X, A] = Erreur, l’analyseur appelle une

procédure de récupération sur erreur.
✓ Le comportement de l’analyseur peut se décrire
en termes de ses configurations, qui décrivent le
contenu de sa pile et le texte d’entrée restant.

ESPRIM Khouja Med Khairallah 199

 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Algorithme d’analyse prédictive non récursive :
✓ Supposons qu'on a déjà la table d’analyse.
✓ Comment l'utiliser pour déterminer si un mot w
donné est reconnu par la grammaire G ?
✓ Les données de l’algorithme sont :

▪ Un mot à analyser (l’entrée) : w.

▪ La table d’analyse : M[X, a] de la grammaire G.

✓ Le résultat : w « accepté » ou « erreur ».

ESPRIM Khouja Med Khairallah 200
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Algorithme d’analyse prédictive non récursive :
✓ Paramètres de l’algorithme :
▪ Une plie.

▪ ps : pointeur vers la chaîne d’entrée.

✓ Initialisations de l’algorithme :

▪ La pile : « S » au sommet et « $ » au fond.

▪ ps : pointe vers le 1er symbole d’entrée (celle-ci

étant terminée par un « $ »).
ESPRIM Khouja Med Khairallah 201
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Itération de l’algorithme :
✓ On note par X le symbole en sommet de la pile,
et par a le symbole pointé par ps.
✓ Il y a trois cas possible pour X :

▪ X est un non terminal.

▪ X est un terminal.

▪ X est le symbole de fin $.

ESPRIM Khouja Med Khairallah 202

 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Itération de l’algorithme :
✓ 1er cas : X est un symbole non terminal.
▪ Si M[X, a] = X → Y1…Yn, alors :

❖On dépile X.

❖ On empile Yn, Yn-1, ..., Y1 dans cet ordre.

❖ On imprime en sortie : X → Y1…Yn (mais

n’importe quelle autre action pourrait être
effectuée à la place).
ESPRIM Khouja Med Khairallah 203
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Itération de l’algorithme :
Si M[X, a] = ERREUR, alors l’analyse se
▪
termine en énonçant un cas d’erreur.
✓ 2ème cas : X est un symbole terminal.
▪ Si X = a, alors :
❖ On dépile X.
❖ On avance le pointeur ps.
▪ Si X  a, alors l’analyse se termine en
énonçant un cas d’erreur.
ESPRIM Khouja Med Khairallah 204
 CH5. Analyse syntaxique

Analyse prédictive non

récursive

➢ Itération de l’algorithme :
✓ 3ème cas : X est le symbole de fin $.
▪ Si a = $, alors l’analyse se termine en
énonçant un succès.
▪ Si a  $, alors l’analyse se termine en
énonçant un cas d’erreur.

ESPRIM Khouja Med Khairallah 205

 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Exemple :
✓ Considérons la grammaire :
▪ S → aS | bS | c | d

✓ Effectuons l’analyse syntaxique prédictive non

récursive de cette grammaire pour le mot ababc.
✓ La table d’analyse de cette grammaire est telle
que : M[S, a] = S → aS, M[S, b] = S → bS, M[S,
c] = S → c et M[S, d] = S → d.
ESPRIM Khouja Med Khairallah 206
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Exemple : Itération (1)
a b a b c $

ps
Un non terminal au sommet :
S pile Dépiler(S), Empiler(S, a),
Afficher en sortie : S → aS
$

S→aS S→bS S→c S→d

ESPRIM Khouja Med Khairallah 207
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Exemple :

a b a b c $ Itération (2)

ps
a pile Concordance de ps et pile :
S Dépiler(a), Avancer(ps)
$
ESPRIM Khouja Med Khairallah 208
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Exemple : Itération (3)
a b a b c $

ps
pile Un non terminal au sommet :
S
Dépiler(S), Empiler(S, b),
$ Afficher en sortie : S → bS

S→aS S→bS S→c S→d

ESPRIM Khouja Med Khairallah 209
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Exemple :

a b a b c $ Itération (4)

ps
b pile Concordance de ps et pile :
S Dépiler(b), Avancer(ps)
$
ESPRIM Khouja Med Khairallah 210
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Exemple : Itération (5)

a b a b c $

pile ps Un non terminal au sommet :

S
Dépiler(S), Empiler(S, a),
$ Afficher en sortie : S → aS

S→aS S→bS S→c S→d

ESPRIM Khouja Med Khairallah 211
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Exemple :

a b a b c $ Itération (6)

ps
a pile Concordance de ps et pile :
S Dépiler(a), Avancer(ps)
$
ESPRIM Khouja Med Khairallah 212
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Exemple : Itération (7)
a b a b c $

pile ps Un non terminal au sommet :

S
Dépiler(S), Empiler(S, b),
$ Afficher en sortie : S → bS

S→aS S→bS S→c S→d

ESPRIM Khouja Med Khairallah 213
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Exemple :

a b a b c $ Itération (8)

ps
b pile Concordance de ps et pile :
S Dépiler(b), Avancer(ps)
$
ESPRIM Khouja Med Khairallah 214
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Exemple : Itération (9)

a b a b c $

pile ps Un non terminal au sommet :

S
Dépiler(S), Empiler(c),
$ Afficher en sortie : S → c

S→aS S→bS S→c S→d

ESPRIM Khouja Med Khairallah 215
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Exemple :

a b a b c $ Itération (10)

ps
c pile Concordance de ps et pile :
$ Dépiler(c), Avancer(ps)

ESPRIM Khouja Med Khairallah 216

 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Exemple :

a b a b c $ Itération (11)

ps
$ pile Sommet = entrée = $ :
Arrêt de l’analyse
Sortie : Succès
ESPRIM Khouja Med Khairallah 217
 CH5. Analyse syntaxique

Analyse prédictive non

récursive
➢ Exemple :
✓ Affichage de l’analyse :
▪ S → aS

▪ S → bS

▪ S → aS

▪ S → bS

▪ S→c

▪ ababc → ACCEPTE
ESPRIM Khouja Med Khairallah 218
 CH5. Analyse syntaxique

EXERCICE

Soit la grammaire G=<{ A,B,C},{a,b},P,A>

A →aB
B →bC
C →aC | bC | ɛ
a) Donner la dérivation la plus à gauche de la chaine : abbbaab
b) Donner la dérivation la plus à droite de la chaine : abbbaab
c) Donner le langage engendré par la grammaire.

ESPRIM Khouja Med Khairallah 219

 CH5. Analyse syntaxique

a) La dérivation la plus à gauche de la chaine : abbbaab

A ⇒ aB ⇒ abC ⇒ abbC ⇒ abbbC ⇒ abbbaC ⇒ abbbaaC
⇒ abbbaabC ⇒ abbbaab
b) La dérivation la plus à droite de la chaine : abbbaab
A ⇒ aB ⇒ abC ⇒ abbC ⇒ abbbC ⇒ abbbaC ⇒ abbbaaC
⇒ abbbaabC ⇒ abbbaab
c) Le langage engendré par la grammaire :
L(G) : ab(a|b)*
ESPRIM Khouja Med Khairallah 220
 CH5. Analyse syntaxique

Construction de la table
d'analyse prédictive

ESPRIM Khouja Med Khairallah 221

 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive
➢ Fonctions « PREMIER » et « SUIVANT » :
✓ L’analyseur prédictif s’appui sur la table d’analyse
syntaxique.
✓ La construction de cette table est facilitée par
deux fonctions associées à une grammaire : la
fonction « PREMIER » et « SUIVANT ».
✓ Ces deux fonctions nous permettent de remplir
les entrées de la table d’analyse prédictive pour
une grammaire G.
ESPRIM Khouja Med Khairallah 222
 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive
➢ Fonctions « PREMIER » et « SUIVANT » :
✓ Si  est une forme de G, PREMIER() désigne
l’ensemble des terminaux qui commencent les
mots qui se dérivent de .
✓ Pour chaque non terminal A, SUIVANT(A) définit
l’ensemble des terminaux qui peuvent apparaître
immédiatement à droite de A dans une dérivation
à partir de la racine de la grammaire.
ESPRIM Khouja Med Khairallah 223
 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive
➢ Calcul de la fonction «PREMIER » :
✓ Formellement, un terminal a  PREMIER(), si et
seulement s’il existe une dérivation de la forme
  a.
✓ Soit X un symbole de la grammaire étudiée.

✓ Pour calculer PREMIER(X), on utilise une

fonction auxiliaire appelée la fonction
NULLABLE.
ESPRIM Khouja Med Khairallah 224
 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive
➢ Définition de la fonction « NULLABLE » :
✓ Une forme  est dite "nullable", si et seulement
s’il existe une dérivation de la forme   .
✓ En particulier, si X est un symbole non terminal
tel que X → , alors X est nullable.
✓ On définit une fonction NULLABLE de (V  T)*
vers {Vrai, Faux} de la façon suivante :

ESPRIM Khouja Med Khairallah 225

 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive
➢ Définition de la fonction « NULLABLE » :
✓ NULLABLE() = Vrai.
✓ NULLABLE(a) = Faux, pour tout terminal de G.

✓ NULLABLE() = NULLABLE()  NULLABLE(),

pour toutes formes ,  de G.
✓ NULLABLE(X) = NULLABLE(Y1)  NULLABLE(Y2)
 …  NULLABLE(Yn), pour tout non terminal X, tel
que X → Y1 | Y2 | … | Yn.
ESPRIM Khouja Med Khairallah 226
 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive

➢ Exemple :
✓ On considère la grammaire suivante :
▪ S → R | aSc

▪ R → bR | 

✓ R est nullable, car R → .

✓ S est nullable, car S → R et R nullable.

ESPRIM Khouja Med Khairallah 227

 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive
➢ Définition la fonction « PREMIER » :
✓ PREMIER() = {}.
✓ PREMIER(a) = {a}, pour tout terminal de G.

✓ PREMIER() = PREMIER()  PREMIER(), si 

est nullable.
✓ PREMIER() = PREMIER(), si  n’est pas
nullable.
✓ PREMIER(X) = PREMIER(Y1) … PREMIER(Yn),
pour tout non terminal X, tel que X → Y1| Y2 |…| Yn.
ESPRIM Khouja Med Khairallah 228
 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive

➢ Exemple :
✓ On considère la grammaire suivante :
▪ S → R | aSc

▪ R → bR | 

✓ PREMIER(R) = {b, }.

✓ PREMIER(S) = {a, b, }.

ESPRIM Khouja Med Khairallah 229

 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive
➢ Algorithme pour la fonction « SUIVANT » :
✓ Ajouter le symbole $ à SUIVANT(S) (où S est
l'axiome de la grammaire).
✓ S'il y a une production A → B, où B est un non
terminal, alors ajouter le contenu de SUIVANT(A)
à SUIVANT(B).
✓ S'il y a une production A → B, alors ajouter le
contenu de PREMIER() à SUIVANT(B), sauf .

ESPRIM Khouja Med Khairallah 230

 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive

➢ Algorithme pour la fonction « SUIVANT » :

✓ S'il y a une production A → B avec  
PREMIER(), alors ajouter le contenu de
SUIAVNT(A) à SUIVANT(B).
✓ Recommencer ce processus jusqu'à ce qu'on
n'ajoute rien de nouveau dans les ensembles
SUIVANT.

ESPRIM Khouja Med Khairallah 231

 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive

➢ Exemple :
✓ On considère la grammaire suivante :
▪ S → R | aSc

▪ R → bR | 

✓ SUIVANT(S) = {$, c}.

✓ SUIVANT(R) = {$, c}.

ESPRIM Khouja Med Khairallah 232

 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive
➢ Un autre exemple :
✓ On considère la grammaire suivante :
▪ E → TE’

▪ E’ → +TE’ | 

▪ T → FT’

▪ T’ → *FT’ | 

▪ F → (E) | id

ESPRIM Khouja Med Khairallah 233

 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive
➢ Un autre exemple :
✓ Calcul des ensembles PREMIER :
▪ PREMIER(F) = {(, id}.

▪ PREMIER(T) = PREMIER(F) = {(, id}.

▪ PREMIER(E) = PREMIER(T) = {(, id}.

▪ PREMIER(E’) = {+, }.

▪ PREMIER(T’) = {*, }.

ESPRIM Khouja Med Khairallah 234

 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive
➢ Un autre exemple :
✓ Calcul des ensembles SUIAVNT :
▪ SUIAVNT(E) = {), $}.

▪ SUIAVNT(E’) = SUIVANT(E) = {), $}.

▪ SUIAVNT(T) = {+, ), $}.

▪ SUIAVNT(T’) = {+, ), $}.

▪ SUIAVNT(F) = {+, *, ), $}.

ESPRIM Khouja Med Khairallah 235

 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive
➢ Construction d’une table d’analyse :
✓ Une table d'analyse syntaxique prédictive non
récursive est un tableau M à deux dimensions qui
indique pour chaque symbole non terminal X et
chaque symbole terminal a ou le symbole $, la
règle de production à appliquer.
✓ L’algorithme de construction d’une telle table est
le suivant :
ESPRIM Khouja Med Khairallah 236
 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive
➢ Construction d’une table d’analyse :
✓ Pour chaque production A →  Faire :
▪ Pour tout a  PREMIER() (et a  ), rajouter
la production A →  dans la case M[A, a].
▪ Si   PREMIER(), alors pour chaque
symbole b  SUIVANT(A), ajouter A →  dans
la case M[A, b].
▪ Chaque case M[A, a] vide est une erreur de
syntaxe.
ESPRIM Khouja Med Khairallah 237
 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive
➢ Exemple : table d’analyse pour la grammaire de la
page 233.
id + * ( ) $

E E → TE’ E → TE’

E’ E’ → +TE’ E’ →  E’ → 

T T → FT’ T → FT’

T’ T’ →  T’ → *FT’ T’ →  T’ → 

F F → id F → (E)

ESPRIM Khouja Med Khairallah 238

 CH5. Analyse syntaxique

Construction de la table
d’analyse prédictive
➢ Retour sur l’analyse syntaxique prédictive non
récursive :
✓ On peut représenter facilement une analyse
prédictive non récursive en utilisant un tableau à
3 colonnes dont les contenus décrivent
respectivement :
▪ L’état de la pile (du fond au sommet);

▪ Le reste de l’entrée à analyser;

▪ La règle de production à appliquer.

ESPRIM Khouja Med Khairallah 239
 CH5. Analyse syntaxique

Construction de la table d’analyse

prédictive
PILE ENTREE PRODUCTION
$E id$
$E’T id$ E → TE’
$E’T’F id$ T → FT’
$E’T’id id$ F → id
$E’T’ $
$E’ $ T’ → 
$ $ E’ → 
ESPRIM Khouja Med Khairallah 240
 CH5. Analyse syntaxique

Construction de la table d’analyse

prédictive
E

T E’
Arbre syntaxique
F T’ du mot « id »

id  
ESPRIM Khouja Med Khairallah 241
 CH5. Analyse syntaxique

Grammaires
LL(1)

ESPRIM Khouja Med Khairallah 242

 CH5. Analyse syntaxique

Grammaires LL(1)
➢ Définition :
✓ La table d’analyse M peut avoir des entrées
multiples.
✓ Par exemple, si la grammaire est récursive à
gauche ou ambiguë, la table d’analyse M aura au
moins une de ses entrées définie de façon
multiple.
✓ Une grammaire est dite LL(1), si sa table
d’analyse M ne contient que des entrées simples.
ESPRIM Khouja Med Khairallah 243
 CH5. Analyse syntaxique

Grammaires LL(1)
➢ Que signifie le mot LL(1) ?
✓ Le premier « L » signifie « parcours de l’entreé de
la gauche vers la droite » (Left to right scanning).
✓ Le second « L » signifie « dérivation la plus à
gauche » (Leftmost derivation).
✓ Le « 1 » signifie qu’on utilise un seul symbole
d’entrée de prévision à chaque étape nécessitant
la prise de décision dans l’analyse.
✓ On peut généraliser ceci et parler de GHC LL(k).
ESPRIM Khouja Med Khairallah 244
 CH5. Analyse syntaxique

Grammaires LL(1)
➢ Exemple :
✓ La grammaire définie par :
▪ S → aAd

▪ A → cd | c

n’est pas LL(1).

✓ En effet, on a :

▪ PREMIER(S) = {a}, PREMIER(A) = {c}.

▪ SUIVANT(S) = {$} et SUIVANT(A) = {d}.

ESPRIM Khouja Med Khairallah 245
 CH5. Analyse syntaxique

Grammaires LL(1)
➢ Exemple :
✓ Donc on aura la table d’analyse suivante :
a b c d $
S S → aAd
A A → cd
A→c

Entrée multiple

ESPRIM
Not LL(1)
Khouja Med Khairallah 246
 CH5. Analyse syntaxique

Grammaires LL(1)
➢ Théorème :
✓ Si une grammaire hors contexte est LL(1), alors :
▪ Elle est non ambiguë.

▪ Elle est non récursive à gauche.

▪ Elle est factorisée à gauche.

✓ Autrement dis, si une grammaire est ambiguë,

non récursive à gauche ou non factorisée à
gauche, alors cette grammaire n’est pas LL(1).

ESPRIM Khouja Med Khairallah 247

 CH5. Analyse syntaxique

Analyse syntaxique
ascendante

ESPRIM Khouja Med Khairallah 248

 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Principe :
✓ L’analyse syntaxique ascendante essai de
construire un arbre syntaxique du bas (les unités
lexicales) vers le haut (l'axiome de la grammaire).
✓ L’analyse syntaxique ascendante utilise en
général un modèle appelé modèle par "décalage
& réduction".
✓ Ce modèle n'autorise que deux opérations :
▪ Décalage (shift) : consiste à décaler d'une
lettre le pointeur sur le mot d’entrée.
ESPRIM Khouja Med Khairallah 249
 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Principe :
Réduction (reduce) : consiste à réduire une
▪
forme située à gauche du pointeur sur le mot
d’entrée et finissant sur ce pointeur, par un non
terminal en utilisant une des productions.
➢ Exemple :
✓ Considérons la grammaire définie par deux
règles de production suivantes : S → aSbS | c.
✓ Analysons le mot w = aaacbaacbcbcbcbacbc.
ESPRIM Khouja Med Khairallah 250
 CH5. Analyse syntaxique

Analyse syntaxique
ascendante

ESPRIM Khouja Med Khairallah 251

 CH5. Analyse syntaxique

Analyse syntaxique
ascendante

ESPRIM Khouja Med Khairallah 252

 CH5. Analyse syntaxique

Analyse syntaxique
ascendante

ESPRIM Khouja Med Khairallah 253

 CH5. Analyse syntaxique

Analyse syntaxique
ascendante

ESPRIM Khouja Med Khairallah 254

 CH5. Analyse syntaxique

Analyse syntaxique
ascendante

ESPRIM Khouja Med Khairallah 255

 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Table d’analyse :
✓ Ça serait bien d'avoir une table qui nous dit si on
décale ou si on réduit, et par quoi, lorsque le
pointeur est sur une lettre donnée.
✓ La table d’analyse est une sorte d'automate,
qu'on appelle "automate à pile".
✓ Cette table va nous dire ce qu'il faut faire quand
on lit une lettre « a » et qu'on est dans un certain
état « i ». Il y a deux opérations à faire :
▪ Un décalage, ou bien
▪ Une réduction.
ESPRIM Khouja Med Khairallah 256
 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Table d’analyse :
✓ Décalage : on empile la lettre lue et on va dans
un autre état « j ». Ce qui sera noté par « dj ».
✓ Réduction : on réduit par la règle de production
numéro « p », c'est à dire qu'on remplace la
chaîne en sommet de pile (qui correspond à la
partie droite de la règle numéro « p ») par le non
terminal de la partie gauche de la règle de
production, et on va dans l'état « j » qui dépend
du non terminal en question. On note cette action
par « rp ».
ESPRIM Khouja Med Khairallah 257
 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Table d’analyse :
✓ L’action d’acceptation d’un mot est noté par ACC.
✓ Le refus d’un mot sera matérialisé par une case
vide.
➢ 0-items :
✓ Pour construire la table d’analyse, on utilise les
ensembles PREMIER et SUIVANT, plus ce qu'on
appelle des fermetures de "0-items".
✓ Un « 0-item » est une production de la grammaire
avec un « . » quelque part dans la partie droite.
ESPRIM Khouja Med Khairallah 258
 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Exemples de 0-items :
▪ S → .aSbS
▪ S → [Link]
▪ S → [Link]
▪ S → aSb.S
▪ S → aSbS.
▪ S → .c
▪ S → c.
ESPRIM Khouja Med Khairallah 259
 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Calcul de la fermeture d’un ensemble d’items I :
1. Mettre chaque item de I dans Fermeture(I).
2. Pour chaque item i de Fermeture(I) de la forme A
→ .B Faire :
Pour chaque production B → i Faire :
Rajouter l'item B → .i dans Fermeture(I)
3. Recommencer l’étape 2 jusqu'à ce qu'on n'ajoute
rien de nouveau.
ESPRIM Khouja Med Khairallah 260
 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Exemple :
✓ Soit la grammaire suivante :
▪ E→E+T (1)
▪ E→T (2)
▪ T→T*F (3)
▪ T→F (4)
▪ F → (E) (5)
▪ F → nb (6)
ESPRIM Khouja Med Khairallah 261
 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Exemple :
✓ Soit l'ensemble d'items I formé par :
▪ T → T*. F
▪ E → E.+T
✓ L’ensemble Fermeture(I) comprend :
▪ T → T*. F
▪ E → E.+T
▪ F → .nb
▪ F → .(E)
ESPRIM Khouja Med Khairallah 262
 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Transition par X d'un ensemble d'items I :
✓ Noté par (I, X), c’est la fermeture de l’ensemble
formé par tous les items A → X. où A → .X
est dans I.
✓ Exemple :
▪ I = {T → T*.F, E → E.+T, F → .nb, F → .(E)}.
▪ On aura :
▪ (I, F) = { T → T*F.}
▪ (I, +) = {E → E+.T, T → .T*F, T → .F, F →.nb,
F → .(E)}.
ESPRIM Khouja Med Khairallah 263
 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Collection des items d'une grammaire :
1. Rajouter l'axiome S’ avec la production S’ → S
2. Mettre dans l'item I0 la Fermeture de S’ → .S
3. Mettre I0 dans Collection
4. Pour chaque I dans Collection Faire :
Pour chaque X tel que (I, X) est non vide Faire:
Ajouter (I, X) dans Collection
5. Recommencer l’étape 3 jusqu'à ce qu'on n'ajoute
rien de nouveau.
ESPRIM Khouja Med Khairallah 264
 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Construction de la table d'analyse SLR :
1. Construire la collection d'items {I0, ..., In}.
2. L'état « i » est construit à partir de Ii :

a)Pour chaque (Ii, a) = Ij : mettre « décalage par

j » dans la case M[i, a].
b) Pour chaque (Ii, A) = Ij : mettre « aller à j »
dans la case M[i, A].
c) Pour chaque A → . contenu dans Ii :

ESPRIM Khouja Med Khairallah 265

 CH5. Analyse syntaxique

Analyse syntaxique
ascendante

➢ Construction de la table d'analyse SLR :

Pour chaque a de SUIVANT(A) Faire :
▪

❖ Mettre « réduction par numéro (de la règle A

→ ) » dans la case M[i, a].
✓ Avec notre exemple ETF, on obtient la table
d'analyse LR (voir page suivante).

ESPRIM Khouja Med Khairallah 266

 CH5. Analyse syntaxique

ESPRIM Khouja Med Khairallah 267

 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Analyseur syntaxique SLR :
✓ On part dans l'état 0, et on empile et dépile non
seulement les symboles mais aussi les états
successifs.
✓ Exemple :

▪ L'analyse du mot « 3+*4$ » : voir page 276.

▪ L’analyse du mot « 3+4*2$ » : voir page 277.

ESPRIM Khouja Med Khairallah 268

 CH5. Analyse syntaxique

Analyse syntaxique
ascendante

ESPRIM Khouja Med Khairallah 269

 CH5. Analyse syntaxique

Analyse syntaxique ascendante

ESPRIM Khouja Med Khairallah 270

 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Remarques sur l’analyse syntaxique SLR :
✓ Cette technique permet d'analyser plus de
grammaires que la méthode descendante (car il y
a plus de grammaires SLR que LL).
✓ En TP on va utiliser un outil (bison) qui construit
tout seul une table d'analyse LR (LALR en fait,
mais c'est presque pareil) à partir d'une
grammaire donnée.
ESPRIM Khouja Med Khairallah 271
 CH5. Analyse syntaxique

Analyse syntaxique
ascendante

➢ Remarques sur l’analyse syntaxique SLR :

✓ Dans cette méthode d'analyse, ça n'a strictement
aucune importance que la grammaire soit
récursive à gauche, même au contraire, on
préfère.

ESPRIM Khouja Med Khairallah 272

 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Remarques sur l’analyse syntaxique SLR :
✓ Les grammaires ambiguës provoquent des
conflits :
▪ Conflit décalage/réduction : pas de décision à
la lecture du terminal a (faut-t-il réduire une
production S →  ou décaler le terminal a?).
▪ Conflit réduction/réduction : on ne peut pas
décider à la lecture du terminal a s'il faut
réduire une production S →  ou T → .
ESPRIM Khouja Med Khairallah 273
 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Remarques sur l’analyse syntaxique SLR :
✓ On doit alors résoudre les conflits en donnant des
priorités aux actions (décaler ou réduire) et aux
productions.
✓ Exemple : soit la grammaire définie par les
productions :
▪ E → E + E | E * E | (E) | nb

✓ Soit à analyser le mot « 3+4+5 ».

ESPRIM Khouja Med Khairallah 274

 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Remarques sur l’analyse syntaxique SLR :
✓ Lorsqu'on lit le 2ième « + », on a le choix entre :
▪ Réduire ce qu'on a déjà lu par E → E + E; Ce
qui nous donnera finalement le calcul (3+4)+5.
▪ Décaler ce « + », ce qui nous donnera
finalement le calcul 3+(4+5).
✓ Ici on s'en cague car c'est pareil. Mais bon, «+
» est associatif à gauche, donc on préfèrera
réduire.
ESPRIM Khouja Med Khairallah 275
 CH5. Analyse syntaxique

Analyse syntaxique
ascendante
➢ Remarques sur l’analyse syntaxique SLR :
✓ Soit à analyser « 3+4*5 ».
▪ Lorsqu'on lit le « * », on a encore un choix
« shift/reduce ».
▪ Si l'on réduit, on calcule (3+4)*5, et si on
décale, on calcule 3+(4*5)!
▪ On ne peut plus s'en foutre ! Il faut décaler.

ESPRIM Khouja Med Khairallah 276

 CH5. Analyse syntaxique

Analyse syntaxique
ascendante

➢ Remarques sur l’analyse syntaxique SLR :

✓ Soit à analyser 3*4+5.
▪ On ne s'en fout pas non plus, il faut réduire!

▪ Bref, il faut mettre quelque part dans

l'analyseur le fait que « * » est prioritaire sur
« + ».

ESPRIM Khouja Med Khairallah 277