51
Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) www.zegour.uuuq.com email: [email protected]

Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI) email: [email protected][email protected]

Embed Size (px)

Citation preview

Page 1: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Analyse syntaxique

Pr ZEGOUR DJAMEL EDDINE

Ecole Supérieure d’Informatique (ESI)

www.zegour.uuuq.com

email: [email protected]

Page 2: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Analyse syntaxiqueGrammaires contexte-libre et Automates à pile(PDA)

Analyse descendante récursive

Propriétés LL(1)

Traitement des erreurs

Page 3: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Grammaires à contexte libre

Problème

Les grammaires régulières ne traitent pas la récursion centrale

E = x | "(" E ")".

On utilise alors les grammaires à contexte libre

DéfinitionUne grammaire est dite à contexte libre (CFG) si toutes ses productions ont la forme:

A = . A est un NTS, séquence non vide de TS et NTS

En EBNF le coté droit peut aussi contenir les meta-symboles |, (), [] and {}

Exemple

Expr = Term { ( "+" | "-" ) Term }.Term = Factor { ( "*" | "/" ) Factor }.Factor = id | "(" Expr ")". Récursion centrale indirecte

Les grammaires à contexte libre peuvent être reconnues par les automates à pile (PDA)

Page 4: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Automates à pile :Push-Down Automaton(PDA)

Caractéristiques• Permet les transitions avec des symboles terminaux et des symboles non terminaux• Utilise une pile pour sauvegarder les états visités

Exemple

E = x | "(" E ")".

x

E reconnurevenir 1 arccontinuer à partir de là avec EE/1

( E )E/3

E

stop

État lecture

État réduire

E/1

( E )E/3

Appel récursifde l‘automate E

x

E/1

( E )

x

...

Page 5: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Automates à pile (suite)x

E/1

( E )E/3

E

stop E/1

( E )E/3

x

...

Peut être simplifié comme suit

xE/1

( E )E/3

E

stop

x

(

Utilise une pile pour trouver le cheminde retour des états visités

Page 6: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Comment fonctionne un PDA?

xE/1

( E )E/3

E

stop

x

(

Les états visités sont rangés dans une pile

0 . ( ( x ) )0 2 . ( x ) )

0 2 2 . x ) )0 2 2 1 . ) )

0 2 2 . E ) )0 2 2 3 . ) )

0 2 2 3 4 . )0 2 . E )

0 2 3 . )0 2 3 4 .

0 . E

Exemple: ((x))

Pile Reste à analyser

0 1

2 3 4

0 2( x

E/112(

3E )

E/34

)E/343

E

stop

E

Page 7: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Grammaires régulières et Grammaires à contexte libre

Grammaires régulières Grammaires à contexte libre

Utilisées pour Lexique Syntaxe

Reconnues par DFA (sans pile) PDA (avec pile)

DFA(état)

Entrée

DFA(état)

Entrée

pile

Productions A = a | b C. A = .

Page 8: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Analyse syntaxiqueGrammaires contexte-libre et Automates à pile(PDA

Analyse descendante récursive

Propriétés LL(1)

Traitement des erreurs

Page 9: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Analyse descendante récursive• Technique d‘analyse Top-down (de haut en bas)• L‘arbre syntaxique est construit du symbole initial(axiome) vers la phrase (top-down)

Exemple grammaire Entrée

A = a A c | b b. a b b c

a b

b

b

b

Aa

c

c

ASymbole de départ

Entrée a b b c

A

?Quelle est

L‘alternativequi convient?

a b b

Aa

c

c

A

?

La bonne alternative est sélectionnée utilisant ...

• L‘unité lexicale courante de l‘entrée• Les premiers symboles terminaux des alternatives d‘une production

Page 10: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Variables statiques de l‘analyseur syntaxique

Unité lexicale courante

static int la; // code de l‘unité lexicale courante

A tout moment l‘analyseur connaît la prochaine unité lexicale

Il utilise deux variables pour les unités lexicales (pour la phase sémantique)

static Token token; // unité déjà reconnuestatic Token laToken; // unité courante non encore reconnue

Ces variables sont mises à jour dans la méthode Scan()

static void Scan () {token = laToken;laToken = Scanner.Next();la = laToken.kind;

}

Entrée

Déjà reconnues

Scan() est appelée au début de l‘analyse. La première unité est dans la

ident assign ident plus ident

token laToken

la

Page 11: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Comment analyser les symboles terminaux?

Modèle

Symbole à analyser: aAction de l‘analyseur: Check(a);

On a besoin des méthodes suivantes

static void Check (int expected) {if (la == expected) Scan(); // recognized => read aheadelse Error( );

}

public static void Error (string msg) {Console.WriteLine("– line {0}, col {1}: {2}", laToken.line, laToken.col,

msg);throw new Exception("Panic Mode");

}

Les noms des symboles terminaux sont déclarés comme des constantes dans la classe Token

public const int NONE = 0,IDENT = 1, NUMBER = 2, ...,PLUS = 4, MINUS = 5, ... ;

public static string[] names = {"?", "identifier", "number", ..., "+", "-", ...}; Ordonné parcode

Token.names[expected] + " expected"

Dans la class Token:

Page 12: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Comment analyser les symboles non terminaux?

Modèle

Symbole à analyser : AAction de l‘analyseur : A(); // Appel à la méthode d‘analyse de A

Chaque symbole non terminal est reconnu par une méthode avec le même nom

private static void A() {... parsing actions for the right-hand side of A ...

}

Initialisation de l‘analyseur

public static void Parse () {Scan(); // initialise token, laToken et laProgram(); // appelle la méthode d’analyse de l’axiomeCheck(Token.EOF); // à la fin, l’entrée doit être vide

}

Page 13: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Comment analyser les séquences?

Modèle

production: A = a B c.

Méthode de l‘analyseur: static void A () {// la contains a terminal start symbol of ACheck(a);B();Check(c);// la contains a follower of A

}

b b c

b b c

b c

c

c

Simulation

A = a B c.B = b b.

static void A () {

Check(a);

B();

Check(c);

}

static void B() {

Check(b);

Check(b);

}

a b b c

Entrée restante

Page 14: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Comment analyser les alternatives

Modèle | | , , sont des expressions EBNF

Action de l‘analyseur if (la in First()) { ... parse ... }else if (la in First()) { ... parse ... }else if (la in First()) { ... parse ... }else Error("..."); // find a meaninful error message

Exemple

A = a B | B b.B = c | d.

First(aB) = {a}First(Bb) = First(B) = {c, d}

static void A () {if (la == a) {

Check(a);B();

} else if (la == c || la == d) {B();Check(b);

} else Error ("invalid start of A");}

static void B () {if (la == c) Check(c);else if (la == d) Check(d);else Error ("invalid start of B");

}

exemples: analyser a d et c banalyser b b

Page 15: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Comment analyser les Options EBNF

Modèle [ ] est une expression EBNF

Action de l‘analyseur if (la in First()) { ... parse ... } // no error branch!

Exemple

A = [ a b ] c.

static void A () {if (la == a) {

Check(a);Check(b);

}Check(c);

}

Exemple: analyser a b c analyser c

Page 16: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Comment analyser les itérations EBNF

Modèle { } est une expression EBNF

Action de l‘analyseur while (la in First()) { ... parse ... }

Exemple

A = a { B } b.B = c | d.

static void A () {Check(a);while (la == c || la == d) B();Check(b);

}

Exemple: analyser a c d c b analyser a b

static void A () {Check(a);while (la != b && la != Token.EOF) B();check(b);

}

Ou bien ...

Sans EOF: danger d‘une boucle infinie,si b n‘existe pas dans l‘entrée

Page 17: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Cas des ensembles ‘First’ grands

Si l‘ensemble First a plus de 4 : utiliser la classe BitArray

Exemple: First(A) = {a, b, c, d, e}First(B) = {f, g, h, i, j}

Les ensembles First sont initialisés au début du programme

using System.Collections;

static BitArray firstA = new BitArray(Token.names.Length);firstA[a] = true; firstA[b] = true; firstA[c] = true; firstA[d] = true; firstA[e] = true;

static BitArray firstB = new BitArray(Token.names.Length);firstB[f] = true; firstB[g] = true; firstB[h] = true; firstB[i] = true; firstB[j] = true;

Exemple

static void C () {if (firstA[la]) A();else if (firstB[la]) B();else Error("invalid C");

}

C = A | B.

Page 18: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Cas des ensembles ‘First’ grands

Si l‘ensemble a moins de 4 éléments: utiliser des vérifications explicites (plus rapide)

Exemple : First(A) = {a, b, c}

if (la == a || la == b || la == c) ...

Si l‘ensemble est un intervalle: utiliser un test d‘intervalle

if (a <= la && la <= c) ...

Les codes des unités lexicales sont souvent choisis de telle sorte qu‘ils forment des intervalles

Exemple

First(A) = { a, c, d }First(B) = { a, d }First(C) = { b, e }

const inta = 0,d = 1,c = 2,b = 3,e = 4,

First(A)First(B)

First(C)

Page 19: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

OptimisationsÉviter les multiples vérifications

A = a | b.

static void A () {if (la == a) Scan(); // no Check(a);else if (la == b) Scan();else Error("invalid A");

}

A = { a | B d }.B = b | c.

static void A () {while (la == a || la == b || la == c) {

if (la == a) Scan();else { // no check any more

B(); Check(d);} // no error case

}}

Schéma plus efficace pour analyser les alternatives dans une itération

static void A () {for (;;) {

if (la == a) Scan();else if (la == b || la == c) { B(); Check(d); }else break;

}}

A = { a | B d }.

Page 20: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Optimisations

Modèle d’une itération fréquente

{ separator } ident { "," ident }

Exemple

for (;;) {... parse ...if (la == separator) Scan(); else break;

}

for (;;) {Check(ident);if (la == Token.COMMA) Scan(); else break;

}

Exemple d‘entrée: a , b , c :

Page 21: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Déterminer correctement les ensembles ‘First’

Grammaire

A = B a.B = { b } c

| [ d ]| e.

Méthodes d‘analyse

static void A () {B(); Check(a);

}

static void B () {if (la == b || la == c) {

while (la == b) Scan();Check(c);

} else if (la == d || la == a) {if (la == d) Scan();

} else if (la == e) {Scan();

} else Error("invalid B");}

b et c

d et a (!)

e

FirstC = D e

| f.D = { d }.

d et e (D est ‘annulable’!)

f

static void C () {if (la == d || la == e) {

D(); Check(e);} else if (la == f) {

Scan();} else Error("invalid C");

}

static void D () {while (la == d) Scan();

}

Page 22: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Descente récursive et arbre syntaxique

L‘arbre syntaxique est construit implicitement• Représente les méthodes actives à un moment donné• Représente les productions utilisées

Exemple A = a B c.B = d e.

call A()static void A () {

Check(a); B(); Check(c);} a B c

A

A en exécution

reconnaît acall B()static void B () {

Check(d); Check(e);}

a B c

A

d e

A en exécutionB en exécution

reconnaît d et eRetour de B() a B c

AA en exécution

" pile"

Page 23: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Analyse syntaxiqueGrammaires contexte-libre et Automates à pile(PDA

Analyse descendante récursive

Propriétés LL(1)

Traitement des erreurs

Page 24: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Propriétés LL(1)

Pré condition pour l‘analyse descendante récursive

LL(1) ... peut être analysé de gauche ( Left) à droiteavec des dérivations canoniques gauche (Left) ( le NTS le plus à gauche est dérivé en

premier )et utilise une seule unité lexicale (1) de l‘entrée

Définition

1. Une grammaire est LL(1) si toutes ses productions sont LL(1).

2. Une production A est LL(1) si pour toutes ses alternatives1 | 2 | ... | n

la condition suivante est vérifiée:First(i) Intersection First(j) = {} ( pour tout i et j)

[ Au plus un k peut être vide. Et dans ce cas First(i) Intersection Follow() = {} ( pour tout i #k)]

En d‘autres termes

• Les symboles terminaux de début de toutes les alternatives d‘une production doivent être disjoints deux à deux.

• L‘analyseur doit être capable de choisir l‘une des alternatives par la consultation de lal‘unité lexicale courante.

Page 25: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Comment éliminer les conflits LL(1) ?Factorisation

IfStatement = "if" "(" Expr ")" Statement| "if" "(" Expr ")" Statement "else" Statement.

Extraire la séquence commune de débutIfStatement = "if" "(" Expr ")" Statement (

| "else" Statement).

... Ou en EBNFIfStatement = "if" "(" Expr ")" Statement [ "else" Statement ].

Quelquefois les non terminaux doivent être remplacés avant factorisation

Statement = Designator "=" Expr ";"| ident "(" [ ActualParameters ] ")" ";".

Designator = ident { "." ident }.

Remplacer Designator dans StatementStatement = ident { "." ident } "=" Expr ";"

| ident "(" [ ActualParameters ] ")" ";".

ensuite factoriserStatement = ident ( { "." ident } "=" Expr ";"

| "(" [ ActualParameters ] ")" ";").

Page 26: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Comment éliminer la Récursion gauche

La récursion à gauche est toujours un conflit LL(1)

IdentList = ident | IdentList "," ident.

Par exemple

génère les phrases suivantes

identident "," identident "," ident "," ident...

Peut toujours être remplacée par une itération

IdentList = ident { "," ident }.

Page 27: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Conflits LL(1) cachés

Les itérations et les options EBNF sont des alternatives cachées

A = [ ]. First() Inter Follow(A) doit être {}A = { }. First() Inter Follow(A) doit être {}

A = | . First() Inter Follow(A) doit être {}

A = [ ] . Idem A = | . et sont des expressions EBNF

A = [ ] . First() Inter First() doit être {}A = { } . First() Inter First() doit être {}

Règles

Page 28: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Éliminer les conflits LL(1) cachés

Name = [ ident "." ] ident.

Où est le conflit et comment l‘éliminer?

Name = ident [ "." ident ].

Cette nouvelle production est elle LL(1) ?

Nous devons vérifier si First("." ident) Intersection Follow(Name) = {}

Prog = Declarations ";" Statements.Declarations = D { ";" D }.

Où est le conflit et comment l‘éliminer?

Remplacer Declarations dans Prog

Prog = D { ";" D } ";" Statements.

First(";" D) Inter First(";" Statements) # {}

Prog = D ";" { D ";" } Statements.

Nous devons encore vérifier si First(D ";") Inter First(Statements) = {}

Page 29: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Problème des ‘Else’

L‘ instruction If en Java

Statement = "if" "(" Expr ")" Statement [ "else" Statement ]| ... .

C‘est un conflit LL(1) !

First("else" Statement) Inter Follow(Statement) = {"else"}

C‘est même une ambiguïté qui ne peut être éliminée

if (expr1) if (expr2) stat1; else stat2;

Statement

Statement

Statement

Statement

On peut construire 2 arbres syntaxiquesdifférents!

Page 30: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Problème des ‘Else’

if (expr1) if (expr2) stat1; else stat2;

Statement

Statement

Statement = "if" "(" Expr ")" Statement [ "else" Statement ]| ... .

Si la prochaine unité est "else" L‘analyseur prend comme option:le "else" est associé au dernier "if"

Solution

Page 31: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Autres exigences pour une grammaire(Pré conditions pour les analyseurs syntaxiques)

Complétude

Pour chaque NTS il doit y avoir une production

Non-circularité

Un NTS ne doit pas être dérivable (directement ou pas) en lui-même (A => B1 => B2 => ... => A)

A = a b | B .B = b b | A .

erreur!cette grammaire est circulaire car A => B => A

Dérivabilité

Chaque NTS doit être dérivable (directement ou indirectement) en une chaîne de TS

A = a B | c .B = b B .

erreur!B ne peut être dérivé en une chaîne de TS

A = a B C .B = b b .

erreur!pas de production pour C

Page 32: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Analyse syntaxiqueGrammaires contexte-libre et Automates à pile(PDA

Analyse descendante récursive

Propriétés LL(1)

Traitement des erreurs

Page 33: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Objectifs du traitement des erreurs syntaxiques

Exigences

1. Déterminer le maximum d‘erreurs en une seule compilation

2. Pas de bug (quelque soit l‘erreur)

3. Ne pas ralentir l‘exécution en traitant les erreurs

4. Ne pas gonfler le code

Techniques pour l‘analyse descendante récursive

• Mode panique

• Utilisation des symboles de reprise (ancres)

• Utilisation des symboles spéciaux de reprise

Page 34: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Mode panique

L'analyseur abandonne après la première erreur

static void Error (string msg) {Console.WriteLine("-- line {0}, col {1}: {2}", laToken.line, laToken.col, msg);throw new Exception("Panic Mode - exiting after first error");

}

Avantages

• économique• suffisant pour les langages de commandes ou pour les interpréteurs

Inconvénients

• Non appropriée pour la production des compilateurs de qualité

Page 35: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Traitement des erreurs utilisant les ancres

Exemple

Entrée attendue: a b c d ...Entrée réelle: a x y d ...

Récupération(synchronise l‘entrée restante avec la grammaire)

1. Trouver l’ "unité de reprise " (ancre) avec laquelle l‘analyseur peut continuer après l‘erreur.

Quelles sont les unités avec lesquelles l‘analyseur peut continuer dans la situation donnée?c successeur de b (qui était attendu à la position de l‘erreur)d successeur de b c...Les unités de reprise (ancre) à cette position sont {c, d, ...}

2. Sauter les unités jusqu‘à ce que une unité de reprise soit trouvée .x et y sont sautées dans l‘exemple, mais d est un ancre; l‘analyseur peut continuer avec.

3. Conduire l'analyseur à la position dans la grammaire où il peut continuer. (remonter dans l‘arbre syntaxique)

Page 36: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Détermination des ancres

Chaque méthode d‘analyse d‘un non terminal A possède les successeurs courant de A comme paramètres

static void A (BitArray sux) {...

}

sux ... successeurs de tous les NTS, qui sonten exécution

a A b

B eof

... ...

b C d

B eof

e

a A f

... ...

Dépendant du contexte courant, suxA peut dénoter différents ensembles

suxA = {b, eof} suxA = {f, d, e, eof}

sux contient toujours eof (le successeur du symbole de départ)

Page 37: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Traitement des symboles terminaux

A = ... a s1 s2 ... sn . check(a, suxA Union First(s1) Union First(s2) ... Union First(sn));

Grammaire Action de l‘analyseur

Peut être déterminé au moment de la compilation

Doit être déterminé au moment de l‘exécution

static void Check (int expected, BitArray sux) {...}

Exemple

A = a b c. static void A (BitArray sux) {Check(a, Add(sux, fs1));Check(b, Add(sux, fs2));Check(c, sux);

}

static BitArray Add (BitArray a, BitArray b) {BitArray c = (BitArray) a.Clone();c.Or(b); return c;

}

static BitArray fs1 = new BitArray();fs1[b] = true; fs1[c] = true;

Rempli au début du programme

si : TS ou NTS

Page 38: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Traitement des symboles non terminaux

A = ... B s1 s2 ... sn . B(suxA Union First(s1) Union First(s2) ... Union First(sn));

Grammaire Action de l‘analyseur

Exemple

A = a B c.B = b b.

static void A (BitArray sux) {Check(a, Add(sux, fs3));B(Add(sux, fs4));Check(c, sux);

}

static void B (BitArray sux) {Check(b, Add(sux, fs5));Check(b, sux);

}

fs3 = {b, c}fs4 = {c}

fs5 = {b}

La méthode d‘analyse pour l‘axiome S est appelée S(fs0); où fs0 = {eof}

Page 39: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Sauter les unités invalides

Les erreurs sont détectées dans check()

static void Check (int expected, BitArray sux) {if (la == expected) Scan();else Error(Token.names[expected] + " expected", sux);

}

Après l‘affichage du message les unités sont sautées jusqu‘à la rencontred‘une unité de reprise

static void Error (string msg, BitArray sux) {Console.WriteLine("-- line {0}, col {1}: {2}", laToken.line, laToken.col,

msg);errors++;while (!sux[la]) Scan(); // while (la # sux) Scan();

}

static int errors = 0; // number of syntax errors detected

Page 40: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Synchronisation avec la grammaire

Exemple

A = a B e.B = b c d.

static void A (BitArray sux) {Check(a, Add(sux, fs1));B(Add(sux, fs2));Check(e, sux);

}static void B (BitArray sux) {

Check(b, Add(sux, fs3));Check(c, Add(sux, fs4));Check(d, sux);

}

L‘erreur est détecté ici; ancres = {d, e, eof}

1. x est sauté; la == e ( dans ancres)2. L‘analyseur continue: Check(d, sux);3. Détecte de nouveau une erreur; ancres = {e, eof}4. aucune unité est sautée, car la == e (dans ancres)5. L‘analyseur retourne de B() et lance Check(e, sux);6. Recouvrement réussi!

b c d

Ba e

A eof

ba x e eofEntrée

suxA = {eof}

suxB = {e, eof}

Une fois l‘erreur détectée l‘analyseur avance jusqu‘à trouver un endroit dans la grammaire qui concorde avec l‘unité courante.

Page 41: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Supprimer les faux messages d‘erreur

Durant le recouvrement de l‘erreur l‘analyseur produit des faux messages d‘erreur

Résolu par une simple heuristique

Si moins de 3 unités sont reconnues correctement depuis la dernière erreur, l'analyseur suppose que la nouvelle erreur est une fausse erreur. Les fausses erreurs ne sont pas affichées

static int errDist = 3; // next error should be reported

static void Scan () {...errDist++; // one more token recognized

}

public static void Error (string msg, BitArray sux) {if (errDist >= 3) {

Console.WriteLine("-- line {0}, col {1}: {2}", laToken.line, laToken.col, msg);errors++;

}while (!sux[la]) Scan();errDist = 0; // counting is restarted

}

Page 42: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Traitement des alternatives

A = | | . , , sont des expressions EBNF

static void A (BitArray sux) {// the error check is already done here so that the parser can synchronize with// the starts of the alternatives in case of an errorif (la not in (First() Or First() Or First()))

Error("invalid A", sux Or First() Or First() Or First());// la matches one of the alternatives or is a legal successor of Aif (la in First()) ... parse ...else if (la in First()) ... parse ...else ... parse ... // no error check here; any errors have already been reported

}

First() Or First() Or First() peut être déterminé au moment de la compilationsux Or ... est déterminé au moment de l‘exécution

Page 43: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Traitement des Options et Itérations EBNFOptions

A = [ ] .static void A (BitArray sux) {

// error check already done here, so that the parser can// synchronize with the start of in case of an errorif (la not in (First() Or First()))

Error("...", sux Or First() Or First());// la matches or or is a successor of Aif (la in First()) ... parse ...;... parse ...

}

Itérations

A = { } .static void A (BitArray sux) {

for (;;) {// the loop is entered even if la not in First()if (la in First()) ... parse ...; // correct case 1else if (la in First() Or sux) break; // correct case 2else Error("...", sux Or First(a) Or First(b)); // error case

}... parse ...

}

Page 44: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Exemple

A = a B | b {c d}.B = [b] d.

static void A (BitArray sux) {if (la != a && la != b)

Error("invalid A", Add(sux, fs1)); // fs1 = {a, b}if (la == a) {

Scan(); B(sux);} else if (la == b) {

Scan();for (;;) {

if (la == c) {Scan();Check(d, Add(sux, fs2)); // fs2 = {c}

} else if (sux[la]) {break;

} else {Error("c expected", Add(sux, fs2));

}}

}}

static void B (BitArray sux) {if (la != b && la != d)

Error("invalid B", Add(sux, fs3)); // fs3 = {b, d}if (la == b) Scan();Check(d, sux);

}

Page 45: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

En résumé

Avantage

+ applicable automatiquement

Inconvénients

- Ralentit l‘analyse- gonfle le code de l‘analyseur- complexe

Traitement des erreurs avec des symboles de reprises (ancres)

Page 46: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Traitement des erreurs avec des ancres spéciaux

Le traitement est seulement fait à des positions particulières

Les mot-clés apparaissent à des positions uniques dans la grammaire

Exemple• Début d‘instruction: if, while, do, ...• Début de déclaration: public, static, void, ...

Problème: ident peut figurer à plusieurs endroits!ident n‘est pas un ancre sûr. Il est donc omis de l‘ensemble des ancres

Ensemble d‘ancres

• Pas besoin de passer les ensembles successeur aux méthodes de l‘analyseur• Les ensembles d‘ancres sont connus avant l‘exécution• Après une erreur l‘analyseur ignore des unités jusqu‘au prochain point de synchronisation

Code à insérer aux points de synchronisation

...if (la not in expectedSymbols) {

Error("..."); // no successor sets; no skipping of tokens in Error()while (la not in (expectedSymbols Or {eof})) Scan();

}...

L‘ensemble des ancres à ce point de synchronisation

Pour éviter la boucle infinie

Page 47: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

ExempleSynchronisation au début d‘une instruction

static void Statement () {if (!firstStat[la]) {

Error("invalid start of statement");while (!firstStat[la] && la != Token.EOF) Scan();errDist = 0;

}if (la == Token.IF) { Scan();

Check(Token.LPAR); Conditions(); Check(Token.RPAR);Statement();if (la == Token.ELSE) { Scan(); Statement(); }

} else if (la == Token.WHILE) {...

}

static BitArray firstStat = new BitArray();firstStat[Token.WHILE] = true;firstStat[Token.IF] = true;...

le reste de l‘analyseurreste inchangé(comme s‘il n‘ y a pasde traitement d‘erreur)

Pas de synchronisation dans Error()

public static void Error (string msg) {if (errDist >= 3) {

Console.WriteLine("-- line {0}, col {1}: {2}", laToken.line, laToken.col, msg);errors++;

}errDist = 0;

}

heuristics with errDist can alsobe applied here

Page 48: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Exemple de recouvrementstatic void Statement () {

if (!firstStat[la]) {Error("invalid start of statement");while (!firstStat[la] && la != Token.EOF) Scan();errDist = 0;

}if (la == Token.IF) { Scan();

Check(Token.LPAR); Condition();Check(Token.RPAR);Statement();if (la == Token.ELSE) { Scan(); Statement(); }

...}

static void Check (int expected) {if (la == expected) Scan();else Error(...);

}

Entrée erronée: if a > b then max = a;

if Scan(); if dans firstStat , oka Check(LPAR); message d‘erreur: ‘(‘ attendue

Condition(); reconnaît a > bthen check(RPAR); message d‘erreur: ‘)’ attendue

Statement(); then ne correspond pas, donc erreur, mais pas de message d‘erreurthen est sauté; synchronisation avec ident (si dans firstStat)

max

la action

public static void Error (string msg) {if (errDist >= 3) {

Console.WriteLine(...);errors++;

}errDist = 0;

}

Page 49: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Synchronisation au début d‘une itération

Exemple

Block = "{" { Statement } "}".

Modèle standard dans ce cas

static void Block () {Check(Token.LBRACE);while (firstStat[la])

Statement();Check(Token.RBRACE);

}

Problème: si la prochaine unité ne correspond pas à une instruction la boucle n‘est pas exécutée.Le point de synchronisation dans Statement n‘est jamais atteint.

Page 50: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

Synchronisation au début d‘une itération

Exemple

Block = "{" { Statement } "}".

C‘est meilleur de synchroniser au début de l‘itération

static void Block() {Check(Token.LBRACE);for (;;) {

if (la in First(Statement)) Statement(); // correct case 1else if (la in {rbrace, eof}) break; // correct case 2else { // error case

Error("invalid start of Statement");do Scan(); while (la (First(Statement) union {rbrace, eof}));errDist = 0;

}}Check(Token.RBRACE);

}

Pas de synchronisation dans Statement()

static void Statement () {if (la == Token.IF) { Scan(); ...

}

Page 51: Analyse syntaxique Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure dInformatique (ESI)  email: d_zegour@esi.dzd_zegour@esi.dz

En résumé

Avantages

+ ne ralentit pas l‘exécution de l‘analyseur+ ne gonfle pas le code de l‘analyseur+ simple

Inconvénients

- demande plus d‘expérience

Traitement des erreurs avec des symboles de reprises spéciaux