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
Nie podano opisu zmian
Complak (dyskusja | edycje)
701 edycji
Nie podano opisu zmian
Linia 1: Linia 1:
== Forma zajęć ==
== Forma zajęć ==
Wykład (30 godzin) + laboratorium (30 godzin)
Wykład (30 godzin) + laboratorium (30 godzin)


Linia 8: Linia 7:
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.
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.
Przedmiot "Podstawy kompilatorów" koncentruje się omówieniu etapu analizy kodu i przedstawieniu narzędzi wykorzystywanych w tworzeniu kompilatorów.
Pozostałe zagadnienia omówione są szerzej w ramach przedmiotu "Metody realizacji języków programowania".


== Sylabus ==
== Sylabus ==


=== Autorzy ===
=== Autorzy ===
* Bartosz Bogacki
* Wojciech Complak
* Wojciech Complak
* Bartosz Bogacki


=== Wymagania wstępne ===
=== Wymagania wstępne ===
Linia 22: Linia 22:


=== Zawartość ===
=== Zawartość ===
# Wstęp, organizacja procesu kompilacji (omówienie przedmiotu, rodzaje translatorów, interpretacja a kompilacja, model kompilatora, podział na fazy)
* Model kompilatora
# 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)
** etapy i fazy kompilacji
# Implementacja analizatorów leksykalnych z wykorzystaniem generatora Lex (koncepcja i używanie generatora, konwencje notacyjne, wzorce, akcje, retrakcja, konteksty, odrzucenie dopasowania)
* Analiza leksykalna
# 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)
** podstawowe pojęcia
# Analiza metodą zstępującą (koncepcja metody top-down, metody implementacji, predykcja, analizatory z nawracaniem i bez nawracania, lewostronna rekurencja, faktoryzacja, implementacja na przykłądzie języka C)
** języki i wyrażenia regularne
# Generowanie analizatorów działających metodą zstępującą za pomocą generatora LLGen
** niedeterministyczne i deterministyczne automaty skończone
# Analiza metodą wstępującą (koncepcja metody bottom-up, LR-parsery, metody generowania tablic)
** implementacja analizatorów leksykalnych w języku C i za pomocą generatora LEX
# Podstawy generatora YACC
* Analiza składniowa
# Generator YACC : gramatyki niejednoznaczne, konflikty, rozstrzyganie
** podstawowe pojęcia
# Translacja sterowana składnią w metodzie zstępującej, realizacja translacji w języku C i generatorze LLGen
** gramatyki bezkontekstowe
# Translacja sterowana składnią w generatorze YACC (atrybuty i implementacja, akcje wielokrotne)
** analiza metodą zstępującą i wstępującą
# Analiza zależności kontekstowych (systemy typów, kontrola zgodności typów, konwersje)
** implementacja analizatorów składniowych działających metodą zstępującą w języku C i za pomocą generatora LLgen
# Pozostałe zagadnienia
** implementacja analizatorów składniowych działających metodą wstępującą za pomocą generatora YACC
** translacja sterowana składnią w metodzie zstępującej i wstępującej
** gramatyki niejednoznaczne
* Analiza zależności kontekstowych
** typy zależności kontekstowych
** implementacja kontrolera typów
* Synteza kodu i środowisko czasu wykonania
** generacja kodu pośredniego
** optymalizacja kodu
** generacja kodu wynikowego
** dostęp do nazw nielokalnych
** dynamiczny przydział pamięci
** przekazywanie parametrów


=== Literatura ===
=== Literatura ===
* Aho A. V., Sethi R., Ullman J. D., Kompilatory Reguły, metody i narzędzia, WNT 2002
* Aho A. V., Sethi R., Ullman J. D., ''Kompilatory Reguły, metody i narzędzia'', WNT 2002
* Foryś M., Foryś W., Teoria automatów i języków formalnych, Akademicka Oficyna Wydawnicza Exit 2005
* Foryś M., Foryś W., ''Teoria automatów i języków formalnych'', Akademicka Oficyna Wydawnicza Exit 2005
* Tremblay J. P., Sorenson P. G., The Theory and Practice of Compiler Writing, McGraw-Hill, 1985
* Tremblay J. P., Sorenson P. G., ''The Theory and Practice of Compiler Writing'', McGraw-Hill, 1985
* Waite W. M., Goos G., Konstrukcja kompilatorów, WNT 1989
* Waite W. M., Goos G., ''Konstrukcja kompilatorów'', WNT 1989
* Wilhelm R., Maurer D., Compiler Design, Addison-Wesley 1995
* Wilhelm R., Maurer D., ''Compiler Design'', Addison-Wesley 1995
 
== Moduły ==
* [[pok-1-wyk-toc|Wykład 1: Podstawy kompilatorów. Wprowadzenie do przedmiotu]] ([http://elearning.cs.put.poznan.pl/mediawiki/flash_files/pok/pok-1-wyk/player.html Flash], [[media:pok-1-wyk.pdf|PDF]], [[media:pok-1-wyk-kolor.pdf|PDF kolor]]),[[media:pok-1-lab.pdf| Laboratorium (PDF)]]
* [[pok-2-wyk-toc|Wykład 2: Podstawy kompilatorów. Analiza leksykalna]] ([http://elearning.cs.put.poznan.pl/mediawiki/flash_files/pok/pok-2-wyk/player.html Flash], [[media:pok-2-wyk.pdf|PDF]], [[media:pok-2-wyk-kolor.pdf|PDF kolor]]),[[media:pok-2-lab.pdf| Laboratorium (PDF)]]
* [[pok-3-wyk-toc|Wykład 3: Podstawy kompilatorów. Implementacja analizatorów leksykalnych]] ([http://elearning.cs.put.poznan.pl/mediawiki/flash_files/pok/pok-3-wyk/player.html Flash], [[media:pok-3-wyk.pdf|PDF]], [[media:pok-3-wyk-kolor.pdf|PDF kolor]]),[[media:pok-3-lab.pdf| Laboratorium (PDF)]]
* [[pok-4-wyk-toc|Wykład 4: Podstawy kompilatorów. Wstęp do analizy składniowej]] ([http://elearning.cs.put.poznan.pl/mediawiki/flash_files/pok/pok-4-wyk/player.html Flash], [[media:pok-4-wyk.pdf|PDF]], [[media:pok-4-wyk-kolor.pdf|PDF kolor]]),[[media:pok-4-lab.pdf| Laboratorium (PDF)]]
* [[pok-5-wyk-toc|Wykład 5: Podstawy kompilatorów. Analiza metodą zstępującą]] ([http://elearning.cs.put.poznan.pl/mediawiki/flash_files/pok/pok-5-wyk/player.html Flash], [[media:pok-5-wyk.pdf|PDF]], [[media:pok-5-wyk-kolor.pdf|PDF kolor]]),[[media:pok-5-lab.pdf| Laboratorium (PDF)]]
* [[pok-6-wyk-toc|Wykład 6: Podstawy kompilatorów. Generowanie analizatorów działających metodą zstępującą]] ([http://elearning.cs.put.poznan.pl/mediawiki/flash_files/pok/pok-6-wyk/player.html Flash], [[media:pok-6-wyk.pdf|PDF]], [[media:pok-6-wyk-kolor.pdf|PDF kolor]]),[[media:pok-6-lab.pdf| Laboratorium (PDF)]]
* [[pok-7-wyk-toc|Wykład 7: Podstawy kompilatorów. Translacja sterowana składnią w metodzie zstępującej]] ([http://elearning.cs.put.poznan.pl/mediawiki/flash_files/pok/pok-7-wyk/player.html Flash], [[media:pok-7-wyk.pdf|PDF]], [[media:pok-7-wyk-kolor.pdf|PDF kolor]]),[[media:pok-7-lab.pdf| Laboratorium (PDF)]]
* [[pok-8-wyk-toc|Wykład 8: Podstawy kompilatorów. Analiza metodą wstępującą]] ([http://elearning.cs.put.poznan.pl/mediawiki/flash_files/pok/pok-8-wyk/player.html Flash], [[media:pok-8-wyk.pdf|PDF]], [[media:pok-8-wyk-kolor.pdf|PDF kolor]]),[[media:pok-8-lab.pdf| Laboratorium (PDF)]]
* [[pok-9-wyk-toc|Wykład 9: Podstawy kompilatorów. Podstawy generaratora YACC]] ([http://elearning.cs.put.poznan.pl/mediawiki/flash_files/pok/pok-9-wyk/player.html Flash], [[media:pok-9-wyk.pdf|PDF]], [[media:pok-9-wyk-kolor.pdf|PDF kolor]]),[[media:pok-9-lab.pdf| Laboratorium (PDF)]]
* [[pok-10-wyk-toc|Wykład 10: Podstawy kompilatorów. Translacja sterowana składnią w generatorze YACC]] ([http://elearning.cs.put.poznan.pl/mediawiki/flash_files/pok/pok-10-wyk/player.html Flash], [[media:pok-10-wyk.pdf|PDF]], [[media:pok-10-wyk-kolor.pdf|PDF kolor]]),[[media:pok-10-lab.pdf| Laboratorium (PDF)]]
* [[pok-11-wyk-toc|Wykład 11: Podstawy kompilatorów. Generator YACC : gramatyki niejednoznaczne]] ([http://elearning.cs.put.poznan.pl/mediawiki/flash_files/pok/pok-11-wyk/player.html Flash], [[media:pok-11-wyk.pdf|PDF]], [[media:pok-11-wyk-kolor.pdf|PDF kolor]]),[[media:pok-11-lab.pdf| Laboratorium (PDF)]]
* [[pok-12-wyk-toc|Wykład 12: Podstawy kompilatorów. Analiza zależności kontekstowych]] ([http://elearning.cs.put.poznan.pl/mediawiki/flash_files/pok/pok-12-wyk/player.html Flash], [[media:pok-12-wyk.pdf|PDF]], [[media:pok-12-wyk-kolor.pdf|PDF kolor]]),[[media:pok-12-lab.pdf| Laboratorium (PDF)]]
* [[pok-13-wyk-toc|Wykład 13: Podstawy kompilatorów. Synteza kodu i środowisko czasu wykonania]] ([http://elearning.cs.put.poznan.pl/mediawiki/flash_files/pok/pok-13-wyk/player.html Flash], [[media:pok-13-wyk.pdf|PDF]], [[media:pok-13-wyk-kolor.pdf|PDF kolor]]),[[media:pok-13-lab.pdf| Laboratorium (PDF)]]

Wersja z 18:37, 30 sie 2006

Forma zajęć

Wykład (30 godzin) + laboratorium (30 godzin)

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.

Przedmiot "Podstawy kompilatorów" koncentruje się omówieniu etapu analizy kodu i przedstawieniu narzędzi wykorzystywanych w tworzeniu kompilatorów. Pozostałe zagadnienia omówione są szerzej w ramach przedmiotu "Metody realizacji języków programowania".

Sylabus

Autorzy

  • Bartosz Bogacki
  • 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

Zawartość

  • Model kompilatora
    • etapy i fazy kompilacji
  • Analiza leksykalna
    • podstawowe pojęcia
    • języki i wyrażenia regularne
    • niedeterministyczne i deterministyczne automaty skończone
    • implementacja analizatorów leksykalnych w języku C i za pomocą generatora LEX
  • Analiza składniowa
    • podstawowe pojęcia
    • gramatyki bezkontekstowe
    • analiza metodą zstępującą i wstępującą
    • implementacja analizatorów składniowych działających metodą zstępującą w języku C i za pomocą generatora LLgen
    • implementacja analizatorów składniowych działających metodą wstępującą za pomocą generatora YACC
    • translacja sterowana składnią w metodzie zstępującej i wstępującej
    • gramatyki niejednoznaczne
  • Analiza zależności kontekstowych
    • typy zależności kontekstowych
    • implementacja kontrolera typów
  • Synteza kodu i środowisko czasu wykonania
    • generacja kodu pośredniego
    • optymalizacja kodu
    • generacja kodu wynikowego
    • dostęp do nazw nielokalnych
    • dynamiczny przydział pamięci
    • przekazywanie parametrów

Literatura

  • Aho A. V., Sethi R., Ullman J. D., Kompilatory Reguły, metody i narzędzia, WNT 2002
  • Foryś M., Foryś W., Teoria automatów i języków formalnych, Akademicka Oficyna Wydawnicza Exit 2005
  • Tremblay J. P., Sorenson P. G., The Theory and Practice of Compiler Writing, McGraw-Hill, 1985
  • Waite W. M., Goos G., Konstrukcja kompilatorów, WNT 1989
  • Wilhelm R., Maurer D., Compiler Design, Addison-Wesley 1995

Moduły

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Podstawy_kompilatorów&oldid=36001”