Michał Śmiałek - Języki formalne i kompilatory

Języki formalne i kompilatory

kierunek: informatyka, sem. V-VI

Wykład (sem. V) - zima 2004/2005

Przedmiot zajmuje się teoretycznymi i praktycznymi podstawami konstrukcji kompilatorów. W jego skład wchodzą następujące tematy:

Podstawy języka UML. Co to jest i do czego służy UML? Jak opisać kompilator przy pomocy UML-a? Różne rodzaje modeli w UML-u.
Model klas w języku UML. Klasy, ich metody i atrybuty. Związki klas. Budowa diagramów klas.
Model interakcji w języku UML. Obiekty i czas ich życia. Diagramy sekwencji. Linie życia i komunikaty na diagramach sekwencji.
Struktura i zadania kompilatora. Ogólna prezentacja diagramu klas typowego kompilatora (model w UML-u). Różnice w modelu w przypadku gramatyk LL i LR oraz przy zastosowaniu generatora analizatorów leksykalnych (Lex) i generatora analizatorów składniowych (Yacc, Bison). Języki źródłowe i wynikowe.
Analiza leksykalna - struktura, gramatyka regularna. Struktura analizatora leksykalnego w UML. Wyrażenia i gramatyki regularne.
Lex. Co to jest i do czego służy Lex (Generator Analizatorów Leksykalnych)?. Język źródłowy dla Lex-a. Pisanie wyrażeń w języku Lex.
Analiza składniowa - struktura, gramatyka bezkontekstowa. Struktura analizatora składniowego w UML. Powiązanie analizatora składniowego z analizatorem leksykalnym. Definicja gramatyki bezkontekstowej. Przykłady gramatyk bezkontekstowych.
Analiza składniowa - gramatyki LL(1). Przykład wyprowadzenia LL dla gramatyki. Zbiory „lookahead”, „first” i „follow”. Definicja gramatyki LL(1).
Analiza składniowa - gramatyki LL(k) cz. 1. Zbiory “lookahead", "first" i "follow" dla gramatyk LL(k). Dowodzenie, że gramatyka jest LL.
Analiza składniowa - gramatyki LL(k) cz. 2. Dowodzenie, że gramatyka jest LL (c.d.). Przekształcanie gramatyk na LL(1). Lewostronna faktoryzacja, zastępowanie, eliminacja lewostronnej rekurencji, eliminacja pośredniej lewostronnej rekurencji.
Analiza składniowa - gramatyki LR cz. 1. Cechy gramatyki LR. Tablice "Action" i "Goto". Sposób działania analizatora LR.
Analiza składniowa - Gramatyki LR cz. 2. Tworzenie tablic "Action" i "Goto".
Yacc (Bison). Co to jest i do czego służy Yacc (Generator Analizatorów Składniowych)? Definiowanie gramatyk dla Yacc-a. Sposób działania generatora Yacc.

Tematy dotyczące języka UML służą zdefiniowaniu metody projektowania kompilatorów (metody obiektowej) używanej podczas wykładu.

Literatura
1. A. V. Aho, R. Sethi, J. D. Ullman - Compilers: Principles, Techniques and Tools, Addison-Wesley, 1986
powyższa książka jest również dostępna w wersji polskiej (Kompilatory, WNT, 2002), recenzja

2. W. M. Waite, G. Goos - Konstrukcja kompilatorów, WNT, 1989

3. Michał Śmiałek - Zrozumieć UML 2.0. Metody modelowania obiektowego, Helion, Gliwice, 2005

Slajdy z wykładów

Wykład 1	Wykład 2	Wykład 3	Wykład 4
Wykład 5	Wykład 6	Wykład 7	Wykład 8 i 9
Wykład 10	Wykład 11	Wykład 12
YACC - dokumentacja	Lex - dokumentacja

Przykładowe zadania

Zadania z egzaminu

Zadanie semestralne

Regulamin
1. Zaliczenie wykładu następuje na podstawie oceny pracy semestralnej oraz egzaminu.
2. W trakcie semestru można zebrać maksimum 25 punktów. Na tę sumę składają się oceny wykonania zadań wykładowych.
3. Zadania wykładowe wykonywane w są grupach dwuosobowych tylko podczas wykładu (na drugiej godzinie zajęć).
4. Osoby, które uzyskają najlepsze wyniki z zadań wykładowych - zostaną zwolnione z egzaminu.
5. Za egzamin można otrzymać maksimum 75 punktów.
6. Warunkiem zaliczenia przedmiotu jest uzyskanie w sumie, co najmniej 51 pkt.
7. Ocena końcowa zależna jest od uzyskanej sumarycznej liczby punktów: 51-60 pkt. = 3,0; 61-70 pkt. = 3,5; 71-80 pkt. = 4,0; 81-90 pkt. = 4,5; 91-100 pkt. = 5,0.

Laboratorium (sem. VI) - lato 2005

Prowadzący: Michał Śmiałek, Bartosz Sawicki, Bartosz Świderski.
Podstawowym celem laboratorium jest poznanie metod realizacji systemów kompilatorów przy pomocy generatorów typu lex/yacc i języka obiektowego.

Uwaga: opis zamieszczony poniżej jest nieaktualny! Aktualny opis znajduje się na stronie Zakładu: http://www.iem.pw.edu.pl/zetiis/.

Regulamin
1. Do wykonania są dwa zadania. Pierwsze zadanie jest zadaniem indywidualnym. Drugie zadanie realizowane jest w grupach dwuosobowych. Obydwa zadania polegają na opracowaniu języka oraz zaprojektowaniu i napisaniu aplikacji zawierającej kompilator realizujący ten język. Aplikacje powinny być zaprojektowane przy wykorzystaniu diagramów w języku UML oraz zaimplementowane przy wykorzystaniu języka obiektowego (C++ lub Java).
2. Za wykonanie dwóch zadań można otrzymać maksimum 100 punktów. Na tę sumę składa się po 50 pkt. za każde zadanie.
3. Zadanie pierwsze: Kompilator powinnien być napisany w języku C++ a analiza leksykalna i składniowa zrobiona z pomocą kodu generowanego przez programy Flex i GNU Bison (kompatybilne z lex/yacc). Do tworzenia grafiki należy użyć biblioteki GD. Obowiązującym środowiskiem programistycznym jest LOP, max.iem.pw.edu.pl. Odnośniki: GNU Flex/Bison -- http://www.gnu.org/software/flex/, Biblioteka GD -- http://www.boutell.com/gd/, LOP -- http://max.iem.pw.edu.pl/.
4. Harmonogram zadania pierwszego: zajęcia 1 - organizacja; 2 - konsultacje; 3 - uruchomiony lex/yacc + gramatyka (7 pkt.); 4 - konsultacje; 5 - uruchomiona biblioteka graficzna + diagramy UML (8 pkt.); 6 - konsultacje; 7 - obrona projektu (15 pkt.) + dokumentacja końcowa (20 pkt.).
5. Zadanie drugie: Kompilator powinien być napisany w języku C++ lub Java, a analiza leksykalna i składniowa zrobiona przy pomocy własnych klas o strukturze zgodnej ze strukturą kompilatorów LL przedstawioną na wykładzie. Obowiązującym środowiskiem jest LOP (j.w.).

6. Harmonogram zadania drugiego: zajęcia 1 - organizacja i konsultacje, 2 - konsultacje, 3 - diagramy UML + gramatyka (7 pkt.), 4 - konsultacje, 5 – uruchomione klasy kompilatora (8 pkt.), 6 - konsultacje, 7 - obrona projektu (15 pkt.) + dokumentacja końcowa (20 pkt.).
7. Dokumentacja końcowa powinna zawierać: a) przedstawienie zadania, b) opis języka, c) opis interfejsu użytkownika – instrukcję obsługi, d) definicję gramatyki bezkontekstowej, e) projekt obiektowy (diagramy klas i sekwencji), f) opis najistotniejszych fragmentów kodu źródłowego wraz z opisem implementacji.

8. Przekroczenie terminu oddania wyników pośrednich oraz aplikacji wraz z dokumentacją oznacza obniżenie oceny za dane zadanie o 20% przy spóźnieniu do jednego tygodnia i o 100% przy spóźnieniu powyżej jednego tygodnia
9. Warunkiem zaliczenia jest uzyskanie w sumie co najmniej 51 pkt.
10. Ocena końcowa zależna jest od uzyskanej sumarycznej liczby punktów: 51-60 pkt. = 3,0; 61-70 pkt. = 3,5; 71-80 pkt. = 4,0; 81-90 pkt. = 4,5; 91-100 pkt. = 5,0.

Ważne ustalenia dodatkowe dotyczące zaliczenia:

11. Wszystkie projekty będą oceniane na podstawie obrony i dokumentacji końcowej. Na ocenę z obrony składają się: funkcjonalność i możliwości aplikacji (5 pkt.), jakość kodu i jego znajomość (5 pkt.), podział na pliki i Makefile (5 pkt.). Na ocenę dokumentacji składają się: podręcznik użytkownika (5 pkt.), opis języka (5 pkt.), udokumentowanie obiektowości - UML (5 pkt.), dokumentacja kodu i opis ważniejszych elementów (5 pkt.). Całe sprawozdanie końcowe musi się zmieścić na 5 kartkach papieru - włącznie z wydrukiem kodu (czcionka o min. rozmiarze 8).

12. Wszystkie projekty będą sprawdzane automatycznie pod kątem podobieństwa. Warunkiem zaliczenia jest umieszczenie w katalogu ~/jfik1 (dla zadania 1) oraz ~/jfik2 (dla zadania 2) wszystkich plików źródłowych (szczegóły na stronie http://lop.iem.pw.edu.pl).

Treść zadań

Zadanie pierwsze. Zaprojektować i napisać kompilator języka do nauki programowania opartego na zasadzie „grafiki żółwia” (podobnego do języka LOGO). Język powinien posiadać polecenia do przesuwania żółwia po ekranie (w przód, w tył, obrót), rysowania, zmiany koloru itp. itd. Oprócz poleceń graficznych, język powinien posiadać możliwość definiowania procedur i funkcji.

Zadanie drugie. Zaprojektować i napisać kompilator języka do definiowania i rozgrywania gier komnatowych. Język powinien umożliwiać definiowanie komnat oraz składanie ze zdefiniowanych komnat - obszaru gry. Komnaty powinny być zapisywane jako procedury z parametrami, gdzie parametry definiują np. rozmiary komnaty lub stan przejść. Druga część języka powinna umożliwiać pisanie „programów przejść” dla zdefiniowanego wcześniej obszaru gry. Taki „program przejść” powinien posiadać polecenia przechodzenia w różnych kierunkach, polecenia sprawdzania stanu drzwi, polecenia otwierania drzwi oraz instrukcję warunkową (dotyczącą np. stanu drzwi). Efektem wykonania programu w zdefiniowanym języku powinien być obrazek z narysowanym obszarem gry i szlakiem przejść przez ten obszar.