III. Analyse Syntaxique. 7ème Cours.
III.4 Analyse descendante.
Est une analyse syntaxique efficace sans rebroussement (analyse prédictif). Elle peut :
- Déterminer une dérivation gauche associée à une chaine d’entrée.
- Construire un arbre d’analyse de la chaine d’entrée, en partant de la racine et en créant
les nœuds de l’arbre en pré ordre.
La descente récursive est une forme générale d’analyse descendante, elle peut impliquer
des retours arrière (passages répétés sur le texte source).
N.B :
En écrivant soigneusement une grammaire après élimination des récursivités à gauche et
après avoir appliqué la factorisation à gauche, nous obtenons une grammaire qui peut être
analysée par prédictif.
Exemple :
instr → si expr alors instr sinon instr | tant que expr faire instr | début liste_instr fin
Les mots clés : si, tant que et début nous prédisent quelle alternative est seule susceptible de réussir
lorsque l’on développe une instruction.
Diagramme de transition pour analyseur prédictif.
Un diagramme de transition est un guide dans un analyseur prédictif. Pour construire un
diagramme de transition, il faut :
- Eliminer les récursivités gauches de la grammaire.
- Factoriser la grammaire à gauche.
- Pour chaque non terminal, il faut :
o Créer un état initial et un état final (retour).
o Pour Chaque production A→X1X2 … Xn, créer un chemin de l’état initial à l’état final,
dont les arcs sont étiquetés X1, X2, …, Xn.
- Simplifiez, s’il est possible, ces diagrammes de transition.
III.5 Calcul des ensembles des premiers et suivants.
Les deux fonctions PREMIER et SUIVANT permettent, quand c’est possible, de remplir
les entrées de la table d’analyse prédictive pour une grammaire G. Les ensembles d’unités
lexicales produits par la fonction SUIVANT peuvent être utilisés aussi comme unités
lexicales de synchronisation pendant la récupération sur erreur en mode panique.
On note PREMIER (α) l’ensemble des terminaux qui commencent les chaines qui se
dérivent de la chaine α.
On note SUIVANT (A) l’ensemble des terminaux a qui peuvent apparaitre immédiatement
à droite de A.
• Algorithme de calcul de PREMIER (X) : (Pour tout symbole de la grammaire X)
1. Si X est un terminal, PREMIER (X) = {X}.
2. Si X → ɛ est une production, ajouter ɛ à PREMIER (X).
3. Si X est un non terminal et X → Y1Y2 … YK une production, mettre a dans PREMIER
(X) s’il existe i tel que a est dans PREMIER (Yi) et que ɛ est dans tous les PREMIER
(Y1), …, PREMIER (Yi-1). Si ɛ est dans PREMIER (Yj) pour tous les j =1, 2, …, k,
ajouter ɛ à PREMIER (X). Si Y1 ne se dérive pas en ɛ, on n’ajoute rien de plus à
PREMIER (X), mais si Y1==> ɛ, on ajoute * PREMIER (Y2), etc.
III. Analyse Syntaxique. 7ème Cours.
• Algorithme de calcul de SUIVANT (A) : (Pour tous les non terminaux de A)
1. Mettre $ dans SUIVANT(S), où S est l’axiome et $ est le marqueur droit indiquant la fin
du texte source.
2. S’il y a une production A → αBβ, le contenu de PREMIER(β), excepté ɛ, est ajouté à
SUIVANT(B).
3. S’il existe une production A → αB ou une production A → αBβ telle que
PREMIER(β) contient ɛ (c'est-à-dire
* β==> ɛ), les éléments de SUIVANT(A) sont ajoutés à
SUIVANT(B).
• Algorithme de construction de la table d’analyse prédictive d’une grammaire G.
1. Pour chaque production A → α de la grammaire, procéder aux étapes 2 et 3.
2. Pour chaque terminal a dans PREMIER (α), ajouter A → α à [M, a].
3. Si ɛ est dans PREMIER (α), ajouter A → α à [M, b] pour chaque terminal b dans
SUIVANT(A). Si ɛ est dans PREMIER (α) et $ est dans SUIVANT(A), ajouter A → α à
[M, $].
4. Faire de chaque entrée non définie de M une erreur.
III.6 Grammaires LL (1).
Exemple :
Soit la grammaire G suivante :
S → iEtSS’ | a
S’→ eS | ɛ
E→b
Sa table d’analyse est la suivante :
Non – Symbole d’entrée
Terminal A b e i t $
S S→ a S → iEtss’
S’ → ɛ S’ → ɛ
S’
S’ → eS
E E→b
Table III.1. Table d’analyse de la grammaire G.
Remarque :
L’entrée M [S’, e] contient à la fois S’ → eS et S’ → ɛ, car Suivant (S’) = {e, $}. Cette
grammaire est ambiguë (Problème de choix de production quand on rencontre un e).
Définition :
Une grammaire est dite LL (1) si sa table d’analyse n’a aucune entrée définie de façon
multiple.
L : Left to right scanning (parcours de l’entrée de la gauche vers la droite).
L : Leftmost derivation (dérivation gauche).
1 : On utilise un seul symbole d’entrée de prévision à chaque étape nécessitant la prise d’une
décision d’action d’analyse.
Soit A → α | β l’une des règles de production d’une grammaire G, cette dernière est dite LL
(1) si et seulement si :
- Pour aucun terminal a, α et β ne se dérivent toutes les deux en des chaines
commençant par a.
- Une des chaines au plus α et β peut se dériver en la chaine vide.
- Si β ==> * ɛ, α ne se dérive pas en une chaine commençant par un terminal de
suivant(A).
N.B : Aucune grammaire ambiguë ou récursive à gauche ne peut être LL (1).
