|
|
| (Nie pokazano 9 pośrednich wersji utworzonych przez tego samego użytkownika) |
| Linia 1: |
Linia 1: |
| == Forma zajęć == | | == Forma zajęć == |
| Wykład (30 godzin) + laboratorium (30 godzin) | | Wykład (30 godzin) + laboratorium (60 godzin) |
|
| |
|
| == Opis == | | == Opis == |
| Kompilator jest programem, który przetwarza kod napisany w jednym języku (tzw. języku źródłowym) na równoważny kod w drugim języku (tzw. języku wynikowym).
| | W ramach tego przedmiotu będą omawiane cztery najistotniejsze obecnie paradygmaty programowania (programowanie imperatywne, obiektowe, funkcyjne i programowanie w logice) oraz związane z nimi języki programowania. Zajęcia te mają dać uczestnikom szersze spojrzenie na programowanie, pokazać cechy wspólne i różnice pomiędzy typowymi dla tych paradygmatów językami oraz pokazać metody kompilacji i realizacji programów zapisanych w tych językach. Przedsatwione zostaną poszczególne fazy kompilacji (analiza leksykalna, składniowa i kontekstowa oraz generacja kodu wynikowego) jak również zagadnienia czasu wykonania (takie jak zarządzanie pamięcią). |
| Na rynku funkcjonuje wiele typów kompilatorów dla różnych języków źródłowych i wynikowych oraz wiele narzędzi pokrewnych kompilatorom, takich jak statyczne analizatory i kontrolery kodu, formatery programów źródłowych, kompilatory krzemowe i interpretery zapytań.
| | Istotna cechą tych zajęć jest duża liczba praktycznych ćwiczeń, dających studentom możliwości praktycznego zastosowania prezentowanych paradygmatów (szczególnie tych z którymi dotąd nie mieli do czynienia w czasie studiów) oraz poznania konkretnych narzędzi pozwalających szybko tworzyć parsery i kompilatory. |
| Wraz z rozszerzaniem zakresu zastosowań informatyki oraz pojawianiem się nowych technologii, powstaje potrzeba rozwijania i tworzenia nowych narzędzi tego typu. Zasady i techniki pisania kompilatorów są na tyle ogólne, że obejmują wiedzę z zakresu języków programowania, architektury maszynowej, teorii języków oraz algorytmikę i inżynierię oprogramowania.
| |
| Pierwsze kompilatory powstały w latach 50. i powszechnie uważane były wówczas za programy trudne do napisania. Od tego czasu wytworzono jednak systematyczne techniki wykonywania poszczególnych zadań pojawiających się w trakcie kompilacji, stworzono odpowiednie języki implementacji, środowiska i narzędzia programistyczne istotnie upraszczające te zadania.<br>
| |
| Celem przedmiotu ''Podstawy kompilatorów'' jest przedstawienie zasad, technik i narzędzi wykorzystywanych współcześnie do budowy kompilatorów.<br>
| |
| W ramach przedmiotu przedstawione zostaną zasady implementacji kompilatorów, zarówno z wykorzystaniem specjalizowanych narzędzi takich jak LEX, YACC i LLgen, 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ę na 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 == |
|
| |
|
| === Autor sylabusa === | | === Autor === |
| * Wojciech Complak — Politechnika Poznańska | | Janusz Jabłonowski na podstawie materiałów z Ważniaka autorstwa: |
| | | * Małgorzata Moczurad — Uniwersytet Jagielloński |
| === Autorzy kursu ===
| | * Włodzimierz Moczurad — Uniwersytet Jagielloński |
| Kurs został opracowany przez zespół pracowników Instytutu Informatyki Politechniki Poznańskiej w składzie:
| |
| * dr inż. Wojciech Complak | |
| * mgr inż. Bartosz Bogacki
| |
|
| |
|
| === Wymagania wstępne === | | === Wymagania wstępne === |
| * Umiejętność konstruowania algorytmów iteracyjnych i rekurencyjnych | | * Logika i teoria mnogości |
| * Umiejętność programowania w imperatywnych językach wysokiego poziomu | | * Wstęp do programowania |
| * Podstawowa znajomość architektury procesora i języka asemblera | | * Algorytmy i struktury danych |
| | * Języki, automaty i obliczenia |
|
| |
|
| === Zawartość === | | === Zawartość === |
| * Pierwszy moduł poświęcony jest omówieniu modelu kompilatora, planu i zakresu przedmiotu oraz literatury i narzędzi potrzebnych do wykonywania ćwiczeń. W ramach modułu przedstawiono model kompilatora typu analiza-synteza i zadania wykonywane w fazach analizy leksykalnej, analizy składniowej i analizy semantycznej, wchodzących w skład etapu analizy, oraz fazach generacji kodu pośredniego, generacji i optymalizacji kodu wynikowego, wchodzących w skład etapu syntezy. Omówiono również zagadnienia dotyczące budowy środowiska wykonawczego, takie jak dostęp do nazw nielokalnych, dynamiczny przydział pamięci i przekazywanie parametrów do podprogramów. | | |
| * Kolejna część kursu składa się z dwóch modułów, w których omówiono fazę analizy leksykalnej. Pierwszy moduł tego cyklu jest ogólnym wprowadzeniem do analizy leksykalnej. Przedstawiono zadania, jakie ma do wykonania analizator leksykalny, podstawowe pojęcia związane z analizą leksykalną, konstruowanie niedeterministycznych i deterministycznych automatów skończonych oraz implementowanie na podstawie deterministycznych automatów skończonych prostych analizatorów leksykalnych w uniwersalnych językach programowania na przykładzie języka C. Drugi moduł tego cyklu poświęcony jest omówieniu specjalizowanego narzędzia do tworzenia analizatorów leksykalnych, jakim jest generator LEX. W module przedstawiono ogólną charakterystykę i filozofię działania generatora i wygenerowanych za jego pomocą analizatorów, składnię specyfikacji analizatorów leksykalnych, posługiwanie się definicjami regularnymi i wzorcami oraz prawym i lewym kontekstem. | | * Pojęcia ogólne: |
| * Kolejne osiem modułów tworzy cykl poświęcony analizie składniowej. Pierwszy moduł tego cyklu jest ogólnym wprowadzeniem do analizy składniowej. W ramach modułu omówiono pojęcia związane z posługiwaniem się gramatykami bezkontekstowymi, takie jak jednostki terminalne i nieterminalne, produkcje, wywody, rekurencję prawostronną i lewostronną, niejednoznaczność i równoważność gramatyk bezkontekstowych. W drugim module omówione jest prowadzenie analizy składniowej metodą zstępującą (LL). Przedstawiono ogólną charakterystykę metody zstępującej i metody konstruowania analizatorów działających zgodnie z tą metodą. Wskazano także na ograniczenia, jakie metoda zstępująca nakłada na postać gramatyki źródłowej, zademonstrowano metody dostosowywania gramatyk do odpowiedniej postaci oraz zasady implementacji analizatorów działających metodą zstępującą w uniwersalnym języku programowania na przykładzie języka C. Ważną zaletą metody zstępującej jest możliwość implementowania nawet stosunkowo złożonych analizatorów bezpośrednio w uniwersalnym języku programowania. W przypadku większych projektów korzystne jest jednak użycie specjalizowanego narzędzia, takiego jak generator analizatorów składniowych LLgen. Generator ten został przedstawiony w ramach kolejnego modułu, który zawiera jego ogólną charakterystykę, opis współpracy z analizatorem leksykalnym, omówienie rozszerzeń gramatyk bezkontekstowych wprowadzonych w tym generatorze oraz środowiska generatora i mechanizmów rozstrzygania konfliktów składniowych alternatyw i powtórzeń charakterystycznych dla analizy składniowej prowadzonej metodą zstępującą. W ramach kolejnego modułu przedstawiono translację sterowaną składnią — metodę translacji języków opartą o gramatyki bezkontekstowe. Przedstawiono pojęcia atrybutów syntetyzowanych i dziedziczonych, definicji sterowanych składnią, schematów translacji oraz definicji S-atrybutowych i L-atrybutowych. W drugiej części modułu omówiono zasady implementacji translacji sterowanej składnią w uniwersalnym języku programowania na przykładzie języka C oraz w generatorze LLgen. Kolejny moduł cyklu jest wprowadzeniem do silniejszej metody analizy składniowej – metody wstępującej (LR). W module przedstawiono ogólną charakterystykę metody, zasady konstruowania i działania analizatorów działających metodą LR i metody rozstrzygania konfliktów składniowych. W przypadku metody wstępującej, tworzenie analizatorów składniowych bezpośrednio w uniwersalnym języku programowania jest praktycznie nierealne. Dlatego w kolejnym module przedstawione jest najpopularniejsze specjalistyczne narzędzie wykorzystywane do tworzenia analizatorów składniowych działających metodą wstępującą — generator YACC. W ramach modułu przedstawiono ogólną charakterystykę generatora YACC, składnię specyfikacji analizatora składniowego, zasady współpracy z analizatorem leksykalnym oraz wykrywania i obsługi błędów składniowych. W kolejnym module omawiana jest translacja sterowana składnią w metodzie wstępującej z wykorzystaniem generatora YACC. Przedstawiono sposoby deklarowania i używania różnych typów atrybutów oraz zasady korzystania z atrybutów syntetyzowanych i dziedziczonych. Ostatni moduł z cyklu dotyczącego fazy analizy składniowej poświęcono posługiwaniu się gramatykami niejednoznacznymi w metodzie wstępującej w generatorze YACC. W ramach modułu najpierw pokazano, dlaczego warto posługiwać się gramatykami niejednoznacznymi, a następnie omówiono zasady wykorzystywania ich w generatorze YACC. Przedstawiono sposoby rozstrzygania konfliktów przesuń/redukuj i redukuj/redukuj charakterystycznych dla metody wstępującej przy pomocy opisywania łączności i priorytetów. Następnie omówiono przykłady typowych problemów spotykanych w implementacji translatorów dla popularnych języków programowania – problem tzw. ''wiszącego else'' i korzystanie z przypadków specjalnych. | | ** opis składni i semantyki języków programowania |
| * Kolejny moduł poświęcony jest analizie semantycznej. Przedstawiono różne typy kontroli zależności kontekstowych, takie jak sprawdzenie przepływu sterowania, sprawdzenie unikalności deklaracji nazw i sprawdzenie powtórzeń nazw. W ramach modułu szczególny nacisk położono na najtrudniejszą w implementacji kontrolę — sprawdzanie zgodności typów. Przedstawiono koncepcję nazwowej i strukturalnej zgodności typów oraz szkielet prostego kontrolera zgodności typów. | | ** typy |
| * Ostatni moduł poświęcony jest etapowi syntezy kodu i zagadnieniom dotyczącym budowy środowiska wykonawczego. Omówiono fazę generacji kodu pośredniego oraz różne typy języków pośrednich ze szczególnym naciskiem na kod trójadresowy. Zademonstrowano przykładowe optymalizacje kodu, wykonywane zarówno w fazie generacji kodu pośredniego, jak i w fazie generacji kodu wynikowego. Omówiono również niektóre zagadnienia dotyczące budowy środowiska wykonawczego, takie jak dostęp do nazw nielokalnych, dynamiczny przydział pamięci i przekazywanie parametrów do podprogramów. | | ** przekazywanie parametrów do podprogramów |
| | ** abstrakcyjne typy danych |
| | ** przeciążanie nazw |
| | ** polimorfizm |
| | |
| | * Programowanie imperatywne: |
| | ** zmienne |
| | ** struktura blokowa |
| | ** wiązanie statyczne i dynamiczne |
| | ** organizacja wywołań podprogramów |
| | ** przydział pamięci na stosie i na stercie |
| | ** przykłady z języków Ada, C, Pascal |
| | |
| | * Programowanie obiektowe: |
| | ** klasy jako abstrakcyjne typy danych |
| | ** dziedziczenie |
| | ** późne (dynamiczne) wiązanie wywołań |
| | ** polimorfizm |
| | ** szablony i klasy uogólnione |
| | ** przykłady z języków C++, Java, C#, Ada 95, Smalltalk |
| | |
| | * Programowanie funkcyjne: |
| | ** funkcje jako model programowania |
| | ** rachunek lambda |
| | ** dopasowywanie wzorca |
| | ** uzgadnianie typów |
| | ** rekursja |
| | ** leniwe wyliczanie |
| | ** funkcje wyższego rzędu |
| | ** przykłady z języków Lisp, Scheme, ML, Haskell |
| | |
| | * Programowanie w logice: |
| | ** rachunek predykatów w Prologu |
| | ** rezolucja |
| | ** listy |
| | |
| | * Zagadnienia kompilacji |
| | ** Analiza leksykalna |
| | ** Analiza składniowa |
| | ** Analiza kontekstowa |
| | ** Generowanie kodu |
| | |
| | * Zagadnienia czasu wykonania |
| | ** Realizacja wywołań procedur (funkcji) i metod |
| | ** Zarządzanie pamięcią |
| | ** Przechowywanie środowisk |
|
| |
|
| === Literatura === | | === Literatura === |
| * A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman, ''Compilers: Principles, Techniques, and Tools, 2/E'' (w języku polskim dostępne jest tłumaczenie poprzedniej wersji tej książki z 1986 roku: A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman, ''Kompilatory. Reguły, metody i narzędzia'', Wydawnictwa Naukowo-Techniczne, Warszawa 2002).
| | |
| * M. Foryś,W. Foryś, ''Teoria automatów i języków formalnych'', Akademicka Oficyna Wydawnicza Exit, 2005.
| | # R. Sebesta, ''Concepts of Programming Languages'', Addison Wesley, 2005 |
| * J.P. Tremblay, P.G. Sorenson, ''The Theory and Practice of Compiler Writing'', McGraw-Hill, 1985.
| | # P. Van Roy, S. Haridi, ''Concepts, Techniques, and Models of Computer Programming'', MIT Press, 2004 |
| * W.M. Waite,G. Goos, ''Konstrukcja kompilatorów'', Wydawnictwa Naukowo-Techniczne, Warszawa 1989.
| | # J. Reynolds, ''Theories of Programming Languages'', Cambridge University Press, 1998 |
| * R. Wilhelm, D. Maurer, ''Compiler Design'', Addison-Wesley, 1995.
| | # K. Arnold, J. Gosling, ''The Java Programming Language'' Addison Wesley, 2005 |
| | # R. Bird, ''Introduction to Functional Programming using Haskell'', Prentice Hall, 1988 |
| | # F. Kluźniak, S. Szpakowicz, ''Prolog'', Wydawnictwa Naukowo-Techniczne, 1983 |
| | # A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman, ''Compilers: Principles, Techniques, and Tools, 2/E'', Addison Wesley, 2006 (w języku polskim dostępne jest tłumaczenie poprzedniej wersji tej książki z 1986 roku: A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman, ''Kompilatory. Reguły, metody i narzędzia'', Wydawnictwa Naukowo-Techniczne, Warszawa 2002). |
| | # W.M. Waite,G. Goos, ''Konstrukcja kompilatorów'', Wydawnictwa Naukowo-Techniczne, Warszawa 1989. |
Forma zajęć
Wykład (30 godzin) + laboratorium (60 godzin)
Opis
W ramach tego przedmiotu będą omawiane cztery najistotniejsze obecnie paradygmaty programowania (programowanie imperatywne, obiektowe, funkcyjne i programowanie w logice) oraz związane z nimi języki programowania. Zajęcia te mają dać uczestnikom szersze spojrzenie na programowanie, pokazać cechy wspólne i różnice pomiędzy typowymi dla tych paradygmatów językami oraz pokazać metody kompilacji i realizacji programów zapisanych w tych językach. Przedsatwione zostaną poszczególne fazy kompilacji (analiza leksykalna, składniowa i kontekstowa oraz generacja kodu wynikowego) jak również zagadnienia czasu wykonania (takie jak zarządzanie pamięcią).
Istotna cechą tych zajęć jest duża liczba praktycznych ćwiczeń, dających studentom możliwości praktycznego zastosowania prezentowanych paradygmatów (szczególnie tych z którymi dotąd nie mieli do czynienia w czasie studiów) oraz poznania konkretnych narzędzi pozwalających szybko tworzyć parsery i kompilatory.
Sylabus
Autor
Janusz Jabłonowski na podstawie materiałów z Ważniaka autorstwa:
- Małgorzata Moczurad — Uniwersytet Jagielloński
- Włodzimierz Moczurad — Uniwersytet Jagielloński
Wymagania wstępne
- Logika i teoria mnogości
- Wstęp do programowania
- Algorytmy i struktury danych
- Języki, automaty i obliczenia
Zawartość
- Pojęcia ogólne:
- opis składni i semantyki języków programowania
- typy
- przekazywanie parametrów do podprogramów
- abstrakcyjne typy danych
- przeciążanie nazw
- polimorfizm
- Programowanie imperatywne:
- zmienne
- struktura blokowa
- wiązanie statyczne i dynamiczne
- organizacja wywołań podprogramów
- przydział pamięci na stosie i na stercie
- przykłady z języków Ada, C, Pascal
- Programowanie obiektowe:
- klasy jako abstrakcyjne typy danych
- dziedziczenie
- późne (dynamiczne) wiązanie wywołań
- polimorfizm
- szablony i klasy uogólnione
- przykłady z języków C++, Java, C#, Ada 95, Smalltalk
- Programowanie funkcyjne:
- funkcje jako model programowania
- rachunek lambda
- dopasowywanie wzorca
- uzgadnianie typów
- rekursja
- leniwe wyliczanie
- funkcje wyższego rzędu
- przykłady z języków Lisp, Scheme, ML, Haskell
- Programowanie w logice:
- rachunek predykatów w Prologu
- rezolucja
- listy
- Zagadnienia kompilacji
- Analiza leksykalna
- Analiza składniowa
- Analiza kontekstowa
- Generowanie kodu
- Zagadnienia czasu wykonania
- Realizacja wywołań procedur (funkcji) i metod
- Zarządzanie pamięcią
- Przechowywanie środowisk
Literatura
- R. Sebesta, Concepts of Programming Languages, Addison Wesley, 2005
- P. Van Roy, S. Haridi, Concepts, Techniques, and Models of Computer Programming, MIT Press, 2004
- J. Reynolds, Theories of Programming Languages, Cambridge University Press, 1998
- K. Arnold, J. Gosling, The Java Programming Language Addison Wesley, 2005
- R. Bird, Introduction to Functional Programming using Haskell, Prentice Hall, 1988
- F. Kluźniak, S. Szpakowicz, Prolog, Wydawnictwa Naukowo-Techniczne, 1983
- A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman, Compilers: Principles, Techniques, and Tools, 2/E, Addison Wesley, 2006 (w języku polskim dostępne jest tłumaczenie poprzedniej wersji tej książki z 1986 roku: A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman, Kompilatory. Reguły, metody i narzędzia, Wydawnictwa Naukowo-Techniczne, Warszawa 2002).
- W.M. Waite,G. Goos, Konstrukcja kompilatorów, Wydawnictwa Naukowo-Techniczne, Warszawa 1989.
