Analyse descendante LL(k) Analyse descendante Différence avec l ...
15 pages
Français

Analyse descendante LL(k) Analyse descendante Différence avec l ...

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

  • cours - matière potentielle : k
  • cours - matière potentielle : traitement
  • cours - matière potentielle : reconnaissance
  • cours - matière potentielle : soit
Principes Table d'analyse LL Analyseur recursif Analyseur non-recursif Construction de la table d'analyse Caracterisation d'une grammaire LL(1) Quand une grammaire n'est pas LL(1) Analyse descendante LL(k) Mirabelle Nebut Bureau 332 - M3 mirabelle.nebut at lifl.fr 2011-2012 Mirabelle Nebut Analyse descendante LL(k) 2/117 Principes Table d'analyse LL Analyseur recursif Analyseur non-recursif Construction de la table d'analyse Caracterisation d'une grammaire LL(1) Quand une grammaire n'est pas LL(1) Principes Table d'analyse LL Analyseur recursif Analyseur non-recursif Construction de la table d'analyse Ensembles Premier
  • ab a→
  • analyseur recursif
  • analyseur
  • ab ⇒
  • principes table d'analyse ll
  • remplissage de la table d'analyse outils pour l'analyse predictive
  • ab private void
  • abb
  • piles
  • pile

Sujets

Informations

Publié par
Nombre de lectures 319
Langue Français

Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ecursif Analyseur non-r´ecursif
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Principes
Table d’analyse LL
Analyseur r´ecursif
Analyse descendante LL(k) non-r´ecursif
Construction de la table d’analyse
Ensembles PremierMirabelle Nebut
Ensemble des -prod
Ensembles SuivantBureau 332 - M3
mirabelle.nebut at lifl.fr Remplissage de la table d’analyse
Caract´erisation d’une grammaire LL(1)2011-2012
Quand une grammaire n’est pas LL(1)
Factorisation `a gauche
Suppression de la r´ecursivit´e `a gauche
2/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ Analyseur non-r´
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Analyse descendante Diff´erence avec l’automate des items
L’automate `a pile sous-jacent :
Deux diff´erences fondamentales :I effectue uniquement des lectures et des expansions ;
I analyse d´eterministe dite pr´edictive ;I construit un arbre en ordre pr´efixe (idem aut. items) ;
I plus d’items ni de r´eductions explicites.I part de l’axiome (idem aut. items) ;
I construit une d´erivation gauche (idem aut. items).
3/117 4/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ecursif Analyseur non-r´ecursif
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Analyse d´eterministe Analyse pr´edictive
L’analyseur ”pr´edit” quelle production utiliser. . .
`A chaque expansion l’analyseur sait choisir une production. . . . en analysant les k prochains symboles sous la tˆete de lecture.
Il ne revient jamais sur ce choix : Cons´equences :
I en cas de succ`es le mot appartient au langage ; I ne fonctionne qu’avec certaines grammaires, dites LL(k) ;
I en cas d’´echec on est surˆ que mot n’appartient pas au langage. I tˆete de lecture toujours d´efinie : marqueur de fin de mot #.
NB : dans ce cours k=1, on regarde la tˆete de lecture et c’est tout.
5/117 6/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ Analyseur non-r´
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Exemple `a suivre dans le cours Analyse pr´edictive LL(1), exemple - 1
S→ AB | Da
Soit la grammaire G ={V ,V ,S,P} avec :T N A→ aAb |
abb# ?
I B→ bB | V ={a,b,d,e} ;T
D→ dD | eI V ={S,A,B,D} ;N
I P contient les productions : S ⇒?
4S→ AB | Da
A→ aAb | a bb#
4B→ bB |
D→ dD | e Choix entre S→ AB et S→ Da.
Pr´ediction : expansion par S→ AB
7/117 8/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ecursif Analyseur non-r´ecursif
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Analyse pr´edictive LL(1), exemple - 2 Analyse pr´edictive LL(1), exemple - 3
S→ AB | Da
S→ AB | Da
A→ aAb | A→ aAb | abb# ?
B→ bB | abb# ?
B→ bB |
D→ dD | e
D→ dD | e
S⇒ AB⇒ ?
S⇒ AB⇒ aAbB
4 4
a bb#
a bb#
4
4
Choix entre A→ aAb et A→.
Lecture de a.
Pr´ediction : expansion par A→ aAb
9/117 10/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ Analyseur non-r´
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Analyse pr´edictive LL(1), exemple - 4 Analyse pr´edictive LL(1), exemple - 5
S→ AB | Da S→ AB | Da
A→ aAb | A→ aAb |
abb# ? abb# ?
B→ bB | B→ bB |
D→ dD | e D→ dD | e
S⇒ AB⇒ a AbB⇒ ? S⇒ AB⇒ aAbB⇒ abB⇒ abb B⇒ ?
4 4
a bb# abb #
4 4
Choix entre A→ aAb et A→. Choix entre B→ bB et B→.
Pr´ediction : expansion par A→ Pr´ediction : expansion par B→, acceptation.
11/117 12/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ecursif Analyseur non-r´ecursif
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Se passer des items Se passer des items : cons´equences
Plus besoin d’axiome suppl´ementaire.Rappel : item de la forme [X→α•β] :
I X est en cours de reconnaissance ; Dans la pile :
∗I Iα a d´ej`a ´et´e reconnu ; plus d’items mais des mots ´etendus : mots de (V ∪V ) ;N T
I il reste `a reconnaˆıtre β, le futur de l’item I l’alphabet est V ∪V ;N T
I le symbole de pile initiale est l’axiome.
Un analyseur LL :
I Ane m´emorise pas qu’il est en train de reconnaˆıtre X ;
bI ne m´emorise pas qu’il a reconnu α ;
S B
I consid`ere uniquement β.
pile initiale une pile pile vide (acceptation)
13/117 14/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ Analyseur non-r´
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
PrincipesExemple - les piles pour abb#
Table d’analyse LL
S→ AB | Da B→ bB | Analyseur r´ecursif
abb# ?
A→ aAb | D→ dD | e non-r´ecursif
Construction de la table d’analyse
a
Ensembles PremierA A
Ensemble des -prod
A b b b b
Ensembles SuivantS B B B B B B B
Remplissage de la table d’analyse
abb# abb# abb# bb# bb# b# b# # #
Caract´erisation d’une grammaire LL(1)(1) (2) (3) (4) (5) (6) (7) (8) (9)
Quand une grammaire n’est pas LL(1)
Comparer avec l’automates des items ! Factorisation `a gauche
D´erivation gauche, arbre en ordre pr´efixe. Suppression de la r´ecursivit´e `a gauche15/117 16/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ecursif Analyseur non-r´ecursif
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Deux types de mise en œuvre possibles Table d’analyse - exemple
Avec pile explicite :
I analyseur dit non-r´ecursif ;
I encodage d’un automate `a pile. S A B D
a S→ AB A→ aAb erreur erreur
Avec pile implicite :
b S→ AB A→ B→ bB erreur
I analyseur = ensemble de fonctions r´ecursives ; d S→ Da erreur erreur D→ dD
I pile implicite r´esultant des appels r´ecursifs ; e S→ Da erreur erreur D→ e
I # S→ AB A→ B→ erreuron parle d’analyseur r´ecursif : cf TP.
Dans les deux cas : une table d’analyse indique la production `a
utiliser.
17/117 18/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ Analyseur non-r´
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Table d’analyse LL(1) Interpr´etation de Table[a,X ]
Contient toute l’intelligence de l’analyseur syntaxique.
I si le terminal a∈ V est sous la tˆete de lecture ;T
Definition
I et si le non-terminal en cours de traitement est X∈ V ;NLa table d’analyse Table est un tableau `a deux dimensions tel que :
alors on consulte Table[a,X ].I chaque colonne est indic´ee par un non-terminal∈ V ;N
I chaque ligne est indic´ee par un terminal∈ V ou # ;T Si Table[X,a] contient
I Ichaque case contient une production∈ P ou erreur. X→γ alors on choisit une expansion par cette production ;
I erreur alors erreur de syntaxe : X et a ne s’accordent pas.
On verra plus tard comment remplir cette table.
19/117 20/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ecursif Analyseur non-r´ecursif
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Principes Analyseur descendant r´ecursif
Table d’analyse LL
Analyseur r´ecursif Principe : non-r´ecursif I analyseur LL cod´e par un ensemble de fonctions ;
Construction de la table d’analyse I ces fonctions s’appellent les unes les autres ;
Ensembles Premier
I n’utilise pas de pile explicite : pile implicite des appels.
Ensemble des -prod
Ensembles Suivant Codage des fonctions :
Remplissage de la table d’analyse I une fonction X() par non-terminal X∈ V de la grammaire ;N
Caract´erisation d’une grammaire LL(1) I X() reconnaˆıt un mot engendr´e par X ;
Quand une grammaire n’est pas LL(1) I la fonction X() code les productions Table[X,y] de la table
Factorisation `a gauche d’analyse, pour tout y∈ V ∪ #.T
Suppression de la r´ecursivit´e `a gauche
21/117 22/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ Analyseur non-r´
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Exemple Collaboration avec un analyseur lexical
On reprend les conventions utilis´ees en TP :´Ecrire un analyseur syntaxique r´ecursif LL(1) Parser pour G :
I un an. lexical anLex de type Scanner (suppos´e donn´e) ;
S→ AB | Da
I symboles de type Symbole ;
A→ aAb |
I codage entier du type des symboles dans TypeSymbolesB→ bB |
(not´e TS dans les transparents) ;D→ dD | e
I m´ethode int getType() de Symbole pour obtenir ce type ;
I` m´ethode Symbole next token() de Scanner :A voir :
I avance la tˆete de lecture teteLect ;I ´ecriture de S(), A(), B(), D() ;
I retourne le symbole lu, de type Symbole.
I collaboration avec un analyseur lexical.
I on remplace le marqueur # par TS.EOF.
23/117 24/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ecursif Analyseur non-r´ecursif
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Construction de l’analyseur syntaxique Lancement de l’analyseur syntaxique
Dans la classe Parser :...
public class Parser { public void analyser() throws ScannerException, ParserException {
// analyseur lexical // positionnement tete de lecture
private Scanner anLex; this.teteLect = (Symbole) this.anLex.next_token();
// symbole courant re¸cu de l’analyseur lexical this.S(); // je veux reconna^ıtre l’axiome
private Symbole teteLect;
// et uniquement l’axiome
public Parser (Scanner anLex) { if (this.teteLect.getType() != TS.EOF)
this.anLex = anLex; throw new ParserException();
} }25/117 26/117
...
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ Analyseur non-r´
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Code de S() Code de S()
La tˆete de lecture est d´ej`a positionn´ee sur le symbole de pr´ediction.
On factorise.
private void S() throws ... {
private void S() throws ... {if (this.teteLect.getType() == TS.a)
if (this.teteLect.getType() == TS.a... // S -> AB
S || this.teteLect.getType() == TS.belse if == TS.b)S
a S→ AB... // S -> AB || == TS.EOF)a S→ AB
else if == TS.d) b S→ AB ... // S -> ABb S→ AB
... // S -> Da d S→ Da else if == TS.dd S→ Da
else if (this.teteLect.getType() == TS.e) e S→ Da || == TS.e)e S→ Da ... // S -> Da
# S→ AB ... // S -> Da# S→ AB else if == TS.EOF)
else throw new ParserException();... // S -> AB
}else throw new ParserException();
27/117 28/117
}
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ecursif Analyseur non-r´ecursif
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Code des productions de S() Terminaux : v´erification et consommation
M´ethode consommer d´edi´ee `a la gestion des terminaux :Code pour S→ AB :
I je veux reconnaˆıtre A puis B ; private void consommer(int type)
throws ScannerException, ParserException {I ⇒ A(); B();
if (this.teteLect.getType() == type)
Code pour S→ Da : this.teteLect = (Symbole) this.anLex.next_token();
I else throw new ParserException();je veux reconnaˆıtre D. . .
}I . . . puis v´erifier que a est bien sous la tˆete de lecture ;
I et consommer a.
Code pour S→ Da : D(); this.consommer(TS.a);.
29/117 30/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ Analyseur non-r´
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Code final de S() Code de A()
private void S() throws ... {
if (this.teteLect.getType() == TS.a La tˆete de lecture est d´ej`a positionn´ee sur le symbole de pr´ediction.S
|| this.teteLect.getType() == TS.b
private void A() throws ... {a S→ AB || == TS.EOF) { A if (this.teteLect.getType() == TS.a)b S→ AB A(); B(); // S -> AB
... // A -> aAba A→ aAb} else if == TS.dd S→ Da else if == TS.bb A→|| == TS.e) {e S→ Da || this.teteLect.getType() == TS.EOF)
D(); this.consommer(TS.a); // S -> Da d erreur# S→ AB ... // A ->
} else throw new ParserException(); e erreur else // erreur
} # A→ throw new ParserException();
Quand S() termine, pour un mot accept´e, la tˆete de lecture est sur }
TS.EOF.
31/117 32/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ecursif Analyseur non-r´ecursif
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Code des productions de A() Code final de A()
private void A() throws ... {
if (this.teteLect.getType() == TS.a) {
Code pour A→ aAb :
// A -> aAbA
this.consommer(TS.a); A();a A→ aAbthis.consommer(TS.a); A(); this.consommer(TS.b);
this.consommer(TS.b);b A→
} else if == TS.b
d erreurCode pour A→ : || this.teteLect.getType() == TS.EOF) {
e erreurI // rien, A ->le mot vide est imm´ediatement reconnu ;
# A→ } else // erreur
I sans toucher `a la tˆete de lecture ;
throw new ParserException();
I on ne fait rien. }
Quand A() termine, pour un mot accept´e, la tˆete de lecture est
positionn´ee pour reconnaˆıtre un B ou lire un b.
33/117 34/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ Analyseur non-r´
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Code final de B() Code final de D()
private void D() throws ... {private void B() throws ... {
if (this.teteLect.getType() == TS.d) {B if (this.teteLect.getType() == TS.b) { D
// D -> dD
// B -> bBa erreur a erreur this.consommer(TS.d); D();
this.consommer(TS.b); B();b B→ bB b erreur } else if == TS.e)} else if == TS.EOF) {
d erreur d D→ dD // D -> e
// rien, B ->
this.consommer(TS.e);e erreur e D→ e} else // erreur
else // erreur# B→ throw new ParserException(); # erreur
throw new ParserException();}
}
35/117 36/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ecursif Analyseur non-r´ecursif
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
PrincipesExemple d’ex´ecution
Table d’analyse LL
Analyseur r´ecursif non-r´ecursif
Construction de la table d’analyseReconnaˆıtre abb# ?
Ensembles Premier
Ensemble des -prod
Ensembles Suivant
Remplissage de la table d’analyseMise en pratique : TP3 (Init)
Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1)
Factorisation `a gauche
Suppression de la r´ecursivit´e `a gauche
37/117 38/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ Analyseur non-r´
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Exemple - les piles pour abb# Principes - 1
S→ AB | Da
A→ aAb |
abb# ?
B→ bB |
D→ dD | e
I La configuration initiale est (m#,S) ;
a I La finale est (#, ) : acceptation par pile vide.
A A
A b b b b On traite syst´ematiquement le sommet de pile.
S B B B B B B B
abb# abb# abb# bb# bb# b# b# # #
(1) (2) (3) (4) (5) (6) (7) (8) (9)
Comment ¸ca se g´en´eralise ?
39/117 40/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ecursif Analyseur non-r´ecursif
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Principes - transition de lecture Principes - transition d’expansion
Si le sommet de pile est un non terminal X∈ V . . .NSi le sommet de pile est un terminal a∈ V :T
I . . . et que la tˆete de lecture est y∈ V ∪{#}. . .on contrˆ ole que a est bien sous la tˆete de lecture (sinon T
´echec) ; si Table[X,y] contient X→ X ...X :1 n
I on le consomme ; I on d´epile X ;
I on le d´epile. I on empile `a sa place X ...X , avec X au sommet.1 n 1
Lecture de a :
(m,z ...z X ) ‘ (m,z ...z X ...X )1 n 1 n n 1
(am,z ...z a) ‘ (m,z ...z )1 n 1 n
sinon erreur.
41/117 42/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif
Analyseur non-r´ Analyseur non-r´
Construction de la table d’analyse Construction de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Transition d’expansion : remarque Construction de l’arbre syntaxique : ordre pr´efixe
Transition d’expansion par X→ X ...X :1 n
I X est le prochain nœud `a traiter dans l’arbre (pour
l’ordre pr´efixe) ;Expansion par X→ X ...X :1 n
I on lui rajoute les fils X ...X de la gauche vers la droite ;1 n
(m,z ...z X ) ‘ (m,z ...z X ...X )1 n 1 n n 1
I le prochain nœud `a traiter devient X .1
I X sera trait´e en premier.1 Transition de a-lecture :
I on assure ainsi la construction d’une d´erivation gauche ; I a est le prochain nœud `a traiter dans l’arbre (pour l’ordre
pr´efixe) ;
I on v´erifie que a concorde bien avec la tˆete de lecture ;
I et on passe au nœud suivant.
43/117 44/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Ensembles Premier Ensembles PremierAnalyseur r´ecursif Analyseur r´ecursif
Ensemble des -prod Ensemble des -prodAnalyseur non-r´ecursif Analyseur non-r´ecursif
Ensembles Suivant Ensembles SuivantConstruction de la table d’analyse Construction de la table d’analyse
Remplissage de la table d’analyse Remplissage de la table d’analyseCaract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Principes Principes
Table d’analyse LL Table d’analyse LL
Analyseur r´ecursif Analyseur r´ecursif non-r´ecursif non-r´ecursif
Construction de la table d’analyse Construction de la table d’analyse
Ensembles Premier Ensembles Premier
Ensemble des -prod Ensemble des -prod
Ensembles Suivant Ensembles Suivant
Remplissage de la table d’analyse Remplissage de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Factorisation `a gauche Factorisation `a gauche
Suppression de la r´ecursivit´e `a gauche Suppression de la r´ecursivit´e `a gauche
45/117 46/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LLEnsembles Premier Ensembles Premier
Analyseur r´ecursif Analyseur r´ecursifEnsemble des -prod Ensemble des -prod
Analyseur non-r´ Analyseur non-r´ Suivant Suivant
Construction de la table d’analyse Construction de la table d’analyseRemplissage de la table d’analyse Remplissage de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Outils pour l’analyse pr´edictive, intuition - 1 Outils pour l’analyse pr´edictive, intuition - 1
Maintenant je sais (partiellement) choisir entre S→ AB et
S→ Da :
IComment choisir entre S→ AB et S→ Da ? si tˆete lecture∈{a,b} : choisir S→ AB ;
I si tˆete lecture∈{d,e} : choisir S→ Da.Supposons que je sache que :
I AB ne permet de d´eriver que des mots pr´efix´es par a ou par b ;
∗ ∗ ∗ SI AB⇒ au et AB⇒ bu, pour u∈ V ;T
a S→ ABI Da ne permet de d´eriver que des mots pr´efix´es par d ou par e ;
b S→ AB∗ ∗ ∗I Da⇒ du et Da⇒ eu, pour u∈ V .T d S→ Da
e S→ Da
# ?
47/117 48/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)Principes Principes
Table d’analyse LL Table d’analyse LL
Ensembles Premier Ensembles PremierAnalyseur r´ecursif Analyseur r´ecursif
Ensemble des -prod Ensemble des -prodAnalyseur non-r´ecursif Analyseur non-r´ecursif
Ensembles Suivant Ensembles SuivantConstruction de la table d’analyse Construction de la table d’analyse
Remplissage de la table d’analyse Remplissage de la table d’analyseCaract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Ensemble Premier - d´efinition Les Premier sur les arbres syntaxiques - notation
On dit que Premier(AB) ={a,b} et Premier(Da) ={d,e}.
+Pour α∈ (V ∪V ) , Premier(α) contient l’ensemble desT N
+terminaux de V susceptibles de commencer un mot de VT T α∈ (V ∪V )∗T N
d´eriv´e de α.
A B A B
Si α =, cet ensemble est vide.
A BDefinition
Soit une grammaire alg´ebrique. On d´efinit : a b b
∗Premier : (V ∪V ) → P(V )T N T ∈ Premier(α)
∗ ∗α 7→ {a∈ V |α⇒ au,u∈ V }T T
49/117 50/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LLEnsembles Premier Ensembles Premier
Analyseur r´ecursif Analyseur r´ecursifEnsemble des -prod Ensemble des -prod
Analyseur non-r´ Analyseur non-r´ Suivant Suivant
Construction de la table d’analyse Construction de la table d’analyseRemplissage de la table d’analyse Remplissage de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Calcul des Premier - 0 Calcul des Premier - 1
∗ ∗Soit α∈ (V ∪V ) : Soit α∈ (V ∪V ) :N T N T
cas cas
α = : ? α = :∅
α = a, a∈ V : ? α = a, a∈ V :{a}T T
∗ ∗α = aβ, a∈ V , β∈ (V ∪V ) : ? α = aβ, a∈ V , β∈ (V ∪V ) :{a}T N T T N T
α = X , X∈ V : ? α = X , X∈ V : ?N N
∗ ∗α = Xβ, X∈ V , β∈ (V ∪V ) : ? α = Xβ, X∈ V , β∈ (V ∪V ) : ?N N T N N T
fcas fcas
51/117 52/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Ensembles Premier Ensembles PremierAnalyseur r´ecursif Analyseur r´ecursif
Ensemble des -prod Ensemble des -prodAnalyseur non-r´ecursif Analyseur non-r´ecursif
Ensembles Suivant Ensembles SuivantConstruction de la table d’analyse Construction de la table d’analyse
Remplissage de la table d’analyse Remplissage de la table d’analyseCaract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Calcul de Premier(X ), X∈ V - exemple Calcul de Premier(X ), X∈ V - g´en´eralisationN N
Si la grammaire contient les productions de membre gauche X :
X→γ | ...|γ1 n
Si l’ensemble des productions de membre gauche S est : X X
S→ AB | Da
γ γ1 n
. . .alors on a :
Premier(S) = Premier(AB)∪Premier(Da)
∈ Premier(γ ) ∈ Premier(γ )1 n
∈(X ) ∈(X )
S
53/117 54/117Premier(X ) = {Premier(γ )|X→γ ∈ P}i i
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LLEnsembles Premier Ensembles Premier
Analyseur r´ecursif Analyseur r´ecursifEnsemble des -prod Ensemble des -prod
Analyseur non-r´ Analyseur non-r´ Suivant Suivant
Construction de la table d’analyse Construction de la table d’analyseRemplissage de la table d’analyse Remplissage de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Calcul des Premier - 2 Calcul des Premier, α = Xβ, X∈ VN
∗Soit α∈ (V ∪V ) :N T
cas
Deux cas selon que X peut s’effacer ou non :α = :∅
∗α = a, a∈ V :{a} X⇒ ?T
∗α = aβ, a∈ V , β∈ (V ∪V ) :{a}T N T ∗S Si X⇒ on dit que X est -productif : X∈-Prod
α = X , X∈ V : {Premier(γ )|X→γ ∈ P}N i i
∗α = Xβ, X∈ V , β∈ (V ∪V ) : ?N N T
fcas
55/117 56/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)Principes Principes
Table d’analyse LL Table d’analyse LL
Ensembles Premier Ensembles PremierAnalyseur r´ecursif Analyseur r´ecursif
Ensemble des -prod Ensemble des -prodAnalyseur non-r´ecursif Analyseur non-r´ecursif
Ensembles Suivant Ensembles SuivantConstruction de la table d’analyse Construction de la table d’analyse
Remplissage de la table d’analyse Remplissage de la table d’analyseCaract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Calcul des Premier, α = Xβ, X6∈-Prod - exemple Calcul des Premier, α = Xβ, X6∈-Prod - g´en´eralisation
∗X6⇒
Par exemple D6∈ -productif :
X β
D→ dD | e
alors Premier(Da) = Premier(D)
Premier(X )
Premier(α) = Premier(X )
57/117 58/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LLEnsembles Premier Ensembles Premier
Analyseur r´ecursif Analyseur r´ecursifEnsemble des -prod Ensemble des -prod
Analyseur non-r´ Analyseur non-r´ Suivant Suivant
Construction de la table d’analyse Construction de la table d’analyseRemplissage de la table d’analyse Remplissage de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Calcul des Premier, α = Xβ, X∈-Prod - exemple Calcul des Premier, α = Xβ, X∈ V - g´en´eralisationN
∗X⇒
Par exemple A∈ -productif :
X β
A→|aAb
Premier(AB) = Premier(A)∪Premier(B)
Premier(X ) Premier(β)(ABS) =(A)∪(BS)
Premier(α) =
Premier(X )∪Premier(β)
59/117 60/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Ensembles Premier Ensembles PremierAnalyseur r´ecursif Analyseur r´ecursif
Ensemble des -prod Ensemble des -prodAnalyseur non-r´ecursif Analyseur non-r´ecursif
Ensembles Suivant Ensembles SuivantConstruction de la table d’analyse Construction de la table d’analyse
Remplissage de la table d’analyse Remplissage de la table d’analyseCaract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Calcul des Premier Calcul effectif des ensembles Premier
∗Soit α∈ (V ∪V ) :N T
cas
On proc`ede en deux ´etapes :α = :∅
1. on pose un syst`eme d’´equations pour Premier ;
α = a, a∈ V :{a}T
2. on calcule par it´eration de point fixe les plus petits ensembles∗α = aβ, a∈ V , β∈ (V ∪V ) :{a}T N T qui satisfont ces ´equations.S
α = X , X∈ V : {Premier(γ )|X→γ ∈ P}N i i
Pour le moment on suppose donn´e -Prod, l’ensemble des∗α = Xβ, X∈ V \-Prod, β∈ (V ∪V ) : Premier(X )N N T -productifs.
∗α = Xβ, X∈ V ∩-Prod, β∈ (V ∪V ) :N N T
Premier(X )∪Premier(β)
61/117 62/117fcas
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LLEnsembles Premier Ensembles Premier
Analyseur r´ecursif Analyseur r´ecursifEnsemble des -prod Ensemble des -prod
Analyseur non-r´ Analyseur non-r´ Suivant Suivant
Construction de la table d’analyse Construction de la table d’analyseRemplissage de la table d’analyse Remplissage de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Exemple Exemple
Premier(S) = Premier(A)∪Premier(B)∪Premier(D)α = :∅
S→ AB | Da(A) ={a}
α = a, a∈ V :{a}TA→ aAb | Premier(B) ={b}
∗B→ bB | α = aβ, a∈ V , β∈ (V ∪V ) :{a}T N T(D) ={d,e}
D→ dD | e
α = X , X∈ V :N D’ou`S-Prod ={A, B, S} {Premier(γ )|X→γ ∈ P}i i Premier(S) ={a,b,d,e} Premier(aAb) ={a}
∗Premier(S) = ? α = Xβ, X∈ V \-Prod,β∈ (V ∪V ) : Premier(A) ={a} Premier(bB) ={b}N N T(A) = ? Premier(X )(B) ={b}(dD) ={d}
Premier(B) = ? ∗ Premier(D) ={d,e} Premier(e) ={e}α =Xβ,X∈ V ∩-Prod,β∈ (V ∪V ) :N N T(D) = ?(AB) ={a,b}() =∅Premier(X )∪Premier(β)
Premier(Da) ={d,e}
63/117 64/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)Principes Principes
Table d’analyse LL Table d’analyse LL
Ensembles Premier Ensembles PremierAnalyseur r´ecursif Analyseur r´ecursif
Ensemble des -prod Ensemble des -prodAnalyseur non-r´ecursif Analyseur non-r´ecursif
Ensembles Suivant Ensembles SuivantConstruction de la table d’analyse Construction de la table d’analyse
Remplissage de la table d’analyse Remplissage de la table d’analyseCaract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Exemple : remplissage de la table Exemple : remplissage de la table
A→ aAb et Premier(aAb) ={a} S→ AB et Premier(AB) ={a,b}
A→ et Premier() =∅ S→ Da et(Da) ={d,e}
S A B D S A B D
a S→ AB A→ aAb erreur erreur a S→ AB A→ aAb erreur erreur
b S→ AB A→ B→ bB erreur b S→ AB A→ B→ bB erreur
d S→ Da erreur erreur D→ dD d S→ Da erreur erreur D→ dD
e S→ Da erreur erreur D→ e e S→ Da erreur erreur D→ e
# S→ AB A→ B→ erreur # S→ AB A→ B→ erreur
65/117 66/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LLEnsembles Premier Ensembles Premier
Analyseur r´ecursif Analyseur r´ecursifEnsemble des -prod Ensemble des -prod
Analyseur non-r´ Analyseur non-r´ Suivant Suivant
Construction de la table d’analyse Construction de la table d’analyseRemplissage de la table d’analyse Remplissage de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Remarque : r´esolution du syst`eme R´esolution du syst`eme : autre exemple
S→ S S |a Premier(S) = Premier(S )∪{a}1 2 1(S ) =(S)∪{b}Premier(S) = Premier(A)∪Premier(B)∪Premier(D) S → S|b 11
S → c Premier(S ) ={c}(A) ={a} 2 2
Premier(B) ={b}
iter Premier(S) Premier(S ) Premier(S )1 2(D) ={d,e}
0 ∅ ∅ ∅
Se r´esoud sans it´eration de point fixe : syst`eme d’´equations non 1 {a} {b} {c}
r´ecursif.
2 {a,b} {b,a} {c}
Ce n’est pas toujours le cas. 3 {a,b} {b,a} {c}
stabilisation
67/117 68/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Ensembles Premier Ensembles PremierAnalyseur r´ecursif Analyseur r´ecursif
Ensemble des -prod Ensemble des -prodAnalyseur non-r´ecursif Analyseur non-r´ecursif
Ensembles Suivant Ensembles SuivantConstruction de la table d’analyse Construction de la table d’analyse
Remplissage de la table d’analyse Remplissage de la table d’analyseCaract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Principes D´efinition des -prod
Table d’analyse LL
Analyseur r´ecursif
Definition non-r´ecursif ∗Un non terminal X∈ V est dit -productif si X⇒ .N
Construction de la table d’analyse
L’ensemble des -productif est -Prod.Ensembles Premier
Ensemble des -prod X est -productif si la grammaire contient la production :
Ensembles Suivant
I X→ ;
Remplissage de la table d’analyse
I ou X→ Y Y ...Y telle que l’ensemble des non-terminaux1 2 n
Caract´erisation d’une grammaire LL(1) {Y ,Y ,...,Y}⊆ V ne contient que des non-terminaux1 2 n N
Quand une grammaire n’est pas LL(1) -productifs.
Factorisation `a gauche
Algorithme de calcul similaire `a celui qui calcule les productifs.Suppression de la r´ecursivit´e `a gauche
69/117 70/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LLEnsembles Premier Ensembles Premier
Analyseur r´ecursif Analyseur r´ecursifEnsemble des -prod Ensemble des -prod
Analyseur non-r´ Analyseur non-r´ Suivant Suivant
Construction de la table d’analyse Construction de la table d’analyseRemplissage de la table d’analyse Remplissage de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
PrincipesExemple
Table d’analyse LL
Analyseur r´ecursif non-r´ecursif
Construction de la table d’analyseS→ AB | Da
Ensembles PremierA→ aAb |
Ensemble des -prodB→ bB |
Ensembles SuivantD→ dD | e
Remplissage de la table d’analyse
-Prod ?
Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1)
Factorisation `a gauche
Suppression de la r´ecursivit´e `a gauche71/117 72/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)Principes Principes
Table d’analyse LL Table d’analyse LL
Ensembles Premier Ensembles PremierAnalyseur r´ecursif Analyseur r´ecursif
Ensemble des -prod Ensemble des -prodAnalyseur non-r´ecursif Analyseur non-r´ecursif
Ensembles Suivant Ensembles SuivantConstruction de la table d’analyse Construction de la table d’analyse
Remplissage de la table d’analyse Remplissage de la table d’analyseCaract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Outils pour l’analyse pr´edictive, intuition - 2 Ensembles Suivant, intuition
Quand appliquer A→ ?
Pour choisir entre S→ AB et S→ Da :
Quand la tˆete de lect. correspond `a un terminal qui peut suivre A.
I si tˆete lecture∈{a,b} : choisir S→ AB ; SA
I si tˆete lecture∈{d,e} : choisir S→ Da.
A
A B
Et si la tˆete de lecture est # ? #6∈ Premier(AB)∪Premier(Da).
Comment choisir entre A→ aAb et A→ ? Premier() =∅
a b
⇒ les ensembles Premier ne suffisent pas.
b∈ Suivant(A) Suivant(A)⊇ Premier(B)
73/117 74/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LLEnsembles Premier Ensembles Premier
Analyseur r´ecursif Analyseur r´ecursifEnsemble des -prod Ensemble des -prod
Analyseur non-r´ Analyseur non-r´ Suivant Suivant
Construction de la table d’analyse Construction de la table d’analyseRemplissage de la table d’analyse Remplissage de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Ensembles Suivant, intuition Ensembles Suivant, intuition
On a donc b∈ Suivant(A)
+Pour α∈ (V ∪V ) , Suivant(α) contient l’ensemble desT N
+A terminaux de V susceptibles de suivre α dans un mot de VT T
d´eriv´e de l’axiome S.a A→ aAb
b A→ Si α =, cet ensemble est vide.
d ?
Par convention, Suivant(S)⊇{#}.e ?
# ?
75/117 76/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LL
Ensembles Premier Ensembles PremierAnalyseur r´ecursif Analyseur r´ecursif
Ensemble des -prod Ensemble des -prodAnalyseur non-r´ecursif Analyseur non-r´ecursif
Ensembles Suivant Ensembles SuivantConstruction de la table d’analyse Construction de la table d’analyse
Remplissage de la table d’analyse Remplissage de la table d’analyseCaract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Ensembles Suivant, d´efinitions ´equivalentes Calcul des Suivant - 1
Pour calculer Suivant(X ), on regarde les productions dans
Definition lesquelles X apparaˆıt en partie droite (diff´erent du calcul des
Soit une grammaire alg´ebrique d’axiome S. On d´efinit : Premier).
∗Suivant : (V ∪V ) → P(V )T N T Pour Suivant(A) :
∗α 7→ {a∈ V |S⇒ βαaγ,T S→ ABA→ aAb∗pour β,γ∈ (V ∪V )}N T SA
Definition A
∗ A BSuivant : (V ∪V ) → P(V )T N T
∗α 7→ {a∈ Premier(γ)|S⇒ βαγ,
∗pour β,γ∈ (V ∪V )}N T a b
77/117 78/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)
Principes Principes
Table d’analyse LL Table d’analyse LLEnsembles Premier Ensembles Premier
Analyseur r´ecursif Analyseur r´ecursifEnsemble des -prod Ensemble des -prod
Analyseur non-r´ Analyseur non-r´ Suivant Suivant
Construction de la table d’analyse Construction de la table d’analyseRemplissage de la table d’analyse Remplissage de la table d’analyse
Caract´erisation d’une grammaire LL(1) Caract´erisation d’une grammaire LL(1)
Quand une grammaire n’est pas LL(1) Quand une grammaire n’est pas LL(1)
Calcul des Suivant - 2 Calcul des Suivant, cas de l’axiome
Pour l’axiome, on ajoute le marqueur de fin de mot :Soit P ⊆ P l’ensemble des productions p dans lesquelles XX
apparaˆıt en partie droite : S
Suivant(S) ={#}∪ Suivant (S)pp∈PSS
Suivant(X ) = Suivant (X )pp∈PX
Ex : pour X→ aXb|
Ex : P ={S→ AB,A→ aAb}A P ={X→ aXb}X
Suivant(A) = Suivant(A) ∪Suivant(A)S→AB A→aAb Suivant(X ) ={#}∪Suivant(X )X→aXb
79/117 80/117
Mirabelle Nebut Analyse descendante LL(k) Mirabelle Nebut Analyse descendante LL(k)