Теория языков программирования методов трансляции (стр. 1 )

МИНИСТЕРСТВО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Кафедра автоматизированных систем управления (АСУ)

УТВЕРЖДАЮ Зав. кафедрой АСУ Профессор д-р техн. наук _______________ «____»_________2007 г.

ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

МЕТОДОВ ТРАНСЛЯЦИИ

Методическое Пособие для студентов специальности 230105 «Программное обеспечение вычислительной техники

и автоматизированных систем»

Разработчик _____________

2007

Методическое Пособие рассмотрено и рекомендовано к изданию методическим семинаром кафедры автоматизированных систем управления ТУСУР « » 2004 г.

Зав. кафедрой АСУ

проф. д-р техн. наук __________

Содержание

Введение. 5

1. Предварительные математические сведения.. 7

1.1. Множества. 7

1.2. Операции над множествами.. 8

1.3. Множества цепочек. 14

1.4. Языки.. 15

1.5. Алгоритмы... 16

1.6. Некоторые понятия теории графов.. 19

Контрольные вопросы... 23

2. Введение в компиляцию... 24

2.1. Задание языков программирования.. 24

2.2. Синтаксис и семантика. 25

2.3. Процесс компиляции.. 28

2.4. Лексический анализ. 28

2.5. Работа с таблицами.. 30

2.6. Синтаксический анализ. 31

2.7. Генератор кода. 32

2.8. Оптимизация кода. 37

2.9. Исправление ошибок. 39

2.10. Резюме. 40

Контрольные вопросы... 40

3. Теория языков.. 41

3.1. Способы определения языков.. 41

3.2. Грамматики.. 41

3.3. Грамматики с ограничениями на правила. 45

3.4. Распознаватели.. 45

3.5. Регулярные множества, их распознавание и порождение 48

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

3.7. Графическое представление конечных автоматов.. 55

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

3.9. Минимизация конечных автоматов.. 58

3.10. Контекстно-свободные языки.. 62

3.10.1. Деревья выводов. 62

3.10.2. Преобразование КС–грамматик. 66

3.10.3. Грамматика без циклов. 71

3.10.4. Нормальная форма Хомского.. 71

3.10.5. Нормальная формула Грейбах. 72

3.11. Автоматы с магазинной памятью... 75

3.11.1. Основные определения. 75

3.11.2. Эквивалентность МП-автоматов и КС-грамматик. 77

Контрольные вопросы... 78

4. КС-грамматики и синтаксический анализ сверху вниз. 79

4.1. LL(1)-грамматики.. 80

4.2. LL(1)-таблица разбора. 86

Контрольные вопросы... 90

5. Синтаксический анализ снизу вверх. 91

5.1. Разбор снизу вверх. 91

5.2. LR(1) - таблица разбора. 93

5.3. Построение LR – таблицы разбора. 96

5.4. Сравнение LL – и LR – методов разбора. 99

Контрольные вопросы... 100

6. Оптимизация кода. 100

6.1. Оптимизация линейного участка. 101

6.1.1. Модель линейного участка. 101

6.1.2. Преобразование блока. 103

6.1.3. Графическое представление блоков. 107

6.1.4. Критерий эквивалентности блоков. 110

6.1.5. Оптимизация блоков. 111

6.1.6. Алгебраические преобразования. 115

6.2. Арифметические выражения.. 120

6.2.1. Модель машины.. 120

6.2.2. Разметка дерева. 122

6.2.3. Программы с командами STORE.. 126

6.2.4. Влияние некоторых алгебраических законов. 126

6.3. Программы с циклами.. 138

6.3.1. Модель программы.. 138

6.3.2. Анализ потока управления. 142

6.3.3. Примеры преобразования программ.. 146

6.3.4. Оптимизация циклов. 149

6.4. Анализ потоков данных. 160

6.4.1. Интервалы.. 161

6.4.2. Анализ потоков данных с помощью интервалов. 167

6.4.3. Несводимые графы управления. 175

7. Включение действий в синтаксис. 179

7.1. Получение четверок. 179

7.2. Работа с таблицей символов.. 182

Контрольные вопросы... 184

8. Проектирование компиляторов.. 184

8.1. Число проходов.. 184

8.2. Таблицы символов.. 185

8.3. Таблица видов.. 189

Контрольные вопросы... 191

9. Распределение памяти.. 191

9.1. Стек времени прогона. 191

9.2. Методы вызова параметров.. 198

9.3. Обстановка выполнения процедур.. 199

9.4. «Куча». 200

9.5. Счетчик ссылок. 201

9.6. Сборка мусора. 203

Контрольные вопросы... 208

10. Генерация кода. 208

10.1. Генерация промежуточного кода. 208

10.2. Структура данных для генерации кода. 211

10.3. Генерация кода для типичных конструкций.. 215

10.3.1. Присвоение. 215

10.3.2. Условные зависимости. 216

10.3.3. Описание идентификаторов. 217

10.3.4. Циклы.. 217

10.3.5. Вход и выход из блока. 219

10.3.6. Прикладные реализации. 220

10.4. Проблемы, связанные с типами.. 220

10.5. Время компиляции и время прогона. 222

Контрольные вопросы... 223

11. Исправление и диагностика ошибок. 224

11.1. Типы ошибок. 224

11.2. Лексические ошибки.. 225

11.3. Ошибки в употреблении скобок. 226

11.4. Синтаксические ошибки.. 227

11.5. Методы исправления синтаксических ошибок. 228

11.6. Предупреждения.. 229

11.7. Сообщения о синтаксических ошибках. 230

11.8. Контекстно-зависимые ошибки.. 231

11.9. Ошибки, связанные с употреблением типов.. 232

11.10. Ошибки, допускаемые во время прогона. 233

11.11. Ошибки, связанные с нарушением ограничений.. .... 234

Контрольные вопросы... 234

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

Введение

Настоящее пособие посвящено проблеме теоретического описания вычислительных процессов и структур. Существует достаточно большое количество вариантов организации вычислительного процесса (рис. 1.).

Рис 1. Схемы вариантов организации вычислительного процесса

Однако всем этим схемам присуща общая технологическая цепочка – «лексический анализ – синтаксический анализ – генерация кода – оптимизация кода». Многие элементы этой схемы в процессе развития теории программирования из интуитивных, эмпирических алгоритмов превращались в строго математически обоснованные методы, базирующиеся на теории языков, теории перевода, методах синтаксического анализа и др.

В рассматриваемом пособии используются следующие принципы:

-  основное внимание уделяется теоретическим идеям, а не техническим подробностям реализации;

-  широко используется принцип декомпозиции исходной задачи на составляющие, что позволяет каждую часть задачи подвергнуть оптимизации;

-  изложение материала базируется на уверенности в хорошей математической подготовке слушателей.

1. Предварительные математические сведения

1.1.  Множества

Будем предполагать, что существуют объекты, называемые атомами. Это слово обозначает первоначальное понятие, иначе говоря, термин «атом» остается неопределенным. Что называть атомом, зависит от рассматриваемой области. Часто бывает удобным считать атомами целые числа или буквы некоторого алфавита. Будем также постулировать абстрактное понятие принадлежности. Если принадлежит , то пишут . Отрицание этого утверждения записывается . Полагается, что, если - атом, то ему ничто не принадлежит, т. е. .

Будем также использовать некоторые примитивные объекты, называемые множествами, которые не являются атомами. Если - множество, то его элементы – это есть объекты (не обязательно атомы), для которых . Каждый элемент множества представляет собой либо атом, либо другое множество. Если содержит конечное число элементов, то называется конечным множеством.

Утверждение означает, что множество имеет элементов. Символ обозначает пустое множество, т. е. множество, в котором нет элементов. Заметим, что атом тоже не имеет элементов, но пустое множество не атом и атом не является пустым множеством.