Формальные языки и автоматы

Бакалавриат 2024/2025

Статус: Курс по выбору (Программная инженерия)

Направление: 09.03.04. Программная инженерия

Кто читает: Базовая кафедра «Системное программирование» Института системного программирования им. В.П. Иванникова РАН (ИСП РАН)

Где читается: Факультет компьютерных наук

Когда читается: 2-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Язык: русский

Кредиты: 5

Полная версия программы учебной дисциплины

Аннотация

Курс включает 2 части. Первая часть посвящена изучению теории формальных языков, автоматов и грамматик, а также затрагивает пределы вычислимости (какие задачи можно решать на компьютере). Подробно и формально изучаются регулярные языки, регулярные выражения, конечные автоматы и соответствующие формализации для контекстно-свободных языков. Вторая часть курса знакомит студентов с основами конструирования компиляторов. Подробно рассматриваются LL- и LR- синтаксические анализаторы, рассказывается о промежуточных представлениях программы в компиляторе и основных алгоритмах, используемых при генерации кода. Курс включает сдачу домашних практических заданий на C++, в которых студенты реализуют алгоритмы, изучаемые в рамках курса.

Цель освоения дисциплины

Курс позволит понять математическую базу, используемую при реализации первого этапа (фронтэнда) компилятора, изучить структуру и схему работы компилятора, алгоритмы, необходимые для генерации ассемблерного кода. В результате освоения курса студент будет готов самостоятельно реализовать неоптимизирующий компилятор.

Планируемые результаты обучения

Понятие формальных языков, порождение и распознавание языка. Формальные грамматики, классификация по Хомскому, пустое слово, рекурсивные, рекурсивно-перечислимые и неперечислимые языки.
Регулярные языки, регулярные выражения, НКА, ДКА, построение РВ-> НКА->ДКА, РВ->ДКА, эквивалентность ДКА и НКА, построение РВ по КА, эквивалентность КА, РВ и регулярных грамматик, лемма о накачке, замкнутость регулярных языков, минимизация автоматов
Возможности и практическое применение регулярных выражений (regexp)
КС-языки, КС-грамматики, Деревья разбора, неоднозначность КС-грамматик, Автоматы с магазинной памятью (МП-автоматы), эквивалентность допускания по заключительному состоянию и пустому магазину, эквивалентность языков МП-автомата и КС-грамматик, детерминированные МП-автоматы (ДМП-автоматы), лемма о накачке для КС-языков, замкнутость КС-языков, нормальная форма Хомского (приведение к НФХ)
Разбор КС-языка, алгоритм Кока-Янгера-Касами, общая схема работы компилятора, фазы компиляции
Структура и схема работы нисходящего синтаксического анализатора, построение таблицы анализатора, LL(1)-,LL(k)-грамматики: критерий, приведение, удаление левой рекурсии, левая факторизация. Метод рекурсивного спуска. Восстановление после ошибок
Структура и схема работы восходящего синтаксического анализатора, построение таблицы анализатора, LR(k)-грамматики, сравнение LL и LR анализаторов, восстановление после ошибок, виды LR-анализаторов.
Атрибутные грамматики, синтаксически управляемые определения (СУО), порядок вычисления в СУО, схемы трансляции
Генерация промежуточного кода, трехадресный код, представления программы в компиляторе, поток управления, ГПУ, планирование инструкций, распределение регистров.

Содержание учебной дисциплины

Формальные языки
Регулярные языки
Regexp
Контекстно-свободные языки
Синтаксический анализ
Нисходящий синтаксический анализ
Восходящий синтаксический анализ
Синтаксически управляемая трансляция
Генерация кода

Элементы контроля

КР_1
Максимально – 20 баллов Стоимость задач указана в варианте.
КР_2
Максимально – 20 баллов Стоимость задач указана в варианте.
Экз
Письменно, очно, решение задач и письменные ответы на вопросы. Максимально -- 30 баллов. Экзамен состоит из нескольких задач (6-8) и вопросов. Каждый оценивается в некоторое число баллов, указанное в варианте.
ДЗ
Максимальные оценки: 2 задачи на 10 баллов, 1 задача на 5 баллов. Баллы вычисляются автоматически тестирующей системой в зависимости от кол-ва пройденных тестов. Подробные правила выставления баллов, штрафов антиплагиата и проч. находятся на странице https://earth.ispras.ru/integrity.html Для получения баллов за задачу может потребоваться ее сдать преподавателю очно (или онлайн по уважительной причине) в отведенное время.
КР_п
Контрольная работа на 30 минут на семинаре – 5 баллов макс. Балл вычисляется автоматически тестирующей системой на основе пройденных тестов и решенных заданий.

Промежуточная аттестация

2024/2025 4th module
Итоговая оценка Final = (ДЗ+КР_п+КР_1+КР_2+Экз) определяется по суммарному количеству набранных баллов: Final = 5, 10-балльная оценка = 1; Final = 20, 10-балльная оценка = 2; Final = 30, 10-балльная оценка = 3; Final = 40, 10-балльная оценка = 4; Final = 50, 10-балльная оценка = 5; Final = 60, 10-балльная оценка = 6; Final = 65, 10-балльная оценка = 7; Final = 70, 10-балльная оценка = 8; Final = 80, 10-балльная оценка = 9; Final = 95, 10-балльная оценка = 10;

Список литературы

Авторы

Лебедев Сергей Аркадьевич
Буцкая Евгения Александровна

Программа дисциплины