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
- podstawowe konstrukcje: for, while, zmienne tylko typu int i string, proste
operacje arytmetyczne, funkcje globalne, rekurencja (też wzajemna)
- rekordy, tablice,dynamiczna alokacja, zwalnianie jawne (delete)
- lokalne procedury
- klasy deklarowane na poziomie globalnym
- klasy lokalne
- deklaracje zmiennej z podaną wartością do inichalizacji
Możliwe rozszerzenia
- zmienne double, boolean
- dodatkowe operatory dla wyrażeń (++, --, +=, operatory bitowe, etc)
- 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.
| Konstrukcja | Semantyka |
Wymagania implementacyjne i ocenianieNa 3: Podstawowe konstrukcje, rekordy, tablice, dynamiczna alokacja Na 4: Lokalne deklaracje procedur. Na 5: Obiekty, operator instanceof, rzutowanie (por. zadanie FIXME). Dodatkowo punktowane zadania.
ZadaniaZadanie 1: Inicjalizacja zmiennychAby 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:
Odpowiedz na pytania:
Weź pod uwagę jakie zmienne i funkcje są dostępne z wewnątrz funkcji.
Zadanie 2: Klasy wewnątrze procedurW 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:
Zadanie 3: Klasy wewnątrz klasKolejnym 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.
Zadanie 4: Dowolne, lokalne deklaracje klasZastanów się nad sposobem implementacji dowolnie zagnieżdżonych deklaracji klas. To zadanie jest połączeniem dwóch poprzednich.
Zadanie 5: Poprawność wyrażeń na etapie parsowaniaGrametyka 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 rzutowaniaW 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:
Metody i zmienne statyczneNiektó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ęzykaInicjalizacja zmiennychZmień 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;
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śmiecanieUsuń konstrukcję delete i zrób zamiast tego automatyczne odśmiecanie. Ulepszenie read i writeJęzyk Kotek zawiera bardzo prymitywne mechanizmy wejścia wyjścia. Rozszesz język o:
read a[5]; read mojRekord.pole1;
read a[i], b[i]; write "a[5] = ", a[5];
Rzutowanie i sprawdzanie typu obiektuJę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 boolW 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 zmiennoprzecinkowyDodaj 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 klasyDodaj 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 deklaracjiW 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
|
|---|
