Tabulka symbolů

Tabulka symbolů je v informatice označení pro datovou strukturu, kterou používá překladač nebo interpret pro uložení všech identifikátorů nalezených ve zdrojovém kódu programu, které jsou doplněny o další informace. Tabulku symbolů může používat většina částí překladače. Vzhledem k tomu, že je zde uvedena i informace o velikosti objektu, často se toho využívá při statické nebo dynamické alokaci paměti.

Implementace

Jednou z možností konstrukce tabulky je využití metod podobných prohledávání databází (tvorba indexů pro záznamy). Tvorbu ovlivňuje potřeba dvou základních operací a to vkládání a vyhledávání. Shodným znakem při implementaci tabulky symbolů je většinou použití hashovací tabulky. Překladač může využít jednu velkou tabulku pro všechny symboly nebo několik menších hierarchicky uspořádaných tabulek pro různé části zdrojového kódu. Konkrétní implementace se liší podle toho, zda se tabulka vytváří pro jazyk bez blokové struktury (např. BASIC) nebo jazyk s blokovou strukturou programu (Pascal atd.).

Jazyky bez blokové struktury

U těchto jazyků se využívají tři způsoby implementace: neseřazené tabulky, seřazené tabulky a uložení obsahu tabulky do stromové struktury. Neseřazené i seřazené tabulky mají poměrně neefektivní vyhledávání i zápis (lineární složitost). V třetím případně je složitost vkládání i vyhledávání zredukována, ale za cenu větší paměťové náročnosti a složitostí implementace.

Jazyky s blokovou strukturou

U těchto jazyků je situace složitější o nutnost zachovat blokovou strukturu zápisu programu, tzn. umožnit používání lokálních proměnných, procedur a funkcí. Toho lze docílit vytvořením několika tabulek (pro každý blok jedna), které jsou uspořádány do stromové struktury, přičemž při hledání záznamu se postupuje ve stromu pouze vzhůru (ke kořeni). Může být využito též zásobníku.

Použití

Tabulka symbolů se využívá při sémantické analýze, po které by měla obsahovat všechny nalezené identifikátory jako například proměnné, konstanty, procedury, funkce a informace o nich. Ukládané informace se odvíjí od objektu, který je do tabulky ukládán. Ukládání provádí ve většině případů lexikální analyzátor. Informací se využívá nejen ke kontrole, ale následně i v dalších částech překladače (například při alokaci paměti).

Příklad

Zde je uveden jednoduchý příklad několika položek v tabulce symbolů, který obsahuje pouze proměnné. První sloupec obsahuje adresu do paměti, kde je proměnná uložena. Ukládání provádí interpret a může mít absolutní, nebo relativní podobu. Druhý sloupec popisuje typ symbolu, zde se jedná o typ použité proměnné. Pokud by se jednalo o funkci, bylo by zde uvedeno více údajů (např. typ jednotlivých parametrů, typ návratové hodnoty atd.). Ve třetím sloupci je uveden název symbolu. Čtvrtý sloupec obsahuje délku, nebo také velikost, ta může být závislá na použité platformě a je také dána definicí v konkrétním jazyce.

Ukázková tabulka symbolů
Adresa	Typ	Název	Délka	Deklarováno	Použito
00000020	double array 10	dbl_ary	80B	A	A
20000004	integer	pom	4B	A	N
20000008	double	i	8B	A	A
2000000c	real	konc	4B	A	N
20000018	integer	indexDoPole	7B	N	A

Jak je možné vidět v uvedené tabulce, proměnná indexDoPole nebyla deklarována, ale byla použita. Pokud bychom používali jazyk, který umí používat pouze deklarované proměnné, jednalo by se o sémantickou chybu.

Související články

Externí odkazy

Překladače Ostrava 2005 Archivováno 19. 5. 2016 na Wayback Machine. Odborná publikace
Sémantická analýza PSLib Mgr. Milan Keršláger