Metody realizacji języków programowania/MRJP Wykład 2

obecną postać tego modułu przygotował Andrzej Salwicki w zastępstwie Marka Warpechowskiego (salwicki@mimuw.edu.pl)

Tablica Symboli

Kompilator posługuje się tą struktura danych, w procesie tzw. statycznej analizy semantycznej (por. następny wykład). Znaczenie tablicy symboli wzrosło wraz z rozwojem języków programowania. Nowsze języki w których występuje zarówno zagnieżdżanie modułów programu, jak i dziedziczenie klas wymagają odpowiedniego narzędzia dla ustalenia co oznacza identyfikator występujący w danym wyrażeniu lub danej instrukcji.

Ponadto znaczenie tej struktury wzrosło gdy okazało się, że warto ją przechowywać również po zakończeniu kompilacji. Tablica symboli jest przydatna w procesie debugowania tzn. eksperymentalnego wykonywania programu w celu usunięcia błędów w nim wystepujących. Powstanie i rozpowszechnianie sie środowisk tworzenia i pielęgnacji oprogramowania takich jak Eclipse, ... też wzmocniło rolę tablicy symboli.

Co oznacza identyfikator występujący w danym wyrażeniu lub instrukcji?

Rozpatrzmy jakieś wyrażenie np. x+y

Napis x w nim występujący jestidentyfikatorem. W programie być może jest kilka deklaracji definiujących znaczenie tego identyfikatora. Która z deklaracji opisujących, przypomnijmy na różne sposoby, identyfikator x jest właściwa dla wystąpienia identyfikatora x w tym wyrażeniu?

Specyfikacja tablicy symboli

Zadania

Tablica symboli przechowuje informacje o wielkościach jakie zadeklarowano w każdym module programu(funkcji, klasie, procedurze). Mozż tezżprzechowywać informacje wytworzone podczas dalszych etapów procesu kompilacji np. informację o alokacji zmiennej, wytworzoną przez moduł generacji kodu.

Struktura danych

Z abstrakcyjnego punktu widzenia tablica symboli jest odmianą struktury słownika. Mamy w niej operacje: wpisz(info), szukajInfoPoczynającOd(id, węzeł), szukajInfoW(id, węzeł). Mamy tez operację: UtwórzWęzeł, ZamknijWęzeł. W odróznieniu od zwykłej struktury słownika mamy tu trzy a nie dwa typy: Element(=info), Słownik i Węzeł. Słownik jest kolekcją węzłów, każdy węzeł zawiera elementy.

Rysunek powyższy nie przedstawia wszystkich szczegółów. Zaznaczono na nim rodzaje ważniejszych elementów informacji zapisywanych w węzłach tablicy symboli.

Tworzenie tablicy symboli

Tablicę symboli tworzy parser rozpoznaje deklaracje identyfikatorów, deklaracje modułów(=unit.)Gdy parser stwierdzi, że wystąpiła deklaracja wpisuje informację do bieżącego węzła struktury SymTab. Informacja zawiera klucz(=key) którym jest identyfikator oraz dodatkowe cechy np. typ zmiennej prostej. Gdy stwierdzono deklarację modułu - otwiera się dla niego nowy węzeł w strukturze SymTab. Zaznacza się dla tego węzła - węzeł ojciec oraz węzeł klasy z której dziedziczy węzeł biezący. W ten sposób struktura węzłów SymTab rozpatrywana wraz z atrybutem ojciec jest strukturą drzewa. Ten sam zbiór węzłów rozpatrywany z atrybutem “dziedziczę z ...” tworzy strukturę lasu.

---

która umożliwia odnajdowanie znaczenia identyfikatorów występujących w programie.

1. Wystąpienia definiujące i użytkowe identyfikatorów. Zanim jednak odnajdziemy znaczenie jakiegokolwiek identyfikatora w Tablicy Symboli musi ono w niej zostać uprzednio zdefiniowane. Programista definiuje znaczenie identyfikatora w programie przy pomocy jego deklaracji. Tak więc wszystkie wystąpienia identfikatorów w programie możemy podzielić na definiujące i użytkowe.

Wystąpienie definiujące to wystąpienie identyfikatora, którego znaczenie właśnie definiujemy poprzez deklarację.

Wszystkie pozostałe wystąpienia identyfikatorów to wystąpienia użytkowe.