Mandatory discipline
Навчальна дисципліна професійної підготовки
Теорія формальних граматик і трансляції
Обсяг освітнього компонента:
• у кредитах ЄКТС — 4.5.
Кількість аудиторних занять:
15 лекцій, 7 лабораторних занять.
Самостійна робота:
складає 91 годину. Самостійна робота здобувача відбувається впродовж семестру та складається з підготовки до аудиторних занять та контрольних заходів.
Семестровий контроль:
Exam.
Освітню компоненту забезпечує:
Викладач:
Анотація:
Анотація навчальної дисципліни
Мета вивчення дисципліни
Набуття знань з теоретичних основ процесу трансляції, придбання навичок розробки формальних мов та побудови компіляторів мов програмування. Необхідність вивчення дисципліни обумовлюється швидким зростанням складності обчислюваних систем, розвитком мов програмування та методів трансляції.
Практичне значення та використання отриманих знань
Знайомство з основними поняттями та особливостями побудови компіляторів мов програмування; вивчення особливостей синтаксису для формального опису мов програмування; отримання знань про формальні граматики та їх використання відповідно до обраної вхідної мови; формування уявлення про підходи до лексичного та синтаксичного аналізу з використанням теорії автоматів та формальних мов; отримання знань про базові підходи оптимізації програмного коду; формування уявлень про основні напрямки та перспективи розвитку систем програмування.
Основні результати навчання
ПРН05. Знати і застосовувати відповідні математичні поняття, методи доменного, системного і об’єктно-орієнтованого аналізу та математичного моделювання для розробки програмного забезпечення.
ПРН07. Знати і застосовувати на практиці фундаментальні концепції, парадигми і основні принципи функціонування мовних, інструментальних і обчислювальних засобів інженерії програмного забезпечення.
ПРН13. Знати і застосовувати методи розробки алгоритмів, конструювання програмного забезпечення та структур даних і знань.
ПРН15. Мотивовано обирати мови програмування та технології розробки для розв’язання завдань створення і супроводження програмного забезпечення.
Тематика та види навчальних занять
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. Синтаксичний аналіз з використанням алгоритмів простого та паралельного передування.
15 тиждень
Лекція 15. Внутрішні форми представлення програми.
Модульна контрольна робота 2.
Оцінювання результатів навчання
Оцінювання результатів навчання з дисципліни здійснюється за накопичувальною системою, яка дає можливість здобувачеві протягом семестру отримати максимально 100 балів.
Модуль 1
Оцінка за виконання лабораторних робіт – максимально 20 балів за модуль.
Модульна контрольна робота 1 – за бездоганне виконання 30 балів (в кожному завданні модульної контрольної роботи наведено максимальну кількість балів за виконання завдання).
Модуль 2
Оцінка за виконання лабораторних робіт – максимально 20 балів за модуль.
Модульна контрольна робота 2 – за бездоганне виконання 30 балів (в кожному завданні модульної контрольної роботи наведено максимальну кількість балів за виконання завдання).
Посилання на рекомендовані джерела
1. Douglas Thain. Introduction to Compilers and Language Design, 2nd edition, 2020. - 247 p.
2. Harold Abelson, Gerald Jay Sussman. Structure and Interpretation of Computer Programs: JavaScript Edition. - The MIT Press Cambridge, Massachusetts London, England. - 640 p.
3. Sherzod Turaev, Rawad Abdulghafor, Ali Amer Alwan, Ali Abd Almisreb, Yonis Gulzar. Binary Context-Free Grammars. - Symmetry 2020, 12(8), 1209; doi:10.3390/sym12081209
4. О. І. Марченко Основи проектування трансляторів: навчальний посібник. – Київ, КПІ ім. Ігоря Сікорського, 2021. – 108 с.
5. Гаврилків В.М. Формальні мови та алгоритмічні моделі: навч. посібник. - Івано-Франківськ: Голіней, 2023. - 180 с.
▪ 2022