Второй том фундаментальной монографии известных американских ученых посвящен методам оптимизации синтаксических анализаторов, теории синтаксически управляемого перевода, а также способам организации памяти при переводе. Большое внимание уделяется методам оптимизации объектной программы. Авторы проделали значительную работу по отбору и систематизации многочисленных результатов, полученных в последние годы; они строят изложение на едином подходе к задачам перевода и задачам оптимизации программы.
Книга предназначена тем, кто работает в области системного и теоретического программирования, преподает или изучает эти дисциплины, а также разработчикам математического обеспечения ЭВМ.
ПРЕДИСЛОВИЕ
Конструирование компиляторов—один из первых больших разделов системного программирования, которые получают сейчас строгое теоретическое обоснование. В т. 1 этой книги изложены необходимые для такого обоснования сведения из математики и теории языков и основные методы проведения быстрого синтаксического анализа. Том 2 служит продолжением т. 1,но, за исключением гл. 7 и 8, он ориентирован на несинтаксические аспекты в конструировании компиляторов.
Материал в т. 2 излагается в основном так же, как и в т. 1, но доказательства здесь несколько более схематичны. Мы попытались по возможности облегчить чтение, включив в книгу много примеров, каждый из которых иллюстрирует одно или два
понятия.
Так как акцент делается на идеи, а не на языковые или машинные подробности, то основанный на этой книге курс должен сопровождаться лабораторными занятиями по программированию, чтобы студент мог получить некоторые навыки в применении обсуждаемых идей к практическим задачам. Для таких занятий можно порекомендовать упражнения на программирование, приведенные в конце разделов. Часть лабораторного курса должна быть посвящена вопросу генерации кода для таких конструкций языка программирования, как рекурсия, пересылка параметров, взаимодействие подпрограмм, адресация массивов, циклы и т. д.
О пользовании книгой
Книга возникла на основе записей лекций, прочитанных на старших курсах Принстонского университета и Стивенсовского технологического института. Материал т. 2 использовался в Сти-венсовском институте как семестровый курс конструирования компиляторов, следующий за семестровым курсом, основанным на
С точки зрения изучения конструировани: разделы книги, как мы полагаем, важнее
ОГЛАВЛЕНИЕ
ПРЕДИСЛОВИЕ 5
МЕТОДЫ ОПТИМИЗАЦИИ СИНТАКСИЧЕСКИХ АНАЛИЗАТОРОВ 7
7.1. Функции предшествования 7
7.1.1. Теорема о представлении матрицы 8
7.1.2. Применения к разбору, основанному на операторном предшествовании 14
7.1.3. Функции слабого предшествования 16
7.1.4. Преобразование матриц предшествования 19 Упражнения 25
Замечания по литературе 29
7.2. Оптимизация анализаторов Флойда—Эванса 29
7.2.1. Механическое построение анализаторов Флойда —Эванса для1 грамматик слабого предшествования 30
7.2.2. Усовершенствование анализаторов Флойда — Эванса 35 Упражнения 42
Замечания по литературе 45
7.3. Преобразования, определенные на множествах ЬН(А)-таблиц 45
7.3.1. Общее понятие ЬН(й)-таблицы 47
7.3.2. Эквивалентность множеств таблиц 52
7.3.3. ф-недостижимые множества таблиц 55
7.3.4. Слияние таблиц с помощью совместимых разбиений 99
7.3.5. Отсрочка в обнаружении ошибок 64
7.3.6. Исключение сверток по цепным правилам 76 Упражнения 84
Замечания по литературе 91
7.4. Методы построения ЬН(?)-анализаторов 91
7.4.1. Простые LR-грамматики 92
7.4.2. Распространение SLR-подхода на грамматики, не являющиеся SLR-грамматиками 97
7.4.3: Расщепление грамматики 102
Упражнения 113
Замечания по литературе 117
7.5. Анализирующие автоматы 117
7.5.1. Канонический анализирующий автомат 117
7.5.2. Расщепление функций состояний 122
7.5.3. Обобщение на ЬН(?)-анализат6ры 129
7.5.4. Обзор содержания1 главы 134 Упражнения 136
Замечания по литературе 138
485
8
ТЕОРИЯ ДЕТЕРМИНИРОВАННОГО РАЗБОРА 139
8.1. Теория LL-языков 141
8.1.1. LL- и LR-грамматнки 141
8.1.2. LL-грамматики в нормальной форме Грейбах 147
8.1.3. Проблема эквивалентности для LL-грамматик 156
8.1.4. Иерархия LL-языков 159 Упражнения 162 Замечания по литературе 163
8.2. Классы грамматик, порождающие детерминированные языки 164
8.2.1. ДМП-автоматы в нормальной форме и канонические грамматики 164
8.2.2. Простые ССП-грамматики и детерминированные языки 169
8.2.3. ОПК-грамматики, LR-грамматики и детерминированные языки 174
8.2.4. Грамматики расширенного предшествования и детерминированные языки 176
Упражнения 182
Замечания по литературе 185
8.3. Теория языков простого предшествования 185
8.3.1. Класс языков простого предшествования 185
8.3.2. Языки операторного предшествования 188
8.3.3. Обзор содержания главы 192 Упражнения 194
Замечания по литературе 195
ПЕРЕВОД И ГЕНЕРАЦИЯ КОДА 196
9.1. Роль перевода в процессе компиляции 196
9.1.1. Фазы компиляции 198
9.1.2. Представления промежуточной программы 200
9.1.3. Модели процесса генерации кода 204 Упражнения 205
Замечания по литературе 206
9.2. Синтаксически управляемые переводы 206
9.2.1. Простые синтаксически управляемые переводы 206
9.2.2. Обобщенный преобразователь 214
9.2.3. Детерминированный однопроходной восходящий перевод 218
9.2.4. Детерминированный однопроходной нисходящий перевод 219
9.2.5. Перевод при наличии возвратов 224 Упражнения 232 / Замечания по литературе 236
9.3. Обобщенные схемы переводов 236
9.3.1. Мультисхемы переводов 236
9.3.2. Разновидности переводов 245
9.3.3. Наследственный и синтезированный переводы 255
9.3.4. Замечание о разбиении на фазы 259 Упражнения 261
Замечания по литературе 2С6
10
11
ОРГАНИЗАЦИЯ ИНФОРМАЦИИ 267
10.1. Таблицы имен 267
10.1.1. Хранение информации о лексемах 268
10.1.2. Механизмы запоминания 270
10.1.3. Таблицы расстановки 274
10.1.4. Функции расстановки 277
10.1.5. Эффективность таблиц расстановки 279 Упражнения 287
Замечания по литературе 292
10.2. Грамматики свойств 292
10.2.1. Мотивировка 293
10.2.2. Определение грамматики свойств 395
10.2.3. Реализация грамматик свойств 304
10.2.4. Анализ алгоритма обработки таблиц 314 Упражнения 323
Замечания по литературе 326
ОПТИМИЗАЦИЯ КОДА 327
11.1. Оптимизация линейного участка 328
11.1.1. Модель линейного участка 328
11.1.2. Преобразования блоков 332
11.1.3. Графическое представление блоков 338
11.1.4. Критерий эквивалентности блоков 342
11.1.5. Оптимизация блоков 345
11.1.6. Алгебраические преобразования 351 Упражнения 357
Замечания по литературе 362
11.2. Арифметические выражения 362
11.2.1. Модель машины 363
11.2.2. Разметка деревьев 366
11.2.3. Программы с командами STORE 373
11.2.4. Влияние некоторых алгебраических законов 376 Упражнения 388
Замечания по литературе 392
11.3. Программы с циклами 393
11.3.1. Модель программу 394
11.3.2. Анализ потока управления 398
11.3.3. Примеры преобразований программ 404
11.3.4. Оптимизация циклов 408 Упражнения 418
Замечания по литературе 422
11.4. Анализ потока данных 423
11.4.1. Интервалы 424
11.4.2. Анализ потока данных с помощью интервалов 431
11.4.3. Несводимые графы управления 439
11.4.4. Обзор содержания главы 443 Упражнения 444
Замечания по литературе 448 Список литературы 449
Указатель лемм, теорем и алгоритмов к тому 2 465 Именной указатель к 1 и 2 томам 467 Предметный указатель к 1 и 2 томам 471
Цена: 300руб.
