Москва: МЗ Пресс, 2006. - 352 с
Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г.
Предлагаемая вниманию читателя книга основана на курсе лекций, прочитанных на факультете вычислительной математики и кибернетики МГУ им. М.В. Ломоносова и на факультете управления и прикладной математики Московского физико-технического института в 1991-2002 гг. Авторы надеются, что издание книги восполнит существенный пробел в литературе на русском языке по разработке компиляторов. В книге представлены «классические» разделы теории разработки компиляторов: лексический и синтаксический анализ, организация памяти компилятора (таблицы символов) и периода исполнения (магазина), генерация кода. Рассматриваются такие средства автоматизации процесса разработки трансляторов, как LEX, YACC, СУПЕР, методы генерации оптимального кода. Сделана попытка на протяжении всего изложения провести единую «атрибутную» точку зрения на процесс разработки компилятора. В книге не затрагиваются чрезвычайно важные вопросы глобальной оптимизации и разработки компиляторов для машин с параллельной архитектурой. Авторы надеются восполнить эти пробелы в будущем.
Книга рассчитана как на студентов и аспирантов программистских специальностей, так и на профессионалов в области программирования.
Содержание
Введение 9
Место компилятора в программном обеспечении
Структура компилятора
Языки и их представление
Алфавиты, цепочки и языки
Представление языков
Грамматики
Формальное определение грамматики
Типы грамматик и их свойства
Машины Тьюринга
Неразрешимость проблемы останова
Класс рекурсивных множеств
Связь машин Тьюринга и грамматик типа 0
Линейно-ограниченные автоматы и их связь с контекстно-зависимыми грамматиками
Лексический анализ
Регулярные множества и выражения
Конечные автоматы
Алгоритмы построения конечных автоматов
Построение недетерминированного конечного автомата по регулярному выражению
Построение детерминированного конечного автомата по недетерминированному
Построение детерминированного конечного автомата по регулярному выражению
Построение детерминированного конечного автомата с минимальным числом состояний
Связь регулярных множеств, конечных автоматов и регулярных грамматик
Программирование лексического анализа
Конструктор лексических анализаторов LEX
Синтаксический анализ
Контекстно-свободные грамматики и автоматы с магазинной памятью
Преобразования КС-грамматик
Алгоритм Кока-Янгера-Касами
Предсказывающий разбор сверху-вниз
Алгоритм разбора сверху-вниз
Функции FIRST и FOLLOW
Конструирование таблицы предсказывающего анализатора
LL(1)-грамматики
LL(k)-грамматики
Следствия определения LL(k)-грамматики
Удаление левой рекурсии
Левая факторизация
Рекурсивный спуск
Восстановление процесса анализа после синтаксических ошибок
Разбор снизу-вверх типа сдвиг-свёртка
Основа
LR(1)-aнaлизaтopы
Конструирование LR(1)-таблицы
LR(1)-грамматики
Восстановление процесса анализа после синтаксических ошибок
Варианты LR-анализаторов
Элементы теории перевода
Преобразователи с магазинной памятью
Синтаксически управляемый перевод
Схемы синтаксически управляемого перевода
Обобщённые схемы синтаксически управляемого перевода
Атрибутные грамматики
Определение атрибутных грамматик
Классы атрибутных грамматик и их реализация
Язык описания атрибутных грамматик
Проверка контекстных условий
Описание областей видимости и блочной структуры
Занесение в среду и поиск объектов
Организация таблиц символов
Таблицы идентификаторов
Таблицы расстановки
Таблицы расстановки со списками
Функции расстановки
Таблицы на деревьях
Реализация блочной структуры
Сравнение методов реализации таблиц
Промежуточное представление программы
Представление в виде ориентированного графа
Трёхадресный код
Линеаризованные представления
Виртуальная машина Java
Организация памяти
Набор команд виртуальной машины
Организация информации в генераторе кода
Уровень промежуточного представления .
Генерация кода
Модель машины
Динамическая организация памяти
Организация магазина со статической цепочкой
Организация магазина с дисплеем
Назначение адресов
Трансляция переменных
Трансляция целых выражений
Трансляция арифметических выражений
Трансляция логических выражений
Выделение общих подвыражений
Трансляция объектно-ориентированных свойств языков программирования
Виртуальные базовые классы
Множественное наследование
Единичное наследование и виртуальные функции
Множественное наследование и виртуальные функции
Виртуальные базовые классы с виртуальными функциями
Генерация оптимального кода методами синтаксического анализа
Сопоставление образцов
Синтаксический анализ для Т-грамматик
Выбор дерева вывода наименьшей стоимости
Атрибутная схема для алгоритма сопоставления образцов
Системы автоматизации построения трансляторов
Система СУПЕР
Система YACC
Семантика контекстно-свободных языков
Формальные свойства
Проверка на зацикленность
Простой язык программирования
Атрибутные грамматики
Определение атрибутных грамматик
Атрибутированное дерево разбора
Незацикленные атрибутные грамматики
Вычислительные последовательности и корректность. Определение визита
Чистые многовизитные грамматики
Абсолютно незацикленные атрибутные грамматики
Простые многовизитные атрибутные грамматики
Одновизитные атрибутные грамматики
Многопроходные грамматики
Задачи по разделам книги
Языки и их представление
Алфавиты, цепочки и языки
Представление языков
Грамматики
Лексический анализ
Регулярные множества и выражения
Конечные автоматы
Алгоритмы построения конечных автоматов
Регулярные множества и их представления
Алгебраические свойства регулярных множеств. Лемма о разрастании
Синтаксический анализ
КС-грамматики и МП-автоматы
Алгебраические свойства КС-языков.
Лемма о разрастании
Преобразования КС-грамматик
Предсказывающий разбор сверху-вниз
Разбор снизу-вверх типа сдвиг-свертка
Элементы теории перевода
Атрибутные грамматики
Генерация кода
Трансляция арифметических выражений
Трансляция логических выражений
Генерация оптимального кода методами синтаксического анализа
Литература
Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г.
Предлагаемая вниманию читателя книга основана на курсе лекций, прочитанных на факультете вычислительной математики и кибернетики МГУ им. М.В. Ломоносова и на факультете управления и прикладной математики Московского физико-технического института в 1991-2002 гг. Авторы надеются, что издание книги восполнит существенный пробел в литературе на русском языке по разработке компиляторов. В книге представлены «классические» разделы теории разработки компиляторов: лексический и синтаксический анализ, организация памяти компилятора (таблицы символов) и периода исполнения (магазина), генерация кода. Рассматриваются такие средства автоматизации процесса разработки трансляторов, как LEX, YACC, СУПЕР, методы генерации оптимального кода. Сделана попытка на протяжении всего изложения провести единую «атрибутную» точку зрения на процесс разработки компилятора. В книге не затрагиваются чрезвычайно важные вопросы глобальной оптимизации и разработки компиляторов для машин с параллельной архитектурой. Авторы надеются восполнить эти пробелы в будущем.
Книга рассчитана как на студентов и аспирантов программистских специальностей, так и на профессионалов в области программирования.
Содержание
Введение 9
Место компилятора в программном обеспечении
Структура компилятора
Языки и их представление
Алфавиты, цепочки и языки
Представление языков
Грамматики
Формальное определение грамматики
Типы грамматик и их свойства
Машины Тьюринга
Неразрешимость проблемы останова
Класс рекурсивных множеств
Связь машин Тьюринга и грамматик типа 0
Линейно-ограниченные автоматы и их связь с контекстно-зависимыми грамматиками
Лексический анализ
Регулярные множества и выражения
Конечные автоматы
Алгоритмы построения конечных автоматов
Построение недетерминированного конечного автомата по регулярному выражению
Построение детерминированного конечного автомата по недетерминированному
Построение детерминированного конечного автомата по регулярному выражению
Построение детерминированного конечного автомата с минимальным числом состояний
Связь регулярных множеств, конечных автоматов и регулярных грамматик
Программирование лексического анализа
Конструктор лексических анализаторов LEX
Синтаксический анализ
Контекстно-свободные грамматики и автоматы с магазинной памятью
Преобразования КС-грамматик
Алгоритм Кока-Янгера-Касами
Предсказывающий разбор сверху-вниз
Алгоритм разбора сверху-вниз
Функции FIRST и FOLLOW
Конструирование таблицы предсказывающего анализатора
LL(1)-грамматики
LL(k)-грамматики
Следствия определения LL(k)-грамматики
Удаление левой рекурсии
Левая факторизация
Рекурсивный спуск
Восстановление процесса анализа после синтаксических ошибок
Разбор снизу-вверх типа сдвиг-свёртка
Основа
LR(1)-aнaлизaтopы
Конструирование LR(1)-таблицы
LR(1)-грамматики
Восстановление процесса анализа после синтаксических ошибок
Варианты LR-анализаторов
Элементы теории перевода
Преобразователи с магазинной памятью
Синтаксически управляемый перевод
Схемы синтаксически управляемого перевода
Обобщённые схемы синтаксически управляемого перевода
Атрибутные грамматики
Определение атрибутных грамматик
Классы атрибутных грамматик и их реализация
Язык описания атрибутных грамматик
Проверка контекстных условий
Описание областей видимости и блочной структуры
Занесение в среду и поиск объектов
Организация таблиц символов
Таблицы идентификаторов
Таблицы расстановки
Таблицы расстановки со списками
Функции расстановки
Таблицы на деревьях
Реализация блочной структуры
Сравнение методов реализации таблиц
Промежуточное представление программы
Представление в виде ориентированного графа
Трёхадресный код
Линеаризованные представления
Виртуальная машина Java
Организация памяти
Набор команд виртуальной машины
Организация информации в генераторе кода
Уровень промежуточного представления .
Генерация кода
Модель машины
Динамическая организация памяти
Организация магазина со статической цепочкой
Организация магазина с дисплеем
Назначение адресов
Трансляция переменных
Трансляция целых выражений
Трансляция арифметических выражений
Трансляция логических выражений
Выделение общих подвыражений
Трансляция объектно-ориентированных свойств языков программирования
Виртуальные базовые классы
Множественное наследование
Единичное наследование и виртуальные функции
Множественное наследование и виртуальные функции
Виртуальные базовые классы с виртуальными функциями
Генерация оптимального кода методами синтаксического анализа
Сопоставление образцов
Синтаксический анализ для Т-грамматик
Выбор дерева вывода наименьшей стоимости
Атрибутная схема для алгоритма сопоставления образцов
Системы автоматизации построения трансляторов
Система СУПЕР
Система YACC
Семантика контекстно-свободных языков
Формальные свойства
Проверка на зацикленность
Простой язык программирования
Атрибутные грамматики
Определение атрибутных грамматик
Атрибутированное дерево разбора
Незацикленные атрибутные грамматики
Вычислительные последовательности и корректность. Определение визита
Чистые многовизитные грамматики
Абсолютно незацикленные атрибутные грамматики
Простые многовизитные атрибутные грамматики
Одновизитные атрибутные грамматики
Многопроходные грамматики
Задачи по разделам книги
Языки и их представление
Алфавиты, цепочки и языки
Представление языков
Грамматики
Лексический анализ
Регулярные множества и выражения
Конечные автоматы
Алгоритмы построения конечных автоматов
Регулярные множества и их представления
Алгебраические свойства регулярных множеств. Лемма о разрастании
Синтаксический анализ
КС-грамматики и МП-автоматы
Алгебраические свойства КС-языков.
Лемма о разрастании
Преобразования КС-грамматик
Предсказывающий разбор сверху-вниз
Разбор снизу-вверх типа сдвиг-свертка
Элементы теории перевода
Атрибутные грамматики
Генерация кода
Трансляция арифметических выражений
Трансляция логических выражений
Генерация оптимального кода методами синтаксического анализа
Литература