Théorie des langages : Cours langages et compilation analyse descendante prédictiv
Télécharger PDFLangages et Compilation : Analyse Descendante Prédictive
Introduction aux Grammaires LL(1)
Les grammaires LL(1) forment une famille de grammaires analysables de façon efficace.
Caractéristiques de l'analyse LL(1)
• Analyse descendante
• Construction de l'arbre de dérivations selon l'ordre préfixé : on part de la racine (l'axiome) et on descend vers les feuilles (les terminaux) en développant le nœud interne (une variable) le plus à gauche.
• Analyse prédictive : pour développer un nœud, on choisit la règle à appliquer en prévisualisant le symbole courant du mot analysé.
Exemple de Grammaire LL(1)
Considérons la grammaire :
S → +SS | ∗SS | a
Les chaînes dérivées de S commencent toutes par un terminal distinct. À partir du terminal courant du mot analysé, on peut déterminer la bonne règle.
Analyse d'un Mot avec la Grammaire LL(1)
Exemple : S → aSbS | ε
Le choix devient plus délicat lorsque la grammaire comprend des ε-productions. Quel critère doit-on prendre en compte pour choisir entre la règle S → aSbS et la règle S → ε ?
On est amené à considérer les terminaux qui peuvent suivre S. On introduit un terminal particulier $ pour marquer la fin du mot à analyser.
Si $ et b (mais pas a) peuvent être retrouvés à droite de S, on sait alors déterminer la règle à appliquer au vu du terminal courant.
Exemple d'Analyse LL(1) avec ε-productions
Mot analysé : a$b
Pile : $S
Dérivation :
S → aSbS → ε
Pile : $b
S → ε
Pile : $
Résultat : SUCCÈS
Conditions pour une Analyse LL(1)
À chaque étape, pour la variable X à développer et le terminal courant c en entrée, le choix de la dérivation à appliquer doit être déterministe.
L'analyse LL(1) se base sur une table qui indique, pour chaque variable X et chaque terminal c, la règle correcte à appliquer.
Construction de la Table d'Analyse
La table est une table à deux dimensions indexée par les variables et les terminaux.
Pour chaque production X → α :
• Ajouter X → α à l'entrée T[X, a] pour tout terminal a dans Premier(α)
• Si α est ε-accéptable, ajouter X → α dans la case T[X, a] pour tout terminal a dans Suivant(X)
Variables Éprouvables
Une chaîne α ∈ N* est dite éprouvable si le mot vide se dérive de α : α* → ε.
Calcul des variables éprouvables :
On construit par récurrence sur i, l'ensemble E_i des variables A ∈ N :
E_0 = {A ∈ N : A → ε ∈ P}
E_{i+1} = {A ∈ N : A → α ∈ P et α ∈ E_*^i}
L'arrêt se fait lorsque E_{i+1} = E_i (au bout d'au plus |N| étapes).
Exemple de Calcul des Variables Éprouvables
Grammaire :
S → XY
X → aXb | ε
Y → cZ | Ze
Z → dcZ | ε
E_0 = {X, Z}
E_1 = {X, Z} (pas de changement)
Ensembles Premier
Soit α une chaîne de (Σ ∪ N)*. Premier(α) est l'ensemble des terminaux qui débutent les chaînes dérivées de α : {a ∈ Σ : α* → aβ où β ∈ (Σ ∪ N)*}.
Calcul des ensembles Premier :
Pour un terminal a : Premier(aβ) = {a}
Pour une variable X : Premier(X) = ∪ X → β ∈ P Premier(β)
Pour une chaîne Xβ : Premier(Xβ) = Premier(X) si X n'est pas éprouvable, Premier(X) ∪ Premier(β) sinon.
Exemple de Calcul des Ensembles Premier
Grammaire :
S → XY
X → aXb | ε
Y → cZ | Ze
Z → dcZ | ε
Calcul des ensembles Premier pour les variables :
Premier(S) = Premier(XY) = Premier(X) ∪ Premier(Y) = {a} ∪ {c, e} = {a, c, e}
Premier(X) = Premier(aXb) = {a} (car X est éprouvable)
Premier(Y) = Premier(cZ) ∪ Premier(Ze) = {c} ∪ Premier(Z) ∪ {e} = {c, e} (car Z est éprouvable)
Premier(Z) = Premier(dcZ) = {d}
Ensembles Suivant
Soit X une variable. Suivant(X) est l'ensemble des terminaux qui peuvent apparaître après X dans une dérivation : {a ∈ Σ : S* → αXaβ où α, β ∈ (Σ ∪ N)*}.
Calcul des ensembles Suivant :
Mettre $ dans Suivant(S) (où S est l'axiome).
Pour chaque variable X, examiner chaque production Y → αXβ où X est à droite :
• Si β ≠ ε, ajouter les éléments de Premier(β) à Suivant(X)
• Si β* → ε, ajouter les éléments de Suivant(Y) à Suivant(X)
Exemple de Calcul des Ensembles Suivant
Grammaire :
S → XY
X → aXb | ε
Y → cZ | Ze
Z → dcZ | ε
Suivant(S) contient $
Suivant(X) = Premier(YSuivant(S)) = Premier(Y) = {c, e} (car Y n'est pas éprouvable)
Suivant(Y) = Suivant(S) ∪ Suivant(Z) = {$} ∪ {d, $} = {d, $}
Suivant(Z) = Suivant(Y) = {d, $}
Variables Éprouvables, Ensembles Premier et Suivant
Exemple :
Variables Éprouvables | Premier | Suivant
S non | a, c, e | $
X oui | a, b | c, e
Y non | c, e | d, $
Z oui | d | d, $
Grammaire LL(1)
Définition
Une grammaire est LL(1) s'il existe au plus une production par entrée dans la table.
Proposition
Une grammaire est LL(1) si pour toute paire de productions A → α et A → β, on a :
Premier(αSuivant(A)) ∩ Premier(βSuivant(A)) = ∅.
Ainsi, une grammaire n'est pas LL(1) s'il existe :
• un conflit Premier/Premier, c'est-à-dire deux règles A → α | β telles que : Premier(α) ∩ Premier(β) ≠ ∅
• un conflit Premier/Suivant, c'est-à-dire deux règles A → α | β avec β* → ε telles que : Premier(α) ∩ Suivant(A) ≠ ∅
Exemple de Grammaire LL(1)
Grammaire :
S → XY
X → aXb | ε
Y → cZ | Ze
Z → dcZ | ε
La table d'analyse comprend au plus une alternative par case.
Exemple de table :
S → XY
X → aXb | ε
Y → cZ | Ze
Z → ε | dcZ
Exemple de Grammaire Non LL(1)
Grammaire :
S → XY | Z
X → aXb | ε
Y → bX
Z → bZc | c
Il existe un conflit Premier/Premier pour les règles S → XY et S → Z.
Premier(XY) = Premier(X) ∪ Premier(Y) = {a, b}
Premier(Z) = {b, c}
Premier(XY) ∩ Premier(Z) = {b} ≠ ∅
Exemple de Grammaire Non LL(1) avec Conflit Premier/Suivant
Grammaire :
S → aXb
X → bX | ε
Il existe un conflit Premier/Suivant pour les règles X → bX et X → ε.
Premier(bX) = {b}
Suivant(X) = {b}
Premier(X) ∩ Suivant(X) = {b} ≠ ∅
Analyseur LL(1)
Pour examiner un mot, l'analyseur LL(1) utilise la table d'analyse précédemment construite et une pile.
Initialement, la pile contient le marqueur de fin de mot $ et l'axiome.
Exemple d'Analyseur LL(1)
Mot analysé : a$b
Pile : $S
Dérivation :
S → XY
Pile : $XY
X → aXb
Pile : $aXbY
X → ε
Pile : $bY
Y → Ze
Pile : $ZebY
Z → dcZ
Pile : $dcZebY
Z → ε
Pile : $ebY
Résultat : SUCCÈS
Exemple d'Analyseur LL(1) avec Échec
Mot analysé : a$b
Pile : $S
Dérivation :
S → XY
Pile : $XY
X → aXb
Pile : $aXbY
X → ε
Pile : $bY
Y → cZ
Pile : $cZbY
Résultat : ÉCHEC
Rendre une Grammaire LL(1)
Proposition
Une grammaire ne peut pas être LL(1) si elle est :
• soit ambiguë,
• soit récursive à gauche,
• soit non factorisée à gauche.
On peut modifier une grammaire pour tenter de la rendre LL(1), mais le résultat n'est pas garanti.
Exemple de Récursivité Gauche
Grammaire :
E → E + T | T
T → T * F | F
F → (E) | nb
Cette grammaire n'est pas LL(1) en raison de la récursivité à gauche de E et T.
Conflit Premier/Premier pour les règles E → E + T et E → T.
Conflit Premier/Premier pour les règles T → T * F et T → F.
Suppression de la Récursivité Gauche
Grammaire modifiée :
E → TY
Y → +TY | ε
T → FZ
Z → *FZ | ε
F → (E) | nb
Exemple de Substitution et Factorisation
Grammaire :
E → TR
T → id | (E) | A
R → +E | ε
A → id[E]
Conflit Premier/Premier pour les règles T → id et T → A.
Grammaire modifiée :
E → TR
T → idX | (E)
X → [E] | ε
R → +E | ε
Analyse LL(k)
Généralisation de l'analyse LL(1) avec prévisualisation d'un nombre k de symboles. Une grammaire est LL(k) si l'analyseur peut choisir de façon déterministe la règle à appliquer en examinant les k symboles courants de l'entrée.
On note :
• w|k = {w si w est de longueur au plus k, le préfixe de longueur k de w sinon}
• Premierk(α) = {w|k : α* → w}
• Suivantk(A) = {w : ∃β, γ tels que S* → βAγ et w ∈ Premierk(γ)}
Une grammaire est LL(k) si pour toute paire de productions A → α et A → β, on a :
Premierk(αSuivantk(A)) ∩ Premierk(βSuivantk(A)) = ∅.
Exemple de Grammaire LL(2)
Grammaire :
S → abX | ε
X → Saa | b
Cette grammaire n'est pas LL(1) mais est LL(2).
Variables Éprouvables | Premier2 | Suivant2
S non | ab, aa, b | $
X non | aa, b | $
Exemple d'Analyse LL(k) avec ANTLR
ANTLR4 met en œuvre une analyse descendante prédictive qui :
• factorise à gauche la grammaire automatiquement
• supprime automatiquement les récursivités gauches immédiates
• résout certaines ambiguïtés
• joue sur l'ordre des productions pour lever celles liées aux priorités des opérateurs
• pour les ambiguïtés dues à l'associativité, privilégie les associations à gauche ou à droite explicitement
• se base sur une stratégie LL(k)
• inclut un mécanisme additionnel pour traiter des grammaires non LL(k) mais avec un surcoût en temps.
FAQ
Qu'est-ce qu'une grammaire LL(1) ?
Une grammaire LL(1) est une grammaire contextuelle libre qui permet une analyse syntaxique descendante et prédictive, où le choix de la règle à appliquer dépend uniquement du symbole courant en entrée.
Comment construire la table d'analyse pour une grammaire LL(1) ?
La table d'analyse est construite en déterminant les ensembles Premier et Suivant pour chaque variable, puis en remplissant la table avec les règles correspondantes aux paires variables/terminaux.
Quels sont les conflits possibles dans une grammaire LL(1) ?
Les conflits possibles sont :
• Premier/Premier : deux règles commençant par les mêmes terminaux
• Premier/Suivant : une règle commençant par un terminal qui peut aussi suivre la variable dans une autre règle.