Bachelor
2020/2021
Formal Languages
Category 'Best Course for Broadening Horizons and Diversity of Knowledge and Skills'
Category 'Best Course for New Knowledge and Skills'
Type:
Compulsory course (Applied Mathematics and Information Science)
Area of studies:
Applied Mathematics and Information Science
Delivered by:
Department of Informatics
When:
2 year, 1 module
Mode of studies:
offline
Instructors:
Mikhail Dvorkin,
Aleksei Paletskikh,
Ekaterina Verbitskaia
Language:
English
ECTS credits:
3
Contact hours:
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