Abstract Syntax Semantic Analysis Compilerconstructie les 4 Etymologie Situering Abstract Syntax Semantic actions Abstract Parse Trees Semantic Analysis Symbol Tables Bindings for the (Tiger) compiler Type-checking expressions Type-checking declarations Conclusie Etymologie Ab-stract: disassociated from any specific instance (x concrete) Se-man-tic: of or relating to meaning in language Tot nu toe... ● Herkennen ● Lex: herkennen van tokens ● Parser: herkennen van sentences Nu ook: ● semantiek ● semantic actions Semantic actions Een compiler moet iets nuttig doen met elke sentence. Dit kan met semantic actions van de parser. Remember… ● recursive-descent parser / LL(k) parsing ● andere, zoals Yacc / LR(k) parsing Semantic actions Elke terminal en nonterminal kan geassocieerd worden met zijn eigen soort semantische waarde. A -> B C D moet een waarde teruggeven waarvan het type geassocieerd is met de nonterminal A. Maar deze waarde kan gebouwd worden uit de waarden geassocieerd met de gematchede terminals en nonterminals B, C, D. Semantic actions: Recursive Descent semantic actions zijn: - de waarden teruggegeven door de parsing functies - de side effects van deze functies - beiden Elke terminal & nonterminal symbool is geassocieerd met een type (van de implementatietaal van de compiler) -van semantic values die zinnen tonen afgeleid van dit symbool vb vroeger void T(void) {switch (tok) { case ID: case NUM: case LPAREN: F(); Tprime(); break; default: }} Nu enum token tok; union tokenval tokval; int lookup(String id) { … } /*assumptie : lookup table*/ int T(void) {switch(tok) { case ID: … return Tprime(F()); … } int F(void) {switch (tok) { case ID: {int i=lookup(tokval.id); advance(); return i;} case NUM: {int i=tokval.num; advance(); return i;} case LPAREN: eat(LPAREN); {int i = E(); advance(); return i;} => semantic actions gemakkelijk om te implementeren in recursivedescent parser (sentences herkennen+ acties) Problemen kunnen voorkomen met hergeordende grammars Semantic actions: Yacc-gen. parsers Remember: stack, input, shift/reduce %{declarations of yylex and yyerror %} %left PLUS MINUS %left TIMES %left UMINUS exp : | | | | INT exp PLUS exp exp MINUS exp exp TIMES exp MINUS exp %prec UMINUS Nu ook: semantic actions Remember: stack, input, shift/reduce %{declarations of yylex and yyerror %} %union {int num; string id;} %token <num> INT %token <num> exp ... %left PLUS MINUS %left TIMES %left UMINUS exp : | | | | INT exp PLUS exp exp MINUS exp exp TIMES exp MINUS exp %prec UMINUS {$$ {$$ {$$ {$$ {$$ = = = = = $1;} $1 + $3;} $1 - $3;} $1 * $3;} - $2;} Semantische waarden geïmplementeerd door een stack te houden parallel aan de state stack (bord) Abstract parse trees Het is mogelijk om een hele compiler te schrijven dat in de semantic actions past van een Yacc parser. Zo’n compiler is moeilijk om te lezen en onderhouden… … en deze aanpak verplicht de compiler om het programma te analyseren in exact de volgorde waarin het geparsed is. => modulariteit verhogen Modulariteit verhogen: scheiding ● syntax (parsing) ● semantiek (type-checking & vertaling naar machine code) Een manier: de parser een parse tree laten produceren = een datastructuur dat in latere fases door de compiler bewandeld kan worden =1 blad/toke & 1 interne knoop/gebruikte grammar reductie regel Concrete vs abstract parse tree een parse tree is altijd bepaald door de overeenkomstige grammar ● concrete: onhandig ● ○ veel onnodige leestekens ○ structuur hangt nog te veel af van de grammar (grammar transformations) abstract: clean interface tussen parser en verder ○ zinstructuur van bronprogramma ○ alle parsing problemen opgelost, maar geen semantische interpretatie vb abstract syntax: S → S; S L → S → id := E L → L E S → print L E → id B → + E → num B → - E → E B E B → x E → S, E B → / Parser gebruikt de concrete syntax om een parse tree te bouwen voor de abstracte syntax de semantische analyse gebeurt dan op de abstract syntax tree => geen zorgen meer over ambiguïteit van de grammar ASTs moeten een manipuleerbare datastructuur zijn Positie One-pass compilers: lexicale analyse, parsing en semantische analyse in een pas, simultaan ● error? current position! Abstract syntax tree compiler: parsing en semantische analyse gescheiden ● gecompliceerder voor error berichten ● source-code positie van elke node moet onthouden worden in geval van error ○ ○ pos velden met semantische waare: positie position stack naast parsing stack en semantic value stack Semantische analyse Wat? ● verbinding van variable definities tot gebruik ● type-checking ● vertaling abstract syntax in simpelere voorstelling voor het genereren van machine code In deze fase: ● symbol tables (environments, cfr CPL) ○ ○ set van bindings: id -> type (~location) use: look up in symbol tables ● scope ○ bv: let D in E vb 1 function f(a:int, b:int, c:int) = 2 (print_int(a+c); 3 let var j := a+b 4 var a := “hello” 5 in print(a); print_int(j) 6 end; 7 print_int(b) 8 ) > f(1,2,3)? (uitleg op bord met sigma_0 sigma_1 = sigma_0 + {a->int, b->int,c->int} > lijn per lijn gaan >hoe moeten we die “+” interpreteren? >zeker op lijn 5! >teruggaan van sigma_k naar sigma_k-1 Implementatie 2 mogelijkheden: ● functionele stijl ○ bewaar elke symbol table ● imperatieve stijl ○ ○ ○ destructive update van de symbooltafels moet mogelijk zijn om te undo! undo stack Beide stijlen kunnen gebruikt worden, onafhankelijk of: ● gecompileerde taal ● taal waarin compiler geschreven ● functioneel/imperatief/object-georiënteerd Meerdere symbooltafels In sommige talen: meerdere actieve environments ● forward reference: waarde in andere environment Efficiënte imperatieve symbooltafels Heel efficiënt: hash tables with external chaining Efficiënte functionele symbooltafels Env_(k+1) = Env_k+ {a -> t} > we willen de Env_k bewaren! Efficiënte functionele symbooltafels Env_(k+1) = Env_k+ {a -> t} > we willen de Env_k bewaren! Probleem: Weinig efficiënt voor hash tables: de array zou vrij groot kunnen zijn, proportioneel aan aantal elementen > binary search tree > nieuwe waarden efficiënt toegevoegd Efficiënte functionele symbooltafels Env_(k+1) = Env_k+ {a -> t} > we willen de Env_k bewaren! Weinig efficiënt voor hash tables. > binary search trees > nieuwe waarden efficiënt toegevoegd > nieuwe node op diepte d: d nieuwe noden > nieuwe boom maken = element zoeken = log(n) tijd Tiger: Ipv te hashen tot een string (elke keer String met String vergelijken): hashen tot symbool in Tiger ● symbolen vergelijken is heel snel (pointer/integer vgl’en) ● integer hash-key berekenen is heel snel (voor bij hash tables) ● 2 symbolen vergelijken om “groter dan” symbool is heel snel (bv goed in binary search tree) Tiger: Imperative table: ● hash table ● auxiliary stack (undo) ○ beginScope & endScope Functional-style symbol table ook mogelijk ● geen beginScope en endScope nodig Bindings for the (TIGER) compiler Waarmee moet een symbol table/environment gevuld zijn? - wat is een binding? Tiger: twee name spaces: types & functions + variables Meeste talen hebben primitieve en composiete types. Elke type identifier wordt geassocieerd met een Ty_ty vb Ty_ty Ty_Int(void) In sommige talen: let type a = {x: int, y: int} type b = {x: int, y: int} var i : a := ... var j : b := … in i := j end Niet toegestaan in Tiger. Om hier gelijkheid te testen: elk veld moet geverifieerd worden, recursievelijk. In Tiger heb je ook een table type van het Symbol module die een mapping geeft van symbolen naar bindings. Er is in Tiger dus een type environment en een value environment. let type a = int var a : a := 5 var b : a := a in b+a end In Tiger, na te kijken voor elke value identifier: - variabele of functioin? - als variabele -> type? - als functie -> parameters &result type? enz. Allemaal bewaard in type enventry. Environments worden gebruikt tijdens de type-checking fase. typedef struct E_enventry_ *E_enventry; struct E_enventry_ {enum {E_varEntry, E_funEntry} kind; union {struct {Ty_ty ty;} var; struct {Ty_tyList formals; Ty_ty result;} fun; } u; }; E_enventry E_VarEntry(Ty_ty ty); E_enventry E_FunEntry(Ty_tyList formals, Ty_ty result); S_table E_base_tenv(void); /*Ty_ty environment*/ S_table E_base_venv(void); /*E_enventry environment* Type-checking expressions Een vb van een module die semantische analyse uitvoert waaronder type-checking - van een abstracte syntax. Bevat 4 functies die over de AST een recursie doen: struct expty transVar(S_table venv, S_table tenv, A_var v); struct expty transExp(S_table venv, S_table tenv, A_exp a); void transDec(S_table venv, S_table tenv, A_dec d); struct Ty_ty transTY( , S_table tenv, A_ty a); De type-checker is een recursieve functie over de AST. We gaan die transExp noemen en uitbreiden om niet alleen te type-checken, maar ook expressions te vertalen naar tussencode. De argumenten van transExp zijn: ● een value environment venv adz ● een type environment tenv ● een expression Het resultaat is dan een expty, bevattende: - een vertaalde expression - de overeenkomende type in Tiger struct expty {Tr_exp exp; Ty_ty ty;}; struct expty expTy(Tr_exp exp, Ty_ty ty) { struct expty e; e.exp=exp; e.ty=ty; return e; } met Tr_exp de vertaling van de expression in tussencode, en ty de type van de expression. vb optelling expression e1 + e2 Type-checking van variabelen, subscripten en velden Naast transexp die expressions een recursie uitvoert om te checken, ook nog de functie transvar die hetzelfde doet voor variabelen. Type-checking van een variabele gebeurt door: - kijken of identifier in environment - kijken of gebonden is aan VarEntry (niet FunEntry) dan is de type degene gegeven in VarEntry Elk soort expression heeft zijn eigen type-checking regels. Type-checking declarations Environments zijn gebouwd en bijgevuld met verklaringen. In Tiger is de enige soort verklaring de let-constructie. struct expty transExp(S_table venv, S_table tenv, A_exp a) { switch(a->kind) { … case A_letExp: { struct expty exp; A_decList d; S_beginScope(venv); S_beginScope(tenv); for(d = a->u.let.decs; d; d=d->tail) transDec(venv,tenv,d->head); exp = transExp(venv,tenv,a->u.let.body); S_endScope(tenv); S_endScope(venv); return exp; } ... Variabele verklaring In principe simpel. Probleem: mutueel recursieve types en functie verklaringen. (verder). Eerst nog niet-recursief. Voor een simpele variabele, vb: var x := exp var x : type-id := exp Type verklaringen Niet-recursieve type verklaringen zijn ook niet moeilijk: void transDec(S_table venv, S_table tenv, A_dec d) { ... case A_typeDec: { S_enter(tenv, d->u.type->head->name, transTy(d->u.type->head->ty)); } ... transty : vertaalt type expressions van de abstract syntax (A_ty) naar de type descriptions dat we in de environment steken (Ty_ty) Functie verklaringen Ingewikkelder. void transDec(S_table venv, S_table tenv, A_dec d) { switch(d->kind) { .... case A_functionDec: { A_fundec f = d->u.function->head; Ty_ty resultTy = S_look(tenv, f->result); Ty_tyList formalTys = makeFormalTyList(tenv,f->params); S_enter(venv,f->name,E_FunEntr(formalTys,resultTy)); S_beginScope(venv); {A_fieldList l; TY_tyList t; for(l=f->params, t=formalTys; l; l=l->tail, t=t->tail) S_enter(venv,l->head->name, E_VarEntry(t->head)); } transExp(venv, tenv, d->u.function->body); S_endScope(venv); break; } ... Functie verklaringen Ingewikkelder. Vorige implementatie: ● ● ● ● ● enkelvoudige functie niet recursief mét resultaat (geen procedure) handelt geen program errors (bv onverklaarde type identifiers) kijkt niet na of de body overeenkomt met de verklaarde result type Functie verklaringen Wat doet het wel? In Tiger: function f(a: ta, b: tb) : rt = body 1) transDec zoekt rt op in type environment 2) maakt lijst van types van formele parameters (<tenv) 3) transDec bouwt FunEntry van deze functie in value environmen 4) formele parameters ingevoegd in de value environment: deze environment is gebruikt voor het verwerken van de body 5) Uiteindelijk, endscope() eindigt de formele parameters in de environment; de resulterende environment is nu gebruikt Recursieve verklaringen De implementaties tot nu toe wekern niet voor recursieve types of functieverklaringen, omdat ze ongedefinieerde types en function identifiers tegenkomen. Oplossing: 1) all “headers” in de environment steken 2) all “bodies” in de environment verwerken header: type list = {first: int, rest: list} De headers worden ingevoerd met een lege binding, en pas achteraf worden deze bindings ingevuld Let op: cycles type a = b type b = d type c = a type d = a illegal cycle a -> b -> d -> a > illegal cycles moeten gevonden worden door type checkers (conclusie)
© Copyright 2025 ExpyDoc