Генератор компіляторів

Робоча програма навчальної дисципліни (відповідно до вимог МОН України).
Документ містить мету, результати навчання, структуру змісту, систему оцінювання та літературу.

Код курсу: КА-121-01

Кафедра: Кафедра мовного забезпечення

Кількість кредитів ECTS: 12 (360 годин)

Рівень: Бакалавр / Магістр

Авторський колектив: Ахо, Сеті, Ульман (класичний базис)

Мета та завдання

Формування глибоких знань і практичних навичок з побудови генераторів компіляторів та інтерпретаторів. Курс охоплює повний цикл від синтаксичного аналізу (LL, LR, LALR, PEG, комбінатори, рекурсивний спуск) до семантичного аналізу, генерації коду, алокації регістрів та інтерпретації, з акцентом на відмінності між класами граматик і практичними реалізаціями (C99, APL).

Результати навчання

• Розрізняти та реалізовувати LL(1), LR(1), LALR(1) та більш суворі форми граматик.
• Будувати парсери на основі PEG та комбінаторів.
• Реалізовувати рекурсивний спуск, типовий для C99 та APL-інтерпретаторів.
• Виконувати семантичний аналіз, алокацію регістрів та генерацію коду.
• Проєктувати повний конвеєр компілятора / інтерпретатора.

Структура курсу (модулі)

1. Синтаксичний аналіз
   Граматики та класи: LL(1), LR(0), LR(1), LALR(1), SLR. Відмінності в потужності, конфліктах зсуву/зведення, розмірах таблиць. Генератори (yacc/bison, ANTLR). PEG (Parsing Expression Grammars) та парсерні комбінатори. Рекурсивний спуск: ручна реалізація, притаманна інтерпретаторам C99 та APL. Лексичний аналіз як прелюдія.
2. Семантичний аналіз
   Атрибутні граматики, перевірка типів, таблиці символів, область видимості, роздільна компіляція. Семантичні дії під час парсингу (LL/LR).
3. Алокація регістрів
   Граф інтерференції, розфарбування графа (Chaitin), лінійне сканування, spilling. Взаємодія з генерацією коду.
4. Компіляція
   Проміжне представлення (AST, IR, SSA). Генерація коду для регістрових машин. Оптимізації (локальні, глобальні). Повний конвеєр від вихідного коду до машинного / байткоду.
5. Інтерпретація
   Деревоподібні та стекові інтерпретатори. Байткод-машини. Лінива та сувора семантика. Практичні приклади: мінімальні інтерпретатори в стилі C99 (рекурсивний спуск + AST) та APL-подібні векторизовані інтерпретатори.
6. Практична лабораторна: повний мінімальний генератор / інтерпретатор
   Реалізація парсера (рекурсивний спуск або комбінатори), семантичного аналізу та простої генерації / інтерпретації.

Система оцінювання (100 балів)

• Поточний контроль (лабораторні, реалізація парсерів, звіти): 40 балів
• Модульні контрольні роботи (2): 20 балів
• Підсумковий проєкт (мінімальний компілятор або інтерпретатор): 40 балів

Шкала: 90–100 — відмінно; 75–89 — добре; 60–74 — задовільно; <60 — незадовільно.

Рекомендована література

• Aho A.V., Sethi R., Ullman J.D. Compilers: Principles, Techniques, and Tools (Dragon Book). 1986 / 2006.
• Grune D., Jacobs C.J.H. Parsing Techniques: A Practical Guide. 2008.
• Ford B. Parsing Expression Grammars: A Recognition-Based Syntactic Foundation. 2004.
• Appel A.W. Modern Compiler Implementation in ML / Java / C. 1998.
• Cooper K.D., Torczon L. Engineering a Compiler. 2011.
• Матеріали з рекурсивного спуску, комбінаторних парсерів та практичних реалізацій (C, APL).

← Назад до каталогу курсів