В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395)
Текст из файла
Основы конструирования компиляторовВ.А.Серебряков, М.П.Галочкин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-архитектурами. Естественно, для каждой новой системы команд требуется полный набор новых компиляторов с распространенных языков.Наконец, бурно развиваются различные параллельные архитектуры.Среди них отметим векторные, многопроцессорные, с широким командным словом (вариантом которых являются суперскалярные ЭВМ). Нарынке уже имеются десятки типов ЭВМ с параллельной архитектурой,начиная от супер-ЭВМ (Cray, CDC и другие), через рабочие станции (например, IBM RS/6000) и кончая персональными (например, на основемикропроцессора I-860). Естественно, для каждой из машин создаютсяновые компиляторы для многих языков программирования. Здесь необходимо также отметить, что новые архитектуры требуют разработки совершенно новых подходов к созданию компиляторов, так что наряду ссобственно разработкой компиляторов ведется и большая научная работа по созданию новых методов трансляции.1.2Структура компилятораОбобщенная структура компилятора и основные фазы компиляции показаны на рис.
1.1.На фазе лексического анализа входная программа, представляющаясобой поток литер, разбивается на лексемы – слова в соответствии с определениями языка. Основными формализмами, лежащим в основе реализации лексических анализаторов, являются конечные автоматы и регулярные выражения. Лексический анализатор может работать в двухосновных режимах: либо как подпрограмма, вызываемая синтаксическим анализатором для получения очередной лексемы, либо как полный проход, результатом которого является файл лексем.В процессе выделения лексем лексический анализатор может как самостоятельно строить таблицы объектов (идентификаторов, строк, чисел и т.д.), так и выдавать значения для каждой лексемы при очередномк нему обращении.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
