Metody realizacji języków programowania/MRJP Laboratorium

Język kotek

Imperatywny, podobny do Pascala język programowania

Cechy:

• zwykłe konstrukcje: pętle for i while, wyrażenia arytmetyczne, logiczne
• silne typowanie
• funkcje
• tablice, rekordy
• klasy
• dynamiczna alokacja obiektów,rekordów i tablic (tylko na stercie)
• zagnieżdżone deklaracje funkcji
• zagnieżdżone (w klasach, funkcjach i metodach) deklaracje klas

Etapy pisania kompilatora

1. podstawowe konstrukcje: for, while, zmienne tylko typu int i string, proste

operacje arytmetyczne, funkcje globalne, rekurencja (też wzajemna)

1. rekordy, tablice,dynamiczna alokacja, zwalnianie jawne (delete)
2. lokalne procedury
3. klasy deklarowane na poziomie globalnym
4. klasy lokalne
5. deklaracje zmiennej z podaną wartością do inichalizacji

Możliwe rozszerzenia

1. zmienne double, boolean
2. dodatkowe operatory dla wyrażeń (++, --, +=, operatory bitowe, etc)
3. odśmiecanie zamiast delete

Gramatyka języka

Będzie skopiowana z LaTeXa

Wymagania implementacyjne i ocenianie

Na 3: Podstawowe konstrukcje, rekordy, tablice, dynamiczna alokacja

Na 4: Lokalne deklaracje procedur.

Na 5: Obiekty, operator instanceof, rzutowanie (por. zadanie FIXME).

Dodatkowo punktowane zadania.

• Lokalne deklaracje klas,
• Odśmiecanie zamiast jawnego delete

Zadania

Zadanie 1: 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 zakeklarowanych 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 2: Klasy wewnątrze 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, w przypadku procedur?
• Język Java dopuszcza korzystanie z lokalnych zmiennych procedury, ale tylko ale zmiennych zadeklarowanych jako final. Dlaczego takie rozwiązanie upraszcza implementację?
• Jakie jest możliwe rozwiązanie ogólnego przypadku? Czy widzisz związek z językami funkcyjnymi?

Zadanie 3: 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.
• Czy tworzenie instancji klasy wewnętrznej bez klasy zewnętrznej jest możliwe przy pewnych założeniach?

Zadanie 4: 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ą klasy)?

Zadanie 5: Poprawność wyrażeń na etapie parsowania

Grametyka 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, ani funkcja nie może 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 6: 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ę sematyczną tego fragmentu kodu źródłowego?

Zadanie 7: Sprawdzanie poprawności rzutowania

W językach obiektowych często zachodzi potrzeba rzutowania na inną podklasę. Najprostszą metodą sprawdzania poprawności rzutowania obiektów jest sprawdzenie, czy wskaźnik do tablicy metod wirtulanych 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

Metody i zmienne statyczne

Niektóre języki programowania obiektowego (np. C++, java) dopuszczają statyczne pola klas i metody, 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?

Rozszerzenia języka

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 wyżej na tym samym poziomie, wszystkich funkcji na tym poziomie oraz wszstkich zmiennych i funkcji zadeklarowanych na poziomach wyższych.

Odśmiecanie

Usuń konstrukcję delete i zrób zamiast tego automatyczne odśmiecanie.

Ulepszenie read i write

Język Kotek zawiera bardzo prymitywne mechanizmy wejścia wyjścia. Rozszesz 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];

Rzutowanie i sprawdzanie typu obiektu

Język nie zawiera rzutowania na typy. Jest to konstrukcja bardzo często wykorzystywana w programowaniu obiektowym, gdy trzeba zrzutować obiekt na typ podlkasy. Do tego jest też potrzebne sprawdzanie, czy obiekt jest elementem danej klasy.

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 (wartosc 0 lub nie-zero)

Typ bool

W języku nie ma typu bool. Dodaj ten typ do języka. Popraw analizę semantyczną tak, aby rozróżniać typy int i bool. Rozszeż wyrażenia logiczne tak, aby

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

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

Typ zmiennoprzecinkowy

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

Chronione pola klasy

Dodaj do języka mechanizm ochrony deklaracji klasowych. Deklaracja będzie rozszerzona o modyfikator private, public i 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.