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)

/Gramatyka Kotka

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 omówione są najważniejsze cechy semantyki języka Kotek. 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.

Stringi

Ciągi napisowe są w języku dostępne tylko statycznie (nie ma operacji konkatenacji)i są niezmienialne.

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 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 Virtualna 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, stringi, komentarze (jeśli Twój generator analizatorów leksykalnych umożliwia obsługę zagnieżdżonych komentarzy, to powinny one być usuwane już przez ten analizator).

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_LNAWIAZ, STRING("napis\"napis")

lub równoważny.

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), a dziećmi węzła są 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żej prawej strony produkcji, w której ta lewa strona występuje. Na przykład możemy mieć klasę Intrukcja, z której dziedziczą m.in. klasy Przypisanie, Blok, PustaInstrukcja i Złożona instrukcja. 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).

Parser powinien działać jak pretty printer - powinien wypisywać treść programu na podstawie drzewa składniowego zawartego w pamięci.

Zadanie 3: Tablica symboli

Do Twojego kompilatora dopisz kod tworzący tablicę symboli z każdej listy deklaracji. Połącz tablice syboli 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 architekturze x86, 32 bitowej 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), tak samo zmienne typu obiektowego, tablicowego i rekordowego. Funkcje, rekordy, typy i klasy 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. Np, 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 identyfiktora - określenie w której tablicy symboli jest zawarty,
• określanie pozycji identyfikatora w tablicy symboli,
• podawanie całkowitego rozmiaru deklaracji w 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ń - być może pomogą Ci lepiej zrozumieć semantykę języka 'Kotek'.

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).

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

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;