СОДЕРЖАНИЕ
1. ВВЕДЕНИЕ В АВТОМАТИЗАЦИЮ ПРОГРАММИРОВАНИЯ ......................... 7
1.1. Основная проблема автоматизации ................................. 7
1.2. Основные элементы системы перевода............................... 8
2. ФОРМАЛЬНЫЕ СИСТЕМЫ ............................................... 10
2.1. Основные определения ........................................... 10
2.2. Формальное определение языка и грамматики ...................... 12
2.3. Иерархия языков по Хомскому .................................... 14
3. ЛЕКСИЧЕСКИЙ АНАЛИЗ И ПРОГРАММИРОВАНИЕ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА
   (СКАНЕРА) ........................................................ 16
3.1. Основные задачи лексического анализатора ....................... 16
3.2. Регулярные выражения и конечные автоматы ....................... 17
3.3. Использование регулярных грамматик и конечных автоматов при
     программировании сканера........................................ 19
3.4. Глобальные переменные и необходимые подпрограммы ............... 21
3.5. Добавление семантики в диаграмму состояний ..................... 22
3.6. Диаграмма состояний для новых классов символов.................. 27
3.7. Примеры построения таблиц лексического анализатора
     для программного фрагмента на языке Mini PL .................... 29
3.8. Некоторые приемы написания сканера на языке С/С++ .............. 31
3.9. Контрольные вопросы по теме..................................... 32
4. СИНТАКСИЧЕСКИЙ АНАЛИЗ И ПРОГРАММИРОВАНИЕ СИНТАКСИЧЕСКОГО
   АНАЛИЗАТОРА (ПАРСЕРА) ............................................ 34
4.1. Основные определения и предпосылки.............................. 34
4.2. Таблица стандартных символов.................................... 34
4.3. Грамматика языка................................................ 35
4.4. Понятие атрибутной грамматики................................... 37
4
4.5. Грамматический (синтаксический) разбор предложения.............. 39
4.5.1. Грамматический разбор сверху–вниз ............................ 39
4.5.1.1. LL(1)-грамматики ........................................... 42
4.5.1.2. Расположение грамматики в памяти ........................... 46
4.5.1.3. Метод рекурсивного спуска (recursive descent) .............. 48
4.5.2. Грамматический разбор снизу–вверх ............................ 52
4.5.2.1. Применение отношений в грамматиках.......................... 53
4.5.2.2. Отношения предшествования .................................. 58
4.5.2.3. Определение грамматики предшествования...................... 60
4.5.2.4. Функции предшествования .................................... 61
4.5.2.5. Операторное предшествование................................. 63
4.5.2.6. Операторные грамматики ..................................... 65
4.6. Контрольные вопросы по теме..................................... 67
5. ВНУТРЕННЯЯ ФОРМА ПРЕДСТАВЛЕНИЯ ИСХОДНОЙ ПРОГРАММ
   И СЕМАНТИКА ТАБЛИЦ ............................................... 68
5.1. Общие требования к внутренней форме представления ...............69
5.2. Организация таблиц семантического анализа ...................... 70
5.3. Основные виды ВФП, применяемые в современных компиляторах ...... 73
5.3.1. Тетрады ...................................................... 73
5.3.2. Четверки для построения логических выражений ................. 77
5.3.3. Тройки. ...................................................... 80
5.3.4. Косвенные тройки ............................................. 81
5.3.5. Обратная польская запись ..................................... 82
5.3.6. Представление программы в виде графа ......................... 83
5.3.7. Другие формы представления ВФП ............................... 84
5.4. Контрольные вопросы по теме .................................... 86
6. Введение в семантические процедуры ............................... 87
6.1. Cемантическая обработка при рекурсивном спуске ................. 89
6.2. Семантическая обработка инструкций переходов ................... 93
6.3. Проблема «перехода вперед»...................................... 94
6.4. Контрольные вопросы по теме «Семантические процедуры» .......... 95
7. МАШИННО-НЕЗАВИСИМАЯ ОПТИМИЗАЦИЯ .................................. 96
7.1. Классификация методов оптимизации .............................. 96
7.2. Основные направления оптимизации ВФП ........................... 96
7.2.1. Выполнение операций над операндами, значения которых
       уже известны на этапе компиляции ............................. 97
7.2.2. Удаление избыточных операций ................................. 99
7.2.3. Оптимизация циклов .......................................... 101
7.3. Контрольные вопросы по теме «Машинно-независимая оптимизация» . 104
8. ГЕНЕРАЦИЯ КОДОВ ................................................. 106
8.1. Формы объектного кода.......................................... 106
8.2. Система адресации, используемая при описании генерации кода ... 106
8.3. Генерация команд для простых арифметических выражений.......... 107
8.3.1. Генерация кода для тетрад.................................... 108
8.3.2. Генерация кода для триад .................................... 111
8.3.3. Генерация команд для дерева ................................. 115
8.3.4. Получение более оптимального объектного кода ................ 117
8.4. Память для данных элементарных типов........................... 119
8.5. Векторы и матрицы ............................................. 120
8.6. Формы представления операндов в ВФП ........................... 124
8.7. Области данных и дисплеи....................................... 125
8.8. Адресация операндов на основе ОД и дисплеев ................... 128
8.9. Более полная схема генерации кода для тетрад .................. 131
8.9.1. Описания регистров и сумматора .............................. 131
8.9.2. Ассемблерные команды адресации операндов..................... 134
8.9.3. Список переменных и процедур генерации кода ................. 135
8.9.4. Генерация кода для арифметических тетрад .................... 138
8.9.5. Другие методы генерации кодов ............................... 139
8.9.5.1. Создание общих подпрограмм ................................ 139
8.9.5.2. Шкалы ..................................................... 140
8.10. Контрольные вопросы по теме «Генерация кодов» ................ 143
9. МАШИННО-ЗАВИСИМАЯ ОПТИМИЗАЦИЯ.....................................144
9.1. Распределение регистров ....................................... 145
10. РАСПРЕДЕЛЕНИЕ ПАМЯТИ............................................ 149
10.1. Память........................................................ 149
10.2. Статическая и динамическая память ............................ 153
10.3. Некоторые приемы выделения памяти............................. 154
10.3.1. Присваивание адресов переменным............................. 154
10.3.2. Переменные с начальными значениями ......................... 155
10.3.3. Проблемы выравнивания ...................................... 155
10.3.4. Отведение памяти временным переменным....................... 156
10.3.5. Указание о зоне в описателе временной переменной ............157
11. ВЫХОДНАЯ ИНФОРМАЦИЯ КОМПИЛЯТОРА ................................ 159
12. ОБЩАЯ СХЕМА КОМПИЛЯТОРА ........................................ 160
13. ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ №1 .............................. 161
13.1. Содержание отчета ............................................ 161
13.2. Варианты заданий для лабораторной работы ..................... 162
14. ЗАДАНИЕ ЛАБОРАТОРНОЙ РАБОТЫ №2 ................................. 172
14.1. Содержание отчета ............................................ 172
14.2. Варианты заданий для лабораторной работы ..................... 172
15. ЗАДАНИЕ ЛАБОРАТОРНОЙ РАБОТЫ № 3 ................................ 175
16. РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА........................................ 176