Vazba (binding) z
Tabulka symbolů
z
vazba = spojení mezi entitou a vlastností okamžik vazby (binding time) z
Miroslav Beneš Dušan Kolář
z z z
z
při návrhu jazyka při implementaci jazyka během překladu/spojování/zavádění programu za běhu programu
statická vazba / dynamická vazba z
dynamická vazba vznikne nebo se může změnit po spuštění programu Tabulka symbolů
Vazba - příklad
Deklarace a definice
int count;
z
z z z z z z z
...; count = count + 5;
množina typů proměnné count typ count množina hodnot count hodnota count množina významů symbolu + význam symbolu + v tomto příkazu interní reprezentace literálu 5 Tabulka symbolů
Deklarace (proměnné, funkce) z z
z
specifikuje atributy a způsobuje alokaci paměti
Definice funkce z
3
specifikuje pouze atributy explicitní / implicitní deklarace
Definice proměnné z
z
2
specifikuje atributy a tělo funkce Tabulka symbolů
4
1
Proměnné z
z
abstrakce buňky nebo kolekce buněk v paměti počítače
z
absolutní adresování
z
LOAD ADD STORE z
z
100 101
z
100
z
jazyk symbolických adres X DS LOAD
z
Základní vlastnosti proměnné
z
F X
vyšší programovací jazyky var x: Integer; Tabulka symbolů
5
Adresa a hodnota proměnné z
z
z
z
z
proměnná na levé straně představuje adresu = L-hodnota proměnná na pravé straně představuje hodnotu = Rhodnota
z
z
lokální proměnné v různých podprogramech lokální proměnná v rekurzivní funkci
z
z
proměnné alokované na zásobníku proměnné alokované na hromadě (heap) z
aliasing – parametry předávané odkazem, ukazatele komplikuje optimalizaci programů Tabulka symbolů
adresa: statické proměnné hodnota: konstanty
Dynamická vazba z
Adresa může být spojena s různými jmény z
6
Statická vazba z
Jméno může být spojeno s různými adresami z
Tabulka symbolů
Adresa a hodnota proměnné
L := R z
z
jméno adresa hodnota typ doba života rozsah platnosti
z z 7
alokace proměnné – malloc(), new, … explicitní dealokace – free(), delete, … implicitní dealokace – garbage collector (GC) Tabulka symbolů
8
2
Typ proměnné z
Typ proměnné určuje z z
z
z
z
z
Viditelnost (visibility) z
většina klasických jazyků – součást deklarace možnost implicitní deklarace typu (BASIC, FORTRAN) typická pro skriptovací a interpretované jazyky vyžaduje dynamickou typovou kontrolu – možnost odhalení chyb až při běhu programu, časově náročné Tabulka symbolů
9
Rozsah platnosti (scope)
z
Tabulka symbolů
z
rozsah platnosti je dán lexikální strukturou programu (pozicí zápisu v textu programu) používá se v převážné většině jazyků
Dynamická vazba rozsahu platnosti
z
rozsah platnosti definován prováděním programu (až do další deklarace) z APL, LISP (starší verze), SNOBOL4 z jednoduše implementovatelná v interpretech, nevhodná z hlediska čitelnosti programů a jejich efektivity Př.: p(x) + q(y) - může záležet na pořadí vyhodnocení z
10
= časový interval, v němž má proměnná přidělenou paměť pro uložení hodnoty (je alokována) Statická alokace z
z
z
11
před spuštěním programu
Dynamická alokace
z Tabulka symbolů
proměnná není zakrytá jinou proměnnou téhož jména v zanořeném rozsahu int x, y; float f(float x) { return x * 1.22; } proměnná x typu int je platná v celém programu, ale viditelná jen mimo funkci f
Doba života proměnné
Statická vazba rozsahu platnosti z
z
Rozsah platnosti = úsek programu, ve kterém je entita známá a je tedy možné s ní manipulovat
Dynamická vazba z
z
z
množinu hodnot proměnné množinu aplikovatelných operací
Statická vazba z
z
Rozsah platnosti (scope)
automatická - při vstupu do rozsahu platnosti proměnné provedením příkazu pro vytvoření – např. new Tabulka symbolů
12
3
Tabulka symbolů z
Reprezentace pojmenovaných entit z z
z
Tabulka symbolů z
explicitně pojmenovaných uživatelem implicitně pojmenovaných – standardní entity (typy, funkce, třídy, ...), dočasné proměnné
z z
Účel: z z z
řešení kontextových vazeb (deklarace -> použití) typová kontrola ukládání informací pro generování kódu Tabulka symbolů
z z z
Tabulka symbolů
deklarace typy výrazy příkazy
z
atributy entit z
z
z
z
15
informace dané zdrojovým jazykem (druh entity, jméno, hodnota konstanty, ...) informace dané cílovým jazykem (velikost a zarovnání, relativní adresa, ...)
vztahy mezi entitami z
Tabulka symbolů
14
Model programovacího jazyka
Program můžeme modelovat obecným grafem, jehož uzly jsou jednotlivé sémantické entity: z
z
ukládání identifikátorů během lexikální analýzy využití kontextových informací Expr -> IdVar Index | IdProc Args | IdCon … PASCAL: P(x,y) kontextově závislá syntaxe Write(x:3,y:2:5)
13
Model programovacího jazyka z
Interakce s lexikálním analyzátorem
agregace (funkce - parametr) asociace (proměnná – typ)
Tabulka symbolů
16
4
Návrh struktury modelu
Model programovacího jazyka
class Entity { set
attributes; string name; } class Package extends Entity { list<Entity> contents; } class Class extends Entity { list fields; list<Method> methods; } Tabulka symbolů
17
Návrh struktury modelu
18
Funkce tabulky symbolů z
class Method extends Entity { list parameters; list locals; Type returns; Statement body; } class Variable extends Entity { Type type; Expr initial; } class LocalVariable extends Variable { int index; } Tabulka symbolů
Tabulka symbolů
Operace: z z z
z
- inicializace - vkládání - vyhledávání (častější)
Inicializace z z
19
init insert lookup
vytvoření prázdné tabulky naplnění implicitními deklaracemi
Tabulka symbolů
20
5
Funkce tabulky symbolů z
Vkládání – nejprve vyhledá klíč v tabulce z z
není nalezen nalezen z z
z
Implementace tabulky symbolů z
→ vytvoří se nová položka → obvykle chyba
z
deklarace / definice implicitní deklarace (návěští a funkce v C)
z
Vyhledávání – vyhledá klíč v tabulce z z
nalezen nenalezen
O(log2n) pro statické tabulky (např. klíčová slova)
21
Tabulka symbolů
O(n) - O(log2n) doba vyhledávání závisí na vyvážení stromu časová náročnost vkládání není kritická
z
Tabulky s rozptýlenými položkami z z
z
z
z
optimálně vyvážené stromy příliš komplikované
z
suboptimální řešení z
z
např. AVL stromy
Tabulka symbolů
z
23
O(1)
mapovací funkce: klíč → index řešení kolizí z
z
22
Implementace tabulky symbolů
Vyhledávací stromy z
Seřazené tabulky s binárním vyhledáváním z
Implementace tabulky symbolů z
O(n)
jen pro malý počet prvků
→ vrátí odpovídající entitu → obvykle ohlásí chybu Tabulka symbolů
z
Neseřazené tabulky
seznamy/stromy synonym rozptylovací funkce: index → index
rychlost závisí na zaplnění tabulky problematický průchod položkami podle klíče obtížně se řeší přetečení tabulky Tabulka symbolů
24
6
Blokově strukturovaná tabulka
Blokově strukturovaná tabulka z
z
z
Vhodná pro jazyky se zanořenými deklaracemi (hierarchické struktury) Řeší rozsah platnosti a viditelnost jména v zanořených blocích Nové operace: z z
z
Vkládání z z
z
Vyhledávání z
otevření rozsahu platnosti (open) uzavření rozsahu platnosti (close)
z z
Tabulka symbolů
25
Implementace blokově strukturované tabulky symbolů z
z
vyhledávací stromy tabulky s rozptýlenými položkami
z
Přirozenou datovou strukturou pro reprezentaci hierarchie je ZÁSOBNÍK z
z
Úrovně se nemohou překrývat
Tabulka symbolů
26
Zásobníková tabulka z
z
klíč se vyhledává nejprve v aktuální úrovni, pokud se nenajde, hledá o úroveň výš neúspěch se hlásí až po prohledání nejvyšší úrovně (globální jména) explicitní přístup na globální úroveň ::x Tabulka symbolů
Založena na některé z metod pro nestrukturovanou tabulku z
pracuje pouze s aktuální úrovní tabulky jména na vyšších úrovních se neuvažují
z
27
Položky se ukládají v pořadí deklarací na vrchol zásobníku Druhý zásobník obsahuje odkazy na začátky jednotlivých úrovní Vyhledávání se provádí od konce zásobníku zpět – při vkládání pouze na aktuální úrovni Neseřazená tabulka → pro malý počet položek Tabulka symbolů
28
7
Příklad jméno entity
Kombinace zásobníku a stromu další atributy
int x,y; double fun(x,num) { int max; … { double delta,y; … } }
TOP
8 y 7 delta 6 max 5 num 4 x 3 fun 2 y 1 x
7 4
z
Každá úroveň je reprezentována stromem Zásobník obsahuje kořenové uzly jednotlivých úrovní
z
Vhodné pro velký počet položek
z
z
1 index bloku
Tabulka symbolů
29
Příklad
Tabulka symbolů
30
Kombinace TRP a zásobníku z
z
x
x
delta
Doplnění jednoduché zásobníkové tabulky o rychlé vyhledávání pomocí TRP Vkládání: z z
z
fun
nízká spotřeba paměti (dynamická alokace)
y
num
y
Vyhledávání: z
z
Tabulka symbolů
31
deklarace se uloží na konec pole index položky se vloží do TRP deklarace se stejným jménem leží ve stejném řetězu synonym vybere se deklarace s nejvyšším indexem
Tabulka symbolů
32
8
Jednoúrovňová blokově strukturovaná tabulka
Příklad jméno entity
8 y 7 delta 6 max 5 num 4 x 3 fun 2 y 1 x
další atributy
z
TOP
6 / 8 / / 5 4
z
z
7
z
4 1
synonyma
TRP
z
Tabulka symbolů
index bloku
z
33
Příklad 2
fun
0
max y
odkaz na entitu z vyšší úrovně, kterou její deklarace zakrývá informaci o úrovni zanoření – proč?
Vyhledávání probíhá pouze jednou, paralelně na všech úrovních Kam se ztratil zásobník? Tabulka symbolů
34
Composite – diagram tříd
delta
num x
Vyhledávací tabulka odkazuje pouze na viditelné deklarace Každá entita obsahuje
1 1
0 2
2
Tabulka symbolů
0
35
Tabulka symbolů
36
9
Composite – diagram objektů
Rozhraní tabulky identifikátorů Položka vyhledávací tabulky interface CIdent { string name; attribute CDecl meaning; }; z
libovolná vyhledávací struktura z
z
37
Rozhraní tabulky deklarací
Tabulka symbolů
identita jmen se nahradí identitou objektů Tabulka symbolů
38
Implementace metod
Deklarace pojmenovaného prvku interface CDecl { // deklarace CIdent ident; // identifikátor CDecl hides; // zakrytá deklarace CBlock parent; // rozsah platnosti } Deklarace vytvářející rozsah platnosti (např. třída, funkce, ...) interface CBlock { set contents; void insert(CDecl dcl); void removeAll(); }
vyhledávací strom, TRP, ...
může ji vytvářet již lexikální analyzátor z
Tabulka symbolů
// jméno // význam
// obsah // vkládání // uzavření 39
void CBlock::insert(CDecl dcl) { dcl.hides = ident.meaning; ident.meaning = dcl; contents.add(dcl); } void CBlock::removeAll() { forall( dcl in contents) { dcl.ident.meaning = dcl.hides; } } Tabulka symbolů
40
10
