Podstawy kompilatorów

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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-tych 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

  • Dr inż. Wojciech Complak
    E-mail: Wojciech.Complak@cs.put.poznan.pl

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, 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, definicji S-atrybutowych i L-atrybutowych oraz praktycznych implikacji związanych z tymi typami definicji. 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 tworzenia analizatorów składniowych bez wykorzystania specjalizowanych narzędzi jest praktycznie nierealne i dlatego w kolejnym module przedstawione jest najbardziej popularne narzędzie wykorzystywane do generowania 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 wykrywanie i obsługę 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żywanie 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 jak rozstrzygać konflikty przesuń/redukuj i redukuj/redukuj charakterystyczne 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 zależności kontekstowych takie jak sprawdzenie przepływu sterowania, kontrolę unikalności deklaracji nazw i kontrolę 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

  • Aho A. V., Lam M. S., Sethi R., Ullman J. D., Compilers: Principles, Techniques, and Tools, 2/E (w języku polskim dostępne jest tłumaczenie poprzedniej wersji tej książki z 1986 roku: 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=49949”