Click here to load reader

compilation

  • View
    18

  • Download
    1

Embed Size (px)

DESCRIPTION

cours

Text of compilation

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

Search related