Abstract Syntax Semantic Analysis

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)

Download Report