РОССИЙСКАЯ ФЕДЕРАЦИЯ
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Институт математики и компьютерных наук
ПИДЖАКОВ С. И.
ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ И СТРУКТУР
Учебно-методический комплекс.
Рабочая программа для студентов очной формы обучения,
направление 02.03.03 – «Математическое обеспечение и администрирование информационных систем»
Тюменский государственный университет
2013
Пиджаков вычислительных процессов и структур. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения направление 02.03.03 – «Математическое обеспечение и администрирование информационных систем». Тюмень, 2013. 13 стр.
Рабочая программа дисциплины опубликована на сайте ТюмГУ: Теория вычислительных процессов и структур [электронный ресурс] / Режим доступа: http://www. umk. utmn. ru, свободный.
Рекомендовано к изданию кафедрой информационных систем. Утверждено проректором по учебной работе Тюменского государственного университета.
© Тюменский государственный университет, 2013.
© , 2013.
1. Пояснительная записка
1.1 Цели и задачи дисциплины
Цель изучения данной дисциплины – освоение теоретических основ формальных языков и трансляций, современных подходов распознавания и транслирования языков, концепций автоматного программирования.
Задачи дисциплины:
- изучение использования инструментальных средств построения распознавателей, методов построения компиляторов;
- создание распознавателей различных видов;
- применение методов семантического анализа в распознавателях;
- изучение и применение методы анализа и разрешения проблем взаимодействия вычислительных процессов.
- приобретение навыков навыки создания распознавателей, компиляторов, интерпретаторов, анализаторов вычислительных процессов – как инструментов программирования в современных информационных системах и платформах.
- получение практических навыков прикладного программирования
1.2 Требования к уровню освоения содержания дисциплины
В результате изучения дисциплины студенты должны:
· Знать: основные результаты теории формальных языков; методы организации лексического, синтаксического и семантического анализа; особенности использования специализированных инструментальных средств построения трансляторов в системном программировании; парадигму автоматного программирования для распознавания потоков символов различных языков; способы анализа и оптимизации взаимодействия вычислительных процессов;
· Уметь: создавать распознаватели, интерпретаторы и трансляторы информационных потоков; использовать стандартные инструментальные средства построения распознавателей и трансляторов в системном программировании; самостоятельно разрабатывать инструментальные средства построения распознавателей и трансляторов для системного программирования; находить и устранять проблем взаимодействия вычислительных процессов;
· Иметь представление: о формальных методах работы с символьными языками и их особенностях; о наиболее важных функциональных частях компилятора и методах их реализации; о важных характеристиках используемых компиляторов; о направлениях развития языков программирования; о современных методах лексического, синтаксического и семантического анализов; о процессе создания целевого кода компилятора; о способах моделирования и анализа взаимодействия вычислительных процессов;
· Владеть навыками: программного построения распознавателей, интерпретаторов и трансляторов информационных потоков; использования стандартных инструментальных средств построения распознавателей и трансляторов в системном программировании; самостоятельной разработки инструментальных средств построения распознавателей и трансляторов системного программирования; прикладного программирования на С++; практического анализа проблем взаимодействия вычислительных процессов;.
2. Структура и трудоемкость дисциплины
Таблица 1.
Вид учебной работы | Всего часов | Семестры | |
7 | 8 | ||
Аудиторные занятия (всего) | 70 | 35 | 35 |
В том числе: | - | - | - |
Лекции | 35 | 18 | 17 |
Лабораторные работы (ЛР) | 35 | 17 | 18 |
Самостоятельная работа (всего) | 37 | 17 | 20 |
Контрольные работы | + | + | |
Вид промежуточной аттестации (зачет, экзамен) | зачет | экзамен | |
Общая трудоемкость | 107 | 52 | 55 |
3. Тематический план
Таблица 2.
№ | Тема | недели семестра | Виды учебной работы и самостоятельная работа, в час. | Итого часов по теме | Итого количество баллов | ||
Лекции | Семинарские (практические) занятия | Самостоятельная работа | |||||
1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 |
Модуль 1 | |||||||
1.1 | Теория формальных языков и трансляций | 1-2 | 2 | 4 | 4 | 10 | 0-30 |
1.2 | Формальные грамматики. Проблема распознавания языков. | 3-6 | 4 | 4 | 5 | 13 | 0-30 |
1.3 | Автоматы. | 7-18 | 12 | 9 | 8 | 29 | 0-40 |
Итого (часов, баллов) за 7 семестр: | 18 | 17 | 17 | 52 | 0-100 | ||
Модуль 2 | |||||||
2.1 | Трансляторы. | 1-12 | 12 | 8 | 8 | 28 | 0-20 |
2.2 | Семантическая теория программ | 13-14 | 2 | 4 | 2 | 8 | 0-20 |
2.3 | Модели вычислительных процессов | 15-17 | 2 | 2 | 4 | 8 | 0-20 |
2.4 | Сети Петри | 18 | 1 | 4 | 6 | 11 | 0-20 |
Итого (часов, баллов) за 8 семестр: | 17 | 18 | 20 | 55 | 0-100 | ||
Итого часов: | 35 | 35 | 37 | 107 |
Таблица 3.
Виды и формы оценочных средств в период текущего контроля
№ темы | Письменные работы | Технические формы контроля | Информационные системы и технологии | Итого количество баллов | |
программы компьютерного тестирования | электронный практикумы | ||||
Модуль 1 | |||||
Т1 | 0-20 | 0-5 | 0-5 | 0-30 | |
Т2 | 0-20 | 0-5 | 0-5 | 0-30 | |
Т3 | 0-20 | 0-10 | 0-5 | 0-5 | 0-40 |
Итого за 7 семестр | 0-60 | 0-10 | 0-15 | 0-15 | 0-100 |
Модуль 2 | |||||
Т1 | 0-20 | 0-5 | 0-25 | ||
Т2 | 0-20 | 0-5 | 0-25 | ||
Т3 | 0-20 | 0-5 | 0-25 | ||
Т4 | 0-10 | 0-10 | 0-5 | 0-25 | |
Итого за 8 семестр | 0-70 | 0-10 | 0-15 | 0-5 | 0 – 100 |
Планирование самостоятельной работы студентов
По всем темам дисциплины предусмотрены следующие виды самостоятельной работы студентов.
Обязательные:
· конспектирование материала на лекционных занятиях;
· выполнение заданий лабораторных работ;
· выполнение тестовых и контрольных работ.
Дополнительные:
· написание дополнительных программ;
· изучение дополнительной литературы.
Кроме того, по отдельным темам предусмотрены специальные виды самостоятельной работы студентов:
Модуль 1. Основы теории автоматов и её практическое применение.
Т1: Работа с учебной литературой. Изучение записи формальных языков в нормальной форме Бэкуса-Наура.
Т2: Работа с учебной литературой. Изучение примеров формальных грамматик 1-го и 2-го типов.
Т3: Работа с учебной литературой. Изучение автомата Мили, автомата Мура.
Модуль 2. Трансляторы, интерпретаторы, компиляторы.
Т1: Работа с учебной литературой. Разбор схем трансляторов. Изучение отличий компиляторов и интерпретаторов.
Т2: Работа с учебной литературой. Изучение методов определения семантики программ.
Т3: Работа с учебной литературой. Изучение способов взаимодействия процессов.
Т4: Работа с учебной литературой. Изучение примеров сетей Петри.
4. Разделы дисциплины и междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами
Таблица 2
№ п/п | Наименование обеспечиваемых (последующих) дисциплин | Модули | |
1 | 2 | ||
1. | Технологии программирования | Т2 | Т1, Т2 |
2. | Дискретная математика | Т1 | Т3, Т4 |
3 | Структуры и алгоритмы компьютерной обработка данных | Т3 |
5. Содержание дисциплины
Модуль 1. Основы теории автоматов и её практическое применение.
Тема 1. Теория формальных языков и трансляций. Теория формальных языков и трансляций: математическое моделирование языков. Основные теоретические результаты. Синтаксис и семантика. Метаязыки. Нормальные формы Бекуса-Наура (БНФ).
Тема 2. Формальные грамматики. Проблема распознавания языков. Языки, порождаемые грамматиками; Классы формальных грамматик.
Тема 3. Автоматы: конечные автоматы, анализаторы и преобразователи. Анализаторы контекстно-свободных языков.
Модуль 2. Трансляторы, интерпретаторы, компиляторы.
Тема 1. Трансляторы: схема компилятора; методы построения; схематическая теория программ; способы оптимизации кода. Схемы программ, методы формальной спецификации и верификации.
Тема 2. Семантическая теория программ. Современные методы определения семантики программ. Особенности проблемы семантического анализа.
Тема 3. Модели вычислительных процессов: взаимодействие процессов; протоколы и интерфейсы; асинхронные процессы.
Тема 4. Сети Петри: принципы построения, алгоритмы поведения, способы реализации, области применения; принципы и способы технической реализации моделей процессов и структур. Роль в организации вычислительных процессов.
6. Планы семинарских занятий
Не планируется
7. Темы лабораторных работ
Задания лабораторного практикума выполняются с использованием среды разработки Microsoft Visual Studio.
Тема 1. Создать на языке С# программу-распознаватель языковых конструкций в потоке лексем по регулярным выражениям.
Тема 2. Создать на языке С# программу-распознаватель языковых конструкций в потоке лексем по регулярным выражениям, используя Lex.
Тема 3. Создать на языке С# программу удаления комментариев в тексте программы на С.
Тема 4. Создать на языке С# программу удаления комментариев в тексте программы на С, используя Lex.
Тема 5. Создать на языке С# программу синтаксического распознавателя предложений языка (включая лексический анализ). Использовать алгоритмы нисходящего синтаксического анализа. Вывести отчёт о процессе синтаксического разбора.
Тема 6. Создать на языке С# программу синтаксического распознавателя предложений языка (включая лексический анализ), используя алгоритмы восходящего синтаксического анализа (включить алгоритмы: формирования таблицы синтаксического анализа и программы драйвера). Вывести отчёт о процессе синтаксического разбора.
Тема 7. Создать на языке С# программу синтаксического распознавателя предложений любого выбранного контекстно-свободного языка (включить лексический анализ), используя инструментальные средства Lex и YACC.
Тема 8. Создать на языке С# программу вычисления метрики кода программы на С, используя инструментальные средства Lex и YACC.
Тема 9. Создать на языке С# программу - калькулятор с интерпретацией символьной записи арифметических выражений и памятью значений переменных, используя инструментальные средства Lex и YACC.
Тема 10. Создать на языке С# программу построителя графиков сложных функций с интерпретацией символьной записи выражения функции, используя инструментальные средства Lex и YACC.
Тема 11. Создать на языке С# программу интерпретатора С – подобного языка, используя инструментальные средства Lex и YACC.
Тема 12. Создать бесконфликтную модель вычислительного процесса с помощью специализированного инструментального средства.
8. Примерная тематика курсовых работ
Не планируются
9. Учебно - методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости
Контроль качества подготовки осуществляется путем проверки теоретических знаний и практических навыков с использованием
a) Текущей аттестации:
проверка промежуточных контрольных работ и прием лабораторных работ.
b) Промежуточной аттестации:
Тестирование по разделам дисциплины.
Зачёт в конце 7-го семестра (к зачёту допускаются студенты после сдачи всех лабораторных работ).
Экзамен в конце 8-го семестра (к экзамену допускаются студенты, получившие зачёт по итогам 7-го семестра, после сдачи всех лабораторных работ, решения всех задач контрольных).
Текущий и промежуточный контроль освоения и усвоения материала дисциплины осуществляется в рамках рейтинговой (100-бальной) системы оценок.
Пример задания контрольной работы в 7 семестре
1. Дать определение: отношение;
2. Дать определение: формальная грамматика первого типа;
3. С помощью формы Бэкуса-Наура описать формальный язык определяющий все конструкции циклов на языке Delphi;
4. Дать определение: ДКА, автомат Мура;
5. Привести практическое применение автомата Мура.
Пример задания контрольной работы в 8 семестре
Дана сеть Петри с заданной маркировкой. Определить количество и состав всех недостижимых переходов в любой маркировке.
Контроль качества подготовки осуществляется путем проверки теоретических знаний и практических навыков с использованием промежуточной аттестации в виде зачета в конце 8-го семестра.
Вопросы к экзамену:
1. Компиляторы, ассемблеры, интерпретаторы. Примеры.
2. Основные логические части компилятора. Обзор процесса компиляции.
3. Основные этапы, фазы и проходы компилятора. Примеры.
4. Проектирование компиляторов и используемые инструментальные средства. Примеры.
5. Цели и общие понятия формализации определений языка. Примеры.
6. Определение языка при помощи множеств и регулярными выражениями, регулярные языки и грамматики. Примеры.
7. Определение языка при помощи продукций. Понятие порождения, сентенциальной формы. Примеры.
8. Формальное определение грамматики. Обычная и расширенная форма Бекуса-Наура. Примеры.
9. Типы грамматик, иерархии Хомского. Примеры.
10. Соотношение между конечным автоматом, регулярным языком и регулярным выражением. Примеры.
11. Роль грамматик 2-ого и 3-ого типа в написании компиляторов. Различия этих грамматик. Примеры.
12. Порождения. Единственность порождения. Левые и правые порождения, связь с регулярными грамматиками. Представление порождений деревьями. Примеры.
13. Однозначность грамматики. Однозначные языки. Методы устранения неоднозначности. Примеры.
14. Ограничения использования контекстно-свободных грамматик для языков программирования. Примеры.
15. Понятие атрибутивной грамматики. Примеры.
16. Задачи синтаксического анализа. Типы синтаксического разбора. Примеры.
17. Семантика языка. Методы определения семантики языка.
18. Лексический анализ. Его задачи. Примеры.
19. Инструментальные средства лексического анализа: регулярные грамматики, конечные автоматы, программные представления конечных автоматов. Примеры.
20. Формальное определение автомата. Примеры.
21. Регулярные выражения и конечный автомат для распознавания идентификатора (с обязательной первой буквой) и действительных чисел.
22. Стандартные программные средства для построения лексических анализаторов. Представление в них идентификаторов (с обязательной первой буквой) и действительных чисел.
23. Связь между LEX и YACC. Примеры.
24. Представление в LEX комментариев.
25. Определение нисходящего синтаксического анализа и его отличие от восходящего синтаксического анализа. Примеры.
26. Символы предпросмотра при нисходящем синтаксическом анализе. Ограничения, накладываемые на множества символов предпросмотра при нисходящем синтаксическом анализе. Пример.
27. Определение множества первых порождаемых символов, стартового символа, символа последователя при нисходящем синтаксическом анализе. Пример.
28. Определение LL(1), LL(k) грамматики. LL(1), LL(k) языки. Нечистые грамматики. Преобразование грамматик к LL(1), LL(k) грамматикам. Примеры.
29. Метод рекурсивного спуска при программировании нисходящего синтаксического анализа, проблемы его реализации и их преодоление и ограничения. Примеры.
30. Цель и методы преобразования грамматик – удаление левой рекурсии, факторизация. Примеры.
31. Недостатки синтаксического анализа методом рекурсивного спуска, пути их возможного преодоления. Примеры.
32. Введение действий в грамматику. Использование стековых структур. Постфиксные, инфиксные выражения. Примеры.
33. Восходящий синтаксический анализ, особенности реализации. Примеры.
34. Определение LR(1), LR(k) грамматики, возможности сведения к LR(1). LR(1), LR(k) языки (сравнение с LL(1) языками и грамматиками). Примеры.
35. Левые и правые рекурсии, однозначность в LR(1) при синтаксическом разборе. Примеры.
36. Таблицы синтаксического анализа при восходящем синтаксическом анализе. Пример.
37. Использование таблицы синтаксического анализа при восходящем синтаксическом анализе. Стековые структуры (символов и состояний) восходящего синтаксического анализа. Пример.
38. Создание таблиц синтаксического анализа, правила и алгоритм. Правила введения аннотаций в грамматику. Конфигурации и состояния грамматики. Пример.
39. Понятие переноса и свёртки в восходящем синтаксическом анализе, их возможные конфликты и способы разрешения. Примеры.
40. LR(0), SLR(1), LALR(1), LR(1) алгоритмы и их практическое использование для синтаксического анализа языков программирования. Способ сокращения таблицы синтаксического анализа по переносам, к чему это приводит? Примеры.
41. Понятие характеристического конечного автомата в восходящем синтаксическом анализе. Примеры.
42. Желательные особенности LR анализа. Пример.
43. Общие понятия о YACC и его синтаксис входа. Пример.
44. Используемые грамматики в YACC. Пример.
45. Отображения приоритета и ассоциативности оператора в YACC, преимущества такого отображения. Примеры.
46. Варианты введения действий в YACC. Примеры.
10. Образовательные технологии
Сочетание традиционных образовательных технологий в форме лекций, компьютерных лабораторных работ и проведение контрольных мероприятий (контрольных работ, промежуточного тестирования, экзамена).
аудиторные занятия:
лекционные и компьютерные лабораторные занятия; на лабораторных занятиях контроль осуществляется при сдаче лабораторного задания в виде программы (на одном из используемых языков программирования) и пояснительной записки к задаче. В течение семестров студенты выполняют задачи, указанные преподавателем к каждому занятию.
активные и интерактивные формы
компьютерное моделирование и анализ результатов при выполнении лабораторных работ
внеаудиторные занятия:
выполнение дополнительных заданий разного типа и уровня сложности при выполнении лабораторных работ, подготовка к аудиторным занятиям, изучение отдельных тем и вопросов учебной дисциплины в соответствии с учебно-тематическим планом, составлении конспектов. Подготовка индивидуальных заданий: выполнение самостоятельных и контрольных работ, подготовка ко всем видам контрольных испытаний: текущему контролю успеваемости и промежуточной аттестации; индивидуальные консультации.
11. Учебно-методическое и информационное обеспечение дисциплины
Основная литература:
1. Гагарина в теорию алгоритмических языков и компиляторов: учеб. пособие [Электронный ресурс] / , . - М.: ИД ФОРУМ, 2011. - 176 с. – Режим доступа: http:///bookread. php? book=201229 (дата обращения 10.05.2013)
Дополнительная литература:
1. Свердлов программирования и методы трансляции: учеб. пособие для студ. вузов. - Санкт-Петербург: ПИТЕР, 2007. - 638 с.
2. Серебряков и реализация языков программирования: учеб. пособие. - 2-е изд., испр. и доп.. - Москва: МЗ Пресс, 2006.
12. Технические средства и материально-техническое обеспечение дисциплины (модуля)
При освоении дисциплины для проведения лекционных занятий требуются учебные аудитории, оснащённые мультимедийным оборудованием. Для выполнения лабораторных работ необходимы классы персональных компьютеров с набором базового программного обеспечения разработчика – системы программирования на языке С#.
