Основы конструирования компиляторов

В.А.Серебряков, М.П.Галочкин

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

Содержание книги представляет собой «классические» разделы предмета: лексический и синтаксический анализ, организация памяти компилятора (таблицы символов) и периода исполнения (магазина), генерация кода. Рассматриваются некоторые средства автоматизации процесса разработки трансляторов, такие как LEX, YACC, СУПЕР, методы генерации оптимального кода. Сделана попытка на протяжении всего изложения провести единую «атрибутную» точку зрения на процесс разработки компилятора. В книге не затрагиваются чрезвычайно важные вопросы глобальной оптимизации и разработки компиляторов для машин с параллельной архитектурой. Авторы надеются восполнить эти пробелы в будущем.

Книга будет полезной как студентам и аспирантам программистских специальностей, так и профессионалам в этих областях.

Авторы с благодарностью примут все конструктивные замечания по содержанию книги.

В.А.Серебряков
М.П.Галочкин

Оглавление

1 Введение
1.1 Место компилятора в программном обеспечении
1.2 Структура компилятора
2 Языки и их представление
2.1 Алфавиты, цепочки и языки
2.2 Представление языков
2.3 Грамматики
2.3.1 Формальное определение грамматики
2.3.2 Типы грамматик и их свойства
3 Лексический анализ
3.1 Регулярные множества и выражения
3.2 Конечные автоматы
3.3 Алгоритмы построения конечных автоматов
3.3.1 Построение недетерминированного конечного автомата по регулярному выражению
3.3.2 Построение детерминированного конечного автомата по недетерминированному
3.3.3 Построение детерминированного конечного автомата по регулярному выражению
3.3.4 Построение детерминированного конечного автомата с минимальным числом состояний
3.4 Регулярные множества и их представления
3.5 Программирование лексического анализа
3.6 Конструктор лексических анализаторов LEX
4 Синтаксический анализ
4.1 КС-грамматики и МП-автоматы
4.2 Преобразования КС-грамматик
4.3 Предсказывающий разбор сверху-вниз
4.3.1 Алгоритм разбора сверху-вниз
4.3.2 Функции FIRST и FOLLOW
4.3.3 Конструирование таблицы предсказывающего анализатора
4.3.4 LL(1)-грамматики
4.3.5 Удаление левой рекурсии
4.3.6 Левая факторизация
4.3.7 Рекурсивный спуск
4.3.8 Восстановление после синтаксических ошибок
4.4 Разбор снизу-вверх типа сдвиг-свертка
4.4.1 Основа
4.4.2 LR(1)-анализаторы
4.4.3 Конструирование LR(1)-таблицы
4.4.4 LR(1)-грамматики
4.4.5 Восстановление после синтаксических ошибок
4.4.6 Варианты LR-анализаторов
5 Элементы теории перевода
5.1 Преобразователи с магазинной памятью
5.2 Синтаксически управляемый перевод
5.2.1 Схемы синтаксически управляемого перевода
5.2.2 Обобщенные схемы синтаксически управляемого перевода
5.3 Атрибутные грамматики
5.3.1 Определение атрибутных грамматик
5.3.2 Классы атрибутных грамматик и их реализация
5.3.3 Язык описания атрибутных грамматик
6 Проверка контекстных условий
6.1 Описание областей видимости и блочной структуры
6.2 Занесение в среду и поиск объектов
7 Организация таблиц символов
7.1 Таблицы идентификаторов
7.2 Таблицы расстановки
7.3 Таблицы расстановки со списками
7.4 Функции расстановки
7.5 Таблицы на деревьях
7.6 Реализация блочной структуры
7.7 Сравнение методов реализации таблиц
8 Промежуточное представление программы
8.1 Представление в виде ориентированного графа
8.2 Трехадресный код
8.3 Линеаризованные представления
8.4 Виртуальная машина Java
8.4.1 Организация памяти
8.4.2 Набор команд виртуальной машины
8.5 Организация информации в генераторе кода
8.6 Уровень промежуточного представления
9 Генерация кода
9.1 Модель машины
9.2 Динамическая организация памяти
9.2.1 Организация магазина со статической цепочкой
9.2.2 Организация магазина с дисплеем
9.3 Назначение адресов
9.4 Трансляция переменных
9.5 Трансляция целых выражений
9.6 Трансляция арифметических выражений
9.7 Трансляция логических выражений
9.8 Выделение общих подвыражений
9.9 Генерация оптимального кода методами синтаксического анализа
9.9.1 Сопоставление образцов
9.9.2 Синтаксический анализ для T-грамматик
9.9.3 Выбор дерева вывода наименьшей стоимости
9.9.4 Атрибутная схема для алгоритма сопоставления образцов
10 Системы автоматизации построения трансляторов
10.1 Система СУПЕР
10.2 Система Yacc