Analyse descendante LL(k) - FIL Lille 1nebut/portail/compilS5/fichiers/cours/anDesc/...Construction de la table d’analyse Caract erisation d’une grammaire LL(1) Quand une grammaire

PrincipesAnalyseur recursif

Construction de la table d’analyseCaracterisation d’une grammaire LL(1)Quand une grammaire n’est pas LL(1)

Analyseurs LL(k), LL(*)

Analyse descendante LL(k)

Mirabelle Nebut

Bureau 203 - M3 extensionmirabelle.nebut at lifl.fr

2012-2013

Mirabelle Nebut Analyse descendante LL(k)

2/119




Principes

Analyseur recursif

Construction de la table d’analyseEnsembles PremierEnsemble des ε-prodEnsembles SuivantRemplissage de la table d’analyse

Caracterisation d’une grammaire LL(1)

Quand une grammaire n’est pas LL(1)Factorisation a gaucheSuppression de la recursivite a gauche



3/119




Objectif du cours

Comprendre le fonctionnement des generateurs de parserdescendants :

I LL(1), ex antLR V1

I LL(k), ex javaCC

I LL(*), ex antLR V3


4/119




Analyse descendante

L’automate a pile sous-jacent :

I effectue uniquement des lectures et des expansions ;

I construit un arbre en ordre prefixe (idem aut. items) ;

I � part � de l’axiome (idem aut. items) ;

I construit une derivation gauche (idem aut. items).


5/119




Difference avec l’automate des items

Deux differences fondamentales :

I analyse deterministe dite predictive ;

I plus d’items ni de reductions explicites.


6/119




Analyse deterministe

A chaque expansion l’analyseur sait choisir une production.

Il ne revient jamais sur ce choix :

I en cas de succes le mot appartient au langage ;

I en cas d’echec on est sur que mot n’appartient pas au langage.


7/119




Analyse predictive

L’analyseur ”predit” quelle production utiliser. . .

. . . en analysant les k prochains symboles sous la tete de lecture.

Consequences :

I ne fonctionne qu’avec certaines grammaires, dites LL(k) ;

I tete de lecture toujours definie : marqueur de fin de mot #.

NB : dans ce cours techniques pour k=1, on regarde uniquement latete de lecture.


8/119




Se passer des items

Rappel : item de la forme [X → α • β] :

I X est en cours de reconnaissance ;

I α a deja ete reconnu ;

I il reste a reconnaıtre β, le futur de l’item

Un analyseur LL :

I ne memorise pas qu’il est en train de reconnaıtre X ;

I ne memorise pas qu’il a reconnu α ;

I considere uniquement β.


9/119




Se passer des items : consequences

Plus besoin d’axiome supplementaire.

Dans la pile :

I plus d’items mais des mots etendus : mots de (VN ∪ VT )∗ ;

I l’alphabet est VN ∪ VT ;

I le symbole de pile initiale est l’axiome.

Spile initiale

AbB

une pile pile vide (acceptation)


10/119




Exemple a suivre dans le cours

Soit la grammaire G = {VT ,VN ,S ,P} avec :

I VT = {a, b, d , e} ;

I VN = {S ,A,B,D} ;

I P contient les productions :

S → AB | DaA → aAb | εB → bB | εD → dD | e


11/119




Exemple - les piles pour abb#

S → AB | Da B → bB | εA → aAb | ε D → dD | e abb# ?

S

abb#(1)

AB

abb#(2)

aAbB

abb#(3)

AbB

bb#(4)

bB

bb#(5)

B

b#(6)

bB

b#(7)

B

#(8)

#(9)

Comparer avec l’automates des items !Derivation gauche, arbre en ordre prefixe.


12/119




Generalisation

I La configuration initiale est (m#, S) ;

I La configuration finale est (#, ) : acceptation par pile vide.

On traite systematiquement le sommet de pile.


13/119




Transition de lecture

Si le sommet de pile est un terminal a ∈ VT :

I on controle que a est bien sous la tete de lecture (sinonechec) ;

I on le consomme ;

I on le depile.

Lecture de a :

(am, z1 . . . zna) ` (m, z1 . . . zn)


14/119




Transition d’expansion

Si le sommet de pile est un non terminal X ∈ VN . . .

. . . et que la tete de lecture est y ∈ VT ∪ {#}. . .

si Table[X , y ] contient X → X1 . . .Xn :

I on depile X ;

I on empile a sa place X1 . . .Xn, avec X1 au sommet.

(m, z1 . . . znX ) ` (m, z1 . . . znXn . . .X1)

sinon erreur.


15/119




Transition d’expansion : remarque

Expansion par X → X1 . . .Xn :

(m, z1 . . . znX ) ` (m, z1 . . . znXn . . .X1)

I X1 sera traite en premier.

I on assure ainsi la construction d’une derivation gauche ;


16/119




Construction de l’arbre syntaxique : ordre prefixe

Transition d’expansion par X → X1 . . .Xn :

I X est le � prochain � nœud a traiter dans l’arbre (pourl’ordre prefixe) ;

I on lui rajoute les fils X1 . . .Xn de la gauche vers la droite ;

I le prochain nœud a traiter devient X1.

Transition de a-lecture :

I a est le � prochain � nœud a traiter dans l’arbre (pour l’ordreprefixe) ;

I on verifie que a concorde bien avec la tete de lecture ;

I et on passe au nœud suivant.


17/119




Mise en œuvre

Les outils n’implantent pas un automate a pile.

Ils utilisent une implementation recursive.

Dans tous les cas, le choix de l’expansion est indique par une tabled’analyse.


18/119




Table d’analyse - exemple

S A B D

a S → AB A→ aAb erreur erreur

b S → AB A→ ε B → bB erreur

d S → Da erreur erreur D → dD

e S → Da erreur erreur D → e

# S → AB A→ ε B → ε erreur


19/119




Table d’analyse LL(1)

Contient toute l’intelligence de l’analyseur syntaxique.

DefinitionLa table d’analyse Table est un tableau a deux dimensions tel que :

I chaque colonne est indicee par un non-terminal ∈ VN ;

I chaque ligne est indicee par un terminal ∈ VT ou # ;

I chaque case contient une production ∈ P ou erreur.

On verra plus tard comment remplir cette table.


20/119




Interpretation de Table[a,X ]

I si le terminal a ∈ VT est sous la tete de lecture ;

I et si le non-terminal en cours de traitement est X ∈ VN ;

alors on consulte Table[a,X ].

Si Table[X , a] contient

I X → γ alors on choisit une expansion par cette production ;

I erreur alors erreur de syntaxe : X et a ne s’accordent pas.


21/119




Principes

Analyseur recursif






22/119




Analyseur descendant recursif

Principe :

I analyseur LL code par un ensemble de fonctions ;

I ces fonctions s’appellent les unes les autres ;

I n’utilise pas de pile explicite : pile implicite des appels.

Codage des fonctions :

I une fonction X() par non-terminal X ∈ VN de la grammaire ;

I X() reconnaıt un mot engendre par X ;

I la fonction X() code les productions Table[X , y ] de la tabled’analyse, pour tout y ∈ VT ∪#.


23/119




Exemple

Ecrire un analyseur syntaxique recursif LL(1) Parser pour G :


A voir :

I ecriture de S(), A(), B(), D() ;

I collaboration avec un analyseur lexical.


24/119




Collaboration avec un analyseur lexical

On reprend les conventions utilisees en TP :

I un an. lexical anLex de type Scanner (suppose donne) ;

I symboles de type Symbole ;

I codage entier du type des symboles dans TypeSymboles

(note TS dans les transparents) ;

I methode int getType() de Symbole pour obtenir ce type ;I methode Symbole next token() de Scanner :

I avance la tete de lecture teteLect ;I retourne le symbole lu, de type Symbole.

I on remplace le marqueur # par TS.EOF.


25/119




Construction de l’analyseur syntaxique

...

public class Parser {

// analyseur lexical

private Scanner anLex;

// symbole courant recu de l’analyseur lexical

private Symbole teteLect;

public Parser (Scanner anLex) {

this.anLex = anLex;

}

...


26/119




Lancement de l’analyseur syntaxique

Dans la classe Parser :

public void analyser() throws ScannerException, ParserException {

// positionnement tete de lecture

this.teteLect = (Symbole) this.anLex.next_token();

this.S(); // je veux reconnaıtre l’axiome

// et uniquement l’axiome

if (this.teteLect.getType() != TS.EOF)

throw new ParserException();

}


27/119




Code de S()

La tete de lecture est deja positionnee sur le symbole de prediction.

S

a S → AB

b S → AB

d S → Da

e S → Da

# S → AB

private void S() throws ... {

if (this.teteLect.getType() == TS.a)

... // S -> AB

else if (this.teteLect.getType() == TS.b)

... // S -> AB

else if (this.teteLect.getType() == TS.d)

... // S -> Da

else if (this.teteLect.getType() == TS.e)

... // S -> Da

else if (this.teteLect.getType() == TS.EOF)

... // S -> AB

else throw new ParserException();

}


28/119




Code de S()

On factorise.

S

a S → AB

b S → AB

d S → Da

e S → Da

# S → AB


if (this.teteLect.getType() == TS.a

|| this.teteLect.getType() == TS.b

|| this.teteLect.getType() == TS.EOF)

... // S -> AB

else if (this.teteLect.getType() == TS.d

|| this.teteLect.getType() == TS.e)

... // S -> Da


}


29/119




Code des productions de S()

Code pour S → AB :

I je veux reconnaıtre A puis B ;

I ⇒ A() ; B() ;

Code pour S → Da :

I je veux reconnaıtre D. . .

I . . . puis verifier que a est bien sous la tete de lecture ;

I et consommer a.


30/119




Terminaux : verification et consommation

Methode consommer dediee a la gestion des terminaux :

private void consommer(int type)

throws ScannerException, ParserException {

if (this.teteLect.getType() == type)

this.teteLect = (Symbole) this.anLex.next_token();


}

Code pour S → Da : D(); this.consommer(TS.a);.


31/119




Code final de S()

S

a S → AB

b S → AB

d S → Da

e S → Da

# S → AB


if (this.teteLect.getType() == TS.a

|| this.teteLect.getType() == TS.b

|| this.teteLect.getType() == TS.EOF) {

A(); B(); // S -> AB

} else if (this.teteLect.getType() == TS.d

|| this.teteLect.getType() == TS.e) {

D(); this.consommer(TS.a); // S -> Da

} else throw new ParserException();

}

Quand S() termine, pour un mot accepte, la tete de lecture est surTS.EOF.


32/119




Code de A()

La tete de lecture est deja positionnee sur le symbole de prediction.

A

a A→ aAb

b A→ ε

d erreur

e erreur

# A→ ε

private void A() throws ... {

if (this.teteLect.getType() == TS.a)

... // A -> aAb

else if (this.teteLect.getType() == TS.b

|| this.teteLect.getType() == TS.EOF)

... // A ->

else // erreur


}


33/119




Code des productions de A()

Code pour A → aAb :

this.consommer(TS.a); A(); this.consommer(TS.b);

Code pour A → ε :

I le mot vide est immediatement reconnu ;

I sans toucher a la tete de lecture ;

I on ne fait rien.


34/119




Code final de A()

A

a A→ aAb

b A→ ε

d erreur

e erreur

# A→ ε

private void A() throws ... {

if (this.teteLect.getType() == TS.a) {

// A -> aAb

this.consommer(TS.a); A();

this.consommer(TS.b);

} else if (this.teteLect.getType() == TS.b

|| this.teteLect.getType() == TS.EOF) {

// rien, A ->

} else // erreur


}

Quand A() termine, pour un mot accepte, la tete de lecture estpositionnee pour reconnaıtre un B ou lire un b.


35/119




Code final de B()

B

a erreur

b B → bB

d erreur

e erreur

# B → ε

private void B() throws ... {

if (this.teteLect.getType() == TS.b) {

// B -> bB

this.consommer(TS.b); B();

} else if (this.teteLect.getType() == TS.EOF) {

// rien, B ->

} else // erreur


}


36/119




Code final de D()

D

a erreur

b erreur

d D → dD

e D → e

# erreur

private void D() throws ... {

if (this.teteLect.getType() == TS.d) {

// D -> dD

this.consommer(TS.d); D();

} else if (this.teteLect.getType() == TS.e)

// D -> e

this.consommer(TS.e);

else // erreur


}


37/119




Exemple d’execution

Reconnaıtre abb# ?


38/119




Ensembles PremierEnsemble des ε-prodEnsembles SuivantRemplissage de la table d’analyse

Principes

Analyseur recursif






39/119





Principes

Analyseur recursif






40/119





Outils pour l’analyse predictive, intuition - 1

Comment choisir entre S → AB et S → Da ?

Supposons que je sache que :

I AB ne permet de deriver que des mots prefixes par a ou par b ;

I AB ⇒∗ au et AB ⇒∗ bu, pour u ∈ VT∗ ;

I Da ne permet de deriver que des mots prefixes par d ou par e ;

I Da⇒∗ du et Da⇒∗ eu, pour u ∈ VT∗.


41/119






Maintenant je sais (partiellement) choisir entre S → AB etS → Da :

I si tete lecture ∈ {a, b} : choisir S → AB ;

I si tete lecture ∈ {d , e} : choisir S → Da.

S

a S → AB

b S → AB

d S → Da

e S → Da

# ?


42/119





Ensemble Premier - definition

On dit que Premier(AB) = {a, b} et Premier(Da) = {d , e}.

Pour α ∈ (VT ∪ VN)+, Premier(α) contient l’ensemble desterminaux de VT susceptibles de commencer un mot de VT

+

derive de α.

Si α = ε, cet ensemble est vide.

DefinitionSoit une grammaire algebrique. On definit :

Premier : (VT ∪ VN)∗ → P(VT )α 7→ {a ∈ VT |α⇒∗ au, u ∈ VT

∗}


43/119





Les Premier sur les arbres syntaxiques

a

A

a b

A

B A B

B

b

S S S

A B

S

D

dD

a

S

D

e ∈ Premier(α)

α ∈ (VT ∪ VN)∗


44/119





Calcul des Premier - 0

Soit α ∈ (VN ∪ VT )∗ :

casα = ε : ?

α = a, a ∈ VT : ?

α = aβ, a ∈ VT , β ∈ (VN ∪ VT )∗ : ?

α = X , X ∈ VN : ?

α = Xβ, X ∈ VN , β ∈ (VN ∪ VT )∗ : ?

fcas


45/119







casα = ε : ∅α = a, a ∈ VT : {a}α = aβ, a ∈ VT , β ∈ (VN ∪ VT )∗ : {a}α = X , X ∈ VN : ?

α = Xβ, X ∈ VN , β ∈ (VN ∪ VT )∗ : ?

fcas


46/119





Calcul de Premier(X ), X ∈ VN

Si l’ensemble des productions de membre gauche S est :

S → AB | Da

alors on a :

Premier(S) = Premier(AB) ∪ Premier(Da)

Cas general : Si la grammaire contient les productions de membregauche X :

X → γ1 | . . . | γn

alorsPremier(X ) =⋃{Premier(γi ) |X → γi ∈ P}


47/119







casα = ε : ∅α = a, a ∈ VT : {a}α = aβ, a ∈ VT , β ∈ (VN ∪ VT )∗ : {a}α = X , X ∈ VN :

⋃{Premier(γi ) |X → γi ∈ P}

α = Xβ, X ∈ VN , β ∈ (VN ∪ VT )∗ : ?

fcas


48/119





Calcul des Premier , α = Xβ, X ∈ VN

Deux cas selon que X peut � s’effacer � ou non :

X ⇒∗ ε ?

Si X ⇒∗ ε on dit que X est ε-productif : X ∈ ε-Prod


49/119





Calcul des Premier , α = Xβ, X 6∈ ε-Prod - exemple

Par exemple D 6∈ ε-productif :

D → dD | e

alors Premier(Da) = Premier(D)a

S

D

dD

a

S

D

e

Donc, si X 6∈ ε-Prod, Premier(Xβ) = Premier(X )


50/119





Calcul des Premier , α = Xβ, X ∈ ε-Prod - exemple

Par exemple A ∈ ε-productif :

A→ ε | aAb

Premier(AB) = Premier(A) ∪Premier(B)Premier(ABS) = Premier(A) ∪Premier(BS)

S

A

a b

A

B A B

B

b

S

Donc, si X ⇒∗ ε alors Premier(Xβ) = Premier(X ) ∪ Premier(β)


51/119





Calcul des Premier


casα = ε : ∅α = a, a ∈ VT : {a}α = aβ, a ∈ VT , β ∈ (VN ∪ VT )∗ : {a}α = X , X ∈ VN :

⋃{Premier(γi ) |X → γi ∈ P}

α = Xβ, X ∈ VN \ ε-Prod, β ∈ (VN ∪ VT )∗ : Premier(X )

α = Xβ, X ∈ VN ∩ ε-Prod, β ∈ (VN ∪ VT )∗ :Premier(X ) ∪ Premier(β)

fcas


52/119





Calcul effectif des ensembles Premier

On procede en deux etapes :

1. on pose un systeme d’equations pour Premier ;

2. on calcule par iteration de point fixe les plus petits ensemblesqui satisfont ces equations.

Pour le moment on suppose donne ε-Prod, l’ensemble desε-productifs.


53/119





Exemple


ε-Prod = {A, B, S}

Premier(S) = ?Premier(A) = ?Premier(B) = ?Premier(D) = ?

α = ε : ∅

α = a, a ∈ VT : {a}

α = aβ, a ∈ VT , β ∈ (VN ∪ VT )∗ : {a}

α = X , X ∈ VN :⋃{Premier(γi ) |X → γi ∈ P}

α = Xβ, X ∈ VN \ε-Prod, β ∈ (VN ∪VT )∗ :

Premier(X )

α = Xβ, X ∈ VN∩ε-Prod, β ∈ (VN∪VT )∗ :

Premier(X ) ∪ Premier(β)


54/119





Exemple

Premier(S) = Premier(A) ∪ Premier(B) ∪ Premier(D)Premier(A) = {a}Premier(B) = {b}Premier(D) = {d , e}

D’ou

Premier(S) = {a, b, d , e} Premier(aAb) = {a}Premier(A) = {a} Premier(bB) = {b}Premier(B) = {b} Premier(dD) = {d}Premier(D) = {d , e} Premier(e) = {e}Premier(AB) = {a, b} Premier(ε) = ∅Premier(Da) = {d , e}


55/119





Exemple : remplissage de la table

A→ aAb et Premier(aAb) = {a}A→ ε et Premier(ε) = ∅

S A B D







56/119





Exemple : remplissage de la table

S → AB et Premier(AB) = {a, b}S → Da et Premier(Da) = {d , e}

S A B D







57/119





Remarque : resolution du systeme

Premier(S) = Premier(A) ∪ Premier(B) ∪ Premier(D)Premier(A) = {a}Premier(B) = {b}Premier(D) = {d , e}

Se resoud sans iteration de point fixe : systeme d’equations nonrecursif.

Ce n’est pas toujours le cas.


58/119





Resolution du systeme : autre exemple

S → S1S2 | aS1 → S | bS2 → c

Premier(S) = Premier(S1) ∪ {a}Premier(S1) = Premier(S) ∪ {b}Premier(S2) = {c}

iter Premier(S) Premier(S1) Premier(S2)

0 ∅ ∅ ∅1 {a} {b} {c}2 {a, b} {b, a} {c}3 {a, b} {b, a} {c}

stabilisation


59/119





Principes

Analyseur recursif






60/119





Definition des ε-prod

DefinitionUn non terminal X ∈ VN est dit ε-productif si X ⇒∗ ε.

L’ensemble des ε-productif est ε-Prod.

X est ε-productif si la grammaire contient la production :

I X → ε ;

I ou X → Y1Y2 . . .Yn telle que l’ensemble des non-terminaux{Y1,Y2, . . . ,Yn} ⊆ VN ne contient que des non-terminauxε-productifs.

Algorithme de calcul similaire a celui qui calcule les productifs.


61/119





Exemple

S → AB | DaA → aAb | εB → bB | εD → dD | eε-Prod ?


62/119





Principes

Analyseur recursif






63/119






Pour choisir entre S → AB et S → Da :

I si tete lecture ∈ {a, b} : choisir S → AB ;

I si tete lecture ∈ {d , e} : choisir S → Da.

Et si la tete de lecture est # ? # 6∈ Premier(AB) ∪ Premier(Da).

Comment choisir entre A → aAb et A → ε ? Premier(ε) = ∅

⇒ les ensembles Premier ne suffisent pas.


64/119





Ensembles Suivant, intuition

Quand appliquer A → ε ?

Quand la tete de lect. correspond a un terminal qui peut suivre A.

a b

A

A

b ∈ Suivant(A)

A

S

B

Suivant(A) ⊇ Premier(B)


65/119






On a donc b ∈ Suivant(A)

A

a A→ aAb

b A→ ε

d ?

e ?

# ?


66/119






Pour α ∈ (VT ∪ VN)+, Suivant(α) contient l’ensemble desterminaux de VT susceptibles de suivre α dans un mot de VT

+

derive de l’axiome S .

Si α = ε, cet ensemble est vide.

Par convention, Suivant(S) ⊇ {#}.


67/119





Ensembles Suivant, definitions equivalentes

DefinitionSoit une grammaire algebrique d’axiome S . On definit :

Suivant : (VT ∪ VN)∗ → P(VT )α 7→ {a ∈ VT | S ⇒∗ βαaγ,

pour β, γ ∈ (VN ∪ VT )∗}

DefinitionSuivant : (VT ∪ VN)∗ → P(VT )

α 7→ {a ∈ Premier(γ) |S ⇒∗ βαγ,pour β, γ ∈ (VN ∪ VT )∗}


68/119





Calcul des Suivant - 1

Pour calculer Suivant(X ), on regarde les productions danslesquelles X apparaıt en partie droite (different du calcul desPremier).

Pour Suivant(A) :

A → aAb

a b

A

A

S → AB

A

S

B


69/119






Soit PX ⊆ P l’ensemble des productions p dans lesquelles Xapparaıt en partie droite :

Suivant(X ) =⋃

p∈PXSuivantp(X )

Ex : PA = {S → AB,A→ aAb}Suivant(A) = Suivant(A)S→AB ∪ Suivant(A)A→aAb


70/119





Calcul des Suivant, cas de l’axiome

Pour l’axiome, on ajoute le marqueur de fin de mot :

Suivant(S) = {#} ∪⋃

p∈PSSuivantp(S)

Ex : pour X → aXb | ε

PX = {X → aXb}Suivant(X ) = {#} ∪ Suivant(X )X→aXb


71/119





Calcul des Suivant - 3 - exemple

Suivant(A)S→AB ? (exemple precedent)

Cas deja vu :

A

S

B

Suivant(A) ⊇ Premier(B)


72/119






Suivant(A)S→AB ? (exemple precedent)

mais B est ε-Prod !

A

S

B

Suivant(A) ⊇ Suivant(S)


73/119






Puisque B est ε-Prod :

Suivant(A)S→AB = Premier(B) ∪ Suivant(S)


74/119






Quand une production est de la forme . . .→ Xα :

I pour calculer Suivant(X ) ;

I Il faut pouvoir dire si α ∈ (VN ∪ VT )∗ est ε-productif ou pas.

Definitionα ∈ (VN ∪ VT )∗ est ε-productif si α⇒∗ ε. On definit la fonction :

Eps : (VN ∪ VT )∗ → {vrai , faux}α 7→ α est ε-productif

On verra apres comment calculer Eps.


75/119






Pour calculer Suivantp(X ) avec :

p = Y → αXβ et Eps(β) = faux , α, β ∈ (VN ∪ VT )∗

X β

Y

Suivantp(X ) = Premier(β)

Ex : pour Y → Xb, Suivant(X )Y→Xb = {b}.


76/119







p = Y → αX

Xα

Y

Suivantp(X ) = Suivant(Y )


77/119







p = Y → αXβ et Eps(β) = vrai , α, β ∈ (VN ∪ VT )∗

X

Y

β Suivantp(X ) =Premier(β) ∪ Suivant(Y )

Ex : pour S → AB, Suivant(A)S→AB = Premier(B) ∪ Suivant(S).


78/119





Remarque - 1

Si X apparaıt plusieurs fois en partie droite d’une production, ilfaut prendre en compte toutes ses occurrences dans le calcul deSuivant(X ).

Ex : Y → XaXaXc

SuivantY→XaXaXc(X ) = {a, c}


79/119





Remarque - 2

Pourquoi pas Suivant(X )Y→Xβ = Premier(β) ∪ Suivant(β) ?

Parce que Suivant(Y ) ⊆ Suivant(β).

Ex :

S → Y |ZY → X1X2

X1 → aX2 → ε | bZ → X2c

Suivant(S) = {#}Suivant(Y ) = Suivant(S) = {#}Suivant(Z ) = Suivant(S) = {#}Suivant(X2) = {c} ∪ Suivant(Y ) = {c,#}Suivant(X1) = Premier(X2) ∪ Suivant(Y )


80/119





Calcul des Suivant, recapitulons !

# ∈ Suivant(axiome)

Soit PX ⊆ P l’ensemble des productions p dans lesquelles Xapparaıt en partie droite :

Suivant(X ) =⋃

p∈PXSuivantp(X )

avec : Suivantp(X ) =cas

p = Y → αX : Suivant(Y )p = Y → αXβ et Eps(β) = faux : Premier(β)p = Y → αXβ et Eps(β) = vrai : Premier(β) ∪ Suivant(Y )

fincas


81/119





Calcul effectif des ensembles Suivant

On procede en deux etapes :

I on pose un systeme d’equations pour Suivant ;

I on calcule par iteration de point fixe les plus petits ensemblesqui satisfont ces equations.

I avec initialement Suivant(S) = {#}, et pour les autresnon-terminaux Suivant(X ) = ∅.


82/119





Exemple


Eps(B) = vrai

Suivant ?

# ∈ Suivant(axiome)

Suivant(X ) =⋃

p∈PXSuivantp(X )

avec : Suivantp(X ) =casp = Y → αX : Suivant(Y )p = Y → αXβ et Eps(β) = faux : Premier(β)p = Y → αXβ et Eps(β) = vrai : Premier(β)

∪Suivant(Y )fincas


83/119





Exemple de remplissage de table

A→ ε et Suivant(A) = {b,#}

S A B D







84/119





Exemple de remplissage de table

S → AB et Suivant(S) = {#}

S A B D







85/119





Calcul des ε-productifs

On connaıt deja ε-Prod, ens. des non-terminaux ε-productifs.

Pour calculer Eps(α) :

Eps(α) =casα = ε : vraiα = X1 . . .Xn, n ≥ 1 avec {X1, . . . ,Xn} ⊆ VN et

{X1, . . . ,Xn} ⊆ ε-Prod : vraiautre : faux // α contient un terminal

fincas


86/119





Exemple

Sachant que ε-Prod = {A,B,S} :

Eps(Da) ?

Eps(AB) ?

Eps(ε) ?

Eps(B) ?


87/119





Principes

Analyseur recursif






88/119





Table d’analyse : au prealable

On calcule :

I les ε-productifs ;

I les ensembles Premier ;

I les ensembles Suivant.


89/119





Remplissage de la table

Entree : une gram. alg. G , ses ensembles Premier et SuivantSortie : la table d’analyse Tablepour toute production X → γ ∈ Pfaire pour tout a ∈ Premier(γ)

faire ajouter X → γ a Table[X , a] faitsi Eps(γ) = vrai alors pour tout b ∈ Suivant(X )

faire Table[X , b] = X → γfait

finsifait

Ajouter erreur dans les entrees de Table restees vides


90/119





Exemple

S → AB :

I Premier(AB) = {a, b} ;

I Eps(AB) = vrai ;

I Suivant(S) = {#}.S → Da :

I Premier(Da) = {d , e} ;

I Eps(Da) = faux.

Rien a completer par erreur.

S

a S → AB

b S → AB

d S → Da

e S → Da

# S → AB


91/119





Exemple

A→ aAb :

I Premier(aAb) = {a} ;

I Eps(aAb) = faux.

A→ ε :

I Premier(ε) = ∅ ;

I Eps(ε) = vrai ;

I Suivant(A) = {b,#}.On complete par erreur.

A

a A→ aAb

b A→ ε

d erreur

e erreur

# A→ ε


92/119




Principes

Analyseur recursif






93/119




Analyseur LL(1)

Un analyseur LL(1) est deterministe et pilote par le sommet depile :

I si terminal a : lecture de a (ou erreur) ;

I si non terminal X avec a sous la tete de lecture : expansionselon Table[X , a].

Et si Table[X , a] contient plus d’une production ?

Non-determinisme :

I la grammaire n’est pas LL(1) ;

I on ne peut pas appliquer une analyse LL(1).


94/119





Caracterisation par table d’analyse : une grammaire est LL(1) sichaque case contient exactement une production ou erreur.

Caracterisation � par contre-exemple � : une grammaire n’est pasLL(1) s’il existe 2 productions X → α et X → β telles que :

1. soit Premier(α) ∩ Premier(β) 6= ∅ ;Ex : S → aS |A, A→ a

2. soit Eps(α) = vrai et Premier(β) ∩ Suivant(X ) 6= ∅ ;Ex : S → aS |Ab, A→ ε | b

3. soit Eps(α) = vrai et Eps(β) = vrai (la grammaire estambigue)Ex : S → A |B, A→ ε, B → ε


95/119




LL(1) et ambiguıte

Une grammaire LL(1) n’est pas ambigue.

Une grammaire ambigue n’est pas LL(1).


96/119




Cas classiques non LL(1)

Dans les cas suivants, la grammaire n’est pas LL(1) :

I ambiguıte ;I recursivite gauche : A→ Aa | ε ;

I intuitivement recursivite infinie de A().

I non factorisation gauche : S → aA | aB

Solutions : :

I factorisation a gauche (parfois) ;

I suppression de la recursivite gauche (parfois) ;

I utiliser un generateur de parser plus puissant !


97/119




Factorisation a gaucheSuppression de la recursivite a gauche

Principes

Analyseur recursif






98/119





Principes

Analyseur recursif






99/119





Factorisation a gauche : exemple - 1

Les listes d’identificateur de Init :

listeIdent → IDENT | IDENT SEPVAR listeIdent

On factorise IDENT et on obtient :

listeIdent → IDENT suiteListeIdentsuiteListeIdent → ε | SEPVAR listeIdent


100/119





Factorisation a gauche : exemple - 2

X → ab | abbX | abbbX

Factorisation de ab : on prend le plus grand prefixe commun.X → abYY → ε | bX | bbX

Puis a nouveau factorisation de b.


101/119





Factorisation a gauche - algorithme

On remplace les regles de la forme :

X → αβ1 | . . . |αβn | γ1 | . . . | γm

ou

I α ∈ (VT ∪ VN)+ et βi , γj ∈ (VT ∪ VN)∗ ;

I le prefixe commun α est choisi le plus grand possible ;

I α n’est pas prefixe de γj .

par les regles :

X → αX ′ | γ1 | . . . | γmX ′ → β1 | . . . |βn

ou X ′ est un nouveau non-terminal.On reitere ce processus tant que necessaire.


102/119





Principes

Analyseur recursif






103/119





Suppression de la recursivite a gauche

Recursivite gauche :

I immediate : production A→Aα, α ∈ (VT ∪ VN)+ ;

I generale : il existe une derivation A⇒∗Aα, α ∈ (VT ∪ VN)+.

Il est possible de supprimer les deux cas.

On ne verra que la recursivite immediate.


104/119





Suppression de la recursivite gauche immediate

On remplace les regles de la forme

X → Xα1 | . . . |Xαn |β1 | . . . |βm

ou

I αi ∈ (VT ∪ VN)+ et βj ∈ (VT ∪ VN)∗ ;

I les βj ne commencent pas par X .

par les regles :

X → β1X′ | . . . |βmX ′

X ′ → α1X′ | . . . |αnX

′ | ε

ou X ′ est un nouveau non-terminal.


105/119





Suppression de la recursivite gauche : exemple

Grammaire non ambiguedes expressions arithmetiques :

E → E + T |TT → T ∗ F |FF → i | (E )

X → Xα1 | . . . |Xαn

|β1 | . . . |βm

Apres suppression de la recgauche :

E → TE ′

E ′ → +TE ′ | εT → FT ′

T ′ → ∗FT ′ | εF → i | (E )

X → β1X′ | . . . |βmX ′

X ′ → α1X′ | . . . |αnX

′ | ε


106/119





Parfois ca ne suffit pas

La grammaire ({a, b}, {S ,A}, S ,P) avec

P = {S → aSb |A, A→ aA | ε}

I n’est pas ambigue ;

I n’est pas recursive gauche ;

I est factorisee a gauche ;

mais elle n’est pas LL(1).


107/119





Au dela des grammaires LL(1) - 1

La grammaire ({a, b}, {A,B},A,P) avec

P = {A→ abB | ε, B → Aaa | b}

n’est pas LL(1).

En effet Eps(A) = vrai et a ∈ Premier(A) ∩ Suivant(A).


108/119




Principes

Analyseur recursif






109/119




Grammaires LL(k), exemple

La grammaire :

declaration → DECLINT listeIdent FININSTRlisteIdent → IDENT | IDENT SEPVAR listeIdent

n’est pas LL(1).

Elle est LL(2), et acceptee par un analyseur LL(k).

En regardant 2 symboles sous la tete de lecture :

I si IDENT FININSTR : choisir listeIdent → IDENT

I si IDENT SEPVAR : choisir listeIdent → IDENT SEPVARlisteIdent


110/119




Grammaire LL(k), autre exemple

P = {A→ abB | ε, B → Aaa | b}

Cette grammaire est LL(2) :Premier2(A) = {ab}Premier2(B) = {ab, aa, b}Suivant2(A) = {aa,#}


111/119




Table d’analyse LL(2)

A→ abB | εB → Aaa | b

aa ab b #

A A→ ε A→ abB erreur A→ ε

B B → Aaa B → Aaa B → b erreur


112/119




Analyseurs LL(k), principe

Effectuent une prediction basee sur k symboles.

k borne.

Ex : javaCC


113/119




Insuffisance de l’approche LL(k), [antLR]

method → type ID [ args ] ;

| type ID [ args ] { body }args → unarg | unarg , argsunarg → INT ID

. . .

Cette grammaire n’est pas LL(k), mais est acceptee par antLR.


114/119




Analyseurs LL(*)

Ne fixent pas une taille de look-ahead a priori.

Representent par un AFD le langage de look-ahead, pourvu qu’ilsoit regulier.


115/119




Vers les formes eBNF

Meme un analyseur LL(*) refuse la recursivite gauche.

Facheux pour les grammaires a operateurs !

Solution : grammaires dites en forme eBNF.

E → T ( + T ) *T → F ( * T ) *F → ( E ) | id

E → E + T | TT → F * T | FF → ( E ) | id


116/119




Grammaires sous forme eBNF

Grammaires algebriques avec facilites d’ecriture.

En partie droite de production : operateurs a la expression reguliere

Refuse par Cup et tout generateur de parseur n’acceptant pas leseBNF

Accepte par la majorite des analyeurs LL(k).

Semble plus simple, attention a l’attribution.

Ne pas utiliser en DS sauf si explicitement demande.


117/119




Grammaires non LL(*) [antLR]

s : label ID ’=’ expr

| label ’return’ expr

;

label : ID ’:’ label

|

;

n’est pas LL(*) : [fatal] rule s has non-LL(*) decision

due to recursive rule invocations from alts 1,2.

[...]

Version LL(*) :

label : ( ID ’:’)*


118/119




Generation de code a la eBNF

E → T ( + T ) *

E() {

T();

tant que tetelect est ’+’ {

consommer(+);

T();

}

}

Cloture de Kleene ⇒ iteration dans le code


119/119




Generation de code a la eBNF

listeA → a*

listeA() {

tant que tetelect est ’a’ {

consommer(a);

}

}

plus efficace que le code recursif genere par :listeA → a listeA | ε


120/119




AntLR

Outil tres riche.

Decrit dans le meme formalisme eBNF les entites lexicales et lasyntaxe.

Lit toute l’entree avant de lancer l’analyse lexicale.


Documents

Analyse descendante LL(k) - FIL Lille 1nebut/portail/compilS5/fichiers/cours/anDesc/...Construction de la table d’analyse Caract erisation d’une grammaire LL(1) Quand une grammaire