В книге крупнейшего американского специалиста в области компиляторов Д. Гриса нашел отражение богатый опыт разработки и использования трансляторов для ЭВМ третьего поколения. Подробно рассмотрены как теоретические основы разработки компиляторов (теория формальных языков и грамматик), так и практические вопросы их реализации (лексический и синтаксический анализ, организация памяти и таблиц, оптимизация программ).
Книга может служить учебником для тех, кто впервые сталкивается с разработкой компиляторов, и справочным пособием для опытных специалистов в этой области. Книга окажет большую помощь при подготовке в университетах и институтах квалифицированных кадров по системному программированию.
ПРЕДИСЛОВИЕ РЕДАКТОРОВ ПЕРЕВОДА
Советский читатель уже имел возможность познакомиться с автором этой книги, профессором Корнельского университета Дэвидом Грисом по превосходному обзору «Системы построения трансляторов», написанному им совместно с Дж. Фелдманом. Перевод обзора был опубликован в 1971 году в сборнике «Алгоритмы и алгоритмические языки», вып. 5. И хотя значительная часть обзора в переработанном виде вошла в книгу, книга построена в совершенно ином плане. Она, по существу, представляет собой систематическое изложение методов конструирования компиляторов. В ее основу положено несколько курсов лекций, прочитанных автором в ряде американских университетов и в нескольких международных школах. Поэтому неудивительно, что книге свойственна хорошая дидактическая форма, отражающая тщательно продуманную методику изложения предмета.
Автор в своем предисловии говорит о том, что книга содержит весь необходимый материал по курсу 15 «Конструирование компиляторов», рекомендованному Комитетом университетских программ при АСМ. (Мы сочли целесообразным поместить вслед за нашим предисловием программу этого курса.) В настоящее время книга широко используется при изучении курса «Конструирование компиляторов» во многих зарубежных (не только американских) университетах. Редакторы перевода могут также отметить свой положительный опыт использования этой книги (еще в оригинале) при работе со студентами механико-математического факультета МГУ.
Не следует, однако, думать, что это всего лишь учебное пособие. В книге систематизирован и прекрасно изложен многолетний коллективный опыт разработки компиляторов. Заметим, что в список литературы вошло около 200 работ, на которые автор ссылается, иллю-
Оглавление
Предисловие редакторов перевода.................. 5
Программа курса 15 «Конструирование компиляторов»........ 8
Предисловие.............................. Ц
/ Глава 1. Введение.......................... 17
1.1. Компиляторы, ассемблеры, интерпретаторы......... 17
1.2. Краткий обзор процесса компиляции ........... 18
1.3. Примеры структур компиляторов.............. "24
Глава 2. Грамматики и языки..................... 28
2.1. Обсуждение грамматик.................. 28
Упражнения к разделу 2.1.................. 31
2.2. Символы и цепочки . .".................. 32
Упражнения к разделу 2.2.................. 34
2.3. Формальное определение грамматики и языка....... 35
Упражнения к разделу 2.3.................. 39
2.4. Синтаксические деревья и неоднозначность......... 40
Упражнения к разделу 2.4.................. 45
2.5. Задача разбора...................... 46
Упражнения к разделу 2.5................... 49
2.6. Некоторые отношения применительно к грамматикам ... 49 Упражнения к разделу 2.6.....-............... 53
^2мСГ Построение транзитивного замыкания отношений...... 53
Упражнения к разделу 2.7.................. 56
2.8. Практические ограничения, налагаемые на грамматики ... 57 Упражнения к разделу 2.8................... 60
2.9. Другие способы представления синтаксиса......... 60
2.10. Краткий обзор теории формальных языков........ 63
2.11. Резюме.......................... 66
Глава 3. Сканер........................... 69
3.1. Введение......................... 69
3.2. Регулярные выражения и конечные автоматы....... 72
Упражнения к разделу 3.2 .................. 84
3.3. Программирование сканера................. 84
Упражнения к разделу 3.3.................. . 92
§>$. Конструирование сканеров................. 92
Упражнение к разделу 3.4................... 100
3)ё. Система AED RWORD.................. 100
3^5. Исторические замечания.................. 105
[/ Глава 4. Нисходящие распознаватели............^. ..... 106
4.1. Нисходящий разбор с возвратами............. 106
4.2. Проблемы нисходящего разбора и их решение....... 115
I I/ 4.3. Рекурсивный спуск.................... 120
Упражнения к разделу 4.3................... 124
4.4. Исторические замечания.................. 124
V/ Глава 5. Грамматики простого предшествования............ 125
5.1. Отношения предшествования и их использование...... 125
Упражнения к разделу 5.1................... 128
5.2. Определение и построение отношений............ 129
Упражнения к разделу 5.2.................... 134
5.3. Алгоритм разбора..................... 134
Упражнения к разделу 5.3 Г.................. 137
5.4. Функции предшествования................. 137
Упражнения к разделу 5.4.................... 141
5.5. Трудности, возникающие при построении грамматик предшествования............................ 141
Упражнения к разделу 5.5................... 144
5.6. Исторические замечания.................. 144
Глава 6. Другие восходящие распознаватели.............. 145
6.1. Предшествование операторов................ 146
Упражнения к разделу 6.1................... 155
6.2. Предшествование более высокого порядка.......... 156
Упражнения к разделу 6.2................... 163
6.3. Ограниченный контекст.................... 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. Вызов семантических подпрограмм............• 195
7.4. Исторические замечания................. . 197
/ Глава 8, Организация памяти во время выполнения программы .... 198
8.1. Области данных и дисплеи................. 199
. Упражнения к разделу 8.1................... 201
8.2. Описатели......................... 201
8.3. Память для данных элементарных типов ........... 203
8.4. Память для массивов................... 203
Упражнения к разделу 8.4......•............. 208
8.5. Память для строк......, ,............. 208
8^>. Память для структур................... 210
8.7. Соответствие фактических и формальных параметров .... 216 Упражнения к разделу 8.7................... 221
8.8. Управление памятью для ФОРТРАНа............ 222
18*9. Управление памятью для АЛГОЛа............. 223
Упражнения к разделу 8.9................. . 236
8.10. Динамическое распределение памяти . . .......... 237
8.11. Исторические замечания................. 243
'у Глава 9. Организация таблиц символов................ 244
9.1. Введение в организацию таблиц . '.-............ 244
9.2. Неупорядоченные и упорядоченные таблицы......... 246
9.3. Хеш-адресация....................... 247
9.4. Таблицы символов, имеющие структуру дерева........ 256
Упражнения к разделу 9.4.................. 257
9.5. Таблицы символов, имеющие блочную структуру . . . . . 258
9.6. Исторические замечания.................. 262
' Глава 10. Информация в таблице символов............... 264
10.1. Описатель........................ 264
jQdT. Описатели для компонент структур............ 268
Упражнения к разделу 10.2.................. 276
' Глава 11. Внутренние формы исходной программы' .......... 278
11.1. Операторы и операнды.................. 279
11.2. Польская запись..................... 281
; Упражнения к разделу 11.2.................. 286
••" 11.3. Тетрады............. . ........... 286
i Упражнения к разделу 11.3.................... 289
\?А, Триады, деревья и косвенные триады .......... 289
: Ц,5. Линейные участки.................... 292
11.6. Исторические замечания.................. 294
Глава 12. Введение в семантические программы............ 295
12.1. Перевод инфиксной записи в польскую.......... 295
Упражнения к разделу 12.1.................. 299
12.2. Преобразование инфиксной записи в тетрады........ 299
Упражнения к разделу 12.2.................. 302
12.3. Реализация семантических программ и стеков....... 302
12.4. Семантическая обработка при нисходящем разборе..... 305
12.5. Исторические замечания................. 307
Глава 13. Семантические программы для конструкций языка, подобного
АЛГОЛу......-...................... 309
13.1. Обозначения, принятые в семантических программах . . . 310
13.2. Условные инструкции................... 312
Упражнения к разделу 13.2.................. 315
'13.3. Метки и переходы...................... 315
Упражнения к разделу 13,3.................. 318
13.4. Переменные и выражения................. 318
Упражнения к разделу 13.4.................. 321
13.5. FOR-циклы........................ 321
Упражнения к разделу 13.5.................. 323
13.6. Оптимизация логических выражений ............ 323
Глава 14. Отведение памяти переменным в готовой программе
332
14.1. Присваивание адресов переменным .......... ... 332
14.2. Отведение памяти временным переменным ......... 341
Упражнения к разделу 14.2 .................. 341
COMMON и эквивалентность ............... 342
Глава 15. Нейтрализация ошибок ................... 353
15.1. Введение ......................... 353
15.2. Нейтрализация семантических ошибок ........... 356
15.3. Нейтрализация синтаксических ошибок .......... 360
Глава 16. Интерпретаторы ...................... 367
Глава 17. Генерация объектного кода ................. 377
17.1 Введение ......................... 378
17.2. Генерация команд для простых арифметических выражений 379
17.3. Адресация операндов ................. . . 392
17.4. Генерация команд для других типов тетрад ........ 403
17.5. Экономия памяти при генерации кода ........... 407
17.6. Объектные модули .................... 411
Упражнения к разделу 17.6 .................. 420
Глава 18. Оптимизация программы .................. 421
18.1. Оптимизация в пределах линейных участков ........ 422
18.2. Умеренная оптимизация циклов .............. 429
18.3. Более полная оптимизация ................ 444
18.4. Дополнительное обсуждение и исторические замечания . . . 455
Глава 19. Реализация макросредств.................. 461
19.1. Простая схема макрогенераций............... 461
Упражнения к разделу 19.1.................. 472
19.2. Другие свойства макро.................. 472
19.3. Универсальный макрогенератор GPM........... 479
Упражнения к разделу 19.3.................. 484
19.4. Исторические замечания................. 484
Глава 20. Системы построения трансляторов.............. 486
20.1. Введение........................... 486
20.2. Обсуждение двух компиляторов компиляторов....... 489
Глава 21. Советы разработчику компилятора.............. 499
Приложение. Язык программирования, используемый в книге..... 513
Список литературы.......................... 522
Именной указатель . ........................ 533
Предметный указатель....................... 535
Цена: 150руб.
