Podstawy kompilatorów: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Complak (dyskusja | edycje)
701 edycji
Linia 13: Linia 13:


=== Zakres przedmiotu ===
=== Zakres przedmiotu ===
# Wstęp, organizacja procesu kompilacji (zakres przedmiotu, rodzaje translatorów, interpretacja a kompilacja, model kompilatora, podział na fazy)
# Wstęp, organizacja procesu kompilacji (omówienie przedmiotu, rodzaje translatorów, interpretacja a kompilacja, model kompilatora, podział na fazy)
# Analiza leksykalna (wprowadzenie do analizy leksykalnej, podstawowe pojęcia, implementacja analizatorów leksykalnych w językach imperatywnych na przykładzie języka C)
# Analiza leksykalna (wprowadzenie do analizy leksykalnej, podstawowe pojęcia, rozpoznawanie wzorców, automaty NFA, DFA, implementacja analizatorów leksykalnych w językach imperatywnych na przykładzie języka C)
# Implementacja analizatorów leksykalnych w Lexie (koncepcja i używanie generatora, konwencje notacyjne, wzorce, akcje, retrakcja, konteksty, odrzucenie dopasowania)
# Implementacja analizatorów leksykalnych z wykorzystaniem generatora Lex (koncepcja i używanie generatora, konwencje notacyjne, wzorce, akcje, retrakcja, konteksty, odrzucenie dopasowania)
# Wstęp do analizy składniowej (podstawowe pojęcia analizy składniowej, klasyfikacja Chomsky'ego a implementacja analizatorów, gramatyki bezkontekstowe)
# Wstęp do analizy składniowej (podstawowe pojęcia analizy składniowej, klasyfikacja gramatyk a implementacja i wydajność analizatorów, gramatyki bezkontekstowe, wywody, drzewa rozbioru)
# Analiza metodą zstępującą (koncepcja metody top-down, ograniczenia metody : lewostronna rekurencja, faktoryzacja)
# Analiza metodą zstępującą (koncepcja metody top-down, metody implementacji, predykcja, analizatory z nawracaniem i bez nawracania, lewostronna rekurencja, faktoryzacja)
# Implementacja analizatora zstępującego analizatora składniowego w języku imperatywnym (na przykładzie języka C)
# Implementacja analizatora zstępującego analizatora składniowego w języku imperatywnym (na przykładzie języka C)
# Generowanie analizatorów działających metodą zstępującą za pomocą generatora LLGen
# Analiza metodą wstępującą (koncepcja metody bottom-up, LR-parsery, metody generowania tablic)
# Analiza metodą wstępującą (koncepcja metody bottom-up, LR-parsery, metody generowania tablic)
# Podstawy generatora YACC
# Podstawy generatora YACC
# Generator YACC : gramatyki niejednoznaczne, konflikty, rozstrzyganie
# Generator YACC : gramatyki niejednoznaczne, konflikty, rozstrzyganie
# Translacja sterowana składnią w metodzie zstępującej, realizacja translacji w języku C i generatorze LLGen
# Translacja sterowana składnią w generatorze YACC (atrybuty i implementacja, akcje wielokrotne)
# Translacja sterowana składnią w generatorze YACC (atrybuty i implementacja, akcje wielokrotne)
# Zależności kontekstowe (systemy typów, kontrola zgodności typów, konwersje)
# Analiza zależności kontekstowych (systemy typów, kontrola zgodności typów, konwersje)
# Generacja kodu pośredniego (koncepcja języka pośredniego, typy języków pośrednich, maszyny wirtualne)
# Generacja kodu wynikowego (architektury sprzętowe, przydział i wyznaczanie rejestrów, bloki podstawowe, grafy przepływu)
# 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)
# 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)
# 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)
# Obsługa wyjątków, kod wielowątkowy, przekazywanie parametrów (zarządzanie stosem, alokacja ze sterty, tryby i metody przekazywania parametrów)
# Systemy rozproszone, zdalne wywoływanie (translatory dla systemów rozproszonych, konwersje reprezentacji)


=== Wymagania wstępne ===
=== Wymagania wstępne ===

Wersja z 20:36, 6 lip 2006

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 (omówienie przedmiotu, rodzaje translatorów, interpretacja a kompilacja, model kompilatora, podział na fazy)
  2. Analiza leksykalna (wprowadzenie do analizy leksykalnej, podstawowe pojęcia, rozpoznawanie wzorców, automaty NFA, DFA, implementacja analizatorów leksykalnych w językach imperatywnych na przykładzie języka C)
  3. Implementacja analizatorów leksykalnych z wykorzystaniem generatora Lex (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 gramatyk a implementacja i wydajność analizatorów, gramatyki bezkontekstowe, wywody, drzewa rozbioru)
  5. Analiza metodą zstępującą (koncepcja metody top-down, metody implementacji, predykcja, analizatory z nawracaniem i bez nawracania, lewostronna rekurencja, faktoryzacja)
  6. Implementacja analizatora zstępującego analizatora składniowego w języku imperatywnym (na przykładzie języka C)
  7. Generowanie analizatorów działających metodą zstępującą za pomocą generatora LLGen
  8. Analiza metodą wstępującą (koncepcja metody bottom-up, LR-parsery, metody generowania tablic)
  9. Podstawy generatora YACC
  10. Generator YACC : gramatyki niejednoznaczne, konflikty, rozstrzyganie
  11. Translacja sterowana składnią w metodzie zstępującej, realizacja translacji w języku C i generatorze LLGen
  12. Translacja sterowana składnią w generatorze YACC (atrybuty i implementacja, akcje wielokrotne)
  13. Analiza zależności kontekstowych (systemy typów, kontrola zgodności typów, konwersje)

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
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Podstawy_kompilatorów&oldid=2969”