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

From Studia Informatyczne

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

Spis treści

Tablica Symboli

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.

Kompilator posługuje się strukturą danych nazywaną Tablica Symboli, 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.

grafika:mrjp13_Img3.jpg

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

grafika:mrjpW2ListyTS.jpg

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 użytkowego wystąpienia jakiegoś 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? Potrzebny jest nam algorytm wiążący dane wystapienie aplikacyjne identyfikatora id z odpowiednim wystąpieniem deklarującym/definiującym ten identyfikator. Algorytm ten musi być stosowalny do każdego wystąpienia identyfikatora id w sposób jednorodny. Algorytm ten powinien być znany autorowi programu. Inaczej mówiąc autor programu powinien znać zasadę związywania deklaracji opisującej cechy identyfikatora napotkanego w treści wyrażenia lub instrukcji. Algorytm taki powinien umożliwiać analizę działania programu przed jego wykonaniem.

Zasady dynamicznego i statycznego wiązania wystąpień identyfikatora

Historycznie rzecz biorąc możemy mówić o statycznym bądź dynamicznym wiązaniu wystąpienia aplikacyjnego identyfikatora z jego deklaracją. Zasada dynamicznego wiązania powiada, ze znaczeniem nielokalnego identyfikatora jest najświeższa spośród wykonanych deklaracja tego identyfikatora. Zasada w takiej formie jest niezwykle uciążliwa. Dlaczego? Podaj odpowiedni przykład. Przykładem jęzka o dynamicznym wiązaniu wystąpienia aplikacyjnego z wystąpieniem definiującym jest język LISP. Ciekawe, że do przyjecia tej zasady doszło przypadkiem podczas tworzenia kompilatora dla LISPu. Obecnie stosowana jest wersja SCHEME w której składnia nie różni sie niczym od LISPu ale semantyka jest opisana przy pomocy statycznego wiązania wystąpień identyfikatorów. Statyczne wiązanie powiada, że znaczeniem aplikacyjnego wystąpienia identyfikatora jest deklaracja zawarta w najmniejszym module obejmującym moduł zawierający wystąienie aplikacyjne tego identyfikatora. Ale dla języków takich jak Simula67, Loglan82, Beta i Java trzeba tę definicję uściślić biorąc pod uwagę nie tylko moduły obejmujące dany moduł ale i moduły/klasy dziedziczone.


Naiwne poszukiwanie algorytmu

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ę. W jezyku Pascal poszukiwanie powinno być kontynuowane w węźle - ojcu tzn, węźle wskazanym przez wartość wskaźnika SL. W jezyku C++ poszukiwania przenoszą się według wskaźników Extends. Ale jak należy postępowąć w przypadku Simuli67, Loglanu82, Bety i Javy? Masz rację. Poszukiwania należy kontynuować w wężle wskazanym 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? Potrzebna jest definicja bardziej ogólna.

Ogólne sformułowanie zasady statycznego wiązania

Dla każdego języka w którym moduły/klasy mogą być i zagnieżdżane i dziedziczone można przyjąć następującą zasadę statycznej widoczności deklaracji.


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 = SL ^i (Extends ^j(w))

gdzie para <i,j> liczb naturalnych jest najmniejszą w porządku leksykograficznym parą taką, że węzeł SL ^i (Extends ^j(w)) zawiera informację o identyfikatorze id. Jeśli taka para <i,j> liczb naturalnych nie istnieje to stwierdza się błąd użycia niezadeklarowanego identyfikatora id.

Przypomnijmy, że para liczb naturalnych <i,j> jest w porządku leksykograficznym wcześniejsza od pary liczb <k,n> wtedy i tylko wtedy gdy i<k lub gdy i=k oraz j<n.

Zaprogramowanie algorytmu przeszukującego graf tablicy symboli pozostawiamy jako ćwiczenie.

Oczywiście zasadę tę mozna odpowiednio zmodyfikować tak by była przydatna również dla semantyki i kompilacji programów w Pascalu i Algolu, lub programów napisanych w języku C++. W takim przypadku należy odpowiednio pominąć funkcje SL lub Extends.

Przykład

W poniższym przykładzie widać jak niełatwe może być określenie wyniku programu. Jaki bedzie wynik programu?

class  staticBinding
{   class A  { int x; }  // end of A
    class B extends A
    {  
      class G {
        public  G() {  System.out.println(x); }			
      };  // end klasy G
       class C extends A
       {
        class H extends G {public H() {System.out.println(x); }
        };   // end klasy H
	 public  C ()             // konstruktor klasy C
	 {  x = 2;  G gg= new G();  H hh = new H(); }
       };  // end klasy C
     public  B()
     {  x = 1;    C cc = new C();   }
    };  // end klasy B
static B bb;
  public static void main(String[] args) 
  { staticBinding mm = new staticBinding();  bb = mm.new  B(); }
}  // koniec


Kolejne rysunki pokazują na przykładzie jednego programu trzy fazy:

- Tworzenie tablicy symboli
- Analizę semantyczną tego programu,
- Proces wykonywania programu

Program jest napisany w Javie. Ale na rysunkach ten sam program jest zapisany w Loglanie. (Mam nadzieję, że nie będzie to zbytnim utrudnieniem.)

Tworzymy tablicę symboli

Przeprowadzamy analizę

Na poniższych obrazkach zobaczyć można jak w wyniku analizy posługującej się tablicą symboli ustalone zostają miejsca do których odnoszą się użytkowe wystąpienia identyfikatorów.

I jeszcze symulacja wykonania programu

Tu możemy obejrzec jak wykonany zostanie nasz program.

Wyznaczanie klas dziedziczonych

Znamy 4 języki programowania obiektowego, które pozwalają na dziedziczenie klas i na zagnieżdżanie klas. Są to Simula67, Loglan82, Beta i Java. Okazuje się, że dla tych języków pojawia się problem: jeżeli klasa B może dziedziczyć klasę A (w obecnym żargonie mówi się klasa B dziedziczy po klasie A), to którą z być może wielu klas A jakie występują w programie dziedziczy klasa B?

Problem ten rozwiązuje się dość prosto dla Simuli, Loglanu i Bety. W Javie jednak zadanie wyznaczenia klasy z której dziedziczy dana klas może być trudne.

Rozpatrzmy następujący program

class A extends B {
        class C extends D {
                 class F extends G {
        } // end C
        class E { 
                class G{} 
        }  // end E
        class B extends E {}
} //  end A
class B {
        class D extends E {}
} // end B
class E {
        class G extends B {}
        class D {}
} // end E

Skojarzenia klasa dziedzicząca z klasą dziedziczoną mozna by dokonac na 2^6=64 spooby. Który z nich jest poprawny? Czy istnieje więcej niż jedno poprawne rozwiązanie? Czy potrafimy przedstawic algorytm rozwiązujący wszystkie instance tego problemu w czasie wielomianowym?

  • Nie wszystkie znane nam kompilatory Javy potrafią poprawnie rozwiązać ten problem.
  • Warto zauważyć, że w Javie musimy znależć rozwiązanie zanim przejdziemy do statycznej analizy semantycznej. Należy zacząć od drobnej modyfikacji struktury węzła w tablicy symboli. Potrzebne nam są dwa pola, w pierwszym zapisujemy nazwę klasy jaka ma być odziedziczona, w drugim polu zapiszemy wskażnik do tej klasy. Oczywiście Java ma więcej pułapek niż Loglan82 lub Beta. Jedną z nich jest możliwośc wypisania po słowie extends wyrażenia ścieżkowego. Wyrażenie takie składa się z ciągu nazw klas oddzielonych kropkami np. extends B.E.G.A. Którą klasę A mamy naprawdę odziedziczyć? Nie oznacza to wcale, że bedzie to klasa A zadeklarowana w klasie G, która jest zadeklarowana w klasie E, która jest zadeklarowana w klasie B. Zresztą, o której klasie B mówimy? Coraz grubsze specyfikacje języka Java nie stanowią wcale pomocy w rozwiazywaniu takich zagadek.

Poniższy obrazek ilustruję strukturę zagnieżdżenia klas i nasz problem grafika:MRJPw2img51.png

Na następnym obrazku dostrzec można dwie kandydatury. Czy są to rozwiązania? Łatwo dostrzec,że przestrzeń kandydatur ma rozmiar wykładniczy wzgledem długości kodu źródłowego.

grafika:MRJPw2img52.png

W pracy [LSW] przedstawiono problem i podano rozwiązanie tzn. algorytm wyznaczania klas dziedziczonych wraz z dowodem poprawności i kompletności tego algorytmu.

grafika:MRJPw2img53.png