Методичка № 82 - Теория вычислительных процессов - учебное пособие
Название:
Теория вычислительных процессов - учебное пособие
Предмет:
Автоматизированные системы управления (АСУ)
ВУЗ:
ТУСУР: Томский Государственный университет систем управления и радиоэлектроники
Год издания:
2007
Город:
Томск
Количество страниц:
267
Описание:
Учебное пособие по предмету "Теория вычислительных процессов".
Настоящее пособие посвящено проблеме теоретического описания вычислительных процессов и структур. Существует достаточно большое количество вариантов организации вычислительного процесса.
Однако всем этим схемам присуща общая технологическая цепочка — «лексический анализ - синтаксический анализ - генерация кода - оптимизация кода». Многие элементы этой схемы в процессе развития теории программирования из интуитивных, эмпирических алгоритмов превращались в строго математически обоснованные методы, базирующиеся на теории языков, теории перевода, методах синтаксического анализа и др.
В рассматриваемом пособии используются следующие принципы:
- основное внимание уделяется теоретическим идеям, а не техническим подробностям реализации;
- широко используется принцип декомпозиции исходной задачи на составляющие, что позволяет каждую часть задачи подвергнуть оптимизации;
- изложение материала базируется на уверенности в хорошей математической подготовке слушателей.
ОГЛАВЛЕНИЕ:
ВВЕДЕНИЕ 8
1 ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СВЕДЕНИЯ 10
1.1 МНОЖЕСТВА 10
1.2 ОПЕРАЦИИ И ОТНОШЕНИЯ 11
1.2.1 Операции над множествами 11
1.2.2 Отношения на множествах 13
1.3 МНОЖЕСТВА ЦЕПОЧЕК 17
1.3.1 Цепочки 17
1.3.2 Операции над цепочками 18
1.4 ЯЗЫКИ 19
1.4.1 Определения 19
1.4.2 Операции над языком 19
1.5 АЛГОРИТМЫ 20
1.5.1 Частичные алгоритмы 20
1.5.2 Всюду определенные алгоритмы 21
1.5.3 Рекурсивные алгоритмы 22
1.5.4 Задание алгоритмов 23
1.5.5 Проблемы 23
1.6 НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ 23
1.6.1 Ориентированные графы 23
1.6.2 Ориентированные ациклические графы 25
1.6.3 Деревья 26
1.6.4 Упорядоченные графы 27
КОНТРОЛЬНЫЕ ВОПРОСЫ 28
2 ВВЕДЕНИЕ В КОМПИЛЯЦИЮ 29
2.1 ЗАДАНИЕ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ 29
2.2 СИНТАКСИС И СЕМАНТИКА 30
2.3 ПРОЦЕСС КОМПИЛЯЦИИ 33
2.4 ЛЕКСИЧЕСКИЙ АНАЛИЗ 33
2.5 РАБОТА С ТАБЛИЦАМИ 36
2.6 СИНТАКСИЧЕСКИЙ АНАЛИЗ 37
2.7 ГЕНЕРАТОР КОДА 38
2.8 ОПТИМИЗАЦИЯ КОДА 43
2.9 ИСПРАВЛЕНИЕ ОШИБОК 45
2.10 РЕЗЮМЕ 46
КОНТРОЛЬНЫЕ ВОПРОСЫ 47
3 ТЕОРИЯ ЯЗЫКОВ 48
3.1 СПОСОБЫ ОПРЕДЕЛЕНИЯ ЯЗЫКОВ 48
3.2 ГРАММАТИКИ 48
3.3 ГРАММАТИКИ С ОГРАНИЧЕНИЯМИ НА ПРАВИЛА 52
3.4 РАСПОЗНАВАТЕЛИ 53
3.5 РЕГУЛЯРНЫЕ МНОЖЕСТВА, ИХ РАСПОЗНАВАНИЕ И ПОРОЖДЕНИЕ 56
3.5.1 Определения 56
3.5.2 Алгоритм решения стандартной системы уравнений с регулярными выражениями 59
3.6 РЕГУЛЯРНЫЕ МНОЖЕСТВА И КОНЕЧНЫЕ АВТОМАТЫ 61
3.7 ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ КОНЕЧНЫХ АВТОМАТОВ 63
3.8 КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ МНОЖЕСТВА 66
3.9 МИНИМИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВ 67
3.9.1 Постановка задачи 67
3.9.2 Алгоритм построения канонического конечного автомата 69
3.10 КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ 70
3.10.1 Деревья выводов 71
3.10.2 Преобразование КС-грамматик 75
3.10.3 Грамматика без циклов 79
3.10.4 Нормальная форма Хомского 80
3.10.5 Нормальная формула Грейбах 81
3.11 АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 84
3.11.1 Основные определения 84
3.11.2 Эквивалентность МП-автоматов и КС-грамматик 86
КОНТРОЛЬНЫЕ ВОПРОСЫ 87
4 КС-ГРАММАТИКИ И СИНТАКСИЧЕСКИЙ АНАЛИЗ СВЕРХУ ВНИЗ 89
4.1 LL(1)-ГРАММАТИКИ 90
4.2 LL(1)-ТАБЛИЦА РАЗБОРА 96
КОНТРОЛЬНЫЕ ВОПРОСЫ 102
5 СИНТАКСИЧЕСКИЙ АНАЛИЗ СНИЗУ ВВЕРХ 103
5.1 РАЗБОР СНИЗУ ВВЕРХ 103
5.2 LR(1)-ТАБЛИЦА РАЗБОРА 105
5.3 ПОСТРОЕНИЕ LR-ТАБЛИЦЫ РАЗБОРА 109
5.4 СРАВНЕНИЕ LL- И LR-МЕТОДОВ РАЗБОРА 113
КОНТРОЛЬНЫЕ ВОПРОСЫ 113
6 ОПТИМИЗАЦИЯ КОДА 114
6.1 ОПТИМИЗАЦИЯ ЛИНЕЙНОГО УЧАСТКА 114
6.1.1 Модель линейного участка 115
6.1.2 Преобразование блока 117
6.1.3 Графическое представление блоков 122
6.1.4 Критерий эквивалентности блоков 125
6.1.5 Оптимизация блоков 126
6.1.6 Алгебраические преобразования 130
6.2 АРИФМЕТИЧЕСКИЕ ВЫРАЖЕНИЯ 135
6.2.1 Модель машины 136
6.2.2 Разметка дерева 138
6.2.3 Программы с командами STORE 142
6.2.4 Влияние некоторых алгебраических законов 143
6.3 ПРОГРАММЫ С ЦИКЛАМИ 154
6.3.1 Модель программы 154
6.3.2 Анализ потока управления 158
6.3.3 Примеры преобразования программ 163
6.3.4 Оптимизация циклов 166
6.4 АНАЛИЗ ПОТОКОВ ДАННЫХ 178
6.4.1 Интервалы 179
6.4.2 Анализ потоков данных с помощью интервалов 186
6.4.3 Несводимые графы управления 195
КОНТРОЛЬНЫЕ ВОПРОСЫ 199
7 ВКЛЮЧЕНИЕ ДЕЙСТВИЙ В СИНТАКСИС 201
7.1 ПОЛУЧЕНИЕ ЧЕТВЕРОК 201
7.2 РАБОТА С ТАБЛИЦЕЙ СИМВОЛОВ 204
КОНТРОЛЬНЫЕ ВОПРОСЫ 207
8 ПРОЕКТИРОВАНИЕ КОМПИЛЯТОРОВ 208
8.1 ЧИСЛО ПРОХОДОВ 208
8.2 ТАБЛИЦЫ СИМВОЛОВ 209
8.2.1 Сцепление элементов 213
8.2.2 Бинарное дерево 213
8.3 ТАБЛИЦА ВИДОВ 214
КОНТРОЛЬНЫЕ ВОПРОСЫ 216
9 РАСПРЕДЕЛЕНИЕ ПАМЯТИ 217
9.1 СТЕК ВРЕМЕНИ ПРОГОНА 217
9.2 МЕТОДЫ ВЫЗОВА ПАРАМЕТРОВ 224
9.2.1 Вызов по значению 225
9.2.2 Вызов по имени 225
9.2.3 Вызов по результату 225
9.2.4 Вызов по значению и результату 226
9.2.5 Вызов по ссылке 226
9.3 ОБСТАНОВКА ВЫПОЛНЕНИЯ ПРОЦЕДУР 226
9.4 КУЧА 227
9.4.1 Счетчик ссылок 229
9.4.2 Сборка мусора 231
КОНТРОЛЬНЫЕ ВОПРОСЫ 237
10 ГЕНЕРАЦИЯ КОДА 238
10.1 ГЕНЕРАЦИЯ ПРОМЕЖУТОЧНОГО КОДА 238
10.2 СТРУКТУРА ДАННЫХ ДЛЯ ГЕНЕРАЦИИ КОДА 242
10.3 ГЕНЕРАЦИЯ КОДА ДЛЯ ТИПИЧНЫХ КОНСТРУКЦИЙ 245
10.3.1 Присвоение 245
10.3.2 Условные зависимости 246
10.3.3 Описание идентификаторов 247
10.3.4 Циклы 248
10.3.5 Вход и выход из блока 249
10.3.6 Прикладные реализации 251
10.4 ПРОБЛЕМЫ, СВЯЗАННЫЕ С ТИПАМИ 251
10.5 ВРЕМЯ КОМПИЛЯЦИИ И ВРЕМЯ ПРОГОНА 254
КОНТРОЛЬНЫЕ ВОПРОСЫ 255
11 ИСПРАВЛЕНИЕ И ДИАГНОСТИКА ОШИБОК 256
11.1 ТИПЫ ОШИБОК 256
11.2 ЛЕКСИЧЕСКИЕ ОШИБКИ 257
11.3 ОШИБКИ В УПОТРЕБЛЕНИИ СКОБОК 259
11.4 СИНТАКСИЧЕСКИЕ ОШИБКИ 260
11.5 МЕТОДЫ ИСПРАВЛЕНИЯ СИНТАКСИЧЕСКИХ ОШИБОК 261
11.5.1 Режим переполоха 261
11.5.2 Исключение символов 261
11.5.3 Включение символов 262
11.5.4 Правила для ошибок 262
11.6 ПРЕДУПРЕЖДЕНИЯ 263
11.7 СООБЩЕНИЯ О СИНТАКСИЧЕСКИХ ОШИБКАХ 263
11.8 КОНТЕКСТНО-ЗАВИСИМЫЕ ОШИБКИ 264
11.9 ОШИБКИ, СВЯЗАННЫЕ С УПОТРЕБЛЕНИЕМ ТИПОВ 265
11.10 ОШИБКИ, ДОПУСКАЕМЫЕ ВО ВРЕМЯ ПРОГОНА 266
11.11 ОШИБКИ, СВЯЗАННЫЕ С НАРУШЕНИЕМ ОГРАНИЧЕНИЙ 268
КОНТРОЛЬНЫЕ ВОПРОСЫ 268
СПИСОК ЛИТЕРАТУРЫ 269
Если у Вас возникли проблемы со скачиванием методических указаний с сайта, то обратитесь в службу поддержки по эл. почте на адрес . В письме укажите Номер методички, Название и опишите ситуацию.
Тут Вы можете скачать бесплатно методичку Теория вычислительных процессов - учебное пособие по предмету Автоматизированные системы управления (АСУ) под редакцией , ТУСУР, 2007.
Работы на заказ
Компания "SaveStud.Su" уже многие годы работает и помогает студентам. На рынке образовательных услуг мы существуем уже с 2001 года и за это время четко и уверенно вышли в лидеры, благодаря качеству выполняемых работ на заказ, а так же оперативности и индивидуальному подходу к каждому студенту. У нас появились представительства в других городах, не только в Москве и Санкт-Петербурге, а дистанционное сотрудничество дает возможность обратится к нам любому студенту. Мы меняемся для Вашего удобства, лишь наш девиз неизменен: «Качественные работы в срок».
Мы в Вконтакте:
Полезные советы, ежедневное обновление, помощь в учебе, интересные новости и акции - Будем рады видеть Вас в нашей группе Вконтакте. Участникам группы 5% скидка на все услуги.
Магазин готовых работ
Уникальные авторские работы, написанные специалистами компании SaveStud.Su, вы можете приобрести по цене 30% от стоимости нового заказа. Все работы прошли проверку на уникальность и качество. Сдавались 1 раз и были успешно зачтены.
