Metody realizacji języków programowania/MRJP Laboratorium

Autor: Marek Biskup (mbiskup@mimuw.edu.pl)

Wstęp

Tematem Laboratorium Metod Realizacji Języków Programowania jest zaimplementowanie kompletnego kompilatora języka Kotek.

Język kotek

Kotek jest obiektowym językiem programowania zbliżonym do języków takich jak Pascal czy Java. Podstawowe cechy Kotka to:

• obecność zwykłych konstrukcji takich jak pętle for i while, wyrażeń arytmetycznych, logicznych,
• silne typowanie - zgodność typów jest sprawdzana w czasie kompilacji,
• możliwość deklarowania funkcji,
• obecność struktur danych takich jak tablice i rekordy,
• możliwość deklarowania klas i tworzenia obiektów,
• lokalne deklaracje funkcji i klas,
• dynamiczna alokacja obiektów, rekordów i tablic (na stercie).

Gramatyka Kotka

Gramatyka języka jest opisana na stronie Gramatyka Kotka

Semantyka Kotka

Semantyka języka jest opisana na stronie Semantyka Kotka

Zadania

Zadanie 0: Wybierz narzędzia i platformę docelową

Wybierz platformę docelową kompilatora języka Kotek. Zalecane są platforma x86 i system operacyjny Linux (kod byłby generowany w asemblerze x86, np. w formacie akceptowanym przez kompilator gcc), bądź Maszyna Wirtualna Javy (kod generowany w asemblerze JVM, np. w formacie akceptowanym przez asembler Jasmin).

Następnie wybierz język programowania, w którym będzie pisany sam kompilator. Ten język nie ma żadnego związku z platformą docelową. Zorientuj się, jakie narzędzia są dostępne dla języka, na który się decydujesz.

• język C/C++: generator analizatorów leksykalnych lex lub flex, generator parserów yacc lub bison,
• język Java: generator analizatorów leksykalnych JFlex, generator parserów Coco, CUP, Javacc, ANTLR,
• język Ocaml: ocamllex, ocamlyacc.

Niektóre narzędzia wspierają też budowanie drzewa składniowego i jego przekształcanie.

Zadanie 1: Analizator leksykalny

Napisz analizator leksykalny do kompilatora języka Kotek. Użyj generatora analizatorów leksykalnych (takich jak lex dla C) generującego kod w języku, w którym będziesz pisał kompilator. Analizator powinien rozpoznawać konstrukcje leksykalne Kotka: identyfikatory, operatory, stałe napisowe, komentarze (jeśli Twój generator analizatorów leksykalnych umożliwia obsługę zagnieżdżonych komentarzy, to powinny one być usuwane już na tym etapie).

Przetestuj swój analizator leksykalny pisząc program, który zamienia ciąg wejściowy na ciąg leksemów, np. dla wejścia:

asdf + qwer * != ( "napis\"napis"

wynikiem działania programu testowego powinno być:

IDENTYFIKATOR("asdf") OPERATOR_PLUS IDENTYFIKATOR("qwer") OPERATOR_RAZY
OPERATOR_RÓŻNE OPERATOR_LNAWIAS, STRING("napis\"napis")

lub równoważny zapis.

Zadanie 2: Analizator składniowy

Napisz parser języka Kotek wykorzystując generator parserów (np. yacc dla C). Wynikiem analizy składniowej ma być drzewo składni, w którym każdy węzeł odpowiada pewnej produkcji w kodzie źródłowym (lewej stronie), dziećmi węzła są natomiast elementy z prawej strony produkcji. Liśćmi są terminale.

Dopuszczalne są modyfikacje drzewa składniowego, które upraszczają jego strukturę, a nie gubią żadnych istotnych informacji. Np. zamiast przechowywania listy deklaracji jako węzła, który zawiera pojedynczą deklarację i drugą listę deklaracji, dopuszczalne (a nawet zalecane) jest używanie standardowych kontenerów języka programowania, w którym kompilator jest pisany.

Jeśli używasz języka obiektowego, zalecane jest stworzenie oddzielnej klasy dla każdego typu produkcji. Obiekty należy w miarę możliwości i potrzeb powiązać związkami dziedziczenia. Zwykle dobrym pomysłem jest stworzenie oddzielnej klasy dla lewej strony produkcji i podklas dziedziczących z niej dla każdej prawej strony produkcji, w której ta lewa strona występuje. Na przykład możemy mieć klasę Instrukcja, z której dziedziczą m.in. klasy Przypisanie, Blok, PustaInstrukcja i ZłożonaInstrukcja. Z kolei z klasy ZłożonaInstrukcja będą dziedziczyć klasy InstrukcjaIfElse, InstrukcjaIf oraz InstrukcjaWhile.

Hierarchia klas węzłów drzewa składniowego powinna mieć wspólny korzeń (nazwany np. Węzeł). Ten węzeł będzie zawierał abstrakcyjne metody, które są wymagane w innych węzłach, np. metoda gen(), generująca kod na maszynę docelową, metoda sem() przeprowadzająca analizę semantyczną (uwaga: jeśli analiza semantyczna będzie robiona w kilku przebiegach, to warto stworzyć więcej metod sem, np. sem1 i sem2).

Napisz program testujący parser. Program testujący powinien działać jak pretty printer, tzn. wypisywać treść programu na podstawie drzewa składniowego zawartego w pamięci.

Zadanie 2.a: Poprawność wyrażeń na etapie parsowania

Gramatyka języka dopuszcza pewne wyrażenia, które nie są poprawne, np:

funkcja(param)(param2)
zmienna[indeks](param)

Niepoprawność wynika z tego, że funkcja nie może być wynikiem innej funkcji, funkcja nie może też być przechowywana w tablicy. Czy można zmienić gramatykę tak, aby wykluczała podane wyrażenia? Jakie podejście preferujesz: sprawdzanie poprawności tych wyrażeń na etapie parsera czy analizy semantycznej? Podaj zalety i wady obu metod.

Zadanie 2.b: Poprawność przypisań

Obecna postać produkcji przypisania:

Instrukcja ::= WyrazeniePostfiksowe ":=" Wyrazenie ";";

dopuszcza pewne błędne przypisania, np.

"tekst" := 8;

Czy można tak zmienić gramatykę, aby przypisanie zawsze było poprawne? Czy pozwoli to wyeliminować analizę semantyczną tego fragmentu kodu źródłowego?

Zadanie 3: Tablica symboli

Do Twojego kompilatora dopisz kod tworzący tablicę symboli z każdej listy deklaracji. Połącz tablice symboli w graf zgodnie z regułami widoczności nazw. Tablica symboli powinna mieć odniesienie do tablicy symboli nadrzędnej funkcji lub klasy, w której nasza funkcja (lub klasa) została zadeklarowana. W przypadku tablicy symboli klasy dodaj jeszcze odnośniki do tablicy symboli nadklasy. Określ kolejność szukania nazw (najpierw nadklasa, czy nadfunkcja?).

Dla każdej deklaracji określ rozmiar zużytej pamięci, np. w 32 bitowej architekturze x86 zmienne typu int zużywają 4 bajty, zmienne string również 4 bajty (napis jest reprezentowany przez wskaźnik do ciągu znaków zakończonego zerem) i tak samo zmienne typu obiektowego, tablicowego i rekordowego. Deklaracje funkcji, rekordów, typów i klas nie zajmują żadnego miejsca (w Kotku nie są z nimi skojarzone żadne modyfikowalne wartości). Oczywiście rozmiar pamięci zależy od docelowej architektury. Dla każdej kolejnej deklaracji określ jej położenie w pamięci względem pierwszego elementu. Na przykład na wspomnianej wcześniej architekturze dla deklaracji:

var x : int;
var y : string;
function f() : void {return;}
var z : int;

położenie zmiennej x to 0, zmiennej y to 4, funkcji f to 4 (choć ta wartość nie będzie do niczego potrzebna i można ją opuścić), a zmiennej z to 8.

Tablica symboli powinna udostępniać następujące funkcje:

• znajdowanie identyfikatora - określenie, w której tablicy symboli jest zawarty,
• określanie pozycji identyfikatora w tablicy symboli,
• podawanie całkowitego rozmiaru wszystkich deklaracji z tablicy symboli.

Rozbuduj pretty printer z poprzedniego zadania tak, aby obok każdego identyfikatora wypisywał, z której tablicy symboli identyfikator pochodzi i jakie jest jego przesunięcie w tej tablicy symboli. Nie musisz na razie uwzględniać operatora kropki (odwołanie do pól obiektu). Określ sam czytelny format danych wyjściowych.

Przetestuj swój kod na trzech przykładach. Przykłady powinny zawierać wszystkie następujące konstrukcje: dziedziczenie, funkcje lokalne, zmienne lokalne, przysłanianie zmiennej, argumenty funkcji, obiekty lokalne wewnątrz funkcji i innych obiektów, rekordy.

Zadanie 4: Analiza semantyczna

Do swojego kompilatora dopisz kod odpowiedzialny za analizę semantyczną. Głównym zadaniem analizy semantycznej jest określenie typu każdego węzła (niektóre konstrukcje nie mają typu; wtedy typem węzła będzie void) oraz sprawdzanie poprawności typów. Dodatkowo musisz sprawdzać wszystkie inne cechy semantyczne 'Kotka'. Opracowanie kompletnej listy wszystkich rzeczy, które należy sprawdzać jest skomplikowane, więc nie przejmuj się, jeśli o czymś zapomnisz. Zawsze możesz uzupełnić kod analizy semantycznej w czasie pisania generatora kodu. Zajrzyj do zadań z tego rozdziału - być może pomogą Ci lepiej zrozumieć zawiłości semantyki języków programowania.

Na początku przyjmij, że nie jest dozwolona deklaracja klas wewnątrz innych klas i procedur. Następnie, rozwiązując poniższe podzadania, zastanów się jakie ograniczenia należy wprowadzić, aby definiowanie klas wewnątrz klas i procedur miało sens.

Rozszerz program testowy kompilatora (który po poprzednim zadaniu wypisuje tablicę symboli, z której pochodzi każdy symbol wraz z przesunięciem) o wypisywane typu każdego identyfikatora. Dopisz obsługę rekordów i obiektów (operator kropki).

Zadanie 4.a: Klasy wewnętrzne procedur

W tym zadaniu rozważamy jedynie procedury, które nie są metodami klasy ani nie są zawarte z jakiejś metodzie.

Klasy zadeklarowane lokalnie wewnątrz procedur przydają się do zmniejszenia liczby globalnych nazw oraz do ścisłego określenia zakresu użycia klasy. Udostępnienie takich konstrukcji prowadzi do dodatkowych problemów implementacyjnych podobnych do problemów z zagnieżdżonymi procedurami.

Pytania:

• Podaj przykład programu, w którym występuje funkcja zwracająca instancję lokalnie zadeklarowanej klasy.
• Czy do zewnętrznych zmiennych można odwoływać się za pomocą tablicy display, jak w przypadku procedur?
• Język Java dopuszcza korzystanie z lokalnych zmiennych procedury, ale tylko zmiennych zadeklarowanych jako final. Dlaczego takie rozwiązanie upraszcza implementację?
• Czy dostęp do zmiennych globalnych utrudnia implementację?
• Jakie jest możliwe rozwiązanie ogólnego przypadku? Czy widzisz związek z językami funkcyjnymi?

Zadanie 4.b: Klasy wewnątrz klas

Kolejnym krokiem do zwiększenia modularności jest dopuszczenie deklaracji klasy wewnątrz klas (na razie nie wewnątrz metody klasy). Taka klasa wewnętrzna miałaby dostęp do metod i zmiennych klasy, wewnątrz której jest zadeklarowana.

• Zaproponuj sposób implementacji dla takich klas.
• Kiedy jest możliwe utworzenie instancji klasy wewnętrznej bez klasy zewnętrznej?

Zadanie 4.c: Dowolne, lokalne deklaracje klas

Zastanów się nad sposobem implementacji dowolnie zagnieżdżonych deklaracji klas. To zadanie jest połączeniem dwóch poprzednich.

• Jakie informacje musi nieść ze sobą klasa zadeklarowana wewnątrz innej klasy (być może wewnątrz jakiejś metody tamtej klasy lub wewnątrz funkcji zdefiniowanej w metodzie)?
• Jakie informacje musi nieść ze sobą klasa zadeklarowana wewnątrz pewnej funkcji (być może funkcja jest metodą innej klasy)?

Zadanie 4.d: Inicjalizacja zmiennych

Aby język był bardziej bezpieczny chcielibyśmy wyeliminować możliwość użycia niezainicjalizowanych zmiennych. W tym celu modyfikujemy deklaracje zmiennej tak, aby podanie wartości przy deklaracji było obowiązkowe:

var x : int = 5;
var y : int = 3*x+5;

a nie

var x : int;     // zle! - brak wartości
var y : int;     // zle! - brak wartości

Zastanów się, jakie ograniczenia należy wprowadzić na wyrażenia użyte do inicjalizacji aby język był całkowicie bezpieczny. Na przykład poniższa sekwencja deklaracji prowadzi do błędu:

var x : int = y + 4;
var y : int = x + 4;

Przemyśl następujące możliwości:

• dopuszczenie tylko wyrażeń stałych,
• dopuszczenie jedynie zmiennych zadeklarowanych wcześniej na tym samym poziomie,
• dopuszczenie jedynie zmiennych i funkcji zadeklarowanych wcześniej na tym samym poziomie,
• dopuszczenie jedynie zmiennych zadeklarowanych wcześniej na tym samym poziomie i wszystkich funkcji z tego poziomu,
• dopuszczenie zmiennych zadeklarowanych wcześniej na tym samym poziomie i wszystkich funkcji,
• dopuszczenie wszystkich zmiennych zadeklarowanych wcześniej na tym poziomie oraz wszystkich zmiennych i funkcji zadeklarowanych wyżej,
• oznaczanie zmiennych niezainicjalizowanych i sprawdzanie bycia zainicjalizowaną przy każdym odwołaniu,

Odpowiedz na pytania:

• Która z możliwości daje największe bezpieczeństwo?
• Która ma duży narzut czasu wykonania?
• Która jest najbardziej elastyczna z punktu widzenia programisty piszącego w Kotku?
• Które z nich pozwalają obejść zabezpieczenia?
• Jakie rozwiązanie zostało przyjęte w języku Java?

Weź pod uwagę jakie zmienne i funkcje są dostępne z wewnątrz funkcji.

Zadanie 5: Generowanie kodu

Napisz ostatni fragment kompilatora - generator kodu. Dla uproszczenia generuj kod od razu na maszynę docelową i pomiń optymalizację. Uprość też maksymalnie alokację rejestrów.

Możesz sprawdzić jak wygląda przykładowy kod używając istniejącego kompilatora do wygenerowania plików asemblera (np. w gcc opcja -s przy kompilacji). Możesz użyć istniejących kompilatorów do wygenerowania kodu dla operacji wejścia/wyjścia (read i write) oraz dla wygenerowania kodu startu i końca Twojego programu.

Napisz programy w Kotku testowe testujące wszystkie konstrukcje języka i sprawdź ich poprawne działanie po skompilowaniu Twoim kompilatorem.

Zadanie 5.a: Sprawdzanie poprawności rzutowania

W językach obiektowych często zachodzi potrzeba rzutowania na podklasę obiektu. Najprostszą metodą sprawdzania poprawności rzutowania jest sprawdzenie, czy wskaźnik do tablicy metod wirtualnych wskazuje na tablicę dla szukanego typu. Jeśli nie, to musimy sprawdzić również nadklasę naszego obiektu (wskaźnik do tablicy metod wirtualnych nadklasy możemy przechowywać w samej tablicy metod wirtualnych. Takie sprawdzenie wymaga przejścia po nadklasach obiektu i może być czasochłonne.

Zaprojektuj metodę sprawdzającą przynależność obiektu do klasy w stałym czasie.

Wskazówki:

• załóż skończoną wysokość hierarchii klas,
• rozważ dodanie pewnych informacji do każdej klasy.

Zadanie 5.b: Metody i zmienne statyczne

Niektóre języki programowania obiektowego (np. C++, Java) dopuszczają statyczne metody i pola klas, a także metody finalne, czyli nie podlegające przedefiniowaniu w podklasach.

Czym może różnić się kod wynikowy dla dostępu do statycznych pól, statycznych metod i finalnych metod od normalnego kodu? Jak takie właściwości pomagają w optymalizacji?

Zadanie 6: Rozszerzenia języka

Język Kotek w obecnej postaci jest raczej ubogi. Pożądane jest rozszerzenie go. Poniższe rozszerzenia nie muszą być wykonywane w podanej kolejności.

Zadanie 6.a: Typ logiczny

Dodaj do języka typ logiczny bool. Popraw analizę semantyczną tak, aby rozróżniać typy int i bool. Rozszerz gramatykę wyrażeń logicznych tak, aby

a || b || c
a && b && c
a && b || c

były poprawnymi wyrażeniami. Załóż priorytet && nad ||.

Zadanie 6.b: Typ zmiennoprzecinkowy

Dodaj do języka typy zmiennoprzecinkowe: float (pojedyncza precyzja) i double (podwójna precyzja). Zmień analizę semantyczną tak, aby uwzględniała nowe typy. Dodaj operator rzutowania na odpowiednie typy arytmetyczne:

(int) Wyrażenie
(float) Wyrażenie
...

Zadanie 6.c: Dodatkowe operatory

Dodaj nowe operatory dla wyrażeń, znane z języka C: ++, --, += (i pokrewne), operatory bitowe (|, &).

Zadanie 6.d: Automatyczne odśmiecanie

Zrób automatyczne odśmiecanie niedostępnych obiektów (zamiast instrukcji delete). Najlepiej użyj gotowego odśmiecacza (ang. Garbage Collector), choć możesz pokusić się o własną implementację

Zadanie 6.e: Rzutowanie i sprawdzanie typu obiektu

Rzutowanie oraz sprawdzanie typu są konstrukcjami często wykorzystywanymi w programowaniu obiektowym.

Rozszerz język o konstrukcję rzutowania:

(Podklasa) mojObiekt

i sprawdzania typu:

obiekt instance of klasa

Obie konstrukcje są wyrażeniami. Pierwsza daje typ Podklasa a druga typ int (wartość 0 lub nie-zero; jeśli do języka został dodany typ bool, to preferowany jest typ bool). Wartością wyrażenia rzutowania jest zero, jeśli obiekt nie jest instancją klasy na którą rzutowanie jest wykonywane (dynamiczne sprawdzanie typów przy rzutowaniu).

Zadanie 6.f: Ulepszenie read i write

Język Kotek zawiera bardzo prymitywne mechanizmy wejścia wyjścia. Rozszerz język o:

• możliwość odczytania wartości do pola rekordu lub klasy oraz do elementu tablicy (obecnie gramatyka dopuszcza czytanie tylko zmiennej atomowej)

read a[5];
read mojRekord.pole1;

• możliwość czytania i pisania wielu wartości na raz

read a[i], b[i];
write "a[5] = ", a[5];

Zadanie 6.g: Chronione pola klasy

Dodaj do języka mechanizm ochrony deklaracji klasowych. Deklaracja wewnątrz klasy będzie rozszerzona o modyfikator private, public lub protected (obok nazwy typu deklaracji):

var private x : int;
function public f() : bool;
type protected typ = { var x: int; var y : int };

Deklaracje public mają być widoczne zawsze, private tylko wewnątrz klasy a protected wewnątrz klasy i w podklasach.

Zadanie 6.h: Typy złożone dostępne bez deklaracji

W obecnej postaci język wymaga deklaracji typów złożonych przed ich użyciem, np.

type intArr = array of int;
var x : intArr;

zamiast

var x : array of int;

Rozszerz język o tę nową konstrukcję. Zwróć uwagę, że będzie możliwe napisanie:

var x : array of array of int;

Możesz też pokusić się o implementację anonimowych rekordów deklarowanych przy deklaracji zmiennej.

Zadanie 6.i: Inicjalizacja zmiennych

Zmień deklaracje zmiennych tak, żeby przy deklaracji w procedurze, rekordzie lub klasie (ale nie jako parametru funkcji) trzeba było (obowiązkowo!) podać wartość inicjalizacji zmiennej. Przykład:

var x : int := 50;

Przyjmij, że inicjalizacja tablic i rekordów następuje w momencie ich tworzenia (new):

y = new int[3*x] of 5;
z = new myRecord { field1 := 4, field2 := "ala ma kota"};

Przy inicjalizacji zmiennej dopuszczalne jest użycie zmiennej zadeklarowanej wcześniej na tym samym poziomie, wszystkich funkcji na tym poziomie oraz wszystkich zmiennych i funkcji zadeklarowanych na poziomach wyższych.

Wymagania implementacyjne i ocenianie

Aby zaliczyć laboratorium trzeba napisać działający kompilator. Na niższą ocenę nie musi on kompilować wszystkich konstrukcji języka. Implementacja rozszerzeń języka jest dodatkowo punktowana, ale nie wymagana do zaliczenia przedmiotu.

Ocena:	Wymagania:
5	Wszystkie podstawowe rzeczy (bez rozszerzeń języka) a dodatkowo operator instance of i rzutowanie (Zadanie 6.e). W szczególności muszą być zaimplementowane obiekty i lokalne deklaracje procedur (nie muszą być dostępne lokalne deklaracje klas).
4	Bez obiektów. Muszą być dostępne lokalne deklaracje procedur.
3	Bez obiektów i lokalnych deklaracji procedur.