• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Формальные языки и грамматики

2019/2020
Учебный год
RUS
Обучение ведется на русском языке
5
Кредиты

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

Аннотация

Настоящая программа учебной дисциплины устанавливает требования к образовательным результатам и результатам обучения студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих дисциплину «Формальные языки и грамматики», учебных ассистентов и студентов направления подготовки 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-Бакалавр и магистр. Академический курс-978-5-534-00117-4: -Текст электронный // ЭБС Юрайт - https://biblio-online.ru/book/teoriya-avtomatov-444091