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

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 #1/2 4) Implementacja analizatorów leksykalnych w Lexie #2/2 koncepcja i używanie generatora, konwencje notacyjne, wzorce, akcje, retrakcja, konteksty, odrzucenie dopasowania,

5) Wstęp do analizy składniowej podstawowe pojęcia analizy składniowej, klasyfikacja Chomsky'ego a implementacja analizatorów, gramatyki bezkontekstowe,

6) Analiza metodą zstępującą koncepcja metody top-down, ograniczenia metody (lewostronna rekurencja, faktoryzacja)

7) Implementacja analizatora zstępującego analizatora składniowego w języku imperatywnym na przykładzie języka C

8) Analiza metodą wstępującą #1/2 9) Analiza metodą wstępującą #2/2 koncepcja metody bottom-up, LR-parsery, metody generowania tablic

10) Podstawy generatora YACC

11) Generator YACC : gramatyki niejednoznaczne, konflikty, rozstrzyganie

12) Translacja sterowana składnią w generatorze YACC #1/2 13) Translacja sterowana składnią w generatorze YACC #2/2 atrybuty i implementacja, akcje wielokrotne

14) Zaleźności kontekstowe systemy typów, kontrola zgodności typów, konwersje

15) Generacja kodu pośredniego koncepcja języka pośredniego, typy języków pośrednich, maszyny wirtualne,

16) Generacja kodu wynikowego #1/2 17) Generacja kodu wynikowego #2/3 architektury sprzętowe, przydział i wyznaczanie rejestrów, bloki podstawowe, grafy przepływu,

18) Optymalizacja #1/2 19) Optymalizacja #2/2 cele optymalizacja, optymalizacja zależna i niezależna od maszyny docelowej, analiza przepływu sterowania, analiza przepływu danych, optymalizacja a uruchamianie oprogramowania, superkompilatory

20) Zarządzanie pamięcią #1/2 21) Zarządzanie pamięcią #2/2 strategie alokacji, alokacja stosowa, sterta, algorytmy przydziału ze sterty, arbitralne zarządzanie a usuwanie nieużytków, wykrywanie wiszących referencji, scalanie

22) Dostęp do nazw nielokalnych widzialność, zasięg, zagnieżdżanie bloków, procedur i funkcji, widzialność statyczna (język C vs Pascal i Ada), wiązania dostępu, wektory display, widzialność dynamiczna, płytki i głęboki dostęp

23) Obsługa wyjątków, kod wielowątkowy, przekazywanie parametrów zarządzanie stosem, alokacja ze sterty, tryby i metody przekazywania parametrów

24) Systemy rozproszone, zdalne wywoływanie translatory dla systemów rozproszonych, konwersje reprezentacji

Autorzy

• Wojciech Complak

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