CH.
3 L'ANALYSE SYNTAXIQUE
• 3.1 Le rôle de l’analyseur syntaxique
• 3.2 Les grammaires
• 3.3 L’analyse descendante
• 3.4 L’analyse ascendante
3.1 Le rôle de l’analyseur syntaxique
unité lexicale
programme analyseur analyseur arbre
source lexical (sur requête) syntaxique d’analyse
table des symboles
Rôle central de la partie frontale :
active l’analyseur lexical;
vérifie la conformité syntaxique;
construit l’ arbre d’analyse ;
prépare ou anticipe la traduction ;
gère les erreurs communes de syntaxe.
1
Types d’analyseurs syntaxiques :
• méthodes universelles (Cocke-Younger-Kasami),
permettent une analyse de n’importe quelle
grammaire algébrique, mais performance en O(n3) ;
• méthodes linéaires en O(n), sur certaines grammaires :
analyse descendante, la plus intuitive, se prête bien à
certains types de traductions ;
analyse ascendante, plus sophistiquée, la plus utilisée
par les générateurs automatiques d’analyseurs syntaxiques,
car ne nécessite que peu d’adaptations de la grammaire.
Traitement des erreurs :
• diagnostic (messages) ;
• redémarrage :
mode panique, jusqu’à resynchronisation ;
correction, difficile si l’erreur est antérieure à sa détection ;
règles d’erreurs, intégrées à la grammaire.
2.1 Les grammaires
Syntaxe spécifiée par des règles de grammaire.
• Symboles terminaux (= unités lexicales) alphabet A ;
• Symboles intermédiaires ou variables (= catégories
grammaticales) alphabet X ;
• Règles de grammaire x → w , où x ∈ X et où w ∈ (A∪X)*
w est un mot quelconque, même vide.
Exemples :
instr → si expr alors instr sinon instr
phrase → gsujet gverbe gcomplément
• Axiome (= programme)
Langage engendré = mots terminaux dérivant de l’axiome.
2
Exemple : Expressions arithmétiques
E → nombre Arbre d’analyse de 3*(6+2)
E→(E)
E→E+E E
E→E–E
E * E
E→E*E
E→E/E 3 nombre ( E )
E + E
6 nombre 2 nombre
Les valeurs explicites sont des attributs des unités lexicales.
L’association aux unités lexicales est réalisée par l’analyseur
lexical.
Ambiguïté :
Lorsqu’un même mot possède plusieurs arbres d’analyse.
Exemple précédent ambigu : 5*2+3
E E
E + E E * E
E * E 3 nombre 5 nombre E + E
5 nombre 2 nombre 2 nombre 3 nombre
Inutilisable en l’état : nécessité de lever les ambiguïtés
3
Grammaire non ambiguë pour expressions arithmétiques suffixes :
E → EE + | EE – | EE * | EE / | nombre
Grammaire non ambiguë pour les expressions arithmétiques :
E → E +T | E –T | T Choix : associativité à gauche
T → T *F | T /F | F priorité de * et / sur + et –
F → ( E ) | nombre
Analyse syntaxique :
Étant donné un mot terminal, déterminer s’il est ou non engendré
par la grammaire ; si oui, en donner un arbre d’analyse.
• Méthode universelle : essayer toutes les dérivations à partir de
l’axiome, jusqu’à trouver le mot. Des règles de longueur (après
modifications) permettent d’éliminer les impasses.
• Méthode descendante (descente récursive) : une procédure par
variable, les terminaux servant à choisir la dérivation (prévision)
et à la validation.
• Méthode ascendante : on lit le mot (décalage) jusqu’à identifier
des dérivations, qu’on réduit et empile (réduction).
4
3.3 L’analyse descendante
Une procédure par variable.
Problème : récursivité directe à gauche ;
nécessité une transformation pour l’éliminer.
Grammaire de départ Grammaire modifiée
E → E +T | T A → E$ (production augmentée)
T → T *F | F E → TG
F → (E ) | nombre G → +TG | ε
T → FU
U → *FU | ε
F → (E ) | nombre
Procédures correspondantes : deux procédures supposées écrites :
• prevision retourne l’unité lexicale suivante sans l’enlever ;
• correspond(x) lit l’unité lexicale suivante, l’enlève et signale une
erreur si elle ne vaut pas x. Ici plus, nombre, etc. sont les
codes d’unités lexicales renvoyés par l’analyseur lexical.
procedure expression ; procedure expression ;
begin writeln(‘E>TG’) ; begin writeln(‘E>TG’) ;
terme ; encoreterme terme ;
end ; while prevision = plus do
begin
procedure encoreterme ; writeln(‘G>+TG’) ;
begin correspond(plus) ;
if prevision = plus then terme
begin writeln(‘G>+TG’) ; end ;
correspond(plus) ; writeln(‘G>epsilon’)
terme ; encoreterme end ;
end
else writeln(‘G>epsilon’)
end ; En éliminant la récursivité
terminale et en regroupant
5
procedure terme ; procedure facteur ;
begin writeln(‘T>FU’); begin
facteur ; if prevision = ouvrante then
while prevision = mult do begin writeln(‘F>(E)’) ;
begin writeln(‘U>*FU’) ; correspond(ouvrante) ;
correspond(mult) ; expression ;
facteur correspond(fermante)
end ; end
writeln(‘U>epsilon’) else if prevision = nombre then
end ; begin writeln(‘F>nombre’);
correspond(nombre)
end
procedure analyse ; else writeln(‘erreur syntaxique’)
begin writeln(‘A>E$’) ; end ;
expression ; correspond(dollar) ; writeln(‘analyse reussie’)
end ;
L’échec de l’analyse est aussi pris en charge par correspond(x).
Fonctions PREMIER et SUIVANT
PREMIER(x) SUIVANT(x)
PREMIER(x) = ensemble des terminaux pouvant apparaître
au début d’une dérivation de x.
SUIVANT(x) = ensemble des terminaux pouvant suivre x dans
une dérivation
6
Calcul de PREMIER :
On construit un graphe entre tous les symboles grammaticaux.
Flèche de x vers y ssi
x → α y β et α est vide ou annulable.
Ici, α ne peut contenir que des variables, β est quelconque.
PREMIER( x) = { a terminal | il existe un chemin de x à a } ;
si x est annulable, il faut y ajouter ε.
Exemple de la grammaire précédente : Annulables : G et U
Graphe : A E T F ( G + U *
nombre
PREMIER(A) = PREMIER(E) = PREMIER(T) = PREMIER(F) = { (, nombre }
PREMIER(G) = {+, ε } PREMIER(U) = { *, ε }
Calcul de SUIVANT :
On construit un graphe entre tous les symboles grammaticaux.
Flèche de x vers y ssi ou bien
• il existe z → α x β , y est terminal et y ∈ PREMIER(β) ;
• il existe y → α x β et β est vide ou annulable.
Ici, α et β sont quelconques, même vides, et y ≠ ε.
SUIVANT( x) = { a terminal | il existe un chemin de x à a }.
Exemple de la grammaire précédente :
F *
Graphe : SUIVANT n’a pas de sens pour l’axiome
U T + A de la production augmentée.
SUIVANT(G) = SUIVANT(E) = { $, ) }
G E $ SUIVANT(U) = SUIVANT(T) = { +, $, ) }
SUIVANT(F) = { *, +, $, ) }
)
7
PREMIER et SUIVANT permettent de caractériser les
grammaires analysables de façon descendantes, avec un seul
symbole de prévision a :
partie déjà symbole de partie restant
analysée prévision à analyser
Grammaires LL(1).
E → α règle applicable avec a en prévision lorsque
a ∈ PREMIER (α.SUIVANT (E)),
c ’est-à-dire a ∈ PREMIER (α) si α non annulable
et a ∈ SUIVANT (E) si α annulable
La grammaire est LL(1) lorsqu’à chaque étape une seule règle
satisfait aux critères précédents.
Table d’analyse LL(1) :
0 A → E$
+ * n $ ( ) 1 E → TG
E 1 1 2 G → +TG
G 2 3 3 3G→ε
T 4 4 4 T → FU
U 6 5 6 6 5 U → *FU
6U→ε
F 7 8
7F→(E)
8 F → nombre
Les case vides de la table correspondent à des erreurs syntaxiques.
La table commande les branchements dans les procédures de
l’analyse par descente récursive.
On peut l’utiliser comme donnée d’un programme universel d’ana-
lyse descendante non récursive.
8
3.4 L’analyse ascendante
On utilise une pile, et une table de transition entre états.
(Automate déterministe à une pile)
En fonction du symbole de pré-vision,
• on empile un état en lisant un caractère de l’entrée (décalage) ;
• on dépile autant de symboles que la longueur de la règle
qu’on a reconnue, et on empile un nouvel état (réduction).
pile
partie analysée partie non analysée
Exemple : expressions arithmétiques
0 A → E$ PREMIER :
1 E → E +T
2E→T A E T F (
3 T → T *F n
SUIVANT :
4T→F
5 F → (E ) F T E $
6F→n
+
* )
Calcul des états : ensembles de règles marquées (items) ;
Si un état contient x → u •yv, il contient aussi tous les y → •w
(clôture) ;
Si un état contient x → u •yv, on a une transition par y sur un
état contenant x → uy •v.
9
état 0 état 1 $ ACCEPTÉ
A → •E$ E A → E •$ état 9
état 6
E → •E +T E → E • +T + T
E → E +T •
E → •T E → E + •T
T → T • *F
T → •T *F état 2 T → •T *F
F
T → •F T E→T• T → •F 3 7
*
F → •(E ) T → T • *F F → •( E ) (
4
F → •n F → •n n
* 5
F état 3 état 10
état 7
n T→F• F
T → T *F •
( T → T * •F
état 5 état 4 F → •(E ) (
4
F→n• F → •n n
F → (•E ) 5
E → •E +T état 8 état 11
E → •T E )
F → (E )•
n F → (E •)
T → •T *F
E → E • +T +
T → •F 6
T
F → •(E ) 2
(
F → •n F
3
Fonctionnement de l’analyseur :
Au début, la pile contient l’état 0.
On lit la lettre courante du mot à analyser ; avec l’état du
sommet de pile, elle spécifie l’état à empiler (décalage).
Lorsqu’un état contient un item du type x → u •, on peut
enlever de la pile les | u| états au sommet, et empiler l’état
spécifié par le nouveau sommet et x (réduction).
Parfois des conflits se produisent : décalage–réduction ou
réduction–réduction ; cas général, x → u •, y → v •,
z → r •st, où s est est terminale. Le conflit peut être
tranché lorsque SUIVANT( x), SUIVANT( y) et s sont
disjoints, en examinant le caractère de pré-vision.
Une telle grammaire est dite SLR(1).
10
La suite des réductions constitue une dérivation du mot à
analyser, à partir de la fin, et de droite à gauche.
Tableau d’analyse SLR(1) des expressions arithmétiques
n + * ( ) $ E T F
0 d5 d4 d1 d2 d3
1 d6 A
2 r2 d7 r2 r2
3 r4 r4 r4 r4
4 d5 d4 d8 d2 d3
5 r6 r6 r6 r6
6 d5 d4 d9 d3
7 d5 d4 d10
8 d6 d11
9 r1 d7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
Exemple : (3 + 2) * 4 $ Pile Mot restant Règle
027 4$
Pile Mot restant Règle
0275 $
0 2 7 10 $ F→n
0 (3 + 2) * 4 $ T → T *F
02 $
04 3 + 2) * 4 $ E→T
01 $
045 + 2) * 4 $ ACCEPTÉ
043 + 2) * 4 $ F→n
042 + 2) * 4 $ T→F
048 + 2) * 4 $ E→T
0486 2) * 4 $ Dérivation obtenue :
04865 )*4$
04863 )*4$ F→n E ⇒T ⇒T *F ⇒T * 4 ⇒F * 4
04869 )*4$ T→F ⇒ (E) * 4 ⇒ (E + T) * 4
048 )*4$ E → E +T ⇒ (E + F) * 4 ⇒ (E + 2) * 4
0 4 8 11 *4$ ⇒ (T + 2) * 4 ⇒ (F + 2) * 4
03 *4$ F → (E ) ⇒ (3 + 2) * 4
02 *4$ T→F
11
Parfois, les conflits ne peuvent pas être levés par l’examen
des ensembles SUIVANT. On tient alors compte des
caractères pouvant suivre un item pendant la construction.
Si l’automate ainsi construit n’a plus de conflits, on a une
grammaire LR(1).
Inconvénient : très grand nombre d’états.
Solution de compromis : directement sur l’automate simple
précédent, étudier la propagation des caractères pouvant
suivre un item. Dans le cas des réductions, cet ensemble
joue le rôle des ensembles SUIVANT du cas SLR(1). Si
les conflits sont ainsi réglés, la grammaire est LALR(1).
Méthode adoptée par YACC.
LR(1) ⊃ LALR(1) ⊃ SLR(1)
Propagation du contexte :
item x → u •yv (z) donnant par clôture y → •w (PREMIER (vz))
par transition x → uy •v (z)
N.B. Le graphe obtenu peut avoir des boucles.
état 0
A → •E$ ( )
E → •E +T ($, +)
E → •T ($, +) état 2
T → •T *F ($, +, *) T E→T• ($, +)
T → •F ($, +, *) T → T • *F ($, +, *)
F → •(E ) ($, +, *)
F → •n ($, +, *)
conflit levé
Dans l’exemple, le résultat est le même que par SLR(1).
12
Utilisation de l’ambiguïté :
0 A → E$
1 E → E +E Grammaire ambiguë pour
2 E → E *E expressions arithmétiques
3 E → (E )
4E→n SUIVANT(E ) = {$, +, *, )}
Ne peut être analysée par un analyseur déterministe,
car ambiguë.
Néanmoins, des règles de priorité permettent de lever les
conflits.
état 0 état 1 $ ACCEPTÉ état 6
A → •E$ E A → E •$ E → E +E • +
3
état 3
E → •E +E E → E •+E + E E → E •+E *
E → •E *E E → E •*E E → E + •E E → E •*E
4
E → •(E ) E → •E +E
E → •n ( état 2 E → •E *E (
2
*
E → (•E ) E → •(E ) n
3
n E → •E +E E → •n
(
E → •E *E état 4
état 7
état 9 E → •(E ) E E → E *E • +
E → E * •E 3
E→n• E → •n E → E •+E
n E → •E +E *
E → E •*E 4
E → •E *E
E
E → •(E ) (
2
E → •n n
3
état 5 état 8
E → (E •)
) E → (E ) •
E → E •+E +
3
E → E •*E *
4
13
Conflits décalage-réduction
état 6
E → E +E • Sur $, ), pas de conflit, réduire
E → E •+E Sur +, réduire car + associatif à gauche
E → E •*E Sur *, décaler car * prioritaire sur +
état 7
E → E *E • Sur $, ), pas de conflit, réduire
E → E •+E Sur +, réduire car * prioritaire sur +
E → E •*E Sur *, réduire car * associatif à gauche
Si conflit entre x → u op1y • et x → u •op2y :
1) op1 prioritaire sur op2, réduire ;
2) op2 prioritaire sur op1, décaler ;
3) op1 et op2 ont même priorité :
3.1) associativité à gauche, réduire ;
3.2) associativité à droite, décaler ;
3.3) pas d’associativité, signaler une erreur.
Récupération sur erreurs :
Exemple de correction. Entrées en italique.
n + * ( ) $ E
0 d3 1 1 d2 2 1 d1
1 3 d3 d4 3 2 A
2 d3 1 1 d2 n d5
3 d3 1 1 d2 2 1 d6
4 d3 1 1 d2 2 1 d7
5 3 d3 d4 3 d8 4
6 r1 r1 d4 r1 r1 r1
7 r2 r2 r2 r2 r2 r2
8 r3 r3 r3 r3 r3 r3
9 r4 r4 r4 r4 r4 r4
1 Empiler 5 (un id imaginaire) et signaler “opérande manquant”
2 Enlever ) de l’entrée et signaler “parenthèse fermante en trop”
3 Empiler 6 (un + imaginaire) et signaler “opérateur manquant”
4 Empiler 8 et signaler “parenthèse fermante manquante”
Les réductions sur n amèneront une erreur utérieurement.
14
