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

Мета вивчення дисципліни
Набуття знань з теоретичних основ процесу трансляції, придбання навичок розробки формальних мов та побудови компіляторів мов програмування. Необхідність вивчення дисципліни обумовлюється швидким зростанням складності обчислюваних систем, розвитком мов програмування та методів трансляції.
Практичне значення та використання отриманих знань
Знайомство з основними поняттями та особливостями побудови компіляторів мов програмування; вивчення особливостей синтаксису для формального опису мов програмування; отримання знань про формальні граматики та їх використання відповідно до обраної вхідної мови; формування уявлення про підходи до лексичного та синтаксичного аналізу з використанням теорії автоматів та формальних мов; отримання знань про базові підходи оптимізації програмного коду; формування уявлень про основні напрямки та перспективи розвитку систем програмування.
Тематика та види навчальних занять
Для денної форми здобуття освіти
Лекційні заняття
Лекція 1. Системне і прикладне програмне забезпечення ЕОМ. Системи програмування та їх класифікація за рівнем вхідної мови.
Лекція 2. Принципи побудови трансляторів.
Лекція 3. Формальний опис синтаксису мови.
Лекція 4. Визначення формальної граматики та мови. Класифікація формальних граматик та мов.
Лекція 5. Завдання лексичного аналізатора.
Лекція 6. Автоматні граматики та кінцеві автомати.
Лекція 7. Етапи проектування лексичного аналізатора та діаграма його роботи.
Лекція 8. Поняття зведеної граматики. Деякі бінарні відношення стосовно до граматик.
Лекція 9. Відношення простого передування.
Лекція 10. Налагодження граматики.
Лекція 11. Просте передування: граматика та алгоритм синтаксичного аналізу.
Лекція 12. Паралельне передування: граматика та алгоритм синтаксичного аналізу.
Лекція 13. Слабке (ослаблене) передування: граматика та алгоритм синтаксичного аналізу.
Лекція 14. Розширене передування та метод змішаної стратегії.
Лекція 15. Внутрішні форми представлення програми.
Лабораторні заняття
Лабораторне заняття №1. Вивчення пакета прикладних програм для розробки формальних граматик.
Мета заняття: Навчитися користуватися пакетом прикладних програм для створення та відлагодження формальних граматик.
Лабораторне заняття №2. Розробка формальних граматик відповідно до вимог щодо мови програмування.
Мета заняття: Вивчити засоби опису формальних граматик, а також навчитись методиці і навичкам опису синтаксису мов.
Лабораторне заняття №3. Розробка структур даних для лексичного аналізатора (сканера).
Мета заняття: Вивчити засоби проектування сканерів, а також навчання методиці та навичкам опису лексики мов програмування.
Лабораторне заняття №4. Розробка узагальненого кінцевого автомата для лексичного аналізатора.
Мета заняття: Отримати навички проектування кінцевих автоматів та узагальненого кінцевого автомата, що об’єднує можливості окремих кінцевих автоматів. Навчитися визначати семантику сканера.
Лабораторне заняття №5. Визначення конфліктів та налагодження формальної граматики простого передування.
Мета заняття: Вивчити засоби створення матриць простого передування та визначення у них конфліктів. Навчитися аналізувати конфлікти та визначати їх тип.
Лабораторне заняття №6. Визначення конфліктів та налагодження формальної граматики паралельного передування.
Мета заняття: Вивчити засоби створення матриць паралельного передування та визначення у них конфліктів. Навчитися аналізувати конфлікти та визначати їх тип.
Лабораторне заняття №7. Синтаксичний аналіз з використанням алгоритмів простого та паралельного передування.
Мета заняття: Вивчити методи синтаксичного аналізу простого та паралельного передування. Навчитись проводити аналіз вхідного речення методами синтаксичного аналізу простого та паралельного передування.
Для заочної форми здобуття освіти
Лекційні заняття
Лекція 1. Принципи побудови трансляторів. Формальний опис синтаксису мови. Визначення формальної граматики та мови.
Лекція 2. Завдання лексичного аналізатора. Автоматні граматики та кінцеві автомати. Етапи проектування лексичного аналізатора та діаграма його роботи
Лабораторні заняття
Лабораторне заняття №1. Побудова лексичного аналізатора. Визначення структур даних та створення узагальненого кінцевого автомата.
Мета заняття: Вивчити засоби проектування лексичного аналізатора, а також навчання методиці та навичкам опису лексики мов програмування.
Лабораторне заняття №2. Відлагодження граматик. Синтаксичний аналіз з використанням алгоритмів простого та паралельного передування.
Мета заняття: Вивчити методи синтаксичного аналізу простого та паралельного передування. Навчитись усувати конфлікти та проводити аналіз вхідного речення методами синтаксичного аналізу простого та паралельного передування.
Індивідуальна робота
Для здобувачів очної форми здобуття освіти індивідуальна робота відсутня за планом
Для заочної форми здобуття освіти
Завдання для виконання контрольної роботи здобувач отримує на установчій лекції.
Робота містить 6 теоретичних питань, 5 практичних завдань та звіт з лабораторних робіт.
Обсяг відповіді на кожне теоретичне питання не менше, ніж 1 сторінки машинописного тексту. Текст відповіді має бути виконаний самостійно, а не скопійованим з конспекту лекцій.
Практичні завдання наведені в текстовій формі і присвячені питанням розробки блоків транслятора та маніпулювання даними.
Термін надання виконаної контрольної роботи на перевірку – не менше, ніж за місяць до початку сесії.
Форми контрольних заходів та оцінювання результатів навчання
Для денної форми здобуття освіти
Поточний контроль полягає у виконанні:
1) 7-ми індивідуальних поточних завдань для лабораторних робіт. Індивідуальні поточні завдання виконуються письмово і полягають в розв’язуванні типових задач відповідно до мети та завдань лабораторних занять. Бездоганне виконання завдання №1 оцінюється у 10 балів, №2, №3, №4, №5, №6 та №7 оцінюється у 5 балів;
2) двох модульних контрольних робіт. Модульні контрольні роботи складаються з теоретичної і практичної частин та проводяться у формі розв’язання завдань стосовно проєктування трансляторів з коментарями відносно прийнятих рішень. Бездоганне виконання 1 та 2 модульних контрольних робіт становить по 30 балів.
Підсумковий контроль – іспит. Підсумковий контроль з дисципліни складається з двох частин: теоретичної та практичної. Мінімальна кількість балів, що зараховується як позитивний результат, дорівнює 60 (за 100-бальною шкалою).
Бали розподіляються наступним чином: 40 балів – теоретична частина та 60 балів – практична.
Екзаменаційний білет містить 2 теоретичних питання рівної складності, практична – 2 питання рівної складності.
За бездоганну відповідь на кожне теоретичне питання здобувач отримує 20 балів. При цьому відповідь вважається бездоганною, якщо здобувач повністю розкрив суть питання, послідовно і логічно його доповів, навів приклади. Кожне завдання практичної частини іспиту вважається виконаним бездоганно, якщо отримана правильна відповідь, послідовно наведено рішення, виконано всі необхідні рисунки та схеми, нарисоване синтаксичне дерево та матрицю.
Для заочної форми здобуття освіти
Захист контрольної роботи. Бездоганне виконання контрольної роботи оцінюється у 50 балів. Під час її захисту здобувач може отримати до 50 балів.
Підсумковий контроль – іспит. Іспит усний. Максимальна оцінка, яку можу отримати здобувач – 100 балів.