Компиляторы. Принципы, технологии и инструментарий

Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман

Эта книга начинается с изложения основных принципов разработки компиляторов, включая детальное рассмотрение лексического и синтаксического анализа и генерации кода. Особенностью данного издания является широкое освещение вопросов оптимизации кода, в том числе для работы в многопроцессорных системах.

Строгость изложения материала смягчается большим количеством практических примеров. Написание компиляторов охватывает такие области знаний, как языки программирования, архитектура вычислительных систем, теория языков, алгоритмы и технология создания программного обеспечения. Помочь в освоении этих технологий и соответствующего инструментария и призвана данная книга.

Предназначена для студентов и преподавателей соответствующих специальностей - книга будет полезна всем, кто работает над созданием компиляторов или просто интересуется данной темой.

Издательство: Вильямс, 2008 г.

ISBN 978-5-8459-1349-4, 0-321-48681-1

Количество страниц: 1184.

Содержание книги «Компиляторы. Принципы, технологии и инструментарий»:

  • 24 Предисловие
  • 29 Глава 1. Введение в компиляцию
    • 29 1.1 Компиляторы
      • 32 1.1.1 Упражнения к разделу 1.1
    • 32 1.2 Структура компилятора
      • 33 1.2.1 Лексический анализ
      • 35 1.2.2 Синтаксический анализ
      • 37 1.2.3 Семантический анализ
      • 38 1.2.4 Генерация промежуточного кода
      • 39 1.2.5 Оптимизация кода
      • 39 1.2.6 Генерация кода
      • 40 1.2.7 Управление таблицей символов
      • 41 1.2.8 Объединение фаз в проходы
      • 41 1.2.9 Инструментарий для создания компиляторов
    • 42 1.3 Эволюция языков программирования
      • 42 1.3.1 Переход к языкам высокого уровня
      • 44 1.3.2 Влияние на компиляторы
      • 45 1.3.3 Упражнения к разделу 1.3
    • 45 1.4 «Компилятороведение»
      • 45 1.4.1 Моделирование при проектировании и реализации компилятора
      • 46 1.4.2 Изучение оптимизации кода
    • 48 1.5 Применения технологий компиляторов
      • 48 1.5.1 Реализация высокоуровневых языков программирования
      • 50 1.5.2 Оптимизация для архитектуры компьютера
      • 52 1.5.3 Разработка новых архитектур компьютеров
      • 54 1.5.4 Трансляции программ
      • 55 1.5.5 Инструментарий для повышения производительности программного обеспечения
    • 57 1.6 Азы языков программирования
      • 58 1.6.1 Понятия статического и динамического
      • 58 1.6.2 Среды и состояния
      • 61 1.6.3 Статическая область видимости и блочная структура
      • 65 1.6.4 Явное управление доступом
      • 65 1.6.5 Динамическая область видимости
      • 68 1.6.6 Механизмы передачи параметров
      • 70 1.6.7 Псевдонимы
      • 70 1.6.8 Упражнения к разделу 1.6
    • 72 1.7 Резюме к главе 1
    • 73 1.8 Список литературы к главе 1
  • 75 Глава 2. Простой синтаксически управляемый транслятор
    • 76 2.1 Введение
    • 78 2.2 Определение синтаксиса
      • 79 2.2.1 Определения грамматик
      • 81 2.2.2 Выведение
      • 82 2.2.3 Деревья разбора
      • 84 2.2.4 Неоднозначности
      • 85 2.2.5 Ассоциативность операторов
      • 86 2.2.6 Приоритет операторов
      • 89 2.2.7 Упражнения к разделу 2.2
    • 90 2.3 Синтаксически управляемая трансляция
      • 91 2.3.1 Постфиксная запись
      • 92 2.3.2 Синтезированные атрибуты
      • 94 2.3.3 Простые синтаксически управляемые определения
      • 95 2.3.4 Обходы дерева
      • 97 2.3.5 Схемы трансляции
      • 99 2.3.6 Упражнения к разделу 2.3
    • 100 2.4 Разбор
      • 101 2.4.1 Нисходящий анализ
      • 104 2.4.2 Предиктивный анализ
      • 106 2.4.3 Использование пустых продукций
      • 106 2.4.4 Разработка предиктивного анализатора
      • 107 2.4.5 Левая рекурсия
      • 109 2.4.6 Упражнения к разделу 2.4
    • 109 2.5 Транслятор простых выражений
      • 110 2.5.1 Абстрактный и конкретный синтаксис
      • 111 2.5.2 Адаптация схемы трансляции
      • 113 2.5.3 Процедуры для нетерминалов
      • 114 2.5.4 Упрощение транслятора
      • 115 2.5.5 Завершенная программа
    • 118 2.6 Лексический анализ
      • 119 2.6.1 Удаление пробельных символов и комментариев
      • 120 2.6.2 Опережающее чтение
      • 121 2.6.3 Константы
      • 121 2.6.4 Распознавание ключевых слов и идентификаторов
      • 123 2.6.5 Лексический анализатор
      • 128 2.6.6 Упражнения к разделу 2.6
    • 128 2.7 Таблицы символов
      • 129 2.7.1 Таблица символов для области видимости
      • 133 2.7.2 Использование таблиц символов
    • 136 2.8 Генерация промежуточного кода
      • 136 2.8.1 Два вида промежуточных представлений
      • 137 2.8.2 Построение синтаксических деревьев
      • 142 2.8.3 Статические проверки
      • 144 2.8.4 Трехадресный код
      • 151 2.8.5 Упражнения к разделу 2.8
    • 152 2.9 Резюме к главе 2
  • 155 Глава 3. Лексический анализ
    • 155 3.1 Роль лексического анализатора
      • 157 3.1.1 Лексический и синтаксический анализ
      • 157 3.1.2 Токены, шаблоны и лексемы
      • 159 3.1.3 Атрибуты токенов
      • 160 3.1.4 Лексические ошибки
      • 161 3.1.5 Упражнения к разделу 3.1
    • 162 3.2 Буферизация ввода
      • 162 3.2.1 Пары буферов
      • 163 3.2.2 Ограничители
    • 165 3.3 Спецификация токенов
      • 165 3.3.1 Строки и языки
      • 166 3.3.2 Операции над языками
      • 168 3.3.3 Регулярные выражения
      • 170 3.3.4 Регулярные определения
      • 172 3.3.5 Расширения регулярных выражений
      • 173 3.3.6 Упражнения к разделу 3.3
    • 177 3.4 Распознавание токенов
      • 179 3.4.1 Диаграммы переходов
      • 181 3.4.2 Распознавание зарезервированных слов и идентификаторов
      • 183 3.4.3 Завершение примера
      • 184 3.4.4 Архитектура лексического анализатора на основе диаграммы переходов
      • 187 3.4.5 Упражнения к разделу 3.4
    • 191 3.5 Генератор лексических анализаторов Lex
      • 191 3.5.1 Использование Lex
      • 192 3.5.2 Структура программ Lex
      • 196 3.5.3 Разрешение конфликтов в Lex
      • 197 3.5.4 Прогностический оператор
      • 198 3.5.5 Упражнения к разделу 3.5
    • 199 3.6 Конечные автоматы
      • 200 3.6.1 Недетерминированные конечные автоматы
      • 201 3.6.2 Таблицы переходов
      • 201 3.6.3 Принятие входной строки автоматом
      • 203 3.6.4 Детерминированный конечный автомат
      • 204 3.6.5 Упражнения к разделу 3.6
    • 205 3.7 От регулярных выражений к автоматам
      • 206 3.7.1 Преобразование НКА в ДКА
      • 210 3.7.2 Моделирование НКА
      • 210 3.7.3 Эффективность моделирования НКА
      • 213 3.7.4 Построение НКА из регулярного выражения
      • 218 3.7.5 Эффективность алгоритма обработки строк
      • 221 3.7.6 Упражнения к разделу 3.7
    • 221 3.8 Разработка генератора лексических анализаторов
      • 221 3.8.1 Структура генерируемого анализатора
      • 223 3.8.2 Распознавание шаблонов на основе НКА
      • 225 3.8.3 ДКА для лексических анализаторов
      • 226 3.8.4 Реализация прогностического оператора
      • 228 3.8.5 Упражнения к разделу 3.8
    • 229 3.9 Оптимизация распознавателей на основе ДКА
      • 229 3.9.1 Важные состояния НКА
      • 231 3.9.2 Функции, вычисляемые на синтаксическом дереве
      • 232 3.9.3 Вычисление nullable, firstpos и lastpos
      • 234 3.9.4 Вычисление followpos
      • 235 3.9.5 Преобразование регулярного выражения непосредственно в ДКА
      • 237 3.9.6 Минимизация количества состояний ДКА
      • 242 3.9.7 Минимизация состояний в лексических анализаторах
      • 242 3.9.8 Компромисс между скоростью и используемой памятью при моделировании ДКА
      • 244 3.9.9 Упражнения к разделу 3.9
    • 245 3.10 Резюме к главе 3
    • 247 3.11 Список литературы к главе 3
  • 251 Глава 4. Синтаксический анализ
    • 252 4.1 Введение
      • 252 4.1.1 Роль синтаксического анализатора
      • 253 4.1.2 Образцы грамматик
      • 254 4.1.3 Обработка синтаксических ошибок
      • 256 4.1.4 Стратегии восстановления после ошибок
    • 258 4.2 Контекстно-свободные грамматики
      • 258 4.2.1 Формальное определение контекстно-свободной грамматики
      • 260 4.2.2 Соглашения об обозначениях
      • 261 4.2.3 Порождения
      • 263 4.2.4 Деревья разбора и порождения
      • 265 4.2.5 Неоднозначность
      • 266 4.2.6 Проверка языка, сгенерированного грамматикой
      • 267 4.2.7 Контекстно-свободные грамматики и регулярные выражения
      • 269 4.2.8 Упражнения к разделу 4.2
    • 272 4.3 Разработка грамматики
      • 273 4.3.1 Лексический и синтаксический анализ
      • 273 4.3.2 Устранение неоднозначности
      • 275 4.3.3 Устранение левой рекурсии
      • 278 4.3.4 Левая факторизация
      • 279 4.3.5 Не контекстно-свободные языковые конструкции
      • 280 4.3.6 Упражнения к разделу 4.3
    • 281 4.4 Нисходящий синтаксический анализ
      • 283 4.4.1 Синтаксический анализ методом рекурсивного спуска
      • 285 4.4.2 FIRST и FOLLOW
      • 288 4.4.3 LL(1)-грамматики
      • 292 4.4.4 Нерекурсивный предиктивный синтаксический анализ
      • 295 4.4.5 Восстановление после ошибок в предиктивном синтаксическом анализе
      • 298 4.4.6 Упражнения к разделу 4.4
    • 301 4.5 Восходящий синтаксический анализ
      • 302 4.5.1 Свертки
      • 302 4.5.2 Обрезка основ
      • 304 4.5.3 Синтаксический анализ «перенос/свертка»
      • 306 4.5.4 Конфликты в процессе ПС-анализа
      • 309 4.5.5 Упражнения к разделу 4.5
    • 309 4.6 Введение в LR-анализ: простой LR
      • 310 4.6.1 Обоснование использования LR-анализаторов
      • 311 4.6.2 Пункты и LR(0)-автомат
      • 317 4.6.3 Алгоритм LR-анализа
      • 322 4.6.4 Построение таблиц SLR-анализа
      • 326 4.6.5 Активные префиксы
      • 328 4.6.6 Упражнения к разделу 4.6
    • 330 4.7 Более мощные LR-анализаторы
      • 331 4.7.1 Канонические LR(1)-пункты
      • 332 4.7.2 Построение множеств LR(1)-пунктов
      • 336 4.7.3 Канонические таблицы LR(1)-анализа
      • 338 4.7.4 Построение LALR-таблиц синтаксического анализа
      • 344 4.7.5 Эффективное построение таблиц LALR-анализа
      • 349 4.7.6 Уплотнение таблиц LR-анализа
      • 352 4.7.7 Упражнения к разделу 4.7
    • 353 4.8 Использование неоднозначных грамматик
      • 353 4.8.1 Использование приоритетов и ассоциативности для разрешения конфликтов
      • 357 4.8.2 Неоднозначность «висящего else»
      • 358 4.8.3 Восстановление после ошибок в LR-анализе
      • 361 4.8.4 Упражнения к разделу 4.8
    • 363 4.9 Генераторы синтаксических анализаторов
      • 364 4.9.1 Генератор синтаксических анализаторов Yacc
      • 368 4.9.2 Использование Yacc с неоднозначной грамматикой
      • 371 4.9.3 Создание лексического анализатора в Yacc с помощью Lex
      • 372 4.9.4 Восстановление после ошибок в Yacc
      • 375 4.9.5 Упражнения к разделу 4.9
    • 375 4.10 Резюме к главе 4
    • 378 4.11 Список литературы к главе 4
  • 383 Глава 5. Синтаксически управляемая трансляция
    • 384 5.1 Синтаксически управляемые определения
      • 384 5.1.1 Наследуемые и синтезируемые атрибуты
      • 387 5.1.2 Вычисление СУО в узлах дерева разбора
      • 390 5.1.3 Упражнения к разделу 5.1
    • 391 5.2 Порядок вычисления в СУО
      • 391 5.2.1 Графы зависимостей
      • 393 5.2.2 Упорядочение вычисления атрибутов
      • 394 5.2.3 S-атрибутные определения
      • 394 5.2.4 L-атрибутные определения
      • 396 5.2.5 Семантические правила с контролируемыми побочными действиями
      • 398 5.2.6 Упражнения к разделу 5.2
    • 399 5.3 Применения синтаксически управляемой трансляции
      • 400 5.3.1 Построение синтаксических деревьев
      • 404 5.3.2 Структура типа
      • 406 5.3.3 Упражнения к разделу 5.3
    • 406 5.4 Синтаксически управляемые схемы трансляции
      • 407 5.4.1 Постфиксные схемы трансляции
      • 407 5.4.2 Реализация постфиксной СУТ с использованием стека синтаксического анализатора
      • 410 5.4.3 СУТ с действиями внутри продукций
      • 411 5.4.4 Устранение левой рекурсии из СУТ
      • 414 5.4.5 СУТ для L-атрибутных определений
      • 421 5.4.6 Упражнения к разделу 5.4
    • 422 5.5 Реализация L-атрибутных СУО
      • 423 5.5.1 Трансляция в процессе синтаксического анализа методом рекурсивного спуска
      • 425 5.5.2 Генерация кода «на лету»
      • 428 5.5.3 L-атрибутные СУО и LL-синтаксический анализ
      • 434 5.5.4 Восходящий синтаксический анализ L-атрибутных СУО
      • 439 5.5.5 Упражнения к разделу 5.5
    • 439 5.6 Резюме к главе 5
    • 441 5.7 Список литературы к главе 5
  • 443 Глава 6. Генерация промежуточного кода
    • 445 6.1 Варианты синтаксических деревьев
      • 445 6.1.1 Ориентированные ациклические графы для выражений
      • 447 6.1.2 Метод номера значения для построения ориентированных ациклических графов
      • 450 6.1.3 Упражнения к разделу 6.1
    • 450 6.2 Трехадресный код
      • 450 6.2.1 Адреса и команды
      • 454 6.2.2 Четверки
      • 455 6.2.3 Тройки
      • 457 6.2.4 Представление в виде статических единственных присваиваний
      • 458 6.2.5 Упражнения к разделу 6.2
    • 459 6.3 Типы и объявления
      • 459 6.3.1 Выражения типов
      • 461 6.3.2 Эквивалентность типов
      • 462 6.3.3 Объявления
      • 462 6.3.4 Размещение локальных имен в памяти
      • 464 6.3.5 Последовательности объявлений
      • 466 6.3.6 Поля в записях и классах
      • 467 6.3.7 Упражнения к разделу 6.3
    • 468 6.4 Трансляция выражений
      • 468 6.4.1 Операции в выражениях
      • 470 6.4.2 Инкрементная трансляция
      • 471 6.4.3 Адресация элементов массива
      • 473 6.4.4 Трансляция обращений к массиву
      • 475 6.4.5 Упражнения к разделу 6.4
    • 477 6.5 Проверка типов
      • 477 6.5.1 Правила проверки типов
      • 478 6.5.2 Преобразования типов
      • 481 6.5.3 Перегрузка функций и операторов
      • 482 6.5.4 Выведение типа и полиморфные функции
      • 487 6.5.5 Алгоритм унификации
      • 490 6.5.6 Упражнения к разделу 6.5
    • 491 6.6 Поток управления
      • 492 6.6.1 Булевы выражения
      • 492 6.6.2 Код сокращенного вычисления
      • 493 6.6.3 Инструкции потока управления
      • 496 6.6.4 Трансляция логических выражений с помощью потока управления
      • 499 6.6.5 Устранение излишних команд перехода
      • 501 6.6.6 Булевы значения и код с переходами
      • 502 6.6.7 Упражнения к разделу 6.6
    • 504 6.7 Обратные поправки
      • 504 6.7.1 Однопроходная генерация кода с использованием обратных поправок
      • 505 6.7.2 Обратные поправки для булевых выражений
      • 508 6.7.3 Инструкции потока управления
      • 511 6.7.4 Инструкции break, continue и goto
      • 512 6.7.5 Упражнения к разделу 6.7
    • 514 6.8 Инструкции выбора
      • 514 6.8.1 Трансляция инструкций выбора
      • 515 6.8.2 Синтаксически управляемая трансляция инструкций выбора
      • 517 6.8.3 Упражнения к разделу 6.8
    • 517 6.9 Промежуточный код процедур
    • 520 6.10 Резюме к главе 6
    • 521 6.11 Список литературы к главе 6
  • 525 Глава 7. Среды времени выполнения
    • 525 7.1 Организация памяти
      • 527 7.1.1 Статическое и динамическое распределение памяти
    • 528 7.2 Выделение памяти в стеке
      • 529 7.2.1 Деревья активации
      • 532 7.2.2 Записи активации
      • 535 7.2.3 Последовательности вызовов
      • 539 7.2.4 Данные переменной длины в стеке
      • 540 7.2.5 Упражнения к разделу 7.2
    • 542 7.3 Доступ к нелокальным данным в стеке
      • 542 7.3.1 Доступ к данным при отсутствии вложенных процедур
      • 543 7.3.2 Вложенные процедуры
      • 544 7.3.3 Язык с вложенными объявлениями процедур
      • 545 7.3.4 Глубина вложенности
      • 547 7.3.5 Связи доступа
      • 548 7.3.6 Работа со связями доступа
      • 550 7.3.7 Связи доступа для процедур, являющихся параметрами
      • 551 7.3.8 Дисплеи
      • 554 7.3.9 Упражнения к разделу 7.3
    • 555 7.4 Управление кучей
      • 555 7.4.1 Диспетчер памяти
      • 557 7.4.2 Иерархия памяти компьютера
      • 559 7.4.3 Локальность в программах
      • 561 7.4.4 Снижение фрагментации
      • 565 7.4.5 Освобождение памяти вручную
      • 568 7.4.6 Упражнения к разделу 7.4
    • 568 7.5 Введение в сборку мусора
      • 569 7.5.1 Цели проектирования сборщиков мусора
      • 572 7.5.2 Достижимость
      • 574 7.5.3 Сборщики мусора с подсчетом ссылок
      • 576 7.5.4 Упражнения к разделу 7.5
    • 576 7.6 Введение в сборку на основе отслеживания
      • 577 7.6.1 Базовый сборщик мусора
      • 580 7.6.2 Базовая абстракция
      • 582 7.6.3 Оптимизация алгоритма «пометить и подмести»
      • 583 7.6.4 Сборщики мусора «пометить и сжать»
      • 587 7.6.5 Копирующие сборщики
      • 589 7.6.6 Сравнение стоимости
      • 590 7.6.7 Упражнения к разделу 7.6
    • 591 7.7 Распределенная сборка мусора
      • 591 7.7.1 Инкрементная сборка мусора
      • 593 7.7.2 Инкрементный анализ достижимости
      • 596 7.7.3 Основы частичной сборки
      • 597 7.7.4 Сборка мусора по поколениям
      • 599 7.7.5 Алгоритм поезда
      • 603 7.7.6 Упражнения к разделу 7.7
    • 604 7.8 Дополнительные вопросы сборки мусора
      • 605 7.8.1 Параллельная сборка мусора
      • 608 7.8.2 Частичное перемещение объектов
      • 608 7.8.3 Консервативная сборка мусора для небезопасных языков программирования
      • 609 7.8.4 Слабые ссылки
      • 610 7.8.5 Упражнения к разделу 7.8
    • 611 7.9 Резюме к главе 7
    • 614 7.10 Список литературы к главе 7
  • 617 Глава 8. Генерация кода
    • 619 8.1 Вопросы проектирования генератора кода
      • 619 8.1.1 Вход генератора кода
      • 620 8.1.2 Целевая программа
      • 621 8.1.3 Выбор команд
      • 623 8.1.4 Распределение регистров
      • 625 8.1.5 Порядок вычислений
    • 625 8.2 Целевой язык
      • 625 8.2.1 Простая модель целевой машины
      • 629 8.2.2 Стоимость программ и команд
      • 630 8.2.3 Упражнения к разделу 8.2
    • 632 8.3 Адреса в целевом коде
      • 632 8.3.1 Статическое выделение памяти
      • 635 8.3.2 Выделение памяти в стеке
      • 638 8.3.3 Адреса имен времени выполнения
      • 639 8.3.4 Упражнения к разделу 8.3
    • 640 8.4 Базовые блоки и графы потоков
      • 641 8.4.1 Базовые блоки
      • 643 8.4.2 Информация о дальнейшем использовании
      • 644 8.4.3 Графы потоков
      • 646 8.4.4 Представление графов потоков
      • 646 8.4.5 Циклы
      • 647 8.4.6 Упражнения к разделу 8.4
    • 648 8.5 Оптимизация базовых блоков
      • 648 8.5.1 Представление базовых блоков с использованием ориентированных ациклических графов
      • 649 8.5.2 Поиск локальных общих подвыражений
      • 651 8.5.3 Устранение неиспользуемого кода
      • 652 8.5.4 Применение алгебраических тождеств
      • 653 8.5.5 Представление обращений к массивам
      • 655 8.5.6 Присваивание указателей и вызовы процедур
      • 656 8.5.7 Сборка базового блока из ориентированного ациклического графа
      • 658 8.5.8 Упражнения к разделу 8.5
    • 660 8.6 Простой генератор кода
      • 661 8.6.1 Дескрипторы регистров и адресов
      • 661 8.6.2 Алгоритм генерации кода
      • 665 8.6.3 Разработка функции getReg
      • 667 8.6.4 Упражнения к разделу 8.6
    • 668 8.7 Локальная оптимизация
      • 668 8.7.1 Устранение излишних загрузок и сохранений
      • 669 8.7.2 Устранение недостижимого кода
      • 670 8.7.3 Оптимизация потока управления
      • 671 8.7.4 Алгебраические упрощения и снижение стоимости
      • 671 8.7.5 Использование машинных идиом
      • 671 8.7.6 Упражнения к разделу 8.7
    • 672 8.8 Распределение и назначение регистров
      • 672 8.8.1 Глобальное распределение регистров
      • 673 8.8.2 Счетчики использований
      • 676 8.8.3 Назначение регистров для внешних циклов
      • 676 8.8.4 Распределение регистров путем раскраски графа
      • 677 8.8.5 Упражнения к разделу 8.8
    • 677 8.9 Выбор команд путем переписывания дерева
      • 678 8.9.1 Схемы трансляции деревьев
      • 681 8.9.2 Генерация кода путем замощения входного дерева
      • 684 8.9.3 Поиск соответствий с использованием синтаксического анализа
      • 685 8.9.4 Программы семантической проверки
      • 686 8.9.5 Обобщенный поиск соответствий
      • 688 8.9.6 Упражнения к разделу 8.9
    • 688 8.10 Генерация оптимального кода для выражений
      • 689 8.10.1 Числа Ершова
      • 690 8.10.2 Генерация кода на основе помеченных деревьев выражений
      • 692 8.10.3 Вычисление выражений при недостаточном количестве регистров
      • 694 8.10.4 Упражнения к разделу 8.10
    • 695 8.11 Генерация кода с использованием динамического программирования
      • 696 8.11.1 Последовательные вычисления
      • 697 8.11.2 Алгоритм динамического программирования
      • 700 8.11.3 Упражнения к разделу 8.11
    • 700 8.12 Резюме к главе 8
    • 702 8.13 Список литературы к главе 8
  • 705 Глава 9. Машинно-независимые оптимизации
    • 706 9.1 Основные источники оптимизации
      • 706 9.1.1 Причины избыточности
      • 707 9.1.2 Конкретный пример: быстрая сортировка
      • 710 9.1.3 Трансформации, сохраняющие семантику
      • 710 9.1.4 Глобальные общие подвыражения
      • 712 9.1.5 Распространение копий
      • 713 9.1.6 Удаление бесполезного кода
      • 714 9.1.7 Перемещение кода
      • 715 9.1.8 Переменные индукции и снижение стоимости
      • 718 9.1.9 Упражнения к разделу 9.1
    • 719 9.2 Введение в анализ потоков данных
      • 720 9.2.1 Абстракция потока данных
      • 722 9.2.2 Схема анализа потока данных
      • 723 9.2.3 Схемы потоков данных в базовых блоках
      • 725 9.2.4 Достигающие определения
      • 733 9.2.5 Анализ активных переменных
      • 735 9.2.6 Доступные выражения
      • 740 9.2.7 Резюме
      • 740 9.2.8 Упражнения к разделу 9.2
    • 743 9.3 Основы анализа потока данных
      • 744 9.3.1 Полурешетки
      • 750 9.3.2 Передаточные функции
      • 753 9.3.3 Итеративный алгоритм в обобщенной структуре
      • 755 9.3.4 Смысл решения потока данных
      • 759 9.3.5 Упражнения к разделу 9.3
    • 760 9.4 Распространение констант
      • 761 9.4.1 Значения потока данных для структуры распространения констант
      • 762 9.4.2 Сбор в структуре распространения констант
      • 762 9.4.3 Передаточные функции для структуры распространения констант
      • 763 9.4.4 Монотонность структуры распространения констант
      • 764 9.4.5 Недистрибутивность структуры распространения констант
      • 765 9.4.6 Интерпретация результатов
      • 767 9.4.7 Упражнения к разделу 9.4
    • 768 9.5 Устранение частичной избыточности
      • 769 9.5.1 Источники избыточности
      • 771 9.5.2 Все ли избыточные вычисления могут быть устранены?
      • 773 9.5.3 Отложенное перемещение кода
      • 774 9.5.4 Ожидаемость выражений
      • 775 9.5.5 Алгоритм отложенного перемещения кода
      • 785 9.5.6 Упражнения к разделу 9.5
    • 787 9.6 Циклы в графах потоков
      • 787 9.6.1 Доминаторы
      • 790 9.6.2 Упорядочение в глубину
      • 792 9.6.3 Ребра в глубинном остовном дереве
      • 794 9.6.4 Обратные ребра и приводимость
      • 795 9.6.5 Глубина графа потока
      • 796 9.6.6 Естественные циклы
      • 798 9.6.7 Скорость сходимости итеративных алгоритмов потоков данных
      • 801 9.6.8 Упражнения к разделу 9.6
    • 803 9.7 Анализ на основе областей
      • 804 9.7.1 Области
      • 805 9.7.2 Иерархии областей для приводимых графов потоков
      • 808 9.7.3 Обзор анализа на основании областей
      • 810 9.7.4 Необходимые предположения о передаточных функциях
      • 811 9.7.5 Алгоритм анализа на основе областей
      • 816 9.7.6 Обработка неприводимых графов потоков
      • 818 9.7.7 Упражнения к разделу 9.7
    • 819 9.8 Символический анализ
      • 819 9.8.1 Аффинные выражения ссылочных переменных
      • 822 9.8.2 Формулировка задачи потока данных
      • 827 9.8.3 Символический анализ на основе областей
      • 832 9.8.4 Упражнения к разделу 9.8
    • 833 9.9 Резюме к главе 9
    • 838 9.10 Список литературы к главе 9
  • 841 Глава 10. Параллелизм на уровне команд
    • 842 10.1 Архитектуры процессоров
      • 842 10.1.1 Конвейерная обработка команд и задержки ветвления
      • 843 10.1.2 Конвейерное выполнение
      • 844 10.1.3 Многоадресные команды
    • 845 10.2 Ограничения планирования кода
      • 846 10.2.1 Зависимость через данные
      • 846 10.2.2 Поиск зависимостей среди обращений к памяти
      • 848 10.2.3 Компромиссы между использованием регистров и параллелизмом
      • 851 10.2.4 Упорядочение фаз распределения регистров и планирования кода
      • 852 10.2.5 Зависимость от управления
      • 853 10.2.6 Поддержка опережающего выполнения
      • 855 10.2.7 Базовая модель машины
      • 856 10.2.8 Упражнения к разделу 10.2
    • 857 10.3 Планирование базовых блоков
      • 858 10.3.1 Графы зависимости данных
      • 859 10.3.2 Планирование списков базовых блоков
      • 861 10.3.3 Приоритетные топологические порядки
      • 863 10.3.4 Упражнения к разделу 10.3
    • 864 10.4 Глобальное планирование кода
      • 865 10.4.1 Примитивное перемещение кода
      • 867 10.4.2 Восходящее перемещение кода
      • 868 10.4.3 Нисходящее перемещение кода
      • 870 10.4.4 Обновление зависимостей данных
      • 870 10.4.5 Алгоритм глобального планирования
      • 874 10.4.6 Усовершенствованные методы перемещения кода
      • 875 10.4.7 Взаимодействие с динамическими планировщиками
      • 876 10.4.8 Упражнения к разделу 10.4
    • 876 10.5 Программная конвейеризация
      • 877 10.5.1 Введение
      • 879 10.5.2 Программная конвейеризация циклов
      • 882 10.5.3 Распределение регистров и генерация кода
      • 883 10.5.4 Циклы с зависимыми итерациями
      • 884 10.5.5 Цели и ограничения программной конвейеризации
      • 888 10.5.6 Алгоритм программной конвейеризации
      • 889 10.5.7 Планирование ациклических графов зависимости данных
      • 891 10.5.8 Планирование графов с циклическими зависимостями
      • 899 10.5.9 Усовершенствования алгоритма конвейеризации
      • 900 10.5.10 Модульное расширение переменных
      • 903 10.5.11 Условные инструкции
      • 904 10.5.12 Аппаратная поддержка программной конвейеризации
      • 904 10.5.13 Упражнения к разделу 10.5
    • 907 10.6 Резюме к главе 10
    • 909 10.7 Список литературы к главе 10
  • 911 Глава 11. Оптимизация параллелизма и локальности
    • 914 11.1 Фундаментальные концепции
      • 914 11.1.1 Многопроцессорность
      • 917 11.1.2 Параллелизм в приложениях
      • 918 11.1.3 Параллелизм на уровне циклов
      • 920 11.1.4 Локальность данных
      • 922 11.1.5 Введение в теорию аффинных преобразований
    • 927 11.2 Пример посерьезнее: умножение матриц
      • 927 11.2.1 Алгоритм умножения матриц
      • 930 11.2.2 Оптимизации
      • 933 11.2.3 Интерференция кэша
      • 933 11.2.4 Упражнения к разделу 11.2
    • 934 11.3 Пространства итераций
      • 934 11.3.1 Построение пространств итераций вложений циклов
      • 936 11.3.2 Порядок выполнения вложенности циклов
      • 938 11.3.3 Матричная запись неравенств
      • 938 11.3.4 Добавление символьных констант
      • 939 11.3.5 Управление порядком выполнения
      • 944 11.3.6 Изменение осей
      • 945 11.3.7 Упражнения к разделу 11.3
    • 948 11.4 Аффинные индексы массивов
      • 948 11.4.1 Аффинные обращения к данным
      • 949 11.4.2 Аффинное и неаффинное обращения на практике
      • 950 11.4.3 Упражнения к разделу 11.4
    • 951 11.5 Повторное использование данных
      • 952 11.5.1 Типы повторных использований
      • 953 11.5.2 Собственные повторные использования
      • 958 11.5.3 Собственное пространственное повторное использование
      • 959 11.5.4 Групповое повторное использование
      • 962 11.5.5 Упражнения к разделу 11.5
    • 964 11.6 Анализ зависимости данных в массивах
      • 965 11.6.1 Определение зависимостей данных доступов к массивам
      • 966 11.6.2 Целочисленное линейное программирование
      • 967 11.6.3 НОД
      • 969 11.6.4 Эвристики для решения задачи целочисленного линейного программирования
      • 973 11.6.5 Решение обобщенной задачи целочисленного линейного программирования
      • 975 11.6.6 Резюме
      • 976 11.6.7 Упражнения к разделу 11.6
    • 978 11.7 Поиск параллельности, не требующей синхронизации
      • 978 11.7.1 Вводный пример
      • 981 11.7.2 Разбиения аффинного пространства
      • 982 11.7.3 Ограничения разбиений пространства
      • 986 11.7.4 Решение ограничений разбиений пространств
      • 990 11.7.5 Простой алгоритм генерации кода
      • 993 11.7.6 Устранение пустых итераций
      • 996 11.7.7 Устранение проверок из внутреннего цикла
      • 998 11.7.8 Преобразования исходного кода
      • 1003 11.7.9 Упражнения к разделу 11.7
    • 1005 11.8 Синхронизация между параллельными циклами
      • 1006 11.8.1 Постоянное количество синхронизаций
      • 1007 11.8.2 Графы зависимостей программ
      • 1009 11.8.3 Иерархическое время
      • 1012 11.8.4 Алгоритм распараллеливания
      • 1013 11.8.5 Упражнения к разделу 11.8
    • 1013 11.9 Конвейеризация
      • 1014 11.9.1 Что такое конвейеризация
      • 1016 11.9.2 Последовательная сверхрелаксация: пример
      • 1017 11.9.3 Полностью переставляемые циклы
      • 1018 11.9.4 Конвейеризация полностью переставляемых циклов
      • 1021 11.9.5 Общая теория
      • 1022 11.9.6 Ограничения временного разбиения
      • 1026 11.9.7 Решение временных ограничений с использованием леммы Фаркаша
      • 1029 11.9.8 Преобразования кода
      • 1035 11.9.9 Параллелизм с минимальной синхронизацией
      • 1037 11.9.10 Упражнения к разделу 11.9
    • 1039 11.10 Оптимизации локальности
      • 1040 11.10.1 Временная локальность вычисляемых данных
      • 1041 11.10.2 Сжатие массива
      • 1044 11.10.3 Чередование частей
      • 1047 11.10.4 Алгоритмы оптимизации локальности
      • 1050 11.10.5 Упражнения к разделу 11.10
    • 1050 11.11 Прочие применения аффинных преобразований
      • 1050 11.11.1 Машины с распределенной памятью
      • 1051 11.11.2 Процессоры с одновременным выполнением нескольких команд
      • 1052 11.11.3 Векторные и SIMD-команды
      • 1053 11.11.4 Предвыборка
    • 1054 11.12 Резюме к главе 11
    • 1057 11.13 Список литературы к главе 11
  • 1061 Глава 12. Межпроцедурный анализ
    • 1062 12.1 Базовые концепции
      • 1062 12.1.1 Графы вызовов
      • 1064 12.1.2 Чувствительность к контексту
      • 1067 12.1.3 Строки вызовов
      • 1069 12.1.4 Контекстно-чувствительный анализ на основе клонирования
      • 1070 12.1.5 Контекстно-чувствительный анализ на основе резюме
      • 1073 12.1.6 Упражнения к разделу 12.1
    • 1075 12.2 Необходимость межпроцедурного анализа
      • 1076 12.2.1 Вызовы виртуальных методов
      • 1076 12.2.2 Анализ псевдонимов указателей
      • 1077 12.2.3 Параллельность
      • 1077 12.2.4 Поиск программных ошибок и уязвимых мест
      • 1078 12.2.5 SQL-ввод
      • 1080 12.2.6 Переполнение буфера
    • 1081 12.3 Логическое представление потока данных
      • 1082 12.3.1 Введение в Datalog
      • 1083 12.3.2 Правила Datalog
      • 1085 12.3.3 Интенсиональные и экстенсиональные предикаты
      • 1088 12.3.4 Выполнение программы Datalog
      • 1090 12.3.5 Инкрементное вычисление программ Datalog
      • 1091 12.3.6 Проблематичные правила Datalog
      • 1093 12.3.7 Упражнения к разделу 12.3
    • 1095 12.4 Простой алгоритм анализа указателей
      • 1096 12.4.1 Сложность анализа указателей
      • 1097 12.4.2 Модель указателей и ссылок
      • 1098 12.4.3 Нечувствительность к потоку
      • 1099 12.4.4 Формулировка с применением Datalog
      • 1101 12.4.5 Использование информации о типе
      • 1102 12.4.6 Упражнения к разделу 12.4
    • 1105 12.5 Контекстно-нечувствительный межпроцедурный анализ
      • 1105 12.5.1 Влияние вызовов методов
      • 1107 12.5.2 Построение графа вызовов в Datalog
      • 1108 12.5.3 Динамическая загрузка и отражение
      • 1109 12.5.4 Упражнения к разделу 12.5
    • 1109 12.6 Контекстно-чувствительный анализ указателей
      • 1110 12.6.1 Контексты и строки вызовов
      • 1113 12.6.2 Добавление контекста в правила Datalog
      • 1114 12.6.3 Дополнительные наблюдения о чувствительности
      • 1115 12.6.4 Упражнения к разделу 12.6
    • 1115 12.7 Реализация Datalog с применением BDD
      • 1116 12.7.1 Диаграммы бинарного выбора
      • 1118 12.7.2 Преобразования диаграмм бинарного выбора
      • 1119 12.7.3 Представление отношений при помощи BDD
      • 1120 12.7.4 Операции отношений и BDD-операции
      • 1123 12.7.5 Использование диаграмм бинарного выбора для анализа целей указателей
      • 1124 12.7.6 Упражнения к разделу 12.7
    • 1124 12.8 Резюме к главе 12
    • 1128 12.9 Список литературы к главе 12
  • 1133 Приложение А. Завершенный пример начальной стадии компилятора
    • 1133 А.1 Исходный язык
    • 1135 А.2 Main
    • 1135 А.3 Лексический анализатор
    • 1139 А.4 Таблицы символов и типы
    • 1140 А.5 Промежуточный код выражений
    • 1144 А.6 Переходы для булевых выражений
    • 1149 А.7 Промежуточный код для инструкций
    • 1153 А.8 Синтаксический анализатор
    • 1160 А.9 Построение начальной стадии
  • 1163 Приложение Б. Поиск линейно независимых решений
  • 1167 Предметный указатель

Инструкция как скачать книгу Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман: Компиляторы. Принципы, технологии и инструментарий в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.
Компиляторы. Принципы, технологии и инструментарий
Рейтинг книги:
0 голосов
1551

Поиск книг:




При поиске учитываются только слова, длина которых больше 3-х символов.

Статистика: