MIMINF:Języki i paradygmaty programowania

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. Przy omawianiu kompilacji omaó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.

Istotna cechą tych zajęc, jest duża liczba praktycznych ćwiczeń, chodzi o danie studentom możliwości praktycznego zastosowania prezentowanych paradygmatów (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. 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

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 operatorów i podprogramów
  • 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 rodzajowe
  • przykłady z języków C++, Java, C#, Ada 95, Smalltalk

• Programowanie funkcyjne:
  • funkcje jako model programowania
  • rachunek lambda
  • dopasowywanie wzorca
  • nadawanie typów
  • rekursja
  • leniwa ewaluacja
  • 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

Literatura

1. R. Sebesta, Concepts of Programming Languages, Addison Wesley, 2005
2. P. Van Roy, S. Haridi, Concepts, Techniques, and Models of Computer Programming, MIT Press, 2004
3. K. Arnold, J. Gosling, The Java Programming Language Addison Wesley, 2005
4. R. Bird, Introduction to Functional Programming using Haskell, Prentice Hall, 1988
5. M. Moczurad, Wybrane zagadnienia z teorii rekursji, Wydawnictwo UJ, 2002
6. M. Abadi, L. Cardelli, A Theory of Objects, Springer, 1996.
7. J. Reynolds, Theories of Programming Languages, Cambridge University Press, 1998
8. F. Kluźniak, S. Szpakowicz, Prolog, Wydawnictwa Naukowo-Techniczne, 1983
9. U. Nilsson, J. Małuszyński, Logic, Programming and Prolog, John Wiley & Sons, 1995

---

Sylabus

Autor sylabusa

• Wojciech Complak — Politechnika Poznańska

Autorzy kursu

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

• 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ść

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

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.
• J.P. Tremblay, P.G. Sorenson, The Theory and Practice of Compiler Writing, McGraw-Hill, 1985.
• W.M. Waite,G. Goos, Konstrukcja kompilatorów, Wydawnictwa Naukowo-Techniczne, Warszawa 1989.
• R. Wilhelm, D. Maurer, Compiler Design, Addison-Wesley, 1995.