Metody realizacji języków programowania

obowiązkowe

Języki i paradygmaty programowania 1000-216bJPP

Języki, automaty i obliczenia 1000-214bJAO

Przegląd podstawowych zagadnień i technik tworzenia interpreterów i kompilatorów dla języków programowania. Najważniejszymi tematami omawianymi na wykładzie są metody analizy semantycznej oraz generacji i optymalizacji kodu dla różnych maszyn docelowych (JVM, LLVM, asembler).

Przydatna będzie wiedza wyniesiona z przedmiotu Języki i Paradygmaty Programowania (lub równoważnego).

Absolwenci kursu powinni umieć stworzyć kompilator dla prostego języka programowania.

1. Analiza leksykalna i syntaktyczna (2 wykłady): analiza zstępująca i wstępująca; gramatyki LL(1) i konstrukcja parsera metodą zejść rekurencyjnych; gramatyki LR(k),SLR,LALR i konstrukcja automatów dla nich.

2. Analiza semantyczna (2 wykłady): tablica symboli, wiązanie nazw, kontrola typów.

3. Środowisko czasu wykonania (1-2 wykłady): struktury czasu wykonania, organizacja pamięci, realizacja podprogramów.

4. Generacja kodu: języki pośrednie – kod czwórkowy, maszyna stosowa, generacja kodu maszynowego, alokacja rejestrów.

5. Maszyna wirtualna JVM i generacja kodu dla niej.

6. Static Single Assignment i maszyna wirtualna LLVM.

7. Kod asemblera na przykładzie architektury x86.

8. Optymalizacja (2 wykłady): graf bloków prostych, analiza przepływu; alokacja rejestrów; metody ulepszania kodu: zwijanie stałych, eliminacja wspólnych podwyrażeń, eliminacja martwego kodu, optymalizacja pętli, metoda peephole.

9. Obsługa wyjątków: semantyka wyjątków, odnajdywanie bloku obsługi wyjątku, zwijanie stosu.

10. Zarządzanie pamięcią: alokacja i dealokacja pamięci; odśmiecanie: zliczanie odwołań, kopiowanie, „zaznacz i zamieć”; metody synchroniczne i asynchroniczne; konserwatywność odśmiecania.

11.Kompilacja języków funkcyjnych: specyfika; domknięcia, kombinatory i superkombinatory; redukcja grafów, metoda szablonów, G-maszyna i jej warianty; leniwe obliczenia, lambda-lifting.

K.Cooper, L. Torczon, Engineering a Compiler,

A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman, Compilers: Principles, Techniques, and Tools, 2/E (w języku polskim dostępne jest tłumaczenie poprzedniego wydania: Kompilatory. Reguły, metody i narzędzia, Wydawnictwa Naukowo-Techniczne, Warszawa 2002).

http://moodle.mimuw.edu.pl

Wiedza

Zna problemy, techniki i narzędzia związane z budową kompilatorów (K_W03), w szczególności:

● ma pogłębioną wiedzę w zakresie problemów i metod analizy składniowej,

● ma pogłębioną wiedzę w zakresie problemów i metod analizy semantycznej,

● rozumie strukturę i funkcjonalność środowiska czasu wykonania,

● zna przykłady języków pośrednich i sposoby ich wykorzystania w kompilatorze,

● zna podstawowe problemy i techniki związane z generacją kodu maszynowego,

● zna metody ulepszania kodu,

● ma pogłębioną wiedzę w zakresie zarządzania pamięcią, w tym problemy i techniki odsmiecania.

Umiejętności

Potrafi zbudować kompilator dla języka programowania o średnim stopniu złożoności (K_U03).

Kompetencje

Rozumie konieczność systematycznej pracy nad wszelkimi projektami, które mają długofalowy charakter (K_K03).

Uwaga: może być zmienione przez informacje o zasadach w konkretnym cyklu

Egzamin 50%, laboratorium 40% ćwiczenia 10%.

Dla zaliczenia trzeba min 50% punktów z laboratorium oraz min. 50% z ćwiczeń.

Zaliczenie jest wymagane do przystąpienia do egzaminu w pierwszym terminie. Zaliczenie nie jest wymagane do przystąpienia do egzaminu w drugim terminie, wymagane jest uzyskanie przynajmniej 30% możliwych do uzyskania punktów za projekt; punkty uzyskane za ćwiczenia i projekt zaliczeniowy są wliczane do oceny końcowej także w drugim terminie.

Uzyskanie 70% punktów za lab+ćwiczenia uprawnia do uzyskania (na indywidualną prośbę) oceny przed sesją, bez egzaminu, na podstawie tychże punktów pomnożonych przez współczynnik 1.75.