compil7 AG.ppt [Mode de compatibilité]users.polytech.unice.fr/~pfz/COMPILATION/COURS/compil7... · 2015. 6. 3. · † Petit Précis de Yacc. J. Farré; Notes de TP ESSI-2 (1998)

- 1 -

03/06/2015

Compilation - Analyses lexicale, syntaxique et sémantique SI - 2 - Paul Franchi

- 2 -

03/06/2015


Références sur la compilation, l’analyse lexicale et syntaxique

• Compilateurs: Principes, techniques et outils, A. Aho, R. Sethi, J. Ullman; InterEditions (1991)• lex & yacc, JR Lewine, T. Mason, D. Brown; O’Reilly & Associates, Inc (1992)• A first course using ANSI C, LEX and YACC, J. P. Bennett,2nd edition, McGraw Hill (1996)• Modern Compilation Implementation, A. Appel; Cambridge University Press (1998)• Techniques de Compilation IIc: Introduction à Lex et Yacc. J. Farré; Notes de cours ESSI-2 (1998)• Petit Précis de Lex. J. Farré; Notes de TP ESSI-2 (1998)• Petit Précis de Yacc. J. Farré; Notes de TP ESSI-2 (1998)

Liens Web

• Cours de Compilation du MIT (format .ppt en Anglais)

lecture3: grammaires, arbres, langages, analyseurs

lecture4: construction SLR

lecture5: construction LR(1)

lecture6: construction LALR(1)

lecture7: sémantique statique.

•http://toutprogrammer.com/links.html?topic=Top%2FComputers%2FProgramming%2FCompilers

- 3 -

03/06/2015


Introduction

La phase de sémantique statique constitue le "cœur" du processus de compilation. C'est une phase dont la complexité dépend principalement de la sémantique choisie pour le langage source, mais qui peut aussi être influencée par la définition de la cible.

Ce chapitre est une introduction au problème de la sémantique statique. Il a pour but de montrer à partir d'exemples :

▼ comment on peut utiliser la syntaxe d'un langage pour définir formellement un traitement sémantique ▼ comment on peut calculer cette sémantique avec ou sans synchronisation avec l'analyse syntaxique.

Nous classons les techniques issues de cette démarche sous le nom de spécifications sémantiques exécutables.

Les applications traitées se situent dans deux domaines distincts:• la compilation et métacompilation des Langages de Programmation• la transformation des Documents avec XML, DOM et XSL

- 4 -

03/06/2015


Traductions dirigées par la syntaxe

On considère ici une large gamme des traitements effectués par un compilateur (ou un outil logiciel voisin) pendant la phase de sémantique statique: traductions, transformations, contrôles, etc..Il convient de distinguer la définition de ces traitements (spécification utilisée à l'écriture du compilateur) de leur réalisation (pendant l'exécution du compilateur)

Définitions dirigées par la syntaxe (SDTS):

• Un SDTS est un ensemble de règles {(r, Σ)}, composée chacune d'une règle de production syntaxique r et d'un ensemble de calculs sémantiques Σ.• Le traitement défini par un SDTS {(r, Σ)} consiste à associer à tout arbre de dérivation D (ou arbre abstrait) pour un mot de L(G), le résultat des calculs de Σ pour chaque r dans D • Suivant les cas (la manière dont Σ est décrit), Σ sera calculable:

▼ pendant l'analyse syntaxique:♠ une seule passe montante sur l'arbre D ♠ un seul parcours préfixe de D

▼ après l'analyse syntaxique:♠ plusieurs parcours montant ou descendant dans D

Evaluation sémantique: les traitements peuvent être

▼ synchronisés avec l'analyse syntaxique:● avantages: simplicité et performance● inconvénients: manque de puissance d'expression

▼ désynchronisés de l'analyse syntaxique:● avantages: meilleure puissance d'expression● inconvénients: complexité de mise en oeuvre et d'exécution

- ‹N°› -

03/06/2015

- 5 -

03/06/2015


Arbre de Syntaxe Abstraite• La syntaxe abstraite (SA) d'un langage de programmation permet de définir les constructions sémantiques du langage en faisant abstraction des détails lexicaux ou syntaxiques.• L'intérêt de la syntaxe abstraite est triple:

▼ débarrasser la définition du processus sémantique des détails syntaxiques▼ dissocier l'évaluation sémantique de l'analyse syntaxique▼ donner aux programmes une structure inductive en correspondance naturelle avec les constructions sémantiques

• La SA d'un LP est définie formellement par un ensemble d'arbres abstraits, dont les nœuds appartiennent à une algèbre typée.

Définition d'une Syntaxe Abstraite

On peut définir une SA par

• un ensemble fini S de Sortes (Phyla)• un ensemble fini O d'Opérateurs (Constructeurs) typés par S :

▼ les arbres abstraits sont définis comme l'algèbre des termes bien typés pour O et S

Des références:

• Projets Mentor, puis Centaur, puis SmartTools (INRIA)

• Diana, SA du langage Ada

• DTD (Document Type Définition) et XSD (Xml schémas)

• Langage "Pivot" et Métamodèle

- 6 -

03/06/2015


Syntaxe Abstraite de Java

On peut définir une SA (non unique) pour Java, par

S = {INST, OP, NOM, DECL, ..}O = {exp, exp, aff, if, ifelse, while, switch, class, ..}

les arbres abstraits Java sont définis comme l'algèbre des termes bien typés pour O et S

Syntaxe Abstraite & XML / XSD / XSL

On peut définir et implémenter des syntaxes abstraites en

utilisant:

• un dialecte XML pour structurer un LP

• une DTD ou un schéma XSD comme une définition formelle pour la SA choisie

• le DOM (ou Sax) comme une API d'implémentation des arbres

• XSLT pour programmer des traitements sur cette SA, notamment les décompilation

- 7 -

03/06/2015


Arbre de Syntaxe Abstraite• La syntaxe abstraite (SA) d'un langage de programmation permet de définir les constructions sémantiques du langage en faisant abstraction des détails lexicaux ou syntaxiques.• L'intérêt de la syntaxe abstraite est triple:

▼ débarrasser la définition du processus sémantique des détails syntaxiques▼ dissocier l'évaluation sémantique de l'analyse syntaxique▼ donner aux programmes une structure inductive en correspondance naturelle avec les constructions sémantiques

• La SA d'un LP est définie formellement par un ensemble d'arbres abstraits, dont les nœuds appartiennent à une algèbre typée.

Grammaires attribuées (GA)Les grammaires attribuées sont une des premières méthodes proposées pour définir la sémantique statique d'un langage à partir de sa syntaxe en "attribuant"sa grammaire[Knuth, 1968].Le formalisme des GAs est une extension des SDTS (ou de spécifications sémantiques exécutables): il permet, suivant la nature du calcul des attributs, de faire ce calcul en le synchronisant avec l'analyse syntaxique ou pas.

- 8 -

03/06/2015


Grammaires attribuées (GA)Les grammaires attribuées sont une des premières méthodes proposées pour définir la sémantique statique d'un langage à partir de sa syntaxe en "attribuant "sa grammaire [Knuth, 1968].

Le formalisme des GAs est une extension du cas classique de SDTS (ou de spécifications sémantiques exécutables): il permet, suivant la nature du calcul des attributs, de faire ce calcul en le synchronisant avec l'analyse syntaxique ou pas.

- 9 -

03/06/2015


Deux références Universitaires (parmi d'autres):

• FNC2 pour les GA-FNC, INRIA, France

• Synthesizer Generator pour les GA-FNC et Incrémentales,

Cornell University, USA

- 10 -

03/06/2015


Exemple originel de Knuth (attributs purement synthétisés)▼ la syntaxe supporte des nombre binaires avec point décimal▼ la sémantique associée est la valeur décimale▼ le calcul se fait en utilisant deux attributs dits "synthétisés":

● la valeur résultat associée à une liste binaire● la hauteur de la liste binaire qui donne le rang dans la base 2

▼ l'évaluation se fait en une seule montée dans l'arbre de dérivation (ou arbre abstrait, car les terminaux n'interviennent pas ici)

Propriétés▼ On utilise ici le schéma de Hörner et la valeur calculée "localement" pour un élément binaire ne correspond pas à la sémantique finale. ▼ Le calcul peut être synchronisé avec une analyse syntaxique ascendante (sous YACC, par ex.). Ce résultat est vrai pour toute GA purement synthétisée.

Syntaxe Sémantique

N ::= L1 . L2 N.v := L1.v + L2.v / 2^ L2.hN ::= L N.v := L.v

L ::= L’ B L.v := 2*L'.v + B.v ; L.h :=L'.h + 1L ::= B L.v := B.v ; L.h := 1

B ::= 1 B.v := 1B ::= 0 B.v := 0

- 11 -

03/06/2015


Exemple originel de Knuth (attributs synthétisés et hérités)▼ la syntaxe supporte des nombre binaires avec point décimal▼ la sémantique associée est la valeur décimale▼ le calcul se fait en trois passes dans l'arbre de dérivation :

● une passe montante pour calculer les hauteurs de listes (attribut synthétisé h)● une passe descendante pour calculer les rangs dans la base 2 (attribut hérité r)● une passe montante pour calculer les valeurs décimales (attribut synthétisé v)

Propriétés▼ La valeur calculée "localement" est exacte: le calcul peut donc se faire inductivement sur la structure de l'arbre.▼ Le calcul ne peut pas être synchronisé avec une analyse syntaxique ascendante. Il doit être soit programmé à la main (sous YACC, par ex.). soit généré à l'aide d'un évaluateur d'attributs

Syntaxe Sémantique

N ::= L1 . L2 N.v := L1.v + L2.v L1.r := 1 ; L2.r:= - L2.h

N ::= L N.v := L.vL ::= L’ B L.v := L'.v + B.v ; L.h :=L'.h +1 ;

B.r := L.rB.r := L.r ; L’.r :=L.r+1

L ::= B L.v := B.v ; L.h := 1 ; B.r := L.rB ::= 1 B.v := 2^B.rB ::= 0 B.v := 0

- 12 -

03/06/2015


Définition des GAs

Une grammaire d'attributs est une paire (G, Σ) où:▼ G est une grammaire algébrique : ▼ Σ : < As, Ah, Γ, D > où:▼ D est le domaine des calculs (ou types)▼ As est l'ensemble des attributs synthétisés définis comme des fonctions N → D▼ Ah est l'ensemble des attributs hérités définis comme des fonctions N → D▼ Γ est un ensemble de règles (ou équations ) de définition des attributs, avec deux formes associées à une règle de P notée

X → Y1 .. Yl ..Ym ..Yn● X.si = F(Yl.sj, X.hk) (définition d'un synthétisé de X) ● Ym.hi = G(Yl.sj, X.hk) (définition d'un hérité de Ym)● F et G étant des fonctions de calcul dans D

Evaluation d'un système d'attributsLe processus consiste à attribuer ("décorer") chaque nœud n ∈ N dans l'arbre d par une occurrence (instance) pour chaque attribut défini pour n.Le système d'attributs noté Σ(d) est le système d'équations générés par une GA (G, Σ) pour un arbre de dérivation d ∈ L(G) avec les occurrences d'attributs comme inconnues.L'évaluation d'un SA consiste à résoudre le systèmes d'équation pour obtenir une valeur (unique ?) pour toute occurence d'attributs dans D

- 13 -

03/06/2015


Propriétés des GasThéorème: Il existe un algorithme (test de circularité, Knuth 1968)pour décider si une GA a une solution unique pour tout système d'attributs Σ(d) associé à un mot d ∈ L(G). Ce test définit la classe des GA Non Circulaires (NC) ♦

Définition: Une GA est gauche-droite (L-AG) si pour toute les équations d'attributs hérités, les dépendances de calcul entre attributs peuvent être effectuées en parcourant les non terminaux de gauche à droite ♦

Théorème:Toute GA purement synthétisée (S-AG) est évaluable en une seule passe montante, et donc peut être synchronisée avec une analyse ascendante LR(). ♦

Théorème:Toute L-AG est évaluable en une seule passe préfixe(dfs), et donc peut être synchronisée avec une analyse descendante LL(). ♦

Théorème: Une GA NC est évaluable en un nombre fini de passes, et ne peut pas être, à priori, synchronisée avec une analyse descendante LL() ou LR(). ♦

Evaluation incrémentale des GasDéfinition: Une évaluation incrémentale consiste à réévaluer partiellement la solution d'un système d'attributs Σ(d) associé à un mot d ∈ L(G) après une modification de d. Cette réévaluation est optimale si la partie réévaluée ne comporte que des occurrences d'attributs ayant effectivement changé de valeurs. ♦

Théorème: Une large sous classe des GA NC supporte une évaluation incrémentale optimale. ♦

- 14 -

03/06/2015


Evaluation par un Visiteur Gauche-droite en profondeur

d'abord (Depth first , Left to Right)

Input: un arbre de dérivation (ou abstrait) attribué.

Conséquences:

• Evaluation des attributs après l'analyse syntaxique

• La structure attribuée doit être disponible intégralement

• Peut conduire à une évaluation multipasse

Visiteur:

eval (T: ArbreAttribué) {

while ( T.A().nonEvalué()) {

visit (T.racine());

}

}

visit(N: Nœud) {

if (! N.terminal()){

for (X in N.fils() && ! X. terminal()){

X.Ah().evalSiPossible() ;

visit(X) ;

}

N.As().evalSiPossible() ; // toujours possible si N.terminal()

}

- 15 -

03/06/2015


Evaluation par un Visiteur (version optimisée)

eval (T: ArbreAttribué) {

while ( T.A().nonEvalué()) {

visit (T.racine());

}

}

visit(N: Nœud) {

N.A().evalSiPossible() ;

if (! N.terminal()) {

do {

for (X in N.fils()) X.A().evalSiPossible() ;

if (X in N.fils()&& X.newA() ) visit(X) ;

else return ;

} while (true)

}

}

- 16 -

03/06/2015


Evaluation pendant l'analyse syntaxique

Input: le fragment d'arbre de dérivation (ou abstrait) en cours de reconnaissance syntaxique LL() ou LR()

Conséquences:

• Evaluation des attributs pendant l'analyse syntaxique

• La structure attribuée est partielle: des attributs peuvent

être "libérés"

• Limite à une évaluation "synchrone" L-AG ou S-AG

S_AG: GA purement synthétisée.

• Evaluation LR() ,

• compatible Yacc

L_AG: GA gauche-droite.

• Evaluation LL()

• utilisable avec Yacc, avec des restrictions sur les

attributs hérités(grammaires dites "Left Corner"), en

consultant les attributs stockés dans la pile d'analyse.

- 17 -

03/06/2015


Schéma synthétisé pour la production de code

/*version Yacc/C */%union { char code[MAX] ;}%type inst_list inst %%inst_list : inst_list inst

{ sprintf($$,¨%s %s¨, $1, $2) ; }| /* vide */

{ sprintf($$,¨%s¨, "") ; };

/* version Bison/C++ */% { #include #include using namespace std;%}% union { string* code; }%type inst_list inst %%inst_list : inst_list inst

{ ostringstream os; os

- 18 -

03/06/2015


Schéma dfs pour la "collecte" des déclarations/* version Yacc/Bison/C++ */

/*Assert: $0 (sous-sommet de la pile Yacc) est une ref à l'Env courant */

%union { EnvDecl* env ; }%type decl_list decl %%bloc : '{' decl_list inst_list '}'

{ /* $0 est le contexte courant (Env) de ce blocinst_list doit être compilé avec un Env $0 modifié par decl_list */

$$ = $0 ; /* rétablir Env initial en sortie de bloc */};

decl_list : decl_list decl{ $$ = addEnv(addEnv($-1, $1), $2) ; /* ici le contexte courant est sous $0 attribut de '{' */ }| /* vide */{ $$ = $-1 ; /* idem ci-dessus */};

inst_list : inst_list inst{ /* se compile avec l'Env $0: attr de decl_list */ }| ……;

- 19 -

03/06/2015


Schéma synthétisé pour la production de code version Yacc/C%union { char out[MAX] ;}%type while exp inst %%while : '(' exp ')' inst

{sprintf($$,¨ %s %s¨, $2, $4);};

version Bison/C++%{#include #include using namespace std;%}%union { string* out;}%type while exp inst %%while : '(' exp ')' inst

{ ostringstream os; os

- 20 -

03/06/2015


Emboîtements hiérarchisés pour du graphique

▼ la syntaxe(abstraite) supporte des construction h() ou v() pour un système horizontal ou vertical de boites rectangulaires▼ la sémantique associée est le calcul des attributs de visualisation des boites▼ le calcul se fait en trois passes dans l'arbre :

● une passe descendante pour transmettre le mode de placement de chaque boite (attribut hérité p)● une passe montante pour calculer suivant p, les hauteurs et largeurs des boites selon une règle de "bon emboîtement" (attribut synthétisé h et l)● une passe descendante pour calculer les coordonnées du coin supérieur gauche de chaque boite (attributs hérités x et y )

Syntaxe Sémantique

V ::= B B.x := x0; B.y := y0;B ::= h ( L ) B.h := L.h ; B.l := L.l ; L.p :=H

L.x := B.x; L.y := B.y;

B ::= v ( L ) B.h := L.h ; B.l := L.l ; L.p :=VL.x := B.x; L.y := B.y;

L ::= L’ B L.p :=L'.p ;L.p = H => {L.h := Max(L'.h ,B.h) ; L.l := L'.l + B.l ;

B.x := L.x + L'.l ; B.y := L.y }L.p = V => {L.v := Max(L'.v ,B.v) ; L.h:= L'.h + B.h ;

B.y := L.y + L'.l ; B.x := L.x }L ::= B L.l := B.l ; L.h:= B.h ;

B.y := L.y ; B.x := L.x

B ::= texte B.h := ht(texte); B.l:=lg(texte);

- 21 -

03/06/2015


Schéma synthétisé pour la production de code

version Yacc/C%union { char code[MAX] ;}%type inst_list inst %%inst_list : inst_list inst

{ sprintf($$,¨%s %s¨, $1, $2) ; }| /* vide */

{ sprintf($$,¨%s¨, "") ; };

version Bison/C++%{ ostreamstring os; %}%union { string* code;}%type inst_list inst %%inst_list : inst_list inst

{os