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 i YACC 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.
Oprócz wykładów będą prowadzone ćwiczenia laboratoryjne, w trakcie których rozwiązywane będą zadania ilustrujące zagadnienia omawiane na wykładach.
Sylabus
Autorzy
- Wojciech Complak
- 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ść
- Wstęp, organizacja procesu kompilacji (omówienie przedmiotu, rodzaje translatorów, interpretacja a kompilacja, model kompilatora, podział na fazy)
- Analiza leksykalna (wprowadzenie do analizy leksykalnej, podstawowe pojęcia, rozpoznawanie wzorców, automaty NFA, DFA, implementacja analizatorów leksykalnych w językach imperatywnych na przykładzie języka C)
- Implementacja analizatorów leksykalnych z wykorzystaniem generatora Lex (koncepcja i używanie generatora, konwencje notacyjne, wzorce, akcje, retrakcja, konteksty, odrzucenie dopasowania)
- Wstęp do analizy składniowej (podstawowe pojęcia analizy składniowej, klasyfikacja gramatyk a implementacja i wydajność analizatorów, gramatyki bezkontekstowe, wywody, drzewa rozbioru)
- Analiza metodą zstępującą (koncepcja metody top-down, metody implementacji, predykcja, analizatory z nawracaniem i bez nawracania, lewostronna rekurencja, faktoryzacja, implementacja na przykłądzie języka C)
- Generowanie analizatorów działających metodą zstępującą za pomocą generatora LLGen
- Analiza metodą wstępującą (koncepcja metody bottom-up, LR-parsery, metody generowania tablic)
- Podstawy generatora YACC
- Generator YACC : gramatyki niejednoznaczne, konflikty, rozstrzyganie
- Translacja sterowana składnią w metodzie zstępującej, realizacja translacji w języku C i generatorze LLGen
- Translacja sterowana składnią w generatorze YACC (atrybuty i implementacja, akcje wielokrotne)
- Analiza zależności kontekstowych (systemy typów, kontrola zgodności typów, konwersje)
- Pozostałe zagadnienia
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
