Бакалавриат
2020/2021
Формальные языки
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс обязательный (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Кто читает:
Департамент информатики
Когда читается:
2-й курс, 1 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Вербицкая Екатерина Андреевна,
Дворкин Михаил Эдуардович,
Палецких Алексей Андреевич
Язык:
английский
Кредиты:
3
Контактные часы:
42
Course Syllabus
Abstract
Целью освоения дисциплины «Формальные языки» является формирование у студентов теоретических знаний и практических навыков по основам теории формальных языков. Существенное внимание уделяется вопросам, связанным с теоретическими аспектами синтаксиса и семантики языков программирования, а также вопросам создания эффективных алгоритмов лексического и синтактического анализа кода программ. В результате освоения дисциплины студент должен: − Знать основные методы синтаксического анализа; основные подходы при генерации объектного кода программы. − Уметь описывать синтаксис языков программирования, используя различные подходы; строить семантику языка используя различные подходы; применять регулярные выражения для лексического анализа; создавать алгоритмы для эффективного синтактического анализа кода программ; создавать JITкомпиляторы. − Иметь навыки (приобрести опыт) применения методов описания синтаксиса и семантики языков программирования с использованием различных подходов; методов создания эффективных алгоритмов лексического и синтактического анализа кода программ.
Learning Objectives
- формирование у студентов теоретических знаний и практических навыков по основам теории формальных языков.
Expected Learning Outcomes
- Знает основные современные принципы и подходы к построению формальных языков. Определяет принадлежность языка программирования к семейству. Владеет навыками поиска актуальной информации по вопросам формальных языков и грамматик
- Знает основные принципы построения современной математики. Применяет современные математические методы к решению математических и программистских задач. Использует полученные навыки в решении практических задач
- Знает алгоритмы для построения дерева разбора. Эффективно реализует метод рекурсивного спуска. Генерирует лексер для заданной грамматики.
- Знает основные методы работы с детерминированным и и конечными автоматами. Умеет представлять и аргументированно обосновывать выбор методов работы с конкретным формальным языком. Владеет навыками представления результатов своей работы с регулярными выражениями и КСграмматиками
Course Contents
- Конечные автоматы
- Регулярные выражения
- КС-грамматики
- Детерминированные автоматы с магазинной памятью
Assessment Elements
- Домашнее задание №1
- Домашнее задание №2
- Домашнее задание №3
- Домашнее задание №4
- Экзамен
Interim Assessment
- Interim assessment (1 module)0.125 * Домашнее задание №1 + 0.125 * Домашнее задание №2 + 0.125 * Домашнее задание №3 + 0.125 * Домашнее задание №4 + 0.5 * Экзамен
Bibliography
Recommended Core Bibliography
- Малявко А. А. - ФОРМАЛЬНЫЕ ЯЗЫКИ И КОМПИЛЯТОРЫ. Учебное пособие для вузов - М.:Издательство Юрайт - 2019 - 429с. - ISBN: 978-5-534-04288-7 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/formalnye-yazyki-i-kompilyatory-438060
Recommended Additional Bibliography
- W. J. Levelt. (2019). An Introduction to the Theory of Formal Languages and Automata (Vol. Reprint 2019). Berlin/Boston: De Gruyter Mouton. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=2039961