Formal Languages

2020/2021

Academic Year

ENG

Instruction in English

3

ECTS credits

Delivered at:

Department of Informatics

Course type:

Compulsory course

When:

2 year, 1 module

Instructors

Verbitskaia, Ekaterina

Dvorkin, Mikhail

Paletskikh, Aleksei

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