Теорія формальних граматик і трансляції

Анотація навчальної дисципліни

Мета дисципліни:
надання знань з теоретичних основ процесу трансляції, придбання навичок розробки формальних мов та побудови компіляторів мов програмування. Необхідність вивчення дисципліни обумовлюється швидким зростанням складності обчислювальних систем, розвитком мов програмування та методів трансляції.
Завдання дисципліни:
ознайомитись з основними поняттями та особливостями побудови компіляторів мов програмування;
вивчити особливості синтаксису для формального опису мов програмування;
отримати знання про формальні граматики та їх використання відповідно до обраної вхідної мови;
сформувати уявлення про підходи до лексичного та синтаксичного аналізу з використанням теорії автоматів та формальних мов;
отримати знання про базові підходи оптимізації програмного коду;
сформувати уявлення про основні напрямки та перспективи розвитку систем програмування.  
Основні результати навчання

Аналізувати, цілеспрямовано шукати і вибирати необхідні для вирішення професійних завдань інформаційно-довідникові ресурси і знання з урахуванням сучасних досягнень науки і техніки.

Знати і застосовувати відповідні математичні поняття, методи доменного, системного і об’єктно-орієнтованого аналізу та математичного моделювання для розробки програмного забезпечення.

Уміння вибирати та використовувати відповідні задачі методології створення програмного забезпечення.

Знати і застосовувати на практиці фундаментальні концепції, парадигми і основні принципи функціонування мовних, інструментальних і обчислювальних засобів інженерії програмного забезпечення.

Знати і застосовувати методи розробки алгоритмів, конструювання програмного забезпечення та структур даних і знань.

Мотивовано обирати мови програмування та технології розробки для розв’язання завдань створення і супроводження програмного забезпечення. 

Форми організації освітнього процесу та види навчальних занять

Л – лекційні заняття; ЛЗ – лабораторні заняття; СРС – самостійна робота здобувача вищої освіти; МКР – модульна контрольна робота; К – консультації.

Тематика та види навчальних занять

1    тиждень

Л1. Визначення прикладного та системного програмне забезпечення. Групи прикладного програмного забезпечення. Визначення системи програмування: основні напрямки та перспективи розвитку. Різновиди та особливості машинно-орієнтованих та машинно-незалежних мов. Поняття транслятора. Особливості компілятора та інтерпретатора.
СРС. К.

2    тиждень

Л2. Різновиди трансляторів. Типовий процес компіляції. Інформаційні таблиці. Призначення лексичного аналізатора (сканера). Призначення синтаксичного та семантичного аналізатора. Внутрішнє представлення програми. Генерація програм. 
ЛЗ1. Вивчення пакета прикладних програм для розробки формальних граматик.
СРС. К.

3    тиждень

Л3. Засоби визначення мови. Форми Бекуса-Наура: звичайні та модифіковані. Особливості БНФ та МБНФ. Синтаксична діаграма. Правила класифікації типів граматики за Хомським. 
СРС. К.

4    тиждень

Л4. Визначення формальної граматики та мови: поняття букви, лексеми, граматики. Початковий символ, правила виводу. Порожні та непорожні мови. Методика виводу ланцюжка символів.
ЛЗ2. Розробка формальних граматик відповідно до вимог щодо мови програмування.
СРС. К.

5    тиждень

Л5. Місце лексичного аналізатора (сканера) у загальній схемі транслятора. Функції та етапи побудови сканера. Постійні та тимчасові таблиці для роботи сканера, взаємозв’язок таблиць. Правила для побудови постійних та тимчасових таблиць. 
СРС. К.

6    тиждень

Л6. Поняття кінцевого автомату. Стани автомату та функції переходу. Детермінований та недетермінований кінцеві автомати. Побудова кінцевого автомату по автоматній граматиці. Обробка помилок у кінцевому автоматі. 
ЛЗ3. Розробка структур даних для лексичного аналізатора (сканера).
СРС. К.

7    тиждень

Л7. Використання узагальненого кінцевого автомату при реалізації лексичного аналізатора (сканера). Методика побудови узагальненого кінцевого автомату. Навантаження узагальненого кінцевого автомату семантичними процедурами.
СРС. К.

8    тиждень

Л8. Призначення синтаксичного аналізатора та його місце у загальній схемі транслятора. Вхідні та вихідні дані для синтаксичного аналізатора. Методи низхідного та висхідного розборів.
ЛЗ4. Розробка узагальненого кінцевого автомата для лексичного аналізатора.
МКР1. СРС. К.

9    тиждень

Л9. Зведення граматики. Алгоритм зведення граматики. Бінарні відношення для граматики. Побудова матриць бінарних відношень. Базові операції над матрицями. Рефлексивні та транзитивні замикання.
СРС. К.

10    тиждень

Л10. Визначення граматики простого передування. Відношення простого передування. Конфлікти у відношеннях між символами граматики, обґрунтування необхідності видалення конфліктів. Типи конфліктів. Методика видалення конфліктів. 
ЛЗ5. Визначення конфліктів та налагодження формальної граматики простого передування.
СРС. К. 

11    тиждень

Л11. Метод синтаксичного аналізу простого передування. Алгоритм синтаксичного аналізу.
СРС. К.

12    тиждень

Л12. Граматика слабкого передування та її особливості. Алгоритм синтаксичного аналізу слабкого передування. Граматика паралельного передування та її особливості. Типи конфліктів та методика видалення конфліктів у граматиці паралельного передування. Алгоритм синтаксичного аналізу паралельного передування.
ЛЗ6. Визначення конфліктів та налагодження формальної граматики паралельного передування.
СРС. К.

13    тиждень

Л13. Різновиди граматик. Переваги згортки та зсуву. Принципи побудови граматики розширеного передування. Метод змішаної стратегії. Контекст правила.
СРС. К.

14    тиждень

Л14. Основні форми внутрішнього представлення програми. Таблиці тріад. Косвені тріади. Таблиці тетрад. Польський запис. Алгоритм перетворення виразу з інфіксної форми у польський запис. Алгоритм перетворення виразу з польського запису в інфіксну форму.
ЛЗ7. Синтаксичний аналіз з використанням алгоритмів простого та паралельного передування.
МКР2.СРС. К.

15    тиждень

Л15. Місце генерації коду у процесі трансляції. Фази оптимізації. Схема генератора коду. 
СРС. К.

Процедура оцінювання

Система оцінювання рівня навчальних досягнень ґрунтується на принципах ЄКТС та є накопичувальною. Здобувачі протягом семестру готуються до лекційних, практичних та лабораторних занять, виконують 2 модульні контрольні роботи.
Для забезпечення оперативного контролю за успішністю та якістю рівня навчальних досягнень здобувачів вищої освіти дисципліна поділяється на два семестрові модулі.

Кожний модуль оцінюється у максимально можливі 50 балів:
Модульна робота складається з теоретичної частини  та практичної частини - задач. 

Максимальна оцінка за правильне виконання теоретичної частини модульної роботи №1 становить 3 бали, за виконання практичної частини – 27 балів. Максимальна оцінка за правильне виконання теоретичної частини модульної роботи №2 становить 2 бали, за виконання практичної частини – 28 балів.
Кількість питань теоретичної частини модульної роботи №1 – 1. Правильна відповідь оцінюється в 3 бали. Кількість питань теоретичної частини модульної роботи №2 – 1. Правильна відповідь оцінюється в 2 бали.
Кількість задач модульної роботи №1 – 9. Правильне розв’язання кожної задачі оцінюється в 3 бали. Задача вважається розв’язаною, якщо коректно визначені правила граматики, розроблено детермінований кінцевий автомат, обчислено матриці бінарних відношень. Кількість задач модульної роботи №2– 7. Правильне розв’язання кожної задачі оцінюється в 4 бали. Задача вважається розв’язаною, якщо при її розв’язанні коректно обчислено матриці простого, паралельного та розширеного передування, безпомилково здійснено перетворення інфіксної форми у польський запис та навпаки.

Максимальна оцінка, яку може отримати здобувач за всі виконані види робіт – 100 балів. 

Підсумковим контролем з дисципліни є усний екзамен, білет до якого складається з теоретичної частини (2 запитання) та практичної частини (3 задачі). За бездоганну відповідь на кожне теоретичне питання студент отримує 20 балів. За бездоганне виконання кожного завдання практичної частини студент отримує 20 балів. 
Максимальна оцінка за правильні відповіді на всі питання екзаменаційного білету становить 100 балів.

Семестровий модуль № 1

ЛЗ1- ЛЗ3. Оцінка за виконання – 15 балів. Поточні контрольні опитування – 5 балів. Термін виконання – 1-8 тиждень. 
МК1. Модульна контрольна робота – 30 балів (8 тиждень). Перескладання можливе протягом 9–11 тижнів за розкладом консультацій.

Семестровий модуль № 2

ЛЗ4- ЛЗ7. Оцінка за виконання – 16 балів. Поточні контрольні опитування – 4 бали. Термін виконання – 9-15 тиждень. 
МК2. Модульна контрольна робота – 30 балів (14 тиждень).

Умови допуску до підсумкового контролю

До екзамену допускаються здобувачі вищої освіти, які виконали всі види навчальних елементів навчальної дисципліни на не менш, ніж на 60%.

Екзамен відбувається за всіма тематичними (змістовними) модулями дисципліни.

Політика освітнього процесу

Здобувач зобов’язаний своєчасно та якісно виконувати всі отримані завдання; за необхідністю з метою з’ясування всіх незрозумілих під час самостійної та індивідуальної роботи питань, відвідувати консультації викладача. Дотримуватись принципів академічної доброчесності.

Виконаний не свій варіант завдання здобувачем не оцінюється.

Робота, яка виконана після встановлених викладачем термінів, не приймається.

Відсутність здобувача на екзамені або на контрольній роботі відповідає оцінці «0». 
Складання/перескладання екзаменів – за встановленим деканатом розкладом.

Під час лекції здійснювати телефонні дзвінки забороняється.

Заборонено використання будь-яких підручників, посібників, конспектів лекцій, шпаргалок під час проходження модульних контролів та екзамену з дисципліни.

Документи (файли), що додаються: Робоча програма навчальної дисципліни.

Література
1.    Вирт, Никлаус. Построение компиляторов, 2-е издание/ Никлаус Вирт. Перевод Е. Борисов, Л. Чернышов. – К.: ДМК Пресс, 2016. – 192 с.  
2.    Ахо, А. В. Компиляторы. Принципы, технологии и инструментарий, 2 издание. / Альфред В. Ахо, Моника С. Лам, Рави Сети. – М.: Вильямс, 2019. – 1184 с.
3.    Хантер, Р. Компиляторы. Краткий справочник (перев.) /  Робин Хантер. – М.: Вильямс, 2018. – 256 с.  
4.    Crespi Reghizzi, Stefano (et al.) Formal Languages and Compilation, 3rd ed. 2019, XIII. – 499 p. 
5.    Kirkpatrick, Lucius. Compiler Construction. – World Technologies, 2013. – 127 p.

Методична література
1.  Конспект лекцій з дисципліни “Теорія формальних граматик і трансляції” для студентів спеціальності 121 – «Інженерія програмного забезпечення» /Укл.: Н.О.Комлева, Л.С. Жиро. – Одеса: ОНПУ, 2018. – 66 с.
2.    Методичні вказівки до лабораторних робіт з дисципліни “Теорія формальних граматик і трансляції” для студентів спеціальності 121 – «Інженерія програмного забезпечення» / Укл.: Н.О.Комлева, Л.С.Жиро. – Одеса: ОНПУ, 2018. – 17 с.

Додаткова література
1.    Комлева Н. О., Зіноватна С. Л., Марулін С. Ю., Оніщенко Т. В. Побудова моделі атрибутів якості формальних граматик та мов програмування. –  Вчені записки ТНУ імені В.І. Вернадського. Серія: технічні науки. –  Київ, 2020. – Том 30 (69) № 6. – С. 77 – 81.
2.    Komleva N.O., Popov S.S. Quality attributes of formal grammars and languages in translator engineering // XII Міжнародна науково-практична конференція «Інформаційні технології і автоматизація – 2019», Одеса, 17-18 жовтня 2019. Том 1. C. 110-112.
3.    Programming Languages and Systems. 29th European Symposium on Programming, ESOP 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin, Ireland, April 25–30, 2020, Proceedings.
4.    Stallings, W. Operating Systems: Internals and Design Principles, 8th ed. / W. Stallings — 2014. 
5.    Таненбаум, Э. Современные операционные системы, 4-е изд. / Э. Таненбаум, Х. Бос — СПб.: Питер, 2015. — 1120 с. 
6.     Love R. Linux Kernel Development, 3rd ed. / Love R. — Addison-Wesley, 2010. — 440 p. 
7.     Руссинович М. Внутреннее устройство Microsoft Windows, 6-е изд. / Руссинович М., Соломон Д., Ионеску А. — СПб.: Питер, 2013. — 800 с. 
8.     Parr, T.J., Quong, R.W. ANTRL: A Predicated-LL(k) Parser Generator // Software Practice And Experience. 1995. №25 (7). Р. 789–810.
9.    Appel, A. W. Modern Compiler Implementation in Java, Second Edition / Andrew W. Appel, Jens Palsberg. – Cambridge University Press, 2002. – 501 p.
10.    Карпов, Ю. Теория и технология программирования. Основы построения трансляторов: учебное пособие. – СПб: БХВ-Петербург, 2005. – 272 с.
11.    Абельсон, Г.    Структура и интерпретация компьютерных программ, 4-е изд. / Г. Абельсон, Дж. Дж. Сассман – MIT Press Cambridge, 1999. – 542 с.