Podstawy kompilatorów

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Forma zajęć

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

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). 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ń. 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.
Celem przedmiotu Podstawy kompilatorów jest przedstawienie zasad, technik i narzędzi wykorzystywanych współcześnie do budowy kompilatorów.
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

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.

Moduły