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

1. Wstęp, organizacja procesu kompilacji (omówienie przedmiotu, rodzaje translatorów, interpretacja a kompilacja, model kompilatora, podział na fazy)
2. 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)
3. Implementacja analizatorów leksykalnych z wykorzystaniem generatora Lex (koncepcja i używanie generatora, konwencje notacyjne, wzorce, akcje, retrakcja, konteksty, odrzucenie dopasowania)
4. 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)
5. Analiza metodą zstępującą (koncepcja metody top-down, metody implementacji, predykcja, analizatory z nawracaniem i bez nawracania, lewostronna rekurencja, faktoryzacja)
6. Implementacja analizatora zstępującego analizatora składniowego w języku imperatywnym (na przykładzie języka C)
7. Generowanie analizatorów działających metodą zstępującą za pomocą generatora LLGen
8. Analiza metodą wstępującą (koncepcja metody bottom-up, LR-parsery, metody generowania tablic)
9. Podstawy generatora YACC
10. Generator YACC : gramatyki niejednoznaczne, konflikty, rozstrzyganie
11. Translacja sterowana składnią w metodzie zstępującej, realizacja translacji w języku C i generatorze LLGen
12. Translacja sterowana składnią w generatorze YACC (atrybuty i implementacja, akcje wielokrotne)
13. Analiza zależności kontekstowych (systemy typów, kontrola zgodności typów, konwersje)

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