TD COMPILATION
Analyse Syntaxique
Analyse Syntaxique
• Le But:
Reconnaitre la suite des entités reconnues en lexicale
• Le Rôle:
La vérification de la forme de la suite des entités lexicales, qui se fait à
l’aide d’une grammaire spécifique
Exemple d’une grammaire
A→aA|bC|c
C→cA
Introduction à la compilation
(Analyse syntaxique)
Méthodes
d’analyse
syntaxique
Méthodes Méthodes
Descendantes Ascendantes
Non
Déterministes
Déterministes
Introduction à la compilation
(Analyse syntaxique)
Méthodes
d’analyse
syntaxique
Méthodes Méthodes
Descendantes Ascendante
Non
Déterministes
Déterministes
Introduction à la compilation
(Analyse syntaxique)
• Méthode descendante:
Consiste à partir de l’axiome à aboutir au programme à analyser (une
série de dérivations).
Méthodes
Descendantes
Non
Déterministes
Déterministes
Introduction à la compilation
(Analyse syntaxique)
• Méthode descendante:
Méthodes
Descendantes
Non
Déterministes
Déterministes
Analyse Syntaxique
• Factorisation
Une des conditions permettant de faire une analyse descendante
déterministe.
Analyse Syntaxique
• Factorisation
Une des conditions permettant de faire une analyse descendante
déterministe.
Exemple:
A→aα|aβ|c
Analyse Syntaxique
• Factorisation
Une des conditions permettant de faire une analyse descendante
déterministe.
Exemple:
A→aα|aβ|c
Après factorisation
A→aB|c
B→α|β
Analyse Syntaxique
• Récursivité Gauche Directe et Indirecte
Une des conditions permettant de faire une analyse descendante
déterministe.
Une grammaire est RGD si au moins une règle est de la forme
A → Aα/β
Analyse Syntaxique
• Récursivité Gauche Directe et Indirecte
Une des conditions permettant de faire une analyse descendante
déterministe.
Une grammaire est RGD si au moins une règle est de la forme
A → Aα/β
• Une grammaire est RGI si
A → Bα1/β1
B → Aα2/β2
Analyse Syntaxique
• Transformation en une grammaire NON Récursive Gauche Directe
A → Aα | β α, β∈ T∪N*
Devient:
A → β | β A’
A’ → α | α A’
Ou bien:
A → β A’
A’ → α A’ | ε
Analyse Syntaxique
• Transformation en une grammaire NON Récursive Gauche InDirecte
A → Bα1/β1
B → Aα2/β2
1)Ordonnancer les terminaux:
A<B<C<D<A (Récursivité Gauche en A)
2) Faire des substitutions de telle manière à faire apparaître une RGD.
3) Eliminer la RGD
Exercice 1
Exercice 1 :
G2 : S→ a / aA
A → Sc /Ad / c Si A → Aα | β
Eliminer la récursivité gauche directe en A: A → β A’
A’ → α A’ | ε
S→ a / aA
A → ScA` / cA`
A`→ dA` | ε
Exercice 1 :
• G3 : S → Abc / Baa
A → Aab / Ab / a Si A → Aα | β
B →Bb / a A → β A’
Eliminer la récursivité gauche directe en A et B: A’ → α A’ | ε
• G3 : S → Abc / Baa
A → aA’
A’→abA’/bA’ / ε
B →aB’
B’ →bB’/ ε
Exercice 1 :
G1 : S → aAba /AB /SA
A→ Bb / a
B→ Sa / c
1)Ordonnancer les terminaux:
RGI A<B<A (Récursivité Gauche en A)
2) Faire des substitutions de telle manière à
S<A<B<S faire apparaître une RGD.
3) Eliminer la RGD
Exercice 1 :
G1 : S → aAba /AB /SA
A→ Bb / a
B→ Sa / c
S<A<B<S
Remplacer B dans A
S→ aAba /AB /SA
A→ Sab/cb / a
B→ Sa / c
Remplacer Adans S
S→ aAba /SabB /cbB /aB /SA
A→ Sab/cb / a
B→ Sa / c
Exercice 1 :
S→ aAba /SabB /cbB /aB /SA Si A → Aα | β
A→ Sab/cb / a A → β A’
B→ Sa / c A’ → α A’ | ε
Eliminer la récursivité directe en S
S → aAbaS` /cbBS` /aBS`
S`→ abBS`/AS`| ε
A → Sab/cb / a
B → Sa / c
Exercice 2
Exercice 2 :
Factoriser la grammaire suivante :
G1: S → S∨T |T
T → T∧F | F
F → ¬F | (S)|x|y
G1 est une grammaire factorisée
Exercice 2 :
Factoriser la grammaire suivante :
G2:E → E+T|E-T|T
T → T*F|T\F|F
F → N|(E)
N → 0N|1N| ε
Exercice 2 :
Factoriser la grammaire: Factorisation:
G2’: E → EA|T
G2:E → E+T|E-T|T A→ +T|-T
T → T*F|T\F|F T → TB|F
F → N|(E) B→*F|\F
N → 0N|1N| ε F → N|(E)
N → 0N|1N| ε
Exercice 2 :
Factoriser la grammaire suivante : Factorisation
G3 : S → abBcA|abABC S → abT
A → cA |abB T→ BcA|ABC
B → cC | caB| ε A → cA |abB
C → Ab |ASa B → cB` / ε
B` → C/aB
C → AC`
C` → b |Sa
Exercice 4
Exercice 4
Soit la grammaire G suivante :
S→ C $
C→ E / -E
E→I/I ⦁I
I → Id / d
a. G est-elle LL(1) ? (Justifier la réponse).
b. Éliminer la récursivité gauche dans G.
c. Factoriser la grammaire obtenue en b.
d. Calculer les ensembles Debut et Suivant de la grammaire obtenue en
Exercice 4
Soit la grammaire G suivante :
S→ C $
C→ E / -E
E→I/I ⦁I
I → Id / d
b. Éliminer la récursivité gauche dans G.
I → dI`
I`→ dI`/ ε
Exercice 4
Factorisation:
S→ C $ debuts suivants
C→ E / -E S d- #
E → I E` C d- $
E` → ε/ ⦁I E d $
I → dI` E`
⦁ε $
I`→ dI`/ ε I d
⦁$
I`
dε ⦁$
Grammaire LL(1)
• G est-elle LL(1) ?
1. Non récursivité à gauche
2. Factorisée
3. Table d’analyse monodéfinie.
ou bien
3. Vérifier les règles:
1. Si A→ αi / αj Alors Deb(αi)∩ Deb(αj)=φ, i≠j
2. Si A→αi / αj et αi→*ε Alors αj -/-> * ε, i≠j
3. Si A→ αi / αj et αi→*ε Alors Deb(αj)∩ Suiv(A)=φ
