|
|
|
|
|
|
|
Ахо, Альфред,
В., Сети, Рави, Ульман, Джеффри, Д. Компиляторы: принципы, технологии и инструменты М.:
Издательский дом "Вильямс", 2002
Содержание
|
|
|
|
|
От редактора
|
18 |
|
|
|
Предисловие |
19 |
|
|
|
Использование
данной книги Упражнения
Благодарности
|
19 20 21 |
|
|
|
ГЛАВА 1. Введение в
компиляцию
|
22 |
|
|
|
1.1.
Компиляторы Модель
анализа-синтеза компиляции Контекст
компилятора 1.2.
Анализ исходной
программы Лексический
анализ Синтаксический
анализ Семантический
анализ Анализ
в программах форматирования текста 1.3. Фазы компилятора Управление
таблицей символов Обнаружение
ошибок и сообщение о них Фазы
анализа Генерация
промежуточного кода Оптимизация
кода Генерация
кода 1.4. Родственники компилятора Препроцессоры Ассемблеры Двухпроходный
ассемблер Загрузчики
и редакторы связей 1.5.
Группировка фаз Предварительная
и заключительная стадии Проходы Уменьшение
количества проходов 1.6. Инструментарий для создания компиляторов Библиографические
примечания |
22 23 25 25 26 26 28 29 30 30 31 33 34 34 35 35 35 37 37 38 39 39 40 40 41 43 |
|
|
|
ГЛАВА 2.
Простой однопроходный компилятор 2.1. Обзор 2.2. Определение синтаксиса Деревья
разбора Неоднозначность Ассоциативность
операторов Приоритет
операторов 2.3. Синтаксически управляемая трансляция Постфиксная
запись Синтаксически
управляемые определения Синтезируемые
атрибуты Рекурсивный
обход дерева Схемы
трансляции Вывод
результатов трансляции 2.4. Разбор Нисходящий
анализ Предиктивный
анализ Использование
£-продукций Создание
предиктивного анализатора Левая
рекурсия 2.5. Транслятор для простых выражений Абстрактный
и конкретный синтаксис Адаптация
схемы трансляции Процедуры
для нетерминалов expr, term и test Оптимизация
транслятора Полная
программа 2.6. Лексический анализ Удаление
пробелов и комментариев Константы Распознавание
идентификаторов и ключевых слов Интерфейс
к лексическому анализатору Лексический
анализатор 2.7. Использование таблиц символов Интерфейс
таблицы символов Обработка
зарезервированных ключевых слов Реализация
таблицы символов 2.8. Абстрактная стековая машина Арифметические
инструкции l-значения и r-значения Работа
со стеком Трансляция
выражений Управление
выполнением Трансляция
инструкций Вывод
результатов трансляции 2.9. Сборка транслятора Описание
транслятора Модуль
лексического анализа lexer.с Модуль
синтаксического анализатора parser.с Модуль
вывода emitter.с Модули
работы с таблицей символов symbol.с и init. с Модуль
обработки ошибок error.с Создание
компилятора Листинг Упражнения Программные упражнения Библиографические
примечания |
44 44 45 47 48 49 50 51 51 52 52 55 55 56 58 58 61 63 63 64 65 65 67 67 69 70 71 71 72 72 73 74 76 76 77 77 79 79 80 80 80 81 82 82 84 84 85 86 87 87 87 87 88 92 95 96 |
|
|
|
ГЛАВА 3.
Лексический анализ 3.1. Роль лексических анализаторов Задачи
лексического анализа Токены,
шаблоны, лексемы Атрибуты
токенов Лексические
ошибки 3.2.
Буферизация ввода Пары
буферов Ограничители 3.3. Определение токенов Строки
и языки Операции
над языками Регулярные
выражения Регулярные
определения Сокращения Нерегулярные
множества 3.4. Распознавание токенов Диаграммы
переходов Реализация
диаграммы переходов 3.5. Язык спецификации лексических анализаторов Спецификации
Lex Прогностический
оператор 3.6. Конечные автоматы Недетерминированные
конечные автоматы Детерминированный
конечный автомат Преобразование
НКА в ДКА 3.7. От регулярного выражения к НКА Построение
НКА по регулярному выражению Двустековое
моделирование НКА Скорость
работы 3.8. Построение генератора лексических анализаторов Поиск
по шаблону на основе НКА ДКА
для лексического анализа Реализация
прогностического оператора 3.9. Оптимизация поиска соответствия шаблону на базе ДКА Важные
состояния в НКА От
регулярного выражения к ДКА Минимизация
количества состояний ДКА Минимизация
состояний в лексических анализаторах Методы
сжатия таблиц Упражнения Программные упражнения Библиографические примечания |
97 97 98 99 100 101 102 102 104 105 105 106 107 109 110 110 111 112 116 119 119 123 125 125 127 128 132 132 136 137 139 140 142 143 144 144 145 150 153 153 155 165 165 |
|
|
|
ГЛАВА 4.
Синтаксический анализ 4.1. Роль синтаксического анализатора Обработка
синтаксических ошибок Стратегии
восстановления после ошибок 4.2. Контекстно-свободные грамматики Соглашения
по обозначениям Порождение Деревья
разбора и приведения Неоднозначность 4.3. Разработка грамматики Регулярные
выражения и контекстно-свободные грамматики Проверка
языка, порождённого грамматикой Устранение
неоднозначности Устранение
левой рекурсии Левая
факторизация Построение
не-контекстно-свободных грамматик 4.4.
Нисходящий анализ Анализ
методом рекурсивного спуска Предиктивные
анализаторы Диаграммы
переходов предиктивных синтаксических анализаторов Нерекурсивный
предиктивный анализ FIRST и FOLLOW Построение
таблиц предиктивного анализа LL(1)-грамматики Восстановление
после ошибок в предиктивном анализе 4.5.
Восходящий синтаксический
анализ Основы Обрезка
основ Стековая
реализация ПС-анализа Активные
префиксы Конфликты
в процессе ПС-анализа 4.6. Синтаксический анализ приоритета операторов Использование
отношений приоритетов операторов Нахождение
отношений приоритетов операторов Обработка
унарных операторов Функции
приоритета Восстановление
после ошибок при синтаксическом анализе приоритета операторов 4.7. LR-анализаторы Алгоритм
LR-анализа LR-грамматики Построение
таблиц SLR-анализа Построение
канонических таблиц LR-анализа Построение
таблиц LARL-анализа Эффективное
построение таблиц LALR-анализа 4.8. Использование неоднозначных грамматик Использование
приоритетов и ассоциативности для разрешения конфликтов Неоднозначность
"кочующего" else Неоднозначности
особых продукций частных случаев Восстановление
после ошибок при LR-анализе 4.9. Генераторы синтаксических анализаторов Генератор
синтаксических анализаторов Yacc Использование
Yacc с
неоднозначной грамматикой Создание
лексического анализатора в Yacc с помощью Lex Восстановление
после ошибок в Yacc Упражнения Библиографические примечания |
167 167 168 172 173 174 175 177 179 179 180 181 181 183 185 186 188 188 189 190 192 195 197 197 199 201 202 204 205 207 207 209 211 213 214 214 216 220 221 225 226 234 240 244 250 251 253 255 257 259 260 263 265 266 268 277 |
|
|
|
ГЛАВА 5.
Синтаксически управляемая трансляция 5.1. Синтаксически управляемые определения Вид
синтаксически управляемого определения Синтезируемые
атрибуты Наследуемые
атрибуты Графы
зависимости Порядок
выполнения 5.2. Построение синтаксических деревьев Синтаксические
деревья Построение
синтаксических деревьев для выражений Синтаксически
управляемое определение для построения синтаксических деревьев Направленные
ациклические графы выражений 5.3. Восходящее выполнение S-атрибутных
определений Синтезируемые
атрибуты в стеке синтаксического анализатора 5.4. L-атрибутные определения L-атрибутные определения Схемы
трансляции 5.5. Нисходящая трансляция Устранение
левой рекурсии из схемы трансляции Разработка
предиктивного транслятора 5.6. Восходящее вычисление наследуемых атрибутов Удаление
внедренных действий из схемы трансляции Наследование
атрибутов в стеке синтаксического анализатора Моделирование
вычисления наследуемых атрибутов Замена
наследуемых атрибутов синтезируемыми Сложное
синтаксически управляемое определение 5.7. Рекурсивные вычислители Обход
слева направо Другие
обходы 5.8. Память для значений атрибутов во время компиляции Назначение
памяти атрибутам во время компиляции Устранение
копий 5.9. Назначение памяти в процессе создания компилятора Вычисление
времени жизни по грамматике Неперекрывающиеся
времена жизни 5.10. Анализ синтаксически управляемых определений Рекурсивное
вычисление атрибутов Строго
нецикличные синтаксически управляемые определения Проверка
цикличности Упражнения Библиографические примечания |
279 280 280 281 282 283 285 286 286 287 288 289 292 292 295 295 296 299 299 303 305 305 306 308 312 312 312 313 314 315 317 318 319 319 323 324 325 327 328 330 334 |
|
|
|
ГЛАВА 6.
Проверка типов 6.1. Системы типов Выражения
типов Системы
типов Статическая
и динамическая проверка типов Восстановление
после ошибки 6.2. Спецификация простой программы проверки типов Простой
язык Проверка
типов выражений Проверка
типов инструкций Проверка
типов функций 6.3. Эквивалентность выражений типа Структурная
эквивалентность выражений типа Имена
выражений типа Циклы
в представлениях типов 6.4. Преобразования типов Неявное
преобразование типов 6.5. Перегрузка функций и операторов Множество
возможных типов подвыражения Сужение
множества возможных типов 6.6. Полиморфные функции Почему
используются полиморфные функции Переменные
типа Язык
с полиморфными функциями Подстановки,
примеры и унификация Проверка
полиморфных функций 6.7. Алгоритм унификации Упражнения Библиографические примечания |
336 337 338 339 340 340 341 341 342 343 343 344 344 347 349 350 350 352 352 354 355 355 356 358 360 361 365 369 374 |
|
|
|
ГЛАВА 7. Среды
времени исполнения 7.1. Вопросы исходного языка Процедуры Деревья
активации Стеки
управления Область
видимости объявления Организация
памяти и связывание имен 7.2. Организация памяти Классификация
памяти времени выполнения Записи
активаций Размещение
локальных данных в процессе компиляции 7.3. Стратегии выделения памяти Статическое
распределение памяти Стековое
распределение памяти Висячие
ссылки Распределение
памяти в куче 7.4. Доступ к нелокальным именам Блоки Лексическая
область видимости без вложенных процедур Лексическая
область видимости при наличии вложенных процедур Дисплеи Динамическая
область видимости 7.5. Передача параметров Передача
по значению Передача
по ссылке Копирование-восстановление Передача
по имени 7.6. Таблицы символов Записи
таблицы символов Символы
имени Информация
о выделенной памяти Использование
списков для представления таблицы символов Хеш-таблицы Представление
информации об области видимости 7.7. Возможности языков по динамическому выделению памяти Мусор Висячие
ссылки 7.8. Технологии динамического распределения памяти Явное
выделение блоков фиксированного размера Явное
выделение блоков переменного размера Неявное
освобождение 7.9. Распределение памяти в Fortran Данные
в областях COMMON Простой
алгоритм эквивалентности Алгоритм
эквивалентности для языка программирования Fortran Отображение
областей данных Упражнения Библиографические примечания |
376 376 376 377 379 380 382 382 382 384 385 386 387 389 394 395 396 396 398 400 403 406 407 408 409 410 411 412 413 414 415 415 416 420 422 424 424 425 425 426 426 428 429 430 433 435 436 442 |
|
|
|
ГЛАВА 8.
Генерация промежуточного кода 8.1. Языки промежуточных представлений Графическое
представление Трёхадресный
код Типы
трёхадресных инструкций Синтаксически
управляемая трансляция в трёхадресный код Реализация
трёхадресных инструкций Сравнение
представлений: использование косвенного обращения 8.2. Объявления Объявления
в процедуре Отслеживание
информации об области видимости Имена
полей в записях 8.3. Инструкции присвоения Имена
в таблице символов Повторное
использование временных имен Адресация
элементов массива Схема
трансляции для адресации элементов массива Преобразования
типов в присвоениях Доступ
к полям записей 8.4. Логические выражения Методы
трансляции логических выражений Числовое
представление Сокращённые
вычисления Инструкции
потока управления Трансляция
логических выражений с помощью потока управления Смешанные
логические выражения 8.5. Инструкции case Синтаксически
управляемая трансляция инструкции case 8.6. Технология обратных поправок Логические
выражения Инструкции
потока управления Схема
реализации трансляции Метки
и безусловные переходы 8.7. Вызовы процедур Вызывающие последовательности Простой пример Упражнения Библиографические примечания |
443 443 444 445 446 447 449 451 452 452 453 455 456 456 458 459 461 463 465 465 466 466 467 468 470 471 473 474 476 476 479 479 481 481 481 482 483 485 |
|
|
|
ГЛАВА 9.
Генерация кода 9.1. Вопросы создания генератора кода Вход
генератора кода Целевые
программы Управление
памятью Выбор
инструкций Распределение
регистров Выбор
порядка вычислений Подходы
к генерации кода 9.2. Целевая машина Стоимость
инструкции 9.3. Управление памятью во время исполнения Статическое
распределение Стековое
распределение Адресация
имен во время исполнения 9.4. Базовые блоки и графы потоков Базовые
блоки Преобразования
в базовых блоках Преобразования,
сохраняющие структуру Алгебраические
преобразования Графы
потоков Представление
базовых блоков Циклы 9.5. Информация о последующем использовании Вычисление
последующих использований Память
для временных имен 9.6. Простой генератор кода Дескрипторы
регистров и адресов Алгоритм
генерации кода Функция
getreg Генерация
кода для других типов инструкций Условные
инструкции 9.7. Распределение и назначение регистров Глобальное
распределение регистров Счетчики
использований Назначение
регистров для внешних циклов Распределение
регистров путём раскраски графа 9.8. Представление базовых блоков в виде дага Построение
дага Применение
дагов Массивы,
указатели и вызовы процедур 9.9. Локальная оптимизация Излишние
загрузки и сохранения Недостижимый
код Оптимизация
потока управления Алгебраические
упрощения Снижение
стоимости Использование
машинных идиом 9.10. Генерация кода на основе дагов Переупорядочение Эвристическое
упорядочение дагов Оптимальное
упорядочение для деревьев Алгоритм
назначения меток Генерация
кода на основе помеченного дерева Многорегистровые
операции Алгебраические
свойства Общие
подвыражения 9.11. Алгоритм динамического программирования для генерации кода Класс
регистровых машин Принцип
динамического программирования Последовательное
вычисление Алгоритм
динамического программирования 9.12.
Генераторы
генераторов кода Генерация
кода путём преобразования дерева Проверка
соответствия шаблону путём синтаксического анализа Программы
семантической проверки Упражнения Библиографические примечания |
487 487 487 488 489 489 490 491 491 492 493 494 495 497 499 500 500 502 502 503 503 504 505 505 505 506 507 508 508 509 511 512 512 513 513 516 516 517 518 520 522 524 524 525 526 527 527 527 527 528 529 530 531 532 535 535 536 537 538 538 538 539 541 542 547 548 548 551 |
|
|
|
ГЛАВА 10.
Оптимизация кода 10.1. Введение Критерии
для преобразований, улучшающих код Повышение
производительности Организация
оптимизирующего компилятора 10.2. Основные источники оптимизации Преобразования,
сохраняющие функции Общие
подвыражения Распространение
копий Удаление
бесполезного кода Оптимизации
циклов Перемещение
кода Переменные
индукции и снижение стоимости 10.3. Оптимизация базовых блоков Использование
алгебраических тождеств 10.4. Циклы в графах потока Доминаторы Естественные
циклы Внутренние
циклы Предзаголовки Приводимые
графы потоков 10.5. Введение в глобальный анализ потоков данных Точки
и пути Достигающие
определения Анализ
потока данных структурированной программы Консервативная
оценка информации потока данных Вычисление
in и out Работа
с циклами Представление
множеств Локальные
достигающие определения Цепочки
определений использований Порядок
вычислений Общий
поток управления 10.6. Итеративное решение уравнений потока данных Итеративный
алгоритм для достигающих определений Доступные
выражения Анализ
активных переменных Цепочки
использований определений 10.7. Преобразования, улучшающие код Устранение
глобальных общих подвыражений Распространение
копирований Поиск
вычислений, инвариантных относительно цикла Выполнение
перемещения кода Альтернативные
стратегии перемещения кода Поддержание
информации о потоке данных после перемещения кода Устранение
переменных индукции Переменные
индукции и выражения, инвариантные относительно
цикла 10.8. Работа с альтернативными именами Простой
язык указателей Воздействие
присвоений указателей Использование
информации об указателях Анализ
межпроцедурного потока данных Модель
кода с вызовами процедур Вычисление
псевдонимов Анализ
потока данных при наличии вызовов процедур Использование
информации об изменениях 10.9. Анализ потока данных структурированных графов потока Поиск
вглубь Дуги
представления графа потока вглубь Глубина
графа потока Интервалы Разбиение
на интервалы Графы
интервалов Разделение
узлов T1-T2-анализ Области Поиск
доминаторов 10.10 Эффективные алгоритмы потоков данных Упорядочение
вглубь в итеративных алгоритмах Анализ
потока данных, основанный на структуре Некоторые
ускорения структурного алгоритма Обработка
неприводимых графов потока 10.11 Средства для анализа потока данных Схема
анализа потока данных Аксиомы
схем анализа потока данных Монотонность
и дистрибутивность Решения
типа "слияние всех путей" в задачах о потоках данных Консервативные
решения задач о потоках Итеративный
алгоритм для обобщенных схем Инструмент
анализа потока данных Свойства
алгоритма 10.18 Сходимость
алгоритма 10.18 Исправление
инициализации 10.12. Оценка типов Работа
с бесконечными множествами типов Простая
система типов Прямая
схема Обратная
схема 10.13. Символьная отладка оптимизированного кода Отслеживание
значений переменных в базовых блоках Влияние
глобальной оптимизации Устранение
переменных индукции Устранение
глобальных общих подвыражений Перемещение
кода Упражнения Библиографические примечания |
553 554 554 555 556 559 559 559 561 562 562 563 563 565 567 568 568 570 571 571 572 574 575 575 577 579 580 581 583 584 585 585 586 588 588 591 594 596 596 596 598 601 602 604 605 605 610 610 611 611 614 615 616 617 618 621 622 622 625 626 626 627 628 629 629 630 631 633 633 635 639 639 640 641 643 644 648 649 650 650 651 652 653 653 654 656 657 658 661 662 667 667 667 668 669 675 |
|
|
|
ГЛАВА 11.
Создание компилятора 11. 1. Планирование компилятора Вопросы
исходного языка Вопросы
целевого языка Критерии
производительности 11.2. Подходы к разработке компилятора Раскрутка 11.3. Среда разработки компилятора 11.4. Тестирование и сопровождение |
679 679 679 680 680 680 681 684 686 |
|
|
|
ГЛАВА 12.
Некоторые компиляторы 12.1. Препроцессор математических формул EQN 12.2. Компиляторы Pascal 12.3. Компиляторы С 12.4. Компиляторы Fortran H Оптимизация
кода в Fortran H Алгебраическая
оптимизация Оптимизация
регистров 12.5. Компилятор Bliss/11 12.6. Оптимизирующий компилятор Modula-2 |
688 688 689 690 691 693 693 694 694 696 |
|
|
|
ПРИЛОЖЕНИЕ А. Программный проект А
1. Введение А.2.
Структура программы А.З.
Синтаксис подмножества Pascal А.4.
Лексические соглашения А.5.
Предлагаемые упражнения А.6.
Эволюция интерпретатора А.7.
Расширения |
698 698 698 699 701 701 703 703 |
|
|
|
ПРИЛОЖЕНИЕ Б. Спецификации языков программирования Б.1.
Язык программирования C++ Б.2.
Язык программирования С# БИБЛИОГРАФИЯ Предметный
указатель |
704 704 721 742 764 |
|
|
|
|
|
|