Podstawy kompilatorów

Forma zajęć

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

Opis

Celem przedmiotu jest przedstawienie zasad i technik budowy kompilatorów. W ramach przedmiotu przedstawione zostaną zasady ich implementacji, 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

Autorzy

• Bartosz Bogacki
• Wojciech Complak

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

• Model kompilatora
  • etapy i fazy kompilacji
• Analiza leksykalna
  • podstawowe pojęcia
  • języki i wyrażenia regularne
  • niedeterministyczne i deterministyczne automaty skończone
  • implementacja analizatorów leksykalnych w języku C i za pomocą generatora LEX
• Analiza składniowa
  • podstawowe pojęcia
  • gramatyki bezkontekstowe
  • analiza metodą zstępującą i wstępującą
  • implementacja analizatorów składniowych działających metodą zstępującą w języku C i za pomocą generatora LLgen
  • implementacja analizatorów składniowych działających metodą wstępującą za pomocą generatora YACC
  • translacja sterowana składnią w metodzie zstępującej i wstępującej
  • gramatyki niejednoznaczne
• Analiza zależności kontekstowych
  • typy zależności kontekstowych
  • implementacja kontrolera typów
• Synteza kodu i środowisko czasu wykonania
  • generacja kodu pośredniego
  • optymalizacja kodu
  • generacja kodu wynikowego
  • dostęp do nazw nielokalnych
  • dynamiczny przydział pamięci
  • przekazywanie parametrów

Literatura

• 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

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