Podstawy kompilatorów

Opis

Celem przedmiotu jest przedstawienie zasad i technik budowy kompilatorów. W ramach przedmiotu przedstawione zostaną zasady ich implementacji zarówno z wykorzystaniem specjalizowanych narzędzi takich jak LEX i YACC jak i z wykorzystaniem uniwersalnych języków programowania wysokiego poziomu, takich jak język C. Omówione zostaną poszczególne fazy kompilacji poczynając od analizy leksykalnej, poprzez analizę składniową, semantyczną, generację kodu pośredniego i wynikowego po optymalizację kodu. Przedstawione zostaną także zagadnienia dotyczące budowy środowiska wykonawczego.

Oprócz wykładów będą prowadzone ćwiczenia laboratoryjne, w trakcie których rozwiązywane będą zadania ilustrujące zagadnienia omawiane na wykładach.

Sylabus

Autorzy

• Wojciech Complak, wojciech.complak@cs.put.poznan.pl
• Bartosz Bogacki, bartosz.bogacki@cs.put.poznan.pl

Zakres przedmiotu

1. Wstęp, organizacja procesu kompilacji (zakres przedmiotu, rodzaje translatorów, interpretacja a kompilacja, model kompilatora, podział na fazy)
2. Analiza leksykalna (wprowadzenie do analizy leksykalnej, podstawowe pojęcia, implementacja analizatorów leksykalnych w językach imperatywnych na przykładzie języka C)
3. Implementacja analizatorów leksykalnych w Lexie (koncepcja i używanie generatora, konwencje notacyjne, wzorce, akcje, retrakcja, konteksty, odrzucenie dopasowania)
4. Wstęp do analizy składniowej (podstawowe pojęcia analizy składniowej, klasyfikacja Chomsky'ego a implementacja analizatorów, gramatyki bezkontekstowe)
5. Analiza metodą zstępującą (koncepcja metody top-down, ograniczenia metody : lewostronna rekurencja, faktoryzacja)
6. Implementacja analizatora zstępującego analizatora składniowego w języku imperatywnym (na przykładzie języka C)
7. Analiza metodą wstępującą (koncepcja metody bottom-up, LR-parsery, metody generowania tablic)
8. Podstawy generatora YACC
9. Generator YACC : gramatyki niejednoznaczne, konflikty, rozstrzyganie
10. Translacja sterowana składnią w generatorze YACC (atrybuty i implementacja, akcje wielokrotne)
11. Zależności kontekstowe (systemy typów, kontrola zgodności typów, konwersje)
12. Generacja kodu pośredniego (koncepcja języka pośredniego, typy języków pośrednich, maszyny wirtualne)
13. Generacja kodu wynikowego (architektury sprzętowe, przydział i wyznaczanie rejestrów, bloki podstawowe, grafy przepływu)
14. Optymalizacja (cele optymalizacja, optymalizacja zależna i niezależna od maszyny docelowej, analiza przepływu sterowania, analiza przepływu danych, optymalizacja a uruchamianie oprogramowania, superkompilatory)
15. Zarządzanie pamięcią (strategie alokacji, alokacja stosowa, sterta, algorytmy przydziału ze sterty, arbitralne zarządzanie a usuwanie nieużytków, wykrywanie wiszących referencji, scalanie)
16. Dostęp do nazw nielokalnych (widzialność, zasięg, zagnieżdżanie bloków, procedur i funkcji, widzialność statyczna, język C a Pascal i Ada, wiązania dostępu, wektory display, widzialność dynamiczna, płytki i głęboki dostęp)
17. Obsługa wyjątków, kod wielowątkowy, przekazywanie parametrów (zarządzanie stosem, alokacja ze sterty, tryby i metody przekazywania parametrów)
18. Systemy rozproszone, zdalne wywoływanie (translatory dla systemów rozproszonych, konwersje reprezentacji)

Wymagania wstępne

• Umiejętność konstruowania algorytmów iteracyjnych i rekurencyjnych
• Umiejętność programowania w imperatywnych językach wysokiego poziomu
• Podstawowa znajomość architektury procesora i języka asemblera

Literatura

• Aho A. V., Sethi R., Ullman J. D., Kompilatory Reguły, metody i narzędzia, WNT 2002.
• Waite W. M., Goos G., Konstrukcja kompilatorów, WNT, 1989