Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Analyse syntaxique descendante
Université Assane Seck
UFR Sciences et technologie
Département Informatique
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
1 Introduction
2 Problématique de la méthode descendante
3 Analyse LL(1)
4 Récursivité à gauche
5 Factorisation à gauche
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
1 Introduction
2 Problématique de la méthode descendante
3 Analyse LL(1)
4 Récursivité à gauche
5 Factorisation à gauche
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Introduction
L’analyseur syntaxique reçoit un mot sous forme de lexèmes
Il crée un arbre de dérivation pour déterminer si le mot est
syntaxiquement correct
Il existe deux approches pour construire un arbre de dérivation
Une méthode descendante : du haut vers le bas
Une méthode ascendante: du bas vers le haut
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Introduction
Construire l’arbre du haut vers le bas
La racine est l’axiome de départ
Les feuilles sont les unités lexicales
Exemple1:
S −→ aSbT|cT|d
T −→ aT|bS|c
Considérons le mot accbbadbc
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
1 Introduction
2 Problématique de la méthode descendante
3 Analyse LL(1)
4 Récursivité à gauche
5 Factorisation à gauche
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Problématique de la méthode descendante
S −→ aAb
On considère la grammaire suivante:
S −→ cd|c
Supposons le mot w = acb
Après la lecture de a on a deux choix pour c:
A −→ cd
A −→ c
Pour le savoir, il faut aussi lire le caractère suivant b
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Problématique de la méthode descendante
Conclusion
Ce qui serait pratique ça serait d’avoir une table qui nous dit: quand je lis un
tel caractère et que je suis à dériver tel symbole non-terminal, alors
j’applique telle règle et je ne me pose pas de question. Ça existe, et ça
s’appelle une table d’analyse.
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
1 Introduction
2 Problématique de la méthode descendante
3 Analyse LL(1)
Ensemble PREMIER
Table d’analyse
Analyseur syntaxique
4 Récursivité à gauche
5 Factorisation à gauche
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Pour construire une table d’analyse, on a besoin des ensembles PREMIER et
SUIVANT
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
Outline
1 Introduction
2 Problématique de la méthode descendante
3 Analyse LL(1)
Ensemble PREMIER
Table d’analyse
Analyseur syntaxique
4 Récursivité à gauche
5 Factorisation à gauche
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
On appelle PREMIER(α) −→ l’ensemble de tous les terminaux qui
peuvent commencer une chaine qui se dérive de α
∗
→ aβ avec β ∈ (VN ∪ VT)∗
On cherche toutes les lettres a tel α −
∗
ϵ ∈ PREMIER(α) si et seulement il existe une dérivation α −
→ϵ
Exemple
S −→ Ba
B −→ cP|bP|P|ϵ
P −→ dS
∗ ∗
S−
→ a donc a ∈ PREMIER(S), S − → cPa donc c ∈ PREMIER(S),
∗ ∗
S−
→ bPa donc b ∈ PREMIER(S), S −→ dSa donc d ∈ PREMIER(S)
Donc PREMIER(α) = {a, b, c, d}
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
Calcul des PREMIER(α) pour α ∈ (VT ∪ VN )∗
On a α → Y1 Y2 ...Yn avecYi ∈ (VN ∪ VT)∗
Si Y1 est un symbole terminal alors ajouter Y1 dans PREMIER(α)
Sinon
//Y1 est un non-terminal
ajouter les éléments de PREMIER(Y1 ) sauf ϵ dans PREMIER(α)
Si ϵ ∈ PREMIER(Y1 ) alors
Faire la meme chose avec Y2
Si Y2 est un symbole terminal alors ajouter Y2 dans PREMIER(α)
Sinon
//Y2 est un non-terminal
ajouter les éléments de PREMIER(Y2 ) sauf ϵ dans PREMIER(α)
Si ϵ ∈ PREMIER(Y2 ) alors
Faire la même chose avec Y3
Ainsi de suite jusqu’à Yn
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
Exemples
′
E −→ TE
′ ′ ′
E −→ +TE | − TE |ϵ
′
T −→ FT
′ ′ ′
T −→ ∗FT |/FT |ϵ
F −→ (E)|nb
PREMIER(E) = PREMIER(T) = {(, nb}
′
PREMIER(E ) = {+, −, ϵ}
PREMIER(T) = PREMIER(F) = {(, nb}
′
PREMIER(T ) = {∗, /, ϵ}
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
Exemples
′
E −→ TE
′ ′ ′
E −→ +TE | − TE |ϵ
′
T −→ FT
′ ′ ′
T −→ ∗FT |/FT |ϵ
F −→ (E)|nb
PREMIER(E) = PREMIER(T) = {(, nb}
′
PREMIER(E ) = {+, −, ϵ}
PREMIER(T) = PREMIER(F) = {(, nb}
′
PREMIER(T ) = {∗, /, ϵ}
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
Exemple
S −→ ABCe
A −→ aA|ϵ
B −→ bB|cB|e
C −→ de|da|dA
PREMIER(S) = {a, b, c, d}
PREMIER(A) = {e, ϵ}
PREMIER(B) = {b, c, ϵ}
PREMIER(C) = {d}
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
Exemple
S −→ ABCe
A −→ aA|ϵ
B −→ bB|cB|e
C −→ de|da|dA
PREMIER(S) = {a, b, c, d}
PREMIER(A) = {e, ϵ}
PREMIER(B) = {b, c, ϵ}
PREMIER(C) = {d}
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
1 Introduction
2 Problématique de la méthode descendante
3 Analyse LL(1)
Ensemble PREMIER
Table d’analyse
Analyseur syntaxique
4 Récursivité à gauche
5 Factorisation à gauche
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
on appelle SUIVANT(A) −→ l’ensemble de tous les terminaux a qui
peuvent apparaitre immédiatement à droite de A dans une dérivation:
∗
S−→ αAaβ
Exemple
S −→ Sc|Ba
B −→ BPa|bPb|P|ϵ
P −→ dS
a, b, c, d ∈ SUIVANT(S) car il y’a les dérivations
∗ ∗ ∗ ∗
S−→ Sc, S − → dSa, S −
→ bdSba, S − → dSdSaa
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
Ajouter un marqueur de fin de chaine (symbole $ par exemple) à
SUIVANT(S)
Pour chaque forme A −→ αBβ où β est un non-terminal, alors ajouter
PREMIER(β) à SUIVANT(B) sauf ϵ
Pour chaque production de la forme A −→ αB ajouter SUIVANT(A) à
SUIVANT(B). En effet, toute régle S −→ SAβ se dérive en
S −→ SαBβ. Donc, SUIVANT(A) ∈ SUIVANT(B)
Pour chaque production de la forme A −→ αBβ avec ϵ ∈ Premier(β)
ajouter SUIVANT(A) à SUIVANT(B)
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
Exemples
′
E −→ TE
′ ′ ′
E −→ +TE | − TE |ϵ
′
T −→ FT
′ ′ ′
T −→ ∗FT |/FT |ϵ
F −→ (E)|nb
SUIVANT(E) = {$, )}
′
SUIVANT(E ) = {$, )}
SUIVANT(T) = {+, −, $, )}
′
SUIVANT(T ) = {+, −, $, )}
SUIVANT(F) = {∗, /, ), +, −$, )}
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
Exemples
′
E −→ TE
′ ′ ′
E −→ +TE | − TE |ϵ
′
T −→ FT
′ ′ ′
T −→ ∗FT |/FT |ϵ
F −→ (E)|nb
SUIVANT(E) = {$, )}
′
SUIVANT(E ) = {$, )}
SUIVANT(T) = {+, −, $, )}
′
SUIVANT(T ) = {+, −, $, )}
SUIVANT(F) = {∗, /, ), +, −$, )}
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
1 Introduction
2 Problématique de la méthode descendante
3 Analyse LL(1)
Ensemble PREMIER
Table d’analyse
Analyseur syntaxique
4 Récursivité à gauche
5 Factorisation à gauche
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
Table d’analyse LL(1): Construction de la table
Une table d’analyse est un tableau à deux dimensions où les cases sont de la
forme [A, a] avec a ∈ VT et A ∈ VN ∪ $
Pour tout a ∈ PREMIER(α) (et a ̸= ϵ), rajouter la production A −→ α
dans la case M[A, a]
Si ϵ ∈ PREMIER(α), alors chaque b ∈ SUIVANT(A) ajouter A −→ α
dans la case M[A, b]
Chaque case M[A, b] vide correspond à une erreur syntaxique
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Ensemble PREMIER
Table d’analyse
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Analyseur syntaxique
Outline
1 Introduction
2 Problématique de la méthode descendante
3 Analyse LL(1)
Ensemble PREMIER
Table d’analyse
Analyseur syntaxique
4 Récursivité à gauche
5 Factorisation à gauche
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Analyseur syntaxique
1 Introduction
2 Problématique de la méthode descendante
3 Analyse LL(1)
Ensemble PREMIER
Table d’analyse
Analyseur syntaxique
4 Récursivité à gauche
5 Factorisation à gauche
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Analyseur syntaxique
Analyseur syntaxique
On utilise une pile initialisée à Z0 , S, et un symbole de "look-ahead" p qui
pointe sur le caractère courant du mot à analyser.
Etape d’analyse : On compare le symbole de haut de pile X avec p.
1er cas : X est un symbole terminal
si X = p, on dépile X et on décale p
sinon, REJECT
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Analyseur syntaxique
2e cas : X est un symbole non-terminal
si [X, p] est une règle X −→ ϵ, on dépile X (et on n’empile rien).
si [X, p] est une règle X −→ Y1 Y2 ...Yn , (où chaque Yi est un
caractère différent), on dépile X et on empile Yn Yn−1 ...Y1 (sauf ϵ).
si [X, p] est une case vide : REJECT.
3e cas : X = Z0
si p=$, ACCEPT
sinon, REJECT
Exemple : on va analyser le mot w = 2 + 3 ∗ 4
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Analyseur syntaxique
Grammaire LL(1)
Définition
On appelle grammaire LL(1) une grammaire pour laquelle chaque case de
la table d’analyse décrite contient au plus une règle de production.
Le terme LL(1) signifie:
L pour Left to right scanning: parcours de l’entrée de gauche à
droite
L pour leftmost derivation: on utilise les dérivations gauches
(1): un seul élément de prévision est nécessaire à chaque étape
Montrez que les grammaires suivantes ne sont pas LL(1)
S −→ aAb S −→ aTbbb
A −→ cd|c T −→ Tb|ϵ
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Récursivité à gauche
Récursivité immédiate à gauche
Une grammaire est immédiatement récursive à gauche si elle contient un
non-terminal A tel qu’il existe une production A −→ Aα où αest une chaine
quelconque
Elimination de la récursivité à gauche immédiate
toute règle de la′ forme A −→ Aα|β par
Remplacer
A −→ βA
′ ′
A −→ αA |ϵ
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Récursivité à gauche
Récursivité immédiate à gauche
Une grammaire est immédiatement récursive à gauche si elle contient un
non-terminal A tel qu’il existe une production A −→ Aα où αest une chaine
quelconque
Elimination de la récursivité à gauche immédiate
toute règle de la′ forme A −→ Aα|β par
Remplacer
A −→ βA
′ ′
A −→ αA |ϵ
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Récursivité à gauche
S −→ ScA|B
A −→ Aa|ϵ
B −→ Bb|d|ϵ
Cette grammaire contient plusieurs récursivités à gauche immédiates
Une grammaire non récursive équivalente est:
′
S −→ BS
′ ′
S −→ cAS |ϵ
′
A −→ A
′ ′
A −→ aA |ϵ
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Récursivité à gauche
Récursivité à gauche
Une grammaire est récursive à gauche si elle contient un non-terminal A tel
+
qu’il existe une dérivation A −
→ Aα où α est une chaine quelconque.
Exemple:
S −→ Aa|b
A −→ Ac|Sd|c
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Récursivité à gauche
Élimination de la récursivité gauche pour toute grammaire sans
ϵ − production
Ordonner tous les non-terminaux A1 , A2 , ..., An
Pour chaque i=1 à n faire
pour j=1 à i-1 faire
remplacer chaque production de la forme Ai −→ Aj α|γ où
Aj −→ β1 ...βp par Ai −→ β1 α|...|βp α|γ
fin pour
éliminer les récursivités à gauche immédiates des productions Ai
fin pour
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Récursivité à gauche
Exemple:
S −→ Aa|b
A −→ Ac|Sd|BA|c
B −→ SSc|a
On ordonne S, A, B
i = 1 pas de récursivité immédiate dans S −→ Aa|b
i = 2 et j = 1 on obtient A −→ Ac|Aad|bd|BA|c
On élimine la récursivité immédiate:
′ ′ ′
A −→ bdA |BAA |cA
′ ′ ′
A −→ cA |adA |ϵ
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Récursivité à gauche
′ ′ ′
i = 3 on obtient B −→ bdA aSc|BAA aSc|cA Asc|bSc|a
On élimine la récursivité immédiate :
′ ′ ′ ′ ′ ′ ′
B −→ bdA aScB |BAA aSc|cA AscB |bScA |aB
′ ′
B −→ AA aScB |ϵ
• S −→ Aa|b
′ ′ ′
• A −→ bdA |BAA |cA
′ ′
• A −→ SSc|cA |ϵ
′ ′ ′ ′ ′ ′
• B −→ bdA aScB |cA AScB |bScA |aB
′ ′
• B −→ AA aScB |ϵ
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
1 Introduction
2 Problématique de la méthode descendante
3 Analyse LL(1)
4 Récursivité à gauche
5 Factorisation à gauche
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Factorisation à gauche
Factorisation à gauche
On dit qu’une grammaire algébrique G est non factorisée à gauche si elle
contient un non terminal A dont l’ensemble des parties droites de
productions est de la forme A −→ αβ1 |αβ2 ....|γ1 |....|γp
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Procédé de factorisation gauches
Pour chaque non-terminal A, trouver un plus long préfixe α commun à
plusieurs parties droites de production dont A est partie gauche
A −→ αβ1 |αβ2 ....|γ1 |....|γp remplacé par
′
A −→ αA |γ1 |....|γp
′
A −→ β1 |β2 |...|βn
Recommencer jusqu’à ce qu’il n’y ait plus de préfixe propre
commun.
On obtient une grammaire équivalente
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Exemple de factorisation
On
considère les règle de production suivantes:
E −→ T + E|T
T −→ F ∗ T|F
F −→ (E)|n
Réécriture de la règle :T −→ T + E|T. On obtient:
′
E −→ TE
′
E −→ +E|ϵ
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Exemple de factorisation
On
considère les règle de production suivantes:
E −→ T + E|T
T −→ F ∗ T|F
F −→ (E)|n
Réécriture de la règle :T −→ T + E|T. On obtient:
′
E −→ TE
′
E −→ +E|ϵ
Malick NDOYE Université Assane Seck
Compilation
Introduction Problématique de la méthode descendante Analyse LL(1) Récursivité à gauche Factorisation à gauche
Exemple de factorisation
Réécriture de la règle : T −→ F ∗ T|F on obtient :
′
T −→ FT
′
T −→ ∗T|ϵ
On obtient globalement la forme :
′
E −→ TE
′
E −→ +E|ϵ
′
T −→ FT
′
T −→ ∗T|ϵ
F −→ (E)|n
Malick NDOYE Université Assane Seck
Compilation
