|
|
 |
|
|
|
Книги: [Классика] [Базы данных] [Internet/WWW] [Сети] [Программирование] [UNIX] [Windows] [Безопасность] [Графика] [Software Engineering] [ERP-системы] [Hardware]
Содержание
От редактора
Предисловие
Использование данной книги
Благодарности
ГЛАВА 1. Введение в компиляцию
1.1. Компиляторы
Модель анализа-синтеза компиляции
Контекст компилятора
1.2. Анализ исходной программы
Лексический анализ
Синтаксический анализ
Семантический анализ
Анализ в программах форматирования текста
1.3. Фазы компилятора
Управление таблицей символов
Обнаружение ошибок и сообщение о них
Фазы анализа
Генерация промежуточного кода
Оптимизация кода
Генерация кода
1.4. Родственники компилятора
Препроцессоры
Ассемблеры
Двухпроходный ассемблер
Загрузчики и редакторы связей
1.5. Группировка фаз
Предварительная и заключительная стадии
Проходы
Уменьшение количества проходов
1.6. Инструментарий для создания компиляторов
Библиографические примечания
ГЛАВА 2. Простой однопроходный компилятор
2.1. Обзор
2.2. Определение синтаксиса
Деревья разбора
Неоднозначность
Ассоциативность операторов
Приоритет операторов
2.3. Синтаксически управляемая трансляция
Постфиксная запись
Синтаксически управляемые определения
Синтезируемые атрибуты
Рекурсивный обход дерева
Схемы трансляции
Вывод результатов трансляции
2.4. Разбор
Нисходящий анализ
Предиктивный анализ
Использование е-продукций
Создание предиктивного анализатора
Левая рекурсия
2.5. Транслятор для простых выражений
Абстрактный и конкретный синтаксис
Адаптация схемы трансляции
Процедуры для нетерминалов expr, term и rest
Оптимизация транслятора
Полная программа
2.6. Лексический анализ
Удаление пробелов и комментариев
Константы
Распознавание идентификаторов и ключевых слов
Интерфейс к лексическому анализатору
Лексический анализатор
2.7. Использование таблиц символов
Интерфейс таблицы символов
Обработка зарезервированных ключевых слов
Реализация таблицы символов
2.8. Абстрактная стековая машина
Арифметические инструкции l-значения и r-значения
Работа со стеком
Трансляция выражений
Управление выполнением
Трансляция инструкций
Вывод результатов трансляции
2.9. Сборка транслятора
Описание транслятора
Модуль лексического анализа lexer. с
Модуль синтаксического анализатора parser. с
Модуль вывода emitter. с
Модули работы с таблицей символов symbol. с и init. с
Модуль обработки ошибок error. с
Создание компилятора
Листинг
Упражнения
Программные упражнения
Библиографические примечания
ГЛАВА 3. Лексический анализ
3.1. Роль лексических анализаторов
Задачи лексического анализа
Токены, шаблоны, лексемы
Атрибуты токенов
Лексические ошибки
3.2. Буферизация ввода
Пары буферов
Ограничители
3.3. Определение токенов
Строки и языки
Операции над языками
Регулярные выражения
Регулярные определения
Сокращения
Нерегулярные множества
3.4. Распознавание токенов
Диаграммы переходов
Реализация диаграммы переходов
3.5. Язык спецификации лексических анализаторов
Спецификации Lex
Прогностический оператор
3.6. Конечные автоматы
Недетерминированные конечные автоматы
Детерминированный конечный автомат
Преобразование НКА в ДКА
3.7. От регулярного выражения к НКА
Построение НКА по регулярному выражению
Двустековое моделирование НКА
Скорость работы
3.8. Построение генератора лексических анализаторов
Поиск по шаблону на основе НКА
ДКА для лексического анализа
Реализация прогностического оператора
3.9. Оптимизация поиска соответствия шаблону на базе ДКА
Важные состояния в НКА
От регулярного выражения к ДКА
Минимизация количества состояний ДКА
Минимизация состояний в лексических анализаторах
Методы сжатия таблиц
Упражнения
Программные упражнения
Библиографические примечания
ГЛАВА 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
Упражнения
Библиографические примечания
ГЛАВА 5. Синтаксически управляемая трансляция
5.1. Синтаксически управляемые определения
Вид синтаксически управляемого определения
Синтезируемые атрибуты
Наследуемые атрибуты
Графы зависимости
Порядок выполнения
5.2. Построение синтаксических деревьев
Синтаксические деревья
Построение синтаксических деревьев для выражений
Синтаксически управляемое определение для построения
синтаксических деревьев
Направленные ациклические графы выражений
5.3. Восходящее выполнение S-атрибутных определений
Синтезируемые атрибуты в стеке синтаксического анализатора
5.4. L-атрибутные определения L-атрибутные определения
Схемы трансляции
5.5. Нисходящая трансляция
Устранение левой рекурсии из схемы трансляции
Разработка предиктивного транслятора
5.6. Восходящее вычисление наследуемых атрибутов
Удаление внедренных действий из схемы трансляции
Наследование атрибутов в стеке синтаксического анализатора
Моделирование вычисления наследуемых атрибутов
Замена наследуемых атрибутов синтезируемыми
Сложное синтаксически управляемое определение
5.7. Рекурсивные вычислители
Обход слева направо
Другие обходы
5.8. Память для значений атрибутов во время компиляции
Назначение памяти атрибутам во время компиляции
Устранение копий
5.9. Назначение памяти в процессе создания компилятора
Вычисление времени жизни по грамматике
Неперекрывающиеся времена жизни
5.10. Анализ синтаксически управляемых определений
Рекурсивное вычисление атрибутов
Строго нецикличные синтаксически управляемые определения
Проверка цикличности
Упражнения
Библиографические примечания
ГЛАВА 6. Проверка типов
6.1. Системы типов
Выражения типов
Системы типов
Статическая и динамическая проверка типов
Восстановление после ошибки
6.2. Спецификация простой программы проверки типов
Простой язык
Проверка типов выражений
Проверка типов инструкций
Проверка типов функций
6.3. Эквивалентность выражений типа
Структурная эквивалентность выражений типа
Имена выражений типа
Циклы в представлениях типов
6.4. Преобразования типов
Неявное преобразование типов
6.5. Перегрузка функций и операторов
Множество возможных типов подвыражения
Сужение множества возможных типов
6.6. Полиморфные функции
Почему используются полиморфные функции
Переменные типа
Язык с полиморфными функциями
Подстановки, примеры и унификация
Проверка полиморфных функций
6.7. Алгоритм унификации
Упражнения
Библиографические примечания
ГЛАВА 7. Среды времени исполнения
7.1. Вопросы исходного языка
Процедуры
Деревья активации
Стеки управления
Область видимости объявления
Организация памяти и связывание имен
7.2. Организация памяти
Классификация памяти времени выполнения
Записи активации
Размещение локальных данных в процессе компиляции
7.3. Стратегии выделения памяти
Статическое распределение памяти
Стековое распределение памяти
Висячие ссылки
Распределение памяти в куче
7.4. Доступ к нелокальным именам
Блоки
Лексическая область видимости без вложенных процедур
Лексическая область видимости при наличии вложенных процедур
Дисплеи
Динамическая область видимости
7.5. Передача параметров
Передача по значению
Передача по ссылке
Копирование-восстановление
Передача по имени
7.6. Таблицы символов
Записи таблицы символов
Символы имени
Информация о выделенной памяти
Использование списков для представления таблицы символов
Хеш-таблицы
Представление информации об области видимости
7.7. Возможности языков по динамическому выделению памяти
Мусор
Висячие ссылки
7.8. Технологии динамического распределения памяти
Явное выделение блоков фиксированного размера
Явное выделение блоков переменного размера
Неявное освобождение
7.9. Распределение памяти в Fortran
Данные в областях COMMON
Простой алгоритм эквивалентности
Алгоритм эквивалентности для языка программирования Fortran
Отображение областей данных
Упражнения
Библиографические примечания
ГЛАВА 8. Генерация промежуточного кода
8.1. Языки промежуточных представлений
Графическое представление
Трехадресный код
Типы трехадресных инструкций
Синтаксически управляемая трансляция в трехадресный код
Реализация трехадресных инструкций
Сравнение представлений: использование косвенного обращения
8.2. Объявления
Объявления в процедуре
Отслеживание информации об области видимости
Имена полей в записях
8.3. Инструкции присвоения
Имена в таблице символов
Повторное использование временных имен
Адресация элементов массива
Схема трансляции для адресации элементов массива
Преобразования типов в присвоениях
Доступ к полям записей
8.4. Логические выражения
Методы трансляции логических выражений
Числовое представление
Сокращенные вычисления
Инструкции потока управления
Трансляция логических выражений с помощью потока управления
Смешанные логические выражения
8.5. Инструкции case
Синтаксически управляемая трансляция инструкции case
8.6. Технология обратных поправок
Логические выражения
Инструкции потока управления
Схема реализации трансляции
Метки и безусловные переходы
8.7. Вызовы процедур
Вызывающие последовательности
Простой пример
Упражнения
Библиографические примечания
ГЛАВА 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. Генераторы генераторов кода
Генерация кода путем преобразования дерева
Проверка соответствия шаблону путем синтаксического анализа
Программы семантической проверки
Упражнения
Библиографические примечания
ГЛАВА 10. Оптимизация кода
10.1. Введение
Критерии для преобразований, улучшающих код
Повышение производительности
Организация оптимизирующего компилятора
10.2. Основные источники оптимизации
Преобразования, сохраняющие функции
Общие подвыражения
Распространение копий
Удаление бесполезного кода
Оптимизации циклов
Перемещение кода
Переменные индукции и снижение стоимости
10.3. Оптимизация базовых блоков
Использование алгебраических тождеств
10.4. Циклы в графах потока
Доминаторы
Естественные циклы
Внутренние циклы
Предзаголовки
Приводимые графы потоков
10.5. Введение в глобальный анализ потоков данных
Точки и пути
Достигающие определения
Анализ потока данных структурированной программы
Консервативная оценка информации потока данных
Вычисление in и out
Работа с циклами
Представление множеств
Локальные достигающие определения
Цепочки определений использований
Порядок вычислений
Общий поток управления
10.6. Итеративное решение уравнений потока данных
Итеративный алгоритм для достигающих определений
Доступные выражения
Анализ активных переменных
Цепочки использований определений
10.7. Преобразования, улучшающие код
Устранение глобальных общих подвыражений
Распространение копирований
Поиск вычислений, инвариантных относительно цикла
Выполнение перемещения кода
Альтернативные стратегии перемещения кода
Поддержание информации о потоке данных после перемещения кода
Устранение переменных индукции
Переменные индукции и выражения, инвариантные относительно цикла
10.8. Работа с альтернативными именами
Простой язык указателей
Воздействие присвоений указателей
Использование информации об указателях
Анализ межпроцедурного потока данных
Модель кода с вызовами процедур
Вычисление псевдонимов
Анализ потока данных при наличии вызовов процедур
Использование информации об изменениях
10.9. Анализ потока данных структурированных графов потока
Поиск вглубь
Дуги представления графа потока вглубь
Глубина графа потока
Интервалы
Разбиение на интервалы
Графы интервалов
Разделение узлов
Т1-Т2-анализ
Области
Поиск доминаторов
10.10. Эффективные алгоритмы потоков данных
Упорядочение вглубь в итеративных алгоритмах
Анализ потока данных, основанный на структуре
Некоторые ускорения структурного алгоритма
Обработка неприводимых графов потока
10.11. Средства для анализа потока данных
Схема анализа потока данных
Аксиомы схем анализа потока данных
Монотонность и дистрибутивность
Решения типа "слияние всех путей" в задачах о потоках данных
Консервативные решения задач о потоках
Итеративный алгоритм для обобщенных схем
Инструмент анализа потока данных
Свойства алгоритма 10.18
Сходимость алгоритма 10.18
Исправление инициализации
10.12. Оценка типов
Работа с бесконечными множествами типов
Простая система типов
Прямая схема
Обратная схема
10.13. Символьная отладка оптимизированного кода
Отслеживание значений переменных в базовых блоках
Влияние глобальной оптимизации
Устранение переменных индукции
Устранение глобальных общих подвыражений
Перемещение кода
Упражнения
Библиографические примечания
ГЛАВА 11. Создание компилятора
11.1. Планирование компилятора
Вопросы исходного языка
Вопросы целевого языка
Критерии производительности
11.2. Подходы к разработке компилятора
Раскрутка
11.3. Среда разработки компилятора
11.4. Тестирование и сопровождение
ГЛАВА 12. Некоторые компиляторы
12.1. Препроцессор математических формул EQN
12.2. Компиляторы Pascal
12.3. Компиляторы С
12.4. Компиляторы Fortran H
Оптимизация кода в Fortran H
Алгебраическая оптимизация
Оптимизация регистров
12.5. Компилятор Bliss/11
12.6. Оптимизирующий компилятор Modula-2
ПРИЛОЖЕНИЕ А. Программный проект
A.1. Введение
А.2. Структура программы
А.З. Синтаксис подмножества Pascal
А.4. Лексические соглашения
А.5. Предлагаемые упражнения
А.6. Эволюция интерпретатора
А.7. Расширения
ПРИЛОЖЕНИЕ Б. Спецификации языков программирования
Б.1. Язык программирования C++
Б.2. Язык программирования С#
БИБЛИОГРАФИЯ
Предметный указатель
Начало
Оглавление
Предисловие
От редактора
Структура книги
Об авторах
Заказать книгу в магазине "Мистраль"
|
|
|
 |
|
|
|
| Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее... |
|
🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях
Виртуальные VPS серверы в РФ и ЕС
