Tablica symboli i generacja kodu - czwarta praca domowa

Na początek trzy linki, które powinny pomóc w implementacji tablicy symboli:

strona mgr inż. Adama Piotrowskiego - z której można pobrać wersję binarną programiku pod GNU/Linuxa, który tworzy i wypisuje tablicę symboli dla kodu w Pascalu.
http://www.ida.liu.se/~TDDB44/lessons/lessons.en.shtml - polecam rzucić okiem na tutorial nr 2.
http://www.iis.sinica.edu.tw/~tshsu/compiler2006/index.html - niżej na stronie są slajdy. Warto zerknąć na część 5 (Symbol Table).

UWAGA: to co nastąpi dalej to moje luźne przemyślenia, które niekoniecznie mogą wypalić. Być może to co tutaj opiszę da się wykonać dużo łatwiej albo dużo poprawniej, zatem proszę o podejście do poniższego artykułu z dużą dozą krytycyzmu.

TODO:

  1. dodać diagramy UML dla trzech rozwiązań.
  2. dodać własny przykład prostej implementacji konwersji z napisu i do napisu.
  3. Wypisać szczególne produkcje parsera i symbole leksera i opisać co przy nich należy zrobić

Tablica Symboli.

Czym jest tablica symboli?

Najprościej tłumacząc, tablica symboli jest po prostu pewną strukturą danych, która przechowuje informacje o napotkanych w kodzie symbolach. O tym, co jest symbolem, a co nie, decydujemy my (np. etykieta może być symbolem, ale nie musi). Każdy symbol w tablicy identyfikowany jest przez swój indeks (np. liczbę całkowitą). Tablicę symboli tworzymy po to, żeby nam ułatwiła generowanie kodu. Dzięki niej możemy operować tylko na indeksach, mając ten komfort, że za ich pomocą zawsze możemy się odnieść do potrzebnych informacji o symbolu. Tablica symboli ułatwia też ujednolicenie pewnych operacji generowania kodu.

Jedyną odpowiedzią na pytanie "czy moja tablica symboli jest wystarczająco dobra?" jest "to się okaże". Trudno jest zweryfikować, czy tablica przechowuje wszystkie potrzebne informacje, dopóki nie zaczniemy generować za jej pomocą kodu.

Sama implementacja tablicy to temat, do którego można podejść na różne sposoby, więc jest po trochu kwestią indywidualnego talentu programistycznego.

Co przechowywać w tablicy symboli?

Co do samych symboli, to właściwie powinno się przekazywac wszystkie zmienne, stałe liczbowe (np. kiedy natrafimy na 123.23 to też powinniśmy umieścić tą liczbę w tablicy symboli), nazwy procedur, funkcji.

Jeśli zaś chodzi o informacje dotyczące symboli, to z dostępnej przykłądowej tablicy symboli można wywnioskować, iż powinno się przechowywać:

  1. nazwę symbolu,
  2. typ symbolu (integer, real, procedura, funkcja, tablica, żaden),
  3. informację o tym, czy jest to referencja, czy też nie,
  4. zakres (są na to co najmniej dwa sposoby, o czym później)
  5. dodatkowe informacje zależne od typu symbolu (np. początkowy i końcowy indeks dla tablicy, typ zwracany i argumenty dla funkcji itd.)
  6. adres w pamięci
  7. informacja o tym, czy symbol ma mieć przydzielone miejsce w pamięci (np. stałe liczbowe ani etykiety nie powinny mieć adresów)?
  8. ????

Dobranie dodatkowych informacji przechowywanych w zależności od typu tokenu może stanowić pewien problem, zatem wypiszę, co ja dodatkowo przechowywałem dla wykorzystanych przeze mnie tokenów opróczy wspólnych informacji takich jak adres itp.:

  1. Liczba całkowita:
    1. wartość (tylko dla stałych liczbowych, bo wartości przydają się do sprawdzania poprawności podania indeksów podczas deklaracji tablicy).
  2. Liczba rzeczywista:
    1. to samo co dla liczby całkowitej
  3. Tablica:
    1. typ argumentów,
    2. indeks początkowy (a raczej indeks do niego tablicy symboli, gdyż tam, jak każda stała liczbowa, znajdzie się indeks początkowy),
    3. indeks końcowy (uwagi j.w.)
  4. Procedura:
    1. liczba argumentów,
    2. typ każdego z argumentów (żeby można było sprawdzić, czy nie wywołujemy funkcji przyjmującej jedną liczbę całowitą i jedną liczbę rzeczywistą z argumentami np. (4.4, 5.5))
  5. Funkcja:
    1. liczba argumentów,
    2. typ każdego z argumentów
    3. typ wartości zwracanej
    4. indeks stałej tymczasowej zawierającej wynik ostatniego wywołania funkcji - ten element wymaga szerszego kometarza. Otóż pamiętajmy, że w Pascalu można napisać takie wywołanie funkcji: zmienna := funkcjaPierwsza(1, funkcjaDruga(3));. Jak wiadomo, funkcja nie przyjmuje tutaj funkcji jako argumentu, tylko wynik jej wywołania. Zauważmy także, że kod wywołania funkcji "zagnieżdżonej" (w tym przypadku funkcjaDruga()) wygeneruje się zawsze wcześniej niż dla funkcji okalającej, więc można bez problemu zamiast funkcji podstawić jej "zmienną zastępczą", czyli taką zmienną tymczasową, do której będzie się wpisywał wynik funkcji po jej wywołaniu w takiej sytuacji. Warto ją w odpowiednim momencie ustawić, a potem wyłuskać przy sprawdzaniu argumentów wywołania (czyli iterując po wszystkich argumentach wywołania funkcji: jeśli typ tokenu argumentu to funkcja, to zamiast niej wpisz do listy argumentów jej "zmienną zastępczą"). Może można to rozwiązać jakoś lepiej, ale ja wymyśliłem tylko taki sposób).
  6. Etykieta:
    1. żadnych dodatkowych informacji.

Ostatnia kwestia która pozostała do poruszenia w tym podrozdziale, to przechowywanie tego wszystkiego. Przecież mimo że wszystkie wpisy muszą być tego samego typu, przechowują inne dane. Jak to rozwiązać?

Najprostsze i chyba wystarczające rozwiązanie, to przechowywać wszystkie z wyżej wymienionych pól w ramach jednej struktury danych, a odczytywać i zapisywać wybrane zależnie od typu tokenu. Jest to pewne marnowanie pamięci, ale sądzę, że w przypadku naszych kompilatorów nie ma to absolutnie żadnego znaczenia.

Drugi sposób (dla bardzo ambitnych), to wykorzystanie typu danych z bibliotek boost o naziwe any. Jest to nic innego jak opakowany w klasę wskaźnik void* (a przynajmniej tak się zachowuje), do którego można wpisać daną dowolnego typu, a potem dynamicznie rozpoznać typ przechowywany i za pomocą funkcji pomocniczej any_cast<T, U>() wyłuskać ten typ. Ma to pewną zaletę (jeśli wyłuskamy nie ten typ,. który naprawdę jest przechowywany, to rzucany jest wyjątek), ale z drugiej strony trzeba się troszkę nakombinować.

Dobór typu YYSTYPE - krótka dyskusja.

W poradach do projektu jest napisane, że "atrybuty wszystkich wezlow moga byc pojedynczymi liczbami calkowitymi, zawierajacymi indeks zmiennej, w ktorej znajduje sie wynik podwyrazenia.". Jest to tylko połowa prawdy (i też nie zawsze, o czym podczas dyskusji na temat podejścia do implementacji tablicy symboli). Tak naprawdę szybko natkniemy się na problem np. z tą produkcją:

declarations var identifier-list : type ;

Dlaczego? Poniewać jeśli dopiero w tym miejscu znamy typ, który mamy przypisać zmiennym zawartym symbolu nieterminalnym identifier-list. Chyba jasne jest, że nie sposób za pomocą jednego indeksu tablicy symboli przedstawić kilka identyfikatorów (bo każdy identyfikator ma swój indeks w tablicy symboli). Są dwa rozwiązania tego problemu: albo przyjmujemy, że YYSTYPE to lista indeksów (i w większości przypadków przekazujemy po prostu listę z jednym elementem, w odpowiednich momentach ją czyszcząc), albo tworzymy sobie globalną zmienną typu lista lub wektor, specjalnie na tę okazję przechowywania wielu identyfikatorów (taki przypadek zdarza się parę razy w gramatyce). Trudno powiedzieć, który sposób jest lepszy, ja stosowałem ten pierwszy, za to ten drugi polecany jest przez dr Jabłońskiego. Co do samego indeksu do tablicy symboli, dr Jabłoński poleca, jak już wspomniałem, liczbę całkowitą jako indeks jakiegoś wektora. Możliwe jest też zrobienie tego na stringu. W zależności od tego, jak się implementuje tablicę symboli, jedno z tych podejść może być korzystniejsze, albo nawet przymusowe.

Kto wypełnia tablicę symboli?

Nazwy symboli do tablicy wpisuje analizator leksykalny i rzadko robi on coś więcej na tablicy (chociaż się zdarza, jeśli nie ma innego wyjścia), za to parser najczęściej uzupełnia te informacje, np. dodaje typ, indeksy dla tablic, liczbę parametrów dla funkcji, itd. Oczywiście możliwa jest taka koncepcja, że całą tablicę wypełnia parser i też może się ona sprawdzić. Wtedy mamy bardziej "zapaćkanego kodem" parsera w zamian za większą kontrolę nad tym, co dzieje się z symbolami.

Problemy związane a tablicą symboli.

Problemów jest wiele. Oto niektóre z nich:

Decyzja kiedy dodawać, a kiedy nie dodawać do tablicy symboli.

Powiedzieliśmy już sobie że to lekser dodaje do tablicy symboli (powiedzieliśmy też sobie, że niekoniecznie, ale ten problem dotyczy takiego właśnie przypadku). W najbardziej przymitywnym wydaniu Lekser wpisuje do tablicy symboli wszystko co napotka na drodze. Jedyne, co możemy mu powiedzieć, to żeby nie wpisywał symbolu do tablicy, kiedy już symbol o tej nazwie znajduje się w aktualnym zakresie. Weźmy np. taki fragment kodu:

program p1(input, output);

function foo() : integer;
var lokalna : integer;
begin
    lokalna := 5;
    foo := lokalna;
end;

Jak widać, mamy tu trzy razy nazwę lokalna, Wiadomo, że za pierwszym razem jest to deklaracja, a za drugim razem już jakieś użycie. To naiwne podejście wydaje się więc słuszne. Rzućmy jednak okiem na drugi kawałek kodu:

program p1(input, output);
var globalna : integer;

function foo() : integer;
var lokalna, lokalna : integer;
begin
    globalna := 5;
    lokalna := 10;
    foo := globalna;
end;

Tutaj już mamy problem - przypisanie do globalnej to pierwsze użycie tej nazwy w bieżący zakresie, więc globalna zostanie dodana do tablicy symboli. Jest to oczywiście błąd - nie chcemy by tak się stało, gdyż podczas przypisania z tablicy symboli zostanie pobrany adres zmiennej globalnej, lecz tej lokalnej (tablica symboli zwraca najbardziej zagnieżdżony wpis). Drugi problem który się nasuwa, dotyczy lokalnej. Zauważmy, że w funkcji została ona zadeklarowana dwa razy. Nie jesteśmy jednak w stanie wykryć tego błędu, gdyż lekser nie jest w stanie odróżnić drugiej deklaracji (które jest błędem) od przypisania do lokalnej (które błędem nie jest). Dzieje się tak, gdyż lekser nie zna kontekstu w jakim użyty jest symbol.

Te dwa zjawiska można wyeliminować za pomocą dosyć prostej sztuczki, która z resztą pochodzi od dr Jabłońskiego. Otóż wprowadzamy boolowską zmienną globalną, która określa, czy lekser może wpisywać nowe ID do tablicy symboli. Ta zmienna sprawdzana jest zawsze gdy lekser natrafi na nowe ID (natomiast nie sprawdzana jest przy stałych liczbowych i w innych miejscach). Jeśli zmienna == true -> wstawiamy symbol, a jeśli zmienna == false, nie wstawiamy i możemy sprawdzić wtedy czy się nie powtarza w aktualnym zakresie (a jeśli tak to bez obaw możemy zgłosić błąd).

Gdzie ustawiać tę zmienną? na false najlepiej ustawić w miejscu napotkania na symbol BEGIN, natomiast na true - zaraz po zakończeniu zakresu (w tym samym miejscu). Wyglądać to będzie w ten sposób:

{na początku zezwalamy lekserowi na wpisywanie}
program p1(input, output);
var globalna : integer;

function foo() : integer;
var lokalna, lokalna : integer;
begin {w tym miejscu zabraniamy lekserowi wpisywać nowych ID}
    globalna := 5; { globalna nie zostanie wpisana, ale 5 tak, czyli jest ok }
    lokalna := 10;
    foo := globalna { foo nie zostanie wpisana do tablicy symboli i dobrze:> }
end;
{ tutaj zezwalamy spowrotem lekserowi na wpisywanie ID }

procedure proc(argument : real);
var lokalnaProcedury : integer;
begin  {w tym miejscu zabraniamy lekserowi wpisywać nowych ID}
    globalna := 90
end;
{ tutaj zezwalamy spowrotem lekserowi na wpisywanie ID }

Pojawia się następująca pokusa: "jeśli zezwalamy lekserowi wstawiać nowe ID zaraz po symbolu END, to może po prostu wstawić kod ustawiający tę zmienną na true w lekserze w obsłudze symbolu END?". Od razu piszę - nie jest to dobry pomysł, gdyż nie zawsze po symbolu END kończymy zakres i nie zawsze po END chcemy zabronić lekserowi wpisywać ID. Przykład:

program prog(input, output);
var globalna : integer;

procedure proc (arg : integer);
begin { zabraniamy lekserowi wpisywać ID }
    if x > i then
    begin {ok, tu możemy jeszcze raz zabronić lekserowi wpisywać ID, bo i tak nie może tego robić, więc to nic nie zmieni }
        x := 5;
        i := x
    end; { tutaj nie możemy znowu pozwolić lekserowi wpisywać nowe ID, bo inaczej...}
    globalna := 133 { ...tu będzie katastrofa }
end;

Dlatego powtarzam - najlepiej ustawiać tę zmienną pomocniczą na true w tym samym miejscu w którym zamykamy zakres.

Zwracanie wartości z funkcji.

Zwracanie z funkcji realizujemy przypisując wynik do zmiennej reprezentującej funkcję. czyli np. jeśli mamy:

foo := 12 {zwracamy 12}

to tak naprawdę przypisujemy coś co ma typ INTEGER do czegoś co ma typ FUNCTION. Czy zatem trzeba tworzyć specjalne przypadki w obsłudze operatora przypisania oraz konwersji typów?

Otóż niekoniecznie.

Najprostszym sposobem na poradzenie sobie z tym problemem jest umieszczenie w tablicy symboli zmiennej referencyjnej o takim samym typie jak typ zwracany funkcji pod odpowiednim adresem. Teraz wszytkie działania dotyczące przypisania do funkcji będą załatwiane przez kod, który już napisaliśmy dla typów INTEGER i REAL. To podejście ma tylko jeden "myk", a mianowicie - co będzie, gdy zapragniemy wywołać funkcję z rekursywnie (czyli z samej siebie)? Przyjrzyjmy się kodowi funkcji gcd() z przykładowego pliku ze strony przdmiotu - gcd.pas:

function gcd(a, b: integer):integer;
begin
  if b=0 then 
    gcd:=a
  else 
    gcd:=gcd(b, a mod b) {próbujemy wywołać funkcję, ale w naszej tablicy symboli 
                          jest już przesłonięta przez zmienną pomocniczą, więc lipa}
end;

Osobiście znam tylko jeden lek na ten problem - po prostu trzeba zaimplementować w tablicy symboli odpowiednią metodę do szukania pierwszej funkcji o danej nazwie. Być może przy niektórych implementacjach tablicy symboli ten problem nie istnieje w ogóle (np. kiedy mamy dwie tablice, lokalną i globalną, to możemy szukać od razu w globalnej), ale nie dam za to głowy.

Implementacja.

Nasza tablica symboli powinna umożliwiać m. in.:

  1. dodawanie nowych symboli,
  2. dostęp do wpisu symbolu (raczej jego referencji niż wartości) za pomocą indeksu w celu zmiany informacji o symbolu.
  3. zmianę informacji dotyczących istniejących w tablicy symboli.
  4. przeszukanie tablicy (wszystkich zakresów) w poszukiwaniu symbolu o danej nazwie
  5. przeszukanie aktualnego zakresu w poszukiwaniu symbolu o danej nazwie (żeby np. zwrócić błąd, gdy ktoś napisze np. var a, a, a : integer;)
  6. otwieranie i zamykanie zakresów?
  7. ???

Jeśli chodzi o implementację, to są cztery poważniejsze problemy do rozwiązania:

  1. sposób implementacji zakresów
  2. dobór typu YYSTYPE
  3. dobór typu który będą miały dodatkowe informacje zależne od typu symbolu (bo dla każdego typu chcemy przechowywać co innego)
  4. przydział adresów dla poszczególnych zmiennych.

Zajmę się teraz punktem pierwszym, czyli zakresami. Wiadomo, że nasza tablica symboli musi umożliwiać przykrywanie nazw, tzn. że jeśli globalnie zadeklarujemy zmienną "pokemon" i potem po rozpocząciu funkcji też zadeklarujemy po raz drugi zmienną "pokemon", to w ciele funkcji będzie widoczna tylko ta druga (ogólniej - ta z najbliższego zakresu). Wiadomo też, że w zakresie powinniśmy widzeć symbole z zakresu w którym aktualnie jesteśmy oraz ze wszystkich zakresów okalających (oczywiście jeśli jakaś nazwa została przesłoniona, to widzimy tylko tą ostatnią przesłaniającą). Kiedy zakres się kończy, wszystkie symbole które zostały w nim wprowadzone mogą być w naszym przypadku usunięte z tablicy (w przypadku ogólnym ponoć wykorzystuje się te tablice jeszcze podczas optymalizacji albo przydają sie, gdy piszemy interpreter zamiast kompilatora, ale nas nie dotyczy ani jedno, ani drugie).

Możliwe podejścia do implementacji zakresów w tablicy symboli

Warto pamiętać, że w naszym przypadku nowy zakres tworzy się w trzech przypadkach:

  1. początek programu
  2. napotkanie początku funkcji
  3. napotkanie początku procedury

Zakresy można implementować na trzy poniższe sposoby:

Zakresy w liście

To podejście (chyba trudniejsze) polega na trzymaniu na liście osobnych tablic symboli dla każdego zakresu. Otwarcie nowego zakresu to po prostu dołożenie kolejnego elementu do listy, a zamknięcie polega na usunięciu ostatnio odłożonego elementu z listy. W tym sensie lista pełni rolę stosu z tym wyjątkiem, że możemy ją przeszukiwać nie usuwając z niej elementów (standardowa klasa std::stack<T> nie zapewnia takiej możliwości, nawet przez iteratory).

Warto zauważyć, że w tym przypadku liczba całkowita nie nadaje się jako indeks do tablicy symboli, gdyż np. indeks w postaci liczby 2 w każdym poziomie zagnieżdżenia może odpowiadać zupełnie innemu symbolowi (innymi słowy iiczba nie definiuje jednoznacznie symbolu we wszystkich zakresach). Weźmy na przykład jakąś zmienną globalną o nazwie z którą wpisaliśmy do tablicy symboli pod pozycję 3. Jeśli teraz otworzymy nowy zakres, w którym będzie nowa zmienna o nazwie z, to ona może się pojawić w tej nowej tablicy pod zupełnie innym indeksem i przeszukiwanie pod kątem znalezienia najbardziej zagnieżdżonej deklaracji zmiennej z posiadając tylko indeks liczbowy staje się niewykonalne.

Najbardziej naturalną implementacją dla takiego podejścia wydaje się być zastosowanie indeksowania nazwami. Ma to tę wadę, że nawet stałym liczbowym musimy nadać jakieś nazwy. Oczywiście trzeba pamiętać, że takie nazwy nie mogą być legalnymi nazwami Pascala, bo co będzie jeśli wymyślimy sobie, że nasze stałe będą się nazywać tmp+numer kolejny, a kod Pascala będzie zawierał np. zmienną tmp1 która pokryje się z nazwą używaną przez nas wewnętrznie? Nie jest to aż tak kłopotliwe, bo można łatwo wymyślić przedrostek, który nie może się pokryć z nazwami w kodzie Pascala (np. "#tmp", "$liczba", "*numer itp".), ale trzeba to zrobić. Warto przechowywać jakiś licznik stałych i zwiększać go za każdym razem, nadając nazwy np. w taki sposób:

try
{
    //tu lexical_cast konwertuje liczbę do typu std::string
    std::string nazwaStałejLiczbowej = std::string("stała") + boost::lexical_cast<std::string>(numerZmiennej);
 
    ++numerZmiennej;
}
catch(const boost::bad_lexical_cast& e) //konwersja się nie powiodła
{
    //obsługa wyjątku
}

Oczywiście jeśli chcemy korzystać z funkcji lexical_cast, musimy zainstalować podstawowe nagłówki bibliotek boost (w Debianopochodnych wystarczy pakiet libboost-dev, w innych dystrybucjach GNU/Linuxa lub Cygwinie - nie wiem). Jeśli nie chce się komuś instalować boosta, to może skorzystać z dowolnego innego mechanizmu zamiany liczby na łańcuch tekstowy. przykładowa trywialna funkcja została zaprezentowana np. na stronie C++ FAQ Lite.

Następna sprawa, to: jak indeksować za pomocą napisów? Do tego celu najlepiej nadaje się typ std::map, z std::string jako kluczem i wpisem jako wartością. Mapa posiada własną metodę do wyszukwiania po kluczach i nie pozwala na duplikowanie kluczy, więc wydaje się dobra do tego celu.

Najogólniej diagram klas takiego rozwiązania może się przedstawiać następująco:

ScopesInList.png

Wskazane na diagramie klasy tworzą tylko ramy dla rozwiązania. Co najmniej kilka klas trzeba będzie dodać. Także należy pomyśleć o metodach dla każdej klasy.

Zalety:

  1. Łatwe zamykanie zakresów.
  2. Przejrzysta i modułowa struktura danych.

Wady:

  1. dostęp tylko do aktualnego zakresu, co powoduje trudności z otworzeniem zakresu we właściwym miejscu (np. jeśli mamy w parserze regułę typu subprogram_head -> function id arguments : standard_type ; to nazwa funkcji należy do zakresu globalnego, natomiast argumenty już do lokalnego). Żeby poradzić sobie z tym problemem, można zadeklarować jakiś przełącznik boolowski, który ustawiamy na true jeśli napotkamy w lekserze na "procedure" lub "function" i kiedy napotykamy na id go sprawdzamy. Jeśli będzie true, to dodajemy id do tablicy symboli, potem otwieramy nowy zakres i ustawiamy przełącznik na false. Mimo że działa, jest to troszkę mało eleganckie rozwiązanie.
  2. Trudności z przenoszeniem zmiennych między zakresami (jeśli istnieje taka potrzeba)
  3. Bardziej rozbudowana struktura danych
  4. Wymagana dobra znajomość biblioteki standardowej (m.in. zastosowania iteratorów, standardowych par itd.).

proponowany typ YYSTYPE: std::list<std::string>, gdyż czasami musimy zwrócić "w górę" w parserze więcej niż jeden indeks tablicy symboli (np. kiedy mamy argumenty, to zanim poznamy typ, musimy zebrać gdzieś wszystkie nazwy). W przypadku gdy wystarczy pojedyncza wartosć, po prostu zwracamy listę z jednym elementem. Alternatywnym wyjściem (opisanym już w tym artykule) jest zrobienie osobnej listy na argumenty itp. natomiast przyjęcie za YYSTYPE pojedynczego stringa.

Zakres jako przełącznik

Oryginalny Pascal pozwala na takie akcje jak definicja procedury w procedurze itp., dzięki czemu stopień zagnieżdżenia może być teoretycznie dowolny, ale nasz podzbiór dopuszcza tak naprawdę dwa - globalny i lokalny. To może spowodować, że komuś nie będzie chciało się bawić w jakieś listy tablic symboli, tylko po prostu zrobi jedną, za to każdy wpis będzie zawierał informacje, czy ma zasięg globalny czy lokalny.

Najbardziej intuicyjna metoda implementacji opiera się na wektorze, który zawiera wpisy. Pojedynczy wpis będzie podobny jak w poprzednim przypadku, z tym wyjątkiem, że będzie musiał również zawierać informację i zakresie. Identyfikator zakresu (to co mówi nam, jaki jest zakres danego wpisu) może być jakąś liczbą naturalną, albo, z uwagi na to, że mamy dwa zakresy, po prostu typem wyliczeniowym (o możliwych wartościach: lokalny/globalny).

Sam interfejs (czyli metody publiczne) takiej tablicy jest właściwie podobny jak w poprzednim podejściu - Największe różnice występują na poziomie implementacji, np. przeszukiwaniu, zamykaniu, otwieraniu zakresów itd.

ScopeSwitch.png

Zalety:

  1. Prostsza i bardziej "łopatologiczna" implementacja
  2. Mniej złożona struktura danych
  3. Łatwiejsze przenoszenie zmiennych między zakresami, jeśli trzeba

Wady:

  1. dostęp tylko do aktualnego zakresu, co powoduje trudności z otworzeniem zakresu we właściwym miejscu (np. jeśli mamy w parserze regułę typu subprogram_head -> function id arguments : standard_type ; to nazwa funkcji należy do zakresu globalnego, natomiast argumenty już do lokalnego). Żeby poradzić sobie z tym problemem, można zadeklarować jakiś przełącznik boolowski, który ustawiamy na true jeśli napotkamy w lekserze na "procedure" lub "function" i kiedy napotykamy na id go sprawdzamy. Jeśli będzie true, to dodajemy id do tablicy symboli, potem otwieramy nowy zakres i ustawiamy przełącznik na false. Mimo że działa, jest to troszkę mało eleganckie rozwiązanie.
  2. Bardziej rozbudowana struktura danych

proponowany typ YYSTYPE: std::list<std::string>, albo std::list<int>, chociaż tego drugiego nie jestem pewien. Reszta uwag jak w poprzednim punkcie. Oczywiście obowiązuje to co napisałem dla poprzedniego podejścia (że można zrobić globalną listę i przerzucać tylko pojedyncze wartości)

Dwie tablice symboli - lokalna i globalna.

Jest to rozwiązanie pośrednie w stosunku do dwóch poprzednich. Mamy dwie tablice i wpisujemy do jednej albo do drugiej. Kiedy zamykamy zakres, po prostu czyścimy odpowiednią tablicę (właściwie to tylko tablicę lokalną, bo główny zakres nie jest zamykany do końca przetwarzania programu). Wybór tablicy może się w najbardziej prymitywnym przypadku opierać o globalny przełącznik (czyli zmienną o dwóch stanach, np. jakiegoś typu wyliczeniowego), który będziemy przestawiać podczas otwierania o zamykania zakresów i z niego odczytywać do której tablicy mamy dodać symbol. Ma to tę wadę, że wszędzie gdzie będzie wpisywany do tablicy jakiś symbol trzeba będzie sprawdzać tę zmienną. Bardziej elegancki sposób polegać może na zdefiniowaniu wskaźnika, który będzie wskazywać albo na globalną, albo na lokalną tablicę symboli (bo obie mogą być tego samego typu) i za jego pośrednictwem wpisywaniu symbolu do odpowiedniej tablicy. Podczas zamykania/otwierania zakresu ten wskaźnik przestawiany byłby na odpowiednią tablicę.

Szczerze pisząc nie próbowałem tego sposobu i nie wiem, jak się sprawdzi w praktyce, ale ponoć był już wykorzystany w niejednym projekcie. Ponoć nawet jeden z prowadzących go poleca, zatem może się okazać najprostszym.

Generowanie kodu.

Generowanie kodu polega na tworzeniu napisu (najlepiej typu std::string), który następnie wypisuje się do pliku lub na ekran.

Najlepiej zacząć od przykładowych plików dostarczonych z binarnym kompilatorem. Na początek wystarczy t0.pas. Mozna zacząć od implementacji operatora :=, potem operatory arytmetyczne dwuargumentowe (można je załatwić za jednym podejściem). Na razie lepiej zignorować adresy zmiennych i roboczo każdemu symbolowi jako adres przypisywać kolejną liczbę, żeby sprawdzić, czy występują w odpowiednich miejscach.

Określanie adresu zmiennej w pamięci.

Określanie adresu zmiennej w pamięci przebiega różnie dla zmiennych zakresu lokalnego, zmiennych procedur oraz dla referencji.

TypRozmiaruZmiennych policzRozmiarZmiennych(nazwaSymboluDoPominięciaPodczasLiczenia domyślnie równa "")
{
    TypRozmiaruZmiennych całkowityRozmiar = 0;
    Iteruj po zakresie i dla każdego wpisu z zakresu:
    {
          jeśli wpis nie dotyczy stałej liczbowej argumentu funkcji (w tym wartości zwracanej)
          oraz jego nazwa nie jest NazwąSymboluDoPominięciaPodczasLiczenia
          {
              calkowityRozmiar += wpis.rozmiar;
          }
    }
    zwróć całkowityRozmiar;
}

Pojawia się pytanie, jak stwierdzić, czy wpis nie dotyczy argumentu ani wartości zwracanej. Sprawdzanie czy wpis jest referencją nie jest dobrym pomysłem, gdyż referencje używane są również do elementów tablic. Ja to zrobiłem w najbardziej ordynarny sposób - jeśli adres (przechowywany jako string) zawiera znak '+', to jego rozmiaru nie uwzględniam:D:D:D.

Następna pytanie jakie się może pojawić brzmi: po co przekazywać tą nazwę symbolu do pominięcia? Otóż w momencie gdy chcemy policzyć adres dla jakiejś zmiennej, ona już jest w tablicy symboli, więc gdybyśmy tego nie uwzględnili, to zostalaby wzięta pod uwagę podczas liczenia rozmiaru. Oczywiście nie o to nam chodzi.

Adresy zmiennych zakresu globalnego i lokalnego - algorytm.

void przydzielAdres(wpis)
{
    Jeśli adres nie został już przydzielony
    {
        jeśli wpis nie dotyczy stałej liczbowej
        {
            jeśli aktualny zakres to zakres globalny
            {
                wpis.adres = policzRozmiarZmiennych(wpis.nazwaSymbolu);
            }
            w przeciwnym wypadku
            {
                wpis.adres = "BP-" + policzRozmiarZmiennych();
            }
        }
    }
}

Zauważmy, że przy generowaniu adresu dla zmiennych globalnych nie podajemy nazwy symbolu do pominięcia. Dzieje się tak dlatego, iż stos w zakresie lokalnym rośnie w kierunku ujemnym, zatem pierwsza zmienna lokalna będzie w adresie (BP - jej rozmiar). Jeśli wciąż nie rozumiesz, spójrz na pierwsze slajdy z wykładu dotyczące generacji kodu dla funkcji.

Adresy argumentów i wartości zwracanych.

Ja wklepywałem je "ręcznie". Nie ma chyba żadnego zautomatyzowanego algorytmu. Na szczęście jest to łatwe, gdyż liczbę wpisów znamy z miejsca i ona się nie zmienia (w przeciwieństwie do zmiennych, których liczby nie znamy dopóki nie wygenerujemy kodu funkcji). Dla procedur oczywiście należy pominąć wartość zwracaną.

Konwersja typów.

Konwersję typów niestety trzeba robić osobno dla operatorów dwuargumentowych i osobno dla przypisania. Wersję dla operatorów dwuargumentowych można znaleźć na slajdzie 139 w materiałach do wykładu. Natomiast algorytm wydzielony jako osobną funkcję prezentuję poniżej (to tylko jeden pomysłów, prawdopodobnie można to rozwiązać lepiej):

Para<TypIndeksu, TypIndeksu> konwertujTypy(Typindeksu indeksDoWartosciPierwszej, TypIndeksu indeksDoWartościDrugiej)
{
    pobierz wpisy dla obu indeksów;
    jeśli drugi wpis to funkcja:
    {
                 pobierz z wpisu funkcji indeks do jej "wartości zastępczej";
                 zwróć konwertujTypy(indeksDoWartosciPierwszej, indeksDoWartościZastępczej);
    }
    w innym wypadku jeśli typy obu wpisów są takie same:
    {
                 zwróć parę <indeksDoWartosciPierwszej, indeksDoWartościDrugiej>;
    }
    w innym wypadku:
    {
    utwórz zmienną tymczasową o indeksie indeksDoZmiennejTymczasowej;
                pobierz wpis dla zmiennej tymczasowej;
 
                jeśli wpis pierwszy ma typ INTEGER a drugi ma typ REAL:
    {
                    wygeneruj inttoreal wpisPierwszy.adresLubWartość, wpisTymczasowy.adres;
                    zwróć parę <indeksDoWartościTymczasowej, indeksDoWartościDrugiej>;
    }
    w innym wypadku jeśli wpis pierwszy ma typ REAL a drugi ma typ INTEGER:
    {
                    wygeneruj inttoreal wpisDrugi.adresLubWartość, wpisTymczasowy.adres;
                    zwróć parę <indeksDoWartościPierwszej, indeksDoWartościTymczasowej>;
    }
    w innym wypadku
    {
                    błąd semantyczny;
    }//dopisać o ? w stringu
    }
}

Na wynikach takiej funkcji można już bezpiecznie wywołać funkcję generującą kod dla operatora dwuargumentowego.

Generowanie kodu indeksowania tablic.

Z indekowaniem tablic jest o tyle wygodnie, że możesz zapomnieć o tym, że w ogóle istnieje, aż do momentu kiedy faktycznie będziesz je musiał zaimplementować. Kiedy już to się stanie, wystarczy, że wklepiesz odpowiedni kod do produkcji:

variable : ID '[' expression ']'

i wszystko będzie działać OK (pod warunkiem, że wziąłeś sobie do serca to co napisałem przy okazji algorytmu zliczania rozmiaru zmiennych).

Generowanie kodu dla instrukcji warunkowych

Tu pojawia się problem który bez odpowiedniej wiedzy jest nie do przeskoczenia. Otóż assembler dla np. takiego kodu w Pascalu:

program sort(input,output);
var i,j,k:integer;
var x,y,z:real;

begin
  if (i > j) then
    x:=0.0
  else
    x:=1.0

powinien wygenerować się następujący kod w assemblerze:

        jump.i #lab0
lab0:
        jg.i 0, 4, #lab1
        mov.i #0, 36
        jump.i #lab2
lab1:
        mov.i #1, 36
lab2:
        je.i 36, #0, #lab3
        mov.r #0.0, 12      ; x := 0.0
        jump.i #lab4
lab3:
        mov.r #1.0, 12      ; x := 1.0
lab4:
        exit

W kodzie zaznaczyłem te dwie linijki, które odpowiadają za przypisania z programu w Pascalu. Jak widać, trzeba wstawić coś przed pierwszą, coś pomiędzy nimi oraz coś za ostatnią. Problem polega na tym, że za if..then..else odpowiada następująca produkcja:

IF expression THEN statement ELSE statement

Skoro bison stosuje analizę wstępującą, to po dopasowaniu całej tej produkcji kod dla obu symboli statement będzie już wygenerowany i nie będzie można wstawić czegoś w środek. Na szczęście istnieje pewien sposób na poradzenie sobie z tym bez konieczności grzebania w środku generowanego kodu. Sposób ten pochodzi znowu od dr Jabłońskiego i jest moim zdaniem jedynym słusznym rozwiązaniem tej kwestii. Mianowicie, na co niewielu z nas zwracało uwagę wcześniej, bison umożliwia wstawianie akcji semantycznych w środek produkcji, czyli:

 IF expression 
{ 
    coś
} 
THEN statement
{
   coś innego
}
ELSE statement
{
   jeszcze coś innego
}
;

Czyli można "wstrzelić" się w środek i wygenerować odpowiednie etykiety i skoki. Pozostaje jeszcze jedna rzecz do powiedzenia - pierwszą część kodu należy wygenerować już w produkcji expression : simple_expression RELOP simple_expression, czyli dla naszego przykładu wyglądałoby to tak:

expression : simple_expression RELOP simple_expression
{
        jg.i 0, 4, #lab1
        mov.i #0, 36
        jump.i #lab2
lab1:
        mov.i #1, 36
}
;

statement : IF expression 
{ 
        je.i 36, #0, #lab3
} 
THEN statement
{
        jump.i #lab4
lab3:
}
ELSE statement
{
lab4:
}

te dwie instrukcje mov.r wygenerują się gdzie indziej i to nas nie obchodzi. Takie potraktowanie sprawy automatycznie załatwi nam problem z warunkami złożonymi, o ile tylko zaimplementuje się or oraz and jako normalne operatory dwuargumentowe.

Generowanie kodu dla instrukcji warunkowych zawierających not.

Ten problem pojawia się, gdy napotykamy na plik t14.pas, gdzie pojawia się konstrukcja not warunek. Teoretycznie można by to zrobić tak samo jak and oraz or, ale sęk w tym, że wirtualna maszyna (przynajmniej w oryginale) nie zawiera instrukcji not.i/r (a zawiera and.i/r oraz or.i/r). Jeśli przyjrzymy się kodowi generowanemu przez binarny kompilator ze strony przedmiotu, to zauważymy, że wyprawia on z okazji not jakieś cudy-niewidy, ktorych ja przynajmeniej nie zrozumiałem. Mój sposób na poradzenie sobie z tym problemem był prosty - do mojej maszyny wirtualnej dołożyłem instrukcję not, bazując na and (tylko że not jest dwuargumentowa, a nie trójargumentowa) i generację kodu w parserze zrobiłem analogicznie jak dla and i or :>.

Obliczanie liczby którą należy wpisać zaraz obok enter.i i wpisywanie tej liczby.

Jak wiadomo choćby z kolokwium i zajęć laboratoryjnych, prolog funkcji/procedury można wygenerować dopiero po wygenerowaniu całego ciała (bo nie wiadomo wcześniej, ile miejsca na zmienne tymczasowe będziemy potrzebować). Jak więc wrócić spowrotem do prologu funkcji, kiedy już wygenerowaliśmy cały kod? Generalnie jest jeden trywialny (choć pewnie nie najbardziej optymalny) sposób na poradzenie sobie z tym: po prostu generujemy linijkę z enter.i w taki sposób:

enter.i     #?

Kiedy już wygenerujemy całe ciało funkcji, za pomocą przedstawionej już wcześniej funkcji policzRozmiarZmiennych() pobieramy rozmiar zmiennych, i teraz za pomocą dwóch metod klasy std::string (bo zakładam, że cały kod generujesz do stringa, a nie do strumienia): find() oraz replace() zamieniasz znak zapytania na ten rozmiar. Jest to trywialne, ponieważ zawsze generujesz jedną funkcję na raz (oczywiste:>), więc postępując w ten sposób zawsze będziesz mieć w tym stringu najwyżej jeden znak zapytania.

Wstawianie etykiety lab0.

Od etykiety lab0 rozpoczyna się wykonanie programu. Powinna ona być wstawiona w miejsce pierwszego begin w zakresie globalnym, jednak zamiast pisać instrukcje warunkowe, można w prosty sposób zapewnić, że etykieta ta zawsze będzie wstawiana we właściwym miejscu, wcinając się w najogólniejszą produkcję:

program -> PROGRAM ID ( identifier_list ) ; declarations subprogram_declarations compound_statement .

Ten ostatni compound_statement w powyższej produkcji odpowiada właśnie blokowi głównemu, więc możemy "wciąć się" w tę produkcję z akcją semantyczną w następujący sposób:

program -> PROGRAM ID ( identifier_list ) ; declarations subprogram_declarations
{
    wstaw do kodu lab0
}
compound_statement .

astralastral

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-Share Alike 2.5 License.