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.

Wstawianie

Informacja o identyfikatorze jest wstawiana do bieżącego węzła. Jedynym utrudnieniem jest wymóg sprawdzenia, czy ten sam identyfikator nie jest juz opisany w bieżącym węźle. Zmiana bieżącego węzła: - po stwierdzeniu, ze zadeklarowano nowy moduł(funkcję, procedurę, klasę,..),dodaje się nowy węzeł i czyni się go węzłem bieżącym, - po zakończeniu analizy składniowej modułu, ponownie węzłem bieżącym staje się ojciec zakończonego węzła.

Odszukiwanie

W trakcie analizy semantycznej, a właściwie mówiąc, podczas kontroli typów, należy dla każdego aplikacyjnego wystąpienia identyfikatora znaleźć odpowiednie wystąpienie deklarujące ten identyfikator. Zauważmy, że często jeden identyfikator może mieć wiele różnych deklaracji w programie. Którą deklarację należy uznać za odpowiednią definicję dla danego wystąpienia identyfikatora id?

Poszukiwanie identyfikatora id zaczynamy od bieżącego węzła. Jeśli znaleziono to mamy do czynienia z lokalną deklaracją. Wynikiem poszukiwania jest informacja o typie, modyfikatorach, etc znalezionego identyfikatora. Jeśli nie to poszukiwanie informacji o identyfikatorze id należy kontynuować w innym węźle. Czy ma to być węzeł modułu obejmującego dany moduł programu tzn. węzeł wskazany przez wskażnik SL węzła bieżącego? czy też węzeł wskazany przez wskaźnik Extends? Zastanów się przez chwilę.

Masz rację. Poszukiwania należy kontynuować w wężle wskaznym przez wskaźnik Extends bieżącego węzła. Ale co dalej gdy i w tym węźle nie znajdziemy informacji o poszukiwanym identyfikatorze id?

Niech w oznacza węzeł bieżący, jest to węzeł modułu w którym znajduje się wystąpienie aplikacyjne identyfikatora id. Węzeł v modułu zawierającego deklarację identyfikatora id, którą należy uznać za właściwą dla tego wystąpienia aplikacyjnego jest określony jako

$v^{\prime }=SL\sup i(Extends\sup j(w))$

gdzie i jest najmniejszą liczbą naturalną taką, że ... Algorytm poszukiwania:

węzeł_przeszukiwany := węzeł_bieżący;
powtarzaj
szukaj w węzeł_przeszukiwany;
jeśli nie znaleziono to 
  jeśli 

---

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.