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

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

• Traitement
• Reconnaissance
• Analyse
• Private
• Analyseur
• Récursif
• Outil
• Erreur
• Symbole

Informations

• Publié par: sewyeng
• Nombre de lectures: 415
• Langue: Français

Extrait

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)
Qu