Delivered at:: Joint Department with the RAS Institute for System Programming

Course type:: Elective course

When:: 2 year, 3, 4 module

Instructors

Игнатьев Валерий Николаевич

Шимчик Никита Владимирович

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

Аннотация

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

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

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

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

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

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

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

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

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

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

2023/2024 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;

Bachelor’s Programme 'Software Engineering'

Contacts

Accredited by the Engineering Commission of ABET

Formal Languages and Automata

Instructors

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

Аннотация

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

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

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

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

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

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

Рекомендуемая основная литература

Рекомендуемая дополнительная литература