II/ Analyse syntaxique ascendante
• Analyse SLR
• Analyse LR
• Analyse LALR
Analyse syntaxique ascendante
• Principe : construire un arbre de dérivation du bas (les
feuilles, i.e les unités lexicales) vers le haut (la racine, i.e
l'axiome de départ).
• Le modèle général utilisé est le modèle par décalages-
réductions. décalage (shift) : décaler d'une lettre le
pointeur sur le mot en entrée
• réduction (reduce) : réduire une chaîne (suite
consécutive de terminaux et non terminaux à gauche du
pointeur sur le mot en entrée et finissant sur ce pointeur)
par un non-terminal en utilisant une des règles de
production
Exemple : avec le mot u=aacbaacbcbcbcbacbc
décaler
décaler
décaler
réduire par S->c
décaler (4 fois encore)
réduire par S->c
décaler
décaler
réduire par S->c
réduire par S-> aSbS
décaler
décaler
réduire par S->c
réduire par S->aSbS
réduire par S->aSbS
décaler
réduire par S->c
réduire par S->aSbS
décaler
décaler
décaler
réduire par S -> c
décaler
décaler
réduire par S-> c
réduire par S->aSbS
réduire par S->aSbS
Remarque:
• Méthodes d’analyses syntaxiques ascendantes: LR (Left
scanning Rightmost derivation)
• Etant donné un mot, elles construisent une dérivation la plus
à droite mais inversée. Dans l’exemple introductif:
aacbaacbcbcbcbacbc ⇐ aaSbaacbcbcbcbacbc ⇐ aaSbaaSbcbcbcbacbc ⇐
⋯ ⇐ aaSbSbacb𝑐 ⇐ aSbacb𝑐 ⇐ aSbaSb𝑐 ⇐ aSbaSbS ⇐ aSbS ⇐ 𝑆
Table d'analyse LR
• Les lignes: numéros d’états de l’automate à pile
• Cette table va nous dire ce qu'il faut faire quand on lit une
lettre a et qu'on est dans un état i
- soit on décale. Dans ce cas, on empile la lettre lue et on va
dans un autre état j. Ce qui sera noté dj
- soit on réduit par la règle de production numéro, 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 cela par rp
- soit on accepte le mot. Ce qui sera noté ACC
- soit c'est une erreur. Case vide
• Un 0-item (ou LR(0)-item ou plus simplement item) est une
production de la grammaire avec un "." quelque part dans la
partie droite. Par exemple (sur la gram ETF) : E -> E . + T ou
encore T-> F. ou encore F -> . ( E )
• 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 𝐴 → 𝛼 ∙ 𝐵𝛽
Pour chaque production 𝐵 → 𝛾
rajouter l'item 𝐵 →∙ 𝛾 dans Fermeture(I)
3- Recommencer 2 jusqu'à ce qu'on n'ajoute rien de nouveau
Exemple:
et soit l'ensemble d'items { T T * . F, E E.+T}. La fermeture de cet ensemble d'items est :
{T T*.F, E E.+T, F .nb, F .(E)}
• Transition par X d'un ensemble d'items I :
𝛿 𝐼, 𝑋 = 𝑓𝑒𝑟𝑚𝑒𝑡𝑢𝑟𝑒 𝑑𝑒 𝑡𝑜𝑢𝑠 𝑙𝑒𝑠 𝑖𝑡𝑒𝑚𝑠 𝐴 → 𝛼𝑋 ∙ 𝛽 𝑜ù 𝐴 → 𝛼 ∙ 𝑋𝛽 est dans I
Soit I={T → T*.F, E → E.+T, F →.nb, F → .(E)}
on a:
𝛿(I,F) = { T→ T*F.}
𝛿(I,+) = { E → E+.T, T →.T*F, T → .F, F → .nb, F →.(E)}
Collection des items d'une grammaire :
Rajouter un nouvel axiome S' avec la production S' → S
1- Mettre dans l'item I0 la Fermeture({S' → .S})
2- Mettre I0 dans Collection
3 - Pour chaque I dans Collection faire
Pour chaque X tel que 𝛿(I, X) est non vide
ajouter ce 𝛿(I, X) dans Collection
Fin pour
4 - Recommencer 3 jusqu'à ce qu'on n'ajoute rien de nouveau
Construction de la table d'analyse SLR (Simple LR):
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 𝐴 → 𝛼 ∙ contenu dans Ii :
pour chaque a de SUIVANT(A) faire
mettre rp (p: numéro de la règle 𝐴 → 𝛼) dans la case M[i,a]
Grammaire SLR(1)
Une grammaire dont la table d’analyse présente au plus une
règle par case est une grammaire SLR(1)
Automate LR(0)
Exemple:
état nb + * ( ) $ E T F
0 d5 d4 1 2 3
1 d6 ACC
2 r2 d7 r2 r2
3 r4 r4 r4 r4
4 d5 d4 8 2 3
5 r6 r6 r6 r6
6 d5 d4 9 3
7 d5 d4 10
8 d6 d11
9 r1 d7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
• Analyseur syntaxique SLR : On part de l'état 0,
et on empile et dépile non seulement les
symboles (comme lors de l'analyse LL) mais
aussi les états successifs.
Exemple:
Exemple:
Conclusion
• cette méthode permet d'analyser plus de grammaires
que la méthode descendante (car il y a plus de
grammaires SLR que LL)
• 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.
• Les grammaires ambigües provoquent des conflits:
– conflit décalage/réduction : on ne peut pas décider à la
lecture du terminal a s'il faut réduire une production ou
décaler le terminal
– conflit réduction/réduction : on ne peut pas décider à la
lecture du terminal a s'il faut réduire par une production
ou par une autre
Exercice
Soit la grammaire:
𝐸 → 𝐸 + 𝐸 𝐸 ∗ 𝐸 𝐸 | 𝑛𝑏
1. Donner la table d’analyse SLR
2. Résoudre les conflits en posant les hypothèses que + et ∗ sont associatifs
à gauche et ∗ est prioritaire par rapport à +
