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

1. Analiza leksykalna

wprowadzenie do analizy leksykalnej, podstawowe pojęcia, implementacja analizatorów leksykalnych w językach imperatywnych na przykładzie języka C

1. Implementacja analizatorów leksykalnych w Lexie #1/2
2. Implementacja analizatorów leksykalnych w Lexie #2/2

koncepcja i używanie generatora, konwencje notacyjne, wzorce, akcje, retrakcja, konteksty, odrzucenie dopasowania,

1. Wstęp do analizy składniowej

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

1. Analiza metodą zstępującą

koncepcja metody top-down, ograniczenia metody (lewostronna rekurencja, faktoryzacja)

1. Implementacja analizatora zstępującego analizatora składniowego w języku imperatywnym

na przykładzie języka C

1. Analiza metodą wstępującą #1/2
2. Analiza metodą wstępującą #2/2

koncepcja metody bottom-up, LR-parsery, metody generowania tablic

1. Podstawy generatora YACC
2. Generator YACC : gramatyki niejednoznaczne, konflikty, rozstrzyganie
3. Translacja sterowana składnią w generatorze YACC #1/2
4. Translacja sterowana składnią w generatorze YACC #2/2

atrybuty i implementacja, akcje wielokrotne

1. Zaleźności kontekstowe

systemy typów, kontrola zgodności typów, konwersje

1. Generacja kodu pośredniego

koncepcja języka pośredniego, typy języków pośrednich, maszyny wirtualne,

1. Generacja kodu wynikowego #1/2
2. Generacja kodu wynikowego #2/3

architektury sprzętowe, przydział i wyznaczanie rejestrów, bloki podstawowe, grafy przepływu,

1. Optymalizacja #1/2
2. 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

1. Zarządzanie pamięcią #1/2
2. 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

1. 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

1. Obsługa wyjątków, kod wielowątkowy, przekazywanie parametrów

zarządzanie stosem, alokacja ze sterty, tryby i metody przekazywania parametrów

1. 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