Formal Languages and Grammars

2019/2020

Academic Year

RUS

Instruction in Russian

5

ECTS credits

Delivered at:

Department of Information Technologies in Business (Faculty of Computer Science, Economics, and Social Sciences)

Course type:

Elective course

When:

3 year, 3, 4 module

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

Аннотация

Настоящая программа учебной дисциплины устанавливает требования к образовательным результатам и результатам обучения студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих дисциплину «Формальные языки и грамматики», учебных ассистентов и студентов направления подготовки 09.03.04 Программная инженерия, обучающихся по образовательной программе «Программная инженерия».

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

• Целью освоения дисциплины «Формальные языки и грамматики» являются изучение теории формальных языков и грамматик, их практического применения для описания языков программирования и построения анализаторов.

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

• Демонстрирует способность классификации формальных языков и грамматики, построения деревьев разбора, анализаторов
• Применяет методы дискретной математики при анализе формальных языков и грамматик
• Использует алгоритмы контекстно-свободной грамматики
• Владеет методами нисходящего и восходящего разборов
• Использует разные виды грамматик в построении алгоритмов решения задач

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

• Раздел 1. Классификация языков и грамматик
  Тема 1. Основные понятия теории формальных языков и грамматик Понятие алфавита, цепочки символов. Операции над цепочками: конкатенация, обращение, возведение в степень. Свойства операций. Примеры. Понятие языка. Способы описания языков: распознавание и порождение. Порождающая грамматика. Язык, порождаемый грамматикой. Выводимость, непосредственная выводимость. Сентенциальная форма. Эквивалентные и почти эквивалентные грамматики. Примеры. Лексиса, синтаксис, семантика, прагматика. Метаязыки. Описание грамматик с помощью металингвистических формул (БНФ) и диаграмм Вирта. Примеры. Тема 2. Классификация грамматик и языков по Хомскому Классификация грамматик и языков по Хомскому: без ограничений на вид правил, неукорачивающие, контекстно-зависимые, контекстно-свободные, регулярные, леволинейные, праволинейные, автоматные. Связь между различными классами. Примеры. Тема 3. Разбор цепочек Разбор цепочек. Понятие вывода. Левосторонний и правосторонний вывод. Дерево разбора. Однозначные и неоднозначные грамматики. Примеры. Нисходящий и восходящий разбор.
• Раздел 2. Регулярные языки и грамматики
  Тема 4. Конечные автоматы Алгоритм разбора по регулярной грамматике. Варианты окончания разбора. Диаграмма состояний. Построение диаграммы состояний. Примеры. Алгоритм разбора по диаграмме состояний. Примеры. Детерминированный и недетерминированный разбор. Детерминированные конечные автоматы (ДКА). Примеры. Язык, допускаемый ДКА. Построение автоматной грамматики на основе ДКА. Примеры. Недетерминированные конечные автоматы (НКА). Примеры. Язык, допускаемый НКА. Связь между ДКА и НКА, детерминированными и недетерминированными регулярными языками. Алгоритм построения ДКА по НКА. Примеры. Минимизация конечных автоматов. Алгоритм минимизации. Примеры. Тема 5. Регулярные выражения Регулярные множества и выражения. Примеры. Алгебра регулярных выражений. Эквивалентность регулярных выражений. Связь между регулярными выражениями и автоматными языками. Теорема Клини о регулярных языках.
• Раздел 3. Контекстно-свободные языки и грамматики
  Тема 6. Преобразование грамматик Недостижимые и бесплодные символы. Граф контекстно-свободной грамматики. Алгоритм удаление бесплодных символов с помощью графов. Алгоритм удаление недостижимых символов с помощью графов. Приведенная грамматика. Алгоритм приведения грамматики. Примеры. Алгоритм исключения цепных правил. Алгоритм устранения правил с пустой правой частью. Примеры. Алгоритм устранения левой рекурсии из правил контекстно-свободной грамматики. Примеры. Нормальные формы Хомского и Грейбаха. Алгоритм преобразования грамматики в нормальную форму Хомского. Примеры. Тема 7. Магазинные автоматы Понятие магазинного автомата. Работа магазинного автомата. Детерминированные магазинные автоматы (ДМА), недетерминированные магазинные автоматы (НМА), детерминированные и недетерминированные КС-языки. Определение НМА. Примеры построения НМА. Конфигурация НМА, переходы из одной конфигурации в другую. Теорема об эквивалентности автоматов с магазинной памятью и КС-языками. Примеры. Связь между ДМА и НМА.
• Раздел 4. Нисходящий и восходящий разбор
  Тема 8. Нисходящий разбор S-грамматика, Q-грамматика, LL(1)-грамматика, LL(k)-грамматика. Формальные определения. Примеры. Множество стартовых и направляющих символов для нетерминалов КС-грамматики. Примеры. Необходимое и достаточное условие того, чтобы грамматика была LL(1) грамматикой. Преобразование грамматики в LL(1)-форму. Примеры. Метод рекурсивного спуска. Примеры. Применимость метода рекурсивного спуска. Нисходящий анализ с прогнозируемым выбором альтернатив. Примеры. Построение таблицы прогнозов. Примеры. Рекурсивный спуск без построения прогнозов. Примеры. Тема 9. Восходящий разбор LR(k) грамматика. Формальное определение. Примеры. Анализ «перенос-свертка» (ПС-анализ). Понятие основы. Основа правосентенциальной формы. Построение управляющей таблицы для LR(1)-разбора. Примеры. Стековая реализация ПС-анализ. Конфликты, возникающие в процессе ПС-анализа. Разрешения конфликта «перенос-свертка». Примеры. LR(k)-анализ. Понятие LR(k)-ситуации. Функции EFF: правила вычисления, примеры. Алгоритм построения множества всех LR(k)-ситуаций для активного префикса. Правила построения LR(k)-таблицы. Примеры.
• Раздел 5. Грамматики без ограничений на вид правил, контекстно-зависимые. Атрибутные грамматики. Графовые грамматики
  Тема 10. Грамматики без ограничений на вид правил, контекстно-зависимые Машины Тьюринга (МТ). Применение МТ. Правила построения МТ. Примеры. Универсальная МТ. Проблема останова. Рекурсивные множества. Связь между МТ и грамматиками без ограничений на вид правил. Линейно ограниченные автоматы. Связь линейно ограниченных автоматов с контекстно-зависимыми языками. Тема 11. Атрибутные грамматики. Графовые грамматики Понятие атрибутной грамматики. Применение атрибутных грамматик. Вычисление значений атрибутов при левостороннем выводе. Примеры. L-атрибутные грамматики. Понятие графовой грамматики. Области применение графовых грамматик. Примеры. Трансформация графов. Методы и языки трансформации графов.

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

• Домашнее задание 1
• Самостоятельная работа
• Домашнее задание 2
• Домашнее задание 3
• Домашнее задание 4
• Домашнее задание 5
• Письменный экзамен

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

• Промежуточная аттестация (4 модуль)
  0.1 * Домашнее задание 1 + 0.1 * Домашнее задание 2 + 0.1 * Домашнее задание 3 + 0.1 * Домашнее задание 4 + 0.1 * Домашнее задание 5 + 0.3 * Письменный экзамен + 0.2 * Самостоятельная работа

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

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

• Формальные языки и компиляторы/МалявкоА.А. - Новосиб.: НГТУ, 2014. - 431 с.: ISBN 978-5-7782-2318-9

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

• Кудрявцев В. Б., Алешин С. В., Подколзин А. С. - ТЕОРИЯ АВТОМАТОВ 2-е изд., испр. и доп. Учебник для бакалавриата и магистратуры - М.:Издательство Юрайт - 2019 - 320с. - ISBN: 978-5-534-00117-4 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/teoriya-avtomatov-444091