Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Analyse descendante LL(k)Mirabelle NebutBureau 203 - M3 extension mirabelle.nebut at lifl.fr
2012-2013
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Principes Analyseur rcursif e Construction de la table danalyse Ensembles Premier Ensemble des -prod Ensembles Suivant Remplissage de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Factorisation ` gauche a Suppression de la rcursivit ` gauche e ea Analyseurs LL(k), LL(*)2/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Objectif du cours
Comprendre le fonctionnement des gnrateurs de parser e e descendants : LL(1), ex antLR V1 LL(k), ex javaCC LL(*), ex antLR V3
3/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Analyse descendante
Lautomate ` pile sous-jacent : a eectue uniquement des lectures et des expansions ; construit un arbre en ordre prxe (idem aut. items) ; e part de laxiome (idem aut. items) ; construit une drivation gauche (idem aut. items). e
4/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Dirence avec lautomate des items e
Deux dirences fondamentales : e analyse dterministe dite prdictive ; e e plus ditems ni de rductions explicites. e
5/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Analyse dterministe e
` A chaque expansion lanalyseur sait choisir une production. Il ne revient jamais sur ce choix : en cas de succ`s le mot appartient au langage ; e en cas dchec on est sr que mot nappartient pas au langage. e u
6/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Analyse prdictive e
Lanalyseur prdit quelle production utiliser. . . e . . . en analysant les k prochains symboles sous la tte de lecture. e Consquences : e ne fonctionne quavec certaines grammaires, dites LL(k) ; tte de lecture toujours dnie : marqueur de n de mot #. e e NB : dans ce cours techniques pour k=1, on regarde uniquement la tte de lecture. e7/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Se passer des itemsRappel : item de la forme [X ] : X est en cours de reconnaissance ; a dj` t reconnu ; eae e il reste ` reconna , le futur de litem a tre Un analyseur LL : ne mmorise pas quil est en train de reconna X ; e tre ne mmorise pas quil a reconnu ; e consid`re uniquement . e8/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Se passer des items : consquences ePlus besoin daxiome supplmentaire. e Dans la pile : plus ditems mais des mots tendus : mots de (VN VT ) ; e lalphabet est VN VT ; le symbole de pile initiale est laxiome. A b B une pile
S pile initiale
pile vide (acceptation)9/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Exemple ` suivre dans le cours a
Soit la grammaire G = {VT , VN , S, P} avec : VT = {a, b, d, e} ; VN = {S, A, B, D} ; P contient les productions : S AB | Da A aAb | B bB | D dD | e
10/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Exemple - les piles pour abb#S AB | Da A aAb | B bB | D dD | e abb# ?
a A A A b b b S B B B B abb# abb# abb# bb# bb# (1) (2) (3) (4) (5)
B b# (6)
b B b# (7)
B # (8)
# (9)
Comparer avec lautomates des items ! Drivation gauche, arbre en ordre prxe. e e11/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Gnralisation e e
La conguration initiale est (m#, S) ; La conguration nale est (#, ) : acceptation par pile vide. On traite systmatiquement le sommet de pile. e
12/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Transition de lecture
Si le sommet de pile est un terminal a VT : on contrle que a est bien sous la tte de lecture (sinon o e chec) ; e on le consomme ; on le dpile. e Lecture de a : (am, z1 . . . zn a) (m, z1 . . . zn )
13/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Transition dexpansionSi le sommet de pile est un non terminal X VN . . . . . . et que la tte de lecture est y VT {#}. . . e si Table[X , y ] contient X X1 . . . Xn : on dpile X ; e on empile ` sa place X1 . . . Xn , avec X1 au sommet. a (m, z1 . . . zn X ) sinon erreur.14/119
(m, z1 . . . zn Xn . . . X1 )
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Transition dexpansion : remarque
Expansion par X X1 . . . Xn : (m, z1 . . . zn X ) X1 sera trait en premier. e on assure ainsi la construction dune drivation gauche ; e (m, z1 . . . zn Xn . . . X1 )
15/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Construction de larbre syntaxique : ordre prxe eTransition dexpansion par X X1 . . . Xn : X est le prochain lordre prxe) ; e nud ` traiter dans larbre (pour a
on lui rajoute les ls X1 . . . Xn de la gauche vers la droite ; le prochain nud ` traiter devient X1 . a Transition de a-lecture : a est le prochain prxe) ; e nud ` traiter dans larbre (pour lordre a
on vrie que a concorde bien avec la tte de lecture ; e e et on passe au nud suivant.16/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Mise en uvre
Les outils nimplantent pas un automate ` pile. a Ils utilisent une implmentation rcursive. e e Dans tous les cas, le choix de lexpansion est indiqu par une table e danalyse.
17/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Table danalyse - exemple
a b d e #
S S AB S AB S Da S Da S AB
A A aAb A erreur erreur A
B erreur B bB erreur erreur B
D erreur erreur D dD De erreur
18/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Table danalyse LL(1)
Contient toute lintelligence de lanalyseur syntaxique.
DenitionLa table danalyse Table est un tableau ` deux dimensions tel que : a chaque colonne est indice par un non-terminal VN ; e chaque ligne est indice par un terminal VT ou # ; e chaque case contient une production P ou erreur. On verra plus tard comment remplir cette table.19/119
Mirabelle Nebut
Analyse descendante LL(k)
Principes Analyseur rcursif e Construction de la table danalyse Caractrisation dune grammaire LL(1) e Quand une grammaire nest pas LL(1) Analyseurs LL(k), LL(*)
Interprtation de Table[a, X ] e
si le terminal a VT est sous la tte de lecture ; e et si le non-terminal en cours de traitement est X VN ; alors on consulte Table[a, X ]. Si Table[X , a] contient X alors on choisit une expansion par cette production ; erreur alors erreur de syntaxe : X et a ne saccordent pas.
20/119
Mirabelle Nebut
