В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов

Основы конструирования компиляторовВ.А.Серебряков, М.П.Галочкин2ПредисловиеПредлагаемая вниманию читателя книга основана на курсе лекций,прочитанных на факультете вычислительной математики и кибернетики Московского государственного университета и факультете управления и прикладной математики Московского физико-технического института в 1991-1999 гг. Авторы надеются, что издание книги восполнит существенный пробел в литературе на русском языке по разработкекомпиляторов.Содержание книги представляет собой “классические” разделы предмета: лексический и синтаксический анализ, организация памяти компилятора (таблицы символов) и периода исполнения (магазина), генерация кода.

Рассматриваются некоторые средства автоматизации процесса разработки трансляторов, такие как LEX, YACC, СУПЕР, методы генерации оптимального кода. Сделана попытка на протяжении всего изложения провести единую “атрибутную” точку зрения на процессразработки компилятора. В книге не затрагиваются чрезвычайно важные вопросы глобальной оптимизации и разработки компиляторов длямашин с параллельной архитектурой. Авторы надеются восполнить этипробелы в будущем.Книга будет полезной как студентам и аспирантам программистскихспециальностей, так и профессионалам в этих областях.Авторы с благодарностью примут все конструктивные замечания посодержанию книги.В.А.Серебряков, serebr@ccas.ruМ.П.Галочкин, galoch@ccas.ruОглавление1 Введение1.1 Место компилятора в программномобеспечении . .

. . . . . . . . . . . . . . . . . . . . . . . .1.2 Структура компилятора . . . . . . . . . . . . . . . . . . .2 Языки и их представление2.1 Алфавиты, цепочки и языки . . . . . . . . .2.2 Представление языков . . . . . . . . . . . .2.3 Грамматики . . . . . . . . . . . . . . . . .

.2.3.1 Формальное определение грамматики2.3.2 Типы грамматик и их свойства . . . .........................................7781313151717183 Лексический анализ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 . . . . . . .212325294 Синтаксический анализ4.1 КС-грамматики и МП-автоматы . . . .4.2 Преобразования КС-грамматик . .

. .4.3 Предсказывающий разбор сверху-вниз4.3.1 Алгоритм разбора сверху-вниз .49495456563............................................29313236384144ОГЛАВЛЕНИЕ44.3.2 Функции F IRST и F OLLOW . . . . . . . . . . . . .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-анализаторов . . . . . . . . . . . . .59616263656667676769737679795 Элементы теории перевода5.1 Преобразователи с магазинной памятью .

. . . . . . . . .5.2 Синтаксически управляемый перевод . . . . . . . . . . .5.2.1 Схемы синтаксически управляемого перевода . . .5.2.2 Обобщенные схемы синтаксически управляемого перевода . . . . . . . . . . . . . . . . . . . . . . . . .5.3 Атрибутные грамматики . . . . . . . .

. . . . . . . . . . .5.3.1 Определение атрибутных грамматик . . . . . . . .5.3.2 Классы атрибутных грамматик и их реализация . .5.3.3 Язык описания атрибутных грамматик . . . . . . .8181828385878792946 Проверка контекстных условий6.1 Описание областей видимости и блочной структуры . . . .6.2 Занесение в среду и поиск объектов . . . . . . . . . . . . .99991017 Организация таблиц символов7.1 Таблицы идентификаторов . .

. . . . .7.2 Таблицы расстановки . . . . . . . . . .7.3 Таблицы расстановки со списками . .7.4 Функции расстановки . . . . . . . . .7.5 Таблицы на деревьях . . . . . . . . . .7.6 Реализация блочной структуры . . . .7.7 Сравнение методов реализации таблиц.................................................1091091111131151161201218 Промежуточное представление программы8.1 Представление в виде ориентированного графа8.2 Трехадресный код . .

. . . . . . . . . . . . . . .8.3 Линеаризованные представления . . . . . . . .8.4 Виртуальная машина Java . . . . . . . . . . . .8.4.1 Организация памяти . . . . . . . . . . ...............................123123124128130131............................ОГЛАВЛЕНИЕ8.4.2 Набор команд виртуальной машины .

. . . . . . . .8.5 Организация информациив генераторе кода . . . . . . . . . . . . . . . . . . . . . . .8.6 Уровень промежуточного представления . . . . . . . . . .51311341349 Генерация кода1359.1 Модель машины . . . . . . . . . . . . . . . . . . . . . . . . 1359.2 Динамическая организация памяти . . . . . . . . .

. . . . 1389.2.1 Организация магазина со статической цепочкой . . 1399.2.2 Организация магазина с дисплеем . . . . . . . . . . 1439.3 Назначение адресов . . . . . . . . . . . . . . . . . . . . . . 1449.4 Трансляция переменных . . . . . . . . .

. . . . . . . . . . 1469.5 Трансляция целых выражений . . . . . . . . . . . . . . . 1489.6 Трансляция арифметических выражений . . . . . . . . . 1499.7 Трансляция логических выражений . . . . . . . . . . . . 1589.8 Выделение общих подвыражений . . . . . . . . . . . . . . 1659.9 Генерация оптимального кода методами синтаксическогоанализа .

. . . . . . . . . . . . . . . . . . . . . . . . . . . 1699.9.1 Сопоставление образцов . . . . . . . . . . . . . . . 1699.9.2 Синтаксический анализ для T-грамматик . . . . . . 1729.9.3 Выбор дерева вывода наименьшей стоимости . . . . 1789.9.4 Атрибутная схема для алгоритма сопоставления образцов . . . . . . . . . . . . . . . . .

. . . . . . . . 18010 Системы автоматизации построения трансляторов18510.1 Система СУПЕР . . . . . . . . . . . . . . . . . . . . . . . . 18510.2 Система Yacc . . . . . . . . . . . . . . . . . . . . . . . . . 1876ОГЛАВЛЕНИЕГлава 1Введение1.1Место компилятора в программномобеспеченииКомпиляторы составляют существенную часть программного обеспечения ЭВМ.

Это связано с тем, что языки высокого уровня стали основнымсредством разработки программ. Только очень незначительная часть программного обеспечения, требующая особой эффективности, программируется с помощью ассемблеров. В настоящее время распространено довольно много языков программирования.

Наряду с традиционными языками, такими, как Фортран, широкое распространение получили такназываемые “универсальные” языки (Паскаль, Си, Модула-2, Ада и другие), а также некоторые специализированные (например, язык обработки списочных структур Лисп). Кроме того, большое распространениеполучили языки, связанные с узкими предметными областями, такие,как входные языки пакетов прикладных программ.Для некоторых языков имеется довольно много реализаций.

Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа IBM PC нарынке десятки.С другой стороны, постоянно растущая потребность в новых компиляторах связана с бурным развитием архитектур ЭВМ. Это развитие идетпо различным направлениям. Совершенствуются старые архитектурыкак в концептуальном отношении, так и по отдельным, конкретным линиям. Это можно проиллюстрировать на примере микропроцессора Intel80X86. Последовательные версии этого микропроцессора 8086, 80186,80286, 80386, 80486, 80586 отличаются не только техническими характеристиками, но и, что более важно, новыми возможностями и, значит,изменением (расширением) системы команд. Естественно, это требуетновых компиляторов (или модификации старых).

То же можно сказатьо микропроцессорах Motorola 68010, 68020, 68030, 68040.В рамках традиционных последовательных машин возникает боль7ГЛАВА 1. ВВЕДЕНИЕ8шое число различных направлений архитектур. Примерами могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как Intel, Motorola,Sun, начинают переходить на выпуск машин с RISC-архитектурами.