Конструирование компиляторов для цифровых вычислительных машин

Description

В книге крупнейшего американского специалиста в области компиляторов Д. Гриса нашел отражение богатый опыт разработки и использования трансляторов для ЭВМ третьего поколения. Подробно рассмотрены как теоретические основы разработки компиляторов (теория формальных языков и грамматик), так и практические вопросы их реализации (лексический и синтаксический анализ, организация памяти и таблиц, оптимизация программ).Книга может служить учебником для тех, кто впервые сталкивается с разработкой компиляторов, и справочным пособием для опытных специалистов в этой области. Книга окажет большую помощь при подготовке в университетах и институтах квалифицированных кадров по системному программированию. Предисловие редакторов перевода 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