В книге крупнейшего американского специалиста в области компиляторов Д. Гриса нашел отражение богатый опыт разработки и использования трансляторов для ЭВМ третьего поколения. Подробно рассмотрены как теоретические основы разработки компиляторов (теория формальных языков и грамматик), так и практические вопросы их реализации (лексический и синтаксический анализ, организация памяти и таблиц, оптимизация программ).Книга может служить учебником для тех, кто впервые сталкивается с разработкой компиляторов, и справочным пособием для опытных специалистов в этой области. Книга окажет большую помощь при подготовке в университетах и институтах квалифицированных кадров по системному программированию.
Author(s): Грис Д
Publisher: Мир
Year: 1975
Language: Russian
Pages: 546
City: Москва
Предисловие редакторов перевода 5
Проrрамма курса 15 «Конструирование компиляторов» 8
Предисловие 11
Глава 1. Введеиие 17
1.1. Компиляторы, ассемблеры, интерпретаторы 17
1.2. Краткий обзор процесса компиляции 18
1.3. Примеры структур компиляторов 24
Глава 2. rрамматики и языки 28
2.1. Обсуждение rрамматик 28
Упражнения к разделу 2.1 31
2.2.- Символы и цепочки 32
Упражнения к разделу 2.2 34
2.3. Формальное определение rрамматики и языка 35
Упражнения к разделу 2.3 39
2.4. Синтаксические деревья инеоднозначность 40
Упражнения к разделу 2.4 45
2.5. Задача разбора 46
Упражнения к разделу 2.5 49
2.6. Некоторые отношения применительно к rрамматикам 49
Упражнения к разделу 2.6 53
2.7. Построение транзитивноrо замыкания отношений 53
Упражнения к разделу 2.7 56
2.8. Практические оrраничения, налаrаемые на rрамматики 57
Упражнения к разделу 2.8 60
2.9. Друrие способы представления синтаксиса 60
2.10. Краткий обзор теории формальных языков 63
2.11. Резюме 66
Глава 3. Сканер 69
3.1. Введение 69
3.2. Реrулярные выражения и конечные автоматы 72
Упражнения к разделу 3.2 84
3.3. Проrраммирование сканера 84
Упражиеиия к разделу 3.3 92
3.4. Конструирование сканеров 92
Упражнение к разделу 3.4 100
3.5. Система АЕО RWORD 100
3.6. Исторические замечания 105
Глава 4. Нисходящие распозннаватели 106
4.1. Нисходищий разбор с возвратами 106
4.2. Проблемы нисходящеrо разбора и их решение 115
4.3. Рекурсивный спуск 120
Упражнения к разделу 4.3 124
4.4. Исторические замечания 124
Глава 5. Грамматики простого npедшествоваиия 125
5.1. Отношения предшествования и их испопьзование 125
Упражнения к разделу 5.1 128
5.2. Определение и построение отношений 129
Упражнения к разделу 5.2 134
5.3. Алrоритм разбора 134
Упражнения к разделу 5.3 137
5.4. Функцин предшествования 137
Упражнения к разделу 5.4 141
5.5. Трудности, возникающие при построении rрамматик предшествования 141
Упражнения к разделу 5.5 144
5.6. Исторические замечания 144
Глава 6. Друrие восходящие распозиаватели 145
6.1. Предшествование операторов 146
Упражнения к разделу 6.1 155
6.2. Предшествование более высокого порядка 156
Упражнения к разделу 6.2 163
6.3. Оrраниченный контекст 164
6.4. Матрицы переходов 170
Упражнения к разделу 6.4 177
6.5. Исторические замечания 178
Глава 7. Продукционный язык 181
7.1. Язык 181
Упражнения к разделу 7.1 189
7.2. Использование ПЯ 189
Упражнения к разделу 7.2 195
7.3. Вызов семантических подпроrрамм 195
7.4. Исторические замечания 197
Глава 8. .Организация памяти во время выполнеиия nporpaммы 198
8. 1. Области данных и дисплеи 199
Упражнения к разделу 8.1 201
8.2. Описатели 201
8.3. Память для данных элемlентарных типов 203
8.4. Память для массивов 203
Упражнения к разделу 8.4 208
8.5. Память для строк 208
8.6. Память для структур 210
8.7. Соответствие фактических и формальных параметров 216
Упражнения к разделу 8.7 221
8.8. Управление памятью для ФОРТРАНа 222
8.9. Управление памятью для АЛГОЛа 223
Упражнения к разделу 8.9 236
8.10. Динамическое распределенне памяти 237
8.11. Исторические замечания 243
Глава 9. Организация таблиц символов 244
9.1. Введение в орrанизацию таблиц 244
9.2. Неупорядоченные и упорядоченные таблицы 246
9.3. Хеш-адресация 247
9.4. Таблицы символов, имеющие структуру дерева 256
Упражнения к разделу 9.4 257
9.5. Таблицы символов, имеющие блочную структуру 258
9.6. Исторические Замечания 262
Глава 10. Ииформация в таблице символов 264
10. 1. Описатель 264
10.2. Описатели для компонент структур 268
Упражнения к разделу 10.2 276
Глава 11. Внутренние формы исходной прогpаммы 278
11.1. Операторы и операнды 279
11.2. Польская запись 281
Упражнения к разделу 11.2 286
11.3. Тетрады 286
Упражнения к разделу 11.3 289
11.4. Триады, деревья и косвенные триады 289
11.5. Линейные участки 292
11.6. Исторические замечания 294
Глава 12. Введение в семантические npoгpaммы 295
12.1. Перевод инфиксной записи в польскую 295
Упражнения к разделу 12.1 299
12.2. Преобразование инфиксной записи в тетрады 299
Упражнения к разделу 12.2 302
12.3. Реализация семантических проrрамм и стеков 302
12.4. Семантическая обработка при нисходящем разборе 305
12.5. Исторические замечания 307
Глава 13. Семаитические nporpaMMbl для конструкций языка, подобного АЛГОЛу 309
13.1. Обозначения, принятые в семантических проrраммах 310
13.2. Условные ннструкции 312
Упражнения к разделу 13.2 315
13.3. Метки и переходы 315
Упражнения к разделу 13.3 318
13.4. Переменные и выражения 318
Упражнения к разделу 13.4 321
13.5. FОR-циклы 321
Упражнения к разделу 13.5 323
13.6. Оптимизация лоrических выражений 323
Глава 14. Отведение памяти переменным в готовой проrрамме 332
14.1. Присваивание адресов переменным 332
14.2. Отведение памятн временным переменным 341
Упражнения к разделу 14.2 341
14.3. COMMON и эквивалентность 342
Глава 15. Нейтрализация ошибок 353
15.1. Введение 353
15.2. Нейтрализация семантических ошибок 356
15.3. Нейтрализация сннтаксических ошибок 360
Глава 16. Иитерпретаторы 367
Глава 17. Генерация объектноrо кода 377
17.1 Введение 378
17.2. Генерация команд для простых арифметических выражений 379
17.3. Адресация операндов 392
17.4. rенерация команд для других типов тетрад 403
17.5. Экономия памяти при генерации кода . 407
17.6. Объектные модули 411
Упражнения к разделу 17.6 420
Глава 18. Оптимизация проrраммы 421
18.1. Оптимизация в пределах линейных участков. 422
18.2. Умеренная оптимизация циклов 429
18.3. Более полная оптимизация 444
18.4. Дополнительное обсуждение и исторические замечания 455
Глава 19. Реализация макросредств 461
19.1. Простая схема макроrенерации 461
Упражнения к разделу 19.1 472
19.2. Друrие свойства макро 472
19.3. Универсальный мaкpoгeнepaтop GPM 479
Упражнения к разделу 19.3 484
19.4. Исторические замечания 484
Глава 20. Системы построения трансляторов 486
20.1. Введение 486
20.2. Обсуждение двух компиляторов компиляторов 489
Глава 21. Советы разработчику компилятора 499
Приложение. Язык проrраммирования, используемый в книrе 513
Список литературы 522
Именной указатель 533
Предметный указатель 535
