Metody realizacji języków programowania/MRJP Laboratorium

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)

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

Struktura leksykalna języka Kotek

Identyfikatory

Identyfikatory to ciągi znaków zaczynające się literą, a zawierające dowolną kombinację liter, cyfr, i znaków podkreślenia _, poza słowami kluczowymi.

Literały

Literały napisowe <String> mają postać "x", gdzie x jest dowolnym ciągiem znaków z wyjątkiem ", chyba że jest on poprzedzony przez \.

Literały liczbowe <Int> to niepuste ciągi cyfr.

Zarezerwowane słowa i symbole

Zbiór zarezerwowanych słów to zbiór terminali z gramatyki. Te słowa kluczowe składają się ze znaków nie będących literami są zwane symbolami. Są one traktowane w inny sposób niż te, które są podobne do identyfikatorów. Reguły leksykalne są takie same jak w językach Haskell, C, i Java, włączając reguły dla najdłuższego dopasowania i konwencje odnośnie białch znaków.

Słowa kluczowe używane w Kotku to :

array	class	delete
do	done	else
endif	extends	function
if	int	new
null	of	program
read	return	string
super	then	this
type	var	void
while	write

Symbole używane w Kotku to:

;	{	}
=	,	:
(	)	:=
[	]	.
-	+	!
*	/	<
>	<=	>=
==	!=	||
&&

Komentarze

Komentarze jednolinijkowe zaczynają się // i trwają do końca linii. Komentarze wielolinijkowe są otoczone (* i *). Komentarze wielolinijkowe mogą być zagnieżdżone.

Struktura syntaktyczna języka Kotek

Nieterminale są otoczone < i >. Symbole ::= (produkcja), | (suma) i ε (pusta reguła) należą do notacji BNF (uwaga, symbol || jest z języka Kotek). Wszystkie inne sybmole są terminalami.

<Program>	::=	program ; <Ciało>
<Ciało>	::=	<ListaDeklaracji> <Blok>
<Blok>	::=	{ <ListaInstrukcji> }
<ListaDeklaracji>	::=	ε
	|	<Deklaracja> <ListaDeklaracji>
<Deklaracja>	::=	<DeklaracjaTypu>
	|	<DeklaracjaZmiennej>
	|	<DeklaracjaFunkcji>
	|	<DeklaracjaKlasy>
<DeklaracjaTypu>	::=	type <Ident> = <OpisTypu>
<OpisTypu>	::=	<Ident>
	|	{ <ListaDeklaracjiZmiennej> }
	|	array of <Typ>
<ListaDeklaracjiZmiennej>	::=	<DeklaracjaZmiennej>
	|	<DeklaracjaZmiennej> , <ListaDeklaracjiZmiennej>
<Typ>	::=	<Ident>
	|	string
	|	int
	|	void
<DeklaracjaZmiennej>	::=	var <Ident> : <Typ>
<DeklaracjaFunkcji>	::=	function <Ident> ( <DeklaracjaArgumentow> ) : <Typ> <Cialo>
<DeklaracjaArgumentów>	::=	<ListaDeklaracjiZmiennej>
	|	ε
<ListaInstrukcji>	::=	ε
	|	<Instrukcja> <ListaInstrukcji>
<Instrukcja>	::=	<Wyrażenie> ;
	|	<ZłożonaInstrukcja> ;
	|	<WyrażeniePostfiksowe> := <Wyrażenie> ;
	|	<Blok>
	|	delete <Wyrażenie> ;
	|	;
	|	read <Ident> ;
	|	write <Wyrażenie> ;
	|	return <Wyrażenie> ;
	|	return ;
<WyrazeniePodstawowe>	::=	<Ident>
	|	<String>
	|	<Int>
	|	( <Wyrażenie> )
	|	this
	|	super
	|	null
<WyrazeniePostfiksowe>	::=	<WyrażeniePostfiksowe> [ <Wyrażenie> ]
	|	<WyrażeniePostfiksowe> ( <Parametry> )
	|	<WyrażeniePostfiksowe> . <Ident>
	|	<WyrażeniePodstawowe>
<Parametry>	::=	ε
	|	<ListWyrażenie>
<ListaWyrażeń>	::=	<Wyrażenie>
	|	<Wyrażenie> , <ListaWyrażeń>
<WyrażenieUnarne>	::=	<OperatorUnarny> <WyrażenieUnarne>
	|	<WyrażeniePostfiksowe>
<OperatorUnarny>	::=	-
	|	+
	|	!
<WyrażenieMultiplikatywne>	::=	<WyrażenieMultiplikatywne> <OperatorMultiplikatywny> <WyrażenieUnarne>
	|	<WyrażenieUnarne>
<WyrażenieAddytywne>	::=	<WyrażenieAddytywne> <OperatorAddytywny> <WyrażenieMultiplikatywne>
	|	<WyrażenieMultiplikatywne>
<OperatorMultiplikatywny>	::=	*
	|	/
<OperatorAddytywny>	::=	+
	|	-
<WyrażeniePorównania>	::=	<WyrażenieAddytywne> <OperatorPorównania> <WyrażenieAddytywne>
	|	<WyrażenieAddytywne>
<OperatorPorównania>	::=	<
	|	>
	|	<=
	|	>=
	|	==
	|	!=
<WyrażenieLogiczne>	::=	<WyrażeniePorównania> <OperatorLogiczny> <WyrażeniePorównania>
	|	<WyrażeniePorównania>
<OperatorLogiczny>	::=	||
	|	&&
<Wyrażenie>	::=	<WyrażenieLogiczne>
	|	new <Typ>
	|	new <Typ> [ <Wyrazenie> ]
<ZłożonaInstrukcja>	::=	if <Wyrażenie> then <ListaInstrukcji> else <ListaInstrukcji> endif
	|	if <Wyrażenie> then <ListaInstrukcji> endif
	|	while <Wyrażenie> do <ListaInstrukcji> done
<DeklaracjaKlasy>	::=	class <Ident> extends <Ident> { <ListaDeklaracji> }

Semantyka języka

Poniżej przedstawiona jest semantyka najważniejszych konstrukcji Kotka. Jeśli jakaś konstrukcja nie jest omówiona, to jej semantyka nie różni się od semantyki analogicznych konstrukcji w innych językach programowania.

Widoczność deklaracji

Wykonywana instrukcja ma dostęp do wszystkich deklaracji funkcji w której była zadeklarowana (lub do deklaracji głównego programu, jeśli instrukcja występuje bezpośrednio w programie), włącznie z deklaracjami parametrów funkcji, oraz do wszystkich deklaracji z wyższego poziomu. Zadeklarowanie zmiennej o nazwie takiej jak jakaś zmienna z wyższego poziomu przesłania zmienną z wyższego poziomu. Nie ma możliwości odwołania się do przysłoniętej zmiennej. Zabroniona jest deklaracja zmiennej o nazwie takiej jak któryś parametr funkcji w której (bezpośrednio) występuje deklaracja. Przyjrzyjmy się przykładowej deklaracji funkcji.

function f(var x: int) : void
   function a(var s : string) : string
   {                             // deklaracja parametru s przysłania deklarację
                                 // z funkcji f
      if x == 0 then
         return "x jest zerem";
      else
         return b();
      endif
   }
   function b() : string
       var x : string;
   {
      return s;            // zwróci zmienną lokalną funkcji f
   }
   var s : string;
{
   s = "napis";
   print a("inny napis");        
}

W funkcji a widoczna są:

• funkcja b (mimo, że została zadeklarowana później),
• zmienna x - parametr funkcji f,
• zmienna s - parametr funkcji a.

W funkcji b widoczne są:

• zmienna x - lokalna zmienna funkcji b, przysłaniająca parametr funkcji f (zauważ, że przysłaniająca zmienna może być dowolnego typu),
• zmienna s - lokalna zmienna funkcji f,
• funkcja a.

W funkcji f widoczne są:

• funkcja a,
• funkcja b,
• zmienna s - zadeklarowana lokalnie w f,
• zmienna x - parametr f.

Zasady widoczności w przypadku lokalnych deklaracji obiektów są pozostawione jako ćwiczenie.

Alokacja obiektów, rekordów i tablic

Obiekty, rekordy oraz tablice są tworzone dynamicznie na stercie, za pomocą operatora 'new, na przykład:

new int[100];

zwróci tablicę 100 liczb całkowitych,

new mojRekord;

zwróci nowy rekord typu mojRekord, a

new mojObiekt[10];

zwróci tablicę 10 obiektów klasy mojObiekt.

Wywołanie operatora new bez podania rozmiaru tablicy alokuje pojedynczy element. Takie wywołanie jest dozwolone tylko dla typów rekordowych i obiektowych. Tworzenie wielowymiarowych tablic jest możliwe przez zadeklarowanie typu tablicowego:

type tabl = arrayof int;

i alokacja tablicy tego typu:

tablicaTablic = new tabl[10];

i poszczególnych elementów tablicy:

tabl[0] = new int[10];
// ...

Zmienne o typie tablicowym, rekordowym lub obiektowym przechowują referencję do tablicy, rekordu lub obiektu (odpowiednio). Przekazywanie tablic do funkcji, zaracanie ich z funkcji oraz przypisywanie do zmiennej odbywa się przez referencję. Oznacza to, że zmiany elementów tablicy w funkcji do której tablica została przekazana będą zachowane również po powrocie z tej funkcji. Przypisanie tablicy do nowej zmiennej nie kopiuje jej, ale nowa zmienna wzkazuje na tą samą tablicę. Dokładnie tak samo jest w przypadku rekordów i obiektów.

Zwalnianie elementów zaalokowanych operatorem new odbywa się przy pomocy operatora delete. Jedynym parametrem delete jest referencja do zaalokowanego elementu (czyli wartość zmiennej wskazującej na element). Nie należy podawać rozmiaru w przypadku tablic. Każde wywołanie delete usuwa dokłanie jeden element zaalokowany operatorem new.

Kontrola typów

Typy są sprawdzane w czasie kompilacji.

Równoważność typów jest przez nazwę.

Semantyka wyrażeń logicznych

Język Kotek nie przewiduje oddzielnego typu logicznego. Zamiast tego w wyrażeniach logicznych używane są zwykłe wyrażenia arytmetyczne. Jeśli wartość wyrażenia jest niezerowa, to jego logiczną wartością jest prawda (reprezentowana jako 1), a jeśli worażenie zostanie wyliczone do zera, to warością logiczną jest fałsz (reprezentowany przez 0). Uwaga: jeśli wyrażenie logiczne jest w postaci czysto arytmetycznej (bez operatorów logicznych), to jego wartość nie może się zmienić, np. wartością wyrażenia 2+2 jest zawsze 4, niezależnie od tego, czy jest to wyrażenie logiczne, czy nie. Natomiast wartością logiczną 2 || 2 jest 1. Ściśle mówiąc, zmiana wartości wyrażenia na binarną (0 lub 1) odbywa się tylko gdy używane są operatory logiczne.

Wyrażenia logiczne wyliczane są w sposób leniwy, od lewej do prawej. To znaczy jeśli wartość wyrażenia jest zdeterminowana już po obliczeniu jego pierwszej części (np. 0 && 1 lub 1 || 1 - wynik jest znany już po wyliczeniu pierwszej wartości), to druga część nie jest wyliczana.

Odwołania do pól rekordów i obiektów (operator kropka)

Semantyka kropki jest identyczna jak w językach Java, czy C++. Kropka może być aplikowana tylko do typów obiektowych lub rekordowych.

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, jak 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ę?
• 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 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.

Typy 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;

Scrap material

Scrap