Главная

Контакты

Случайная статья

• Автоматизация
• Антропология
• Археология
• Архитектура
• Биология
• Ботаника
• Бухгалтерия
• Военная наука
• Генетика
• География
• Геология
• Демография
• Деревообработка
• Журналистика
• Зоология
• Изобретательство
• Информатика
• Искусство
• История
• Кинематография
• Компьютеризация
• Косметика
• Кулинария
• Культура
• Лексикология
• Лингвистика
• Литература
• Логика
• Маркетинг
• Математика
• Материаловедение
• Медицина
• Менеджмент
• Металлургия
• Метрология
• Механика
• Музыка
• Науковедение
• Образование
• Охрана Труда
• Педагогика
• Полиграфия
• Политология
• Право
• Предпринимательство
• Приборостроение
• Программирование
• Производство
• Промышленность
• Психология
• Радиосвязь
• Религия
• Риторика
• Социология
• Спорт
• Стандартизация
• Статистика
• Строительство
• Технологии
• Торговля
• Транспорт
• Фармакология
• Физика
• Физиология
• Философия
• Финансы
• Химия
• Хозяйство
• Черчение
• Экология
• Экономика
• Электроника
• Электротехника
• Энергетика

Содержание дисциплины (модуля), структурированное по темам (разделам) с указанием отведенного на них количества академических часов и видов учебных занятий

4. Содержание дисциплины (модуля), структурированное по темам (разделам) с указанием отведенного на них количества академических часов и видов учебных занятий

4.1. Разделы дисциплины (модуля) и трудоемкости по видам учебных занятий

№

Тема (раздел) дисциплины

Трудоемкость по видам учебных занятий, включая самостоятельную работу, час.

Лекции

Семинары

Лаборат. работы

Самост. работа

Формальные языки и их представление.

Регулярные множества и конечные автоматы.

Контекстно-свободные грамматики и автоматы с магазинной памятью.

Алгоритмы синтаксического анализа

Элементы теории трансляции Технологии компиляции

Итого часов

Подготовка к зачёту

30 час.

Общая трудоёмкость

180 час., 4 зач.ед.

4.2.

Содержание дисциплины (модуля), структурированное по темам (разделам)

Семестр: 3 (Осенний)

1. Формальные языки и их представление.

Алфавиты, цепочки и языки. Представление языков. Формальное определение грамматики. Классификация языков и грамматик по Хомскому. Ограничения на вид правил вывода. Примеры грамматик и языков. Машины Тьюринга. Неразрешимость проблемы останова. Класс рекурсивных множеств. Связь машин Тьюринга и грамматик типа 0. Линейно-ограниченные автоматы и их связь с контекстно-зависимыми грамматиками, неукорачивающие грамматики. Ремарка о связи языка и грамматики.

2. Конечные автоматы и регулярные множества.

Регулярные множества и выражения. Конечные автоматы и алгоритмы их построения.

Связь регулярных множеств, конечных автоматов и регулярных грамматик.

Минимизация и эквивалентность конечных автоматов.

Приложения. Лексический анализ. Разбор последовательности по диаграмме состояний. Примеры.

3. Контекстно-свободные грамматики и автоматы с магазинной памятью.

Определения, эквивалентность КС-грамматик и магазинных автоматов.

Приведение грамматик.

Общие методы синтаксического анализа.

4. Алгоритмы синтаксического анализа.

Рекурсивный спуск.

Предсказывающий нисходящий разбор.

Функции FIRST и FOLLOW. Построение таблицы анализатора. Алгоритм синтаксического анализа.

Восходящий разбор типа перенос-свертка.

Каноническая система множеств. Построение таблицы анализатора. LR-разбор: варианты реализации. Алгоритм синтаксического анализа.

5. Элементы теории трансляции. Технологии компиляции.

Основные понятия, задачи и механизмы трансляции в технологиях компиляции.

Лексический анализ: разбор по регулярным грамматикам. Регулярные выражения в лексическом анализе. Генераторы анализаторов по грамматике.

Методы распознавания КС-языков в приложениях.

Атрибутные грамматики.

Грамматики с действиями.

Синтаксически управляемая трансляция.

Внутреннее устройство современного компилятора.

Последовательность преобразования программ при компиляции. Связь дерева синтаксического разбора и абстрактного синтаксического дерева. Семантический анализ. Оптимизационные проходы.

Алгоритм генерации исполняемого кода из внутреннего представления программы: пример.