Podstawy kompilatorów

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

• Wykład 1: Podstawy kompilatorów. Wprowadzenie do przedmiotu (Flash, PDF, PDF kolor), Laboratorium (PDF)
• Wykład 2: Podstawy kompilatorów. Analiza leksykalna (Flash, PDF, PDF kolor), Laboratorium (PDF)
• Wykład 3: Podstawy kompilatorów. Implementacja analizatorów leksykalnych (Flash, PDF, PDF kolor), Laboratorium (PDF)
• Wykład 4: Podstawy kompilatorów. Wstęp do analizy składniowej (Flash, PDF, PDF kolor), Laboratorium (PDF)
• Wykład 5: Podstawy kompilatorów. Analiza metodą zstępującą (Flash, PDF, PDF kolor), Laboratorium (PDF)
• Wykład 6: Podstawy kompilatorów. Generowanie analizatorów działających metodą zstępującą (Flash, PDF, PDF kolor), Laboratorium (PDF)
• Wykład 7: Podstawy kompilatorów. Translacja sterowana składnią w metodzie zstępującej (Flash, PDF, PDF kolor), Laboratorium (PDF)
• Wykład 8: Podstawy kompilatorów. Analiza metodą wstępującą (Flash, PDF, PDF kolor), Laboratorium (PDF)
• Wykład 9: Podstawy kompilatorów. Podstawy generaratora YACC (Flash, PDF, PDF kolor), Laboratorium (PDF)
• Wykład 10: Podstawy kompilatorów. Translacja sterowana składnią w generatorze YACC (Flash, PDF, PDF kolor), Laboratorium (PDF)
• Wykład 11: Podstawy kompilatorów. Generator YACC : gramatyki niejednoznaczne (Flash, PDF, PDF kolor), Laboratorium (PDF)
• Wykład 12: Podstawy kompilatorów. Analiza zależności kontekstowych (Flash, PDF, PDF kolor), Laboratorium (PDF)
• Wykład 13: Podstawy kompilatorów. Synteza kodu i środowisko czasu wykonania (Flash, PDF, PDF kolor), Laboratorium (PDF)