Лекции по конструированию компиляторов. В.А. Серебряков (1134688)
Текст из файла
В.А.СеребряковЛекции поконструированию компиляторовМосква1997ПредисловиеПредлагаемая вниманию читателя книга основана на курсе лекций,прочитанных автором на факультете вычислительной математики икибернетики Московского государственного университета в 1991-1993 гг.Автор надеется, что издание книги восполнит существенный пробел влитературе на руссом языке по разработке компиляторов.Содержание книги представляет собой "классические" разделыпредмета: лексический и синтаксический анализ, организация памятитранслятора (таблицы символов) и периода исполнения (магазина),генерация кода, в частности генерация арифметических и логическихвыражений.
Рассматриваются некоторые средства автоматизации процессаразработки трансляторов, такие как LEX, YACC, Супер, методы генерацииоптимального кода. Сделана попытка на протяжении всего изложенияпровести единую "атрибутную" точку зрения на процесс разработкикомпилятора. В книге не затрагиваются чрезвычайно важные вопросыглобальной оптимизации и разработки компиляторов для машин спараллельной архитектурой. Автор надеется восполнить эти пробелы вбудущем.Книга будет полезной как студентам и аспирантам программистскихспециальностей, так и профессионалам в этих областях.11Глава 1. Введение1.1.
Место компилятора в программном обеспечении1.2. Структура компилятораГлава 2. Лексический анализ2.1. Регулярные множества и регулярные выражения2.2. Конечные автоматы2.3. Построение детерминированного конечногоавтомата по недетерминированному2.4. Построение детерминированного конечногоавтомата по регулярному выражению2.5. Построение детерминированного конечногоавтомата с минимальным числом состояний2.6. Программирование лексических анализаторов2.7. Конструктор лексических анализаторов LEXГлава 3. Синтаксический анализ3.1. Основные понятия и определения3.2.
Таблично-управляемый предсказывающий разбор3.2.1. Алгоритм разбора сверху-вниз3.2.2. Множества FIRST и FOLLOW3.2.3. Конструирование таблицпредсказывающего анализатора3.2.4. LL(1)-грамматики3.2.5. Удаление левой рекурсии3.2.6. Левая факторизация3.2.7. Рекурсивный спуск3.2.8. Диаграммы переходов для рекурсивного спуска3.2.9.
Восстановление после синтаксических ошибок3.3. Разбор снизу-вверх типа сдвиг-свертка3.3.1. Основа3.3.2. LR(k)-анализаторы3.3.3. LR грамматики3.3.4. Конфликты разбора типа сдвиг-свертка3.3.5. Восстановление после синтаксических ошибокГлава 4. Элементы теории перевода4.1. Преобразователи с магазинной памятью4.2. Синтаксически управляемый перевод4.3. Атрибутные грамматики4.3.1. Определение атрибутных грамматик4.3.2.
Атрибутированное дерево разбора4.3.3. Язык описания атрибутных грамматик4.3.4. Классы атрибутных грамматик и их реализацияГлава 5. Контекстные условия языков программирования5.1. Описание областей видимости и блочной структуры5.2. Структура среды Модулы-25.3. Занесение в среду и поиск объектов126671113141618212327323234343840414244454649505052576364656566707071727577777881Глава 6. Организация таблиц символов компилятора6.1. Таблицы идентификаторов и таблицы символов6.2. Таблицы идентификаторов6.3. Таблицы символов и таблицы расстановки6.4.
Функции расстановки6.5. Таблицы на деревьях6.6. Реализация блочной структуры6.7. Сравнение различных методов реализации таблицГлава 7. Промежуточные представления программы7.1. Представление в виде ориентированного графа7.2. Трехадресный код7.3. Линеаризованные представления7.4. Виртуальная машина Java7.5. Организация информации в генераторе кода7.6.
Уровень промежуточного представленияГлава 8. Генерация кода8.1. Модель машины8.2. Динамическая организация памяти8.2.1. Организация магазина со статической цепочкой8.2.1. Организация магазина с дисплеем8.3. Назначение адресов8.4. Трансляция переменных8.5. Трансляция целых выражений8.6. Распределение регистров при вычисленииарифметических выражений8.7. Трансляция логических выражений8.8.
Выделение общих подвыражений8.9. Генерация оптимального кода методамисинтаксического анализа8.9.1. Сопоставление образцов8.9.2. Синтаксический анализ для Т-грамматик8.9.3. Выбор дерева вывода наименьшей стоимостиЛитература13898990939496100100102102102107109113115116116119120124126128134136145153157157160168171Глава 1.
Введение1.1. Место компилятора в программном обеспеченииКомпиляторы составляют существенную часть программного обеспеченияЭВМ. Это связано с тем, что языки высокого уровня стали основнымсредством разработки программ. Только очень незначительная частьпрограммного обеспечения, требующая особой эффективности,программируется с помощью ассемблеров. В настоящее времяраспространено довольно много языков программирования. Наряду страдиционными языками, такими, как Фортран, широкое распространениеполучили так называемые "универсальные языки" (Паскаль, Си, Модула-2,Ада и другие), а также некоторые специализированные (например, языкобработки списочных структур Лисп). Кроме того, большоераспространение получили языки, связанные с узкими предметнымиобластями, такие, как входные языки пакетов прикладных программ.Для некоторых языков имеется довольно много реализаций.Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа IBM/PCна рынке десятки.С другой стороны, постоянно растущая потребность в новыхкомпиляторах связана с бурным развитием архитектур ЭВМ.
Это развитиеидет по различным направлениям. Совершенствуются старые архитектурыкак в концептуальном отношении, так и по отдельным, конкретнымлиниям. Это можно проиллюстрировать на примере микропроцессораIntel-80X86. Последовательные версии этого микропроцессора 8086,80186, 80286, 80386, 80486, 80586 отличаются не только техническимихарактеристиками, но и, что более важно, новыми возможностями и,значит, изменением (расширением) системы команд. Естественно, этотребует новых компиляторов (или модификации старых). То же можносказать о микропроцессорах Motorola 68010, 68020, 68030, 68040.В рамках традиционных последовательных машин возникаетбольшое число различных направлений архитектур. Примерами могутслужить архитектуры CISC, RISC.
Такие ведущие фирмы, как Intel,Motorola, Sun, DEC, начинают переходить на выпуск машин с RISCархитектурами. Естественно, для каждой новой системы команд требуетсяполный набор новых компиляторов с распространенных языков.14Наконец, бурно развиваются различные параллельные архитектуры.Среди них отметим векторные, многопроцессорные, с широкимкомандным словом (вариантом которых являются суперскалярные ЭВМ).На рынке уже имеются десятки типов ЭВМ с параллельной архитектурой,начиная от супер-ЭВМ (Cray, CDC и другие), через рабочие станции(например, IBM/RS-6000) и кончая персональными (например, на основемикропроцессора I-860). Естественно, для каждой из машин создаютсяновые компиляторы для многих языков программирования.
Здесьнеобходимо также отметить, что новые архитектуры требуют разработкисовершенно новых подходов к созданию компиляторов, так что наряду ссобственно разработкой компиляторов ведется и большая научная работапо созданию новых методов трансляции.1.2. Структура компилятораОбобщенная структура компилятора и основные фазы компиляциипоказаны на рис. 1.1.На фазе лексического анализа (ЛА) входная программа,представляющая собой поток символов, разбивается на лексемы - слова всоответствии с определениями языка. Основным формализмом, лежащим воснове реализации лексических анализаторов, являются конечныеавтоматы и регулярные выражения.
Лексический анализатор можетработать в двух основных режимах: либо как подпрограмма, вызываемаясинтаксическим анализатором за очередной лексемой, либо как полныйпроход, результатом которого является файл лексем.В процессе выделения лексем ЛА может как самостоятельно строитьтаблицы имен и констант, так и выдавать значения для каждой лексемыпри очередном обращении к нему. В этом случае таблица имен строится впоследующих фазах (например, в процессе синтаксического анализа).15ЛексическийанализлексемДиагностикатаблицы имени константКонечныеавтоматыСинтаксическийанализДиагностикаДерево разбора+ таблицыимен иКонтекстносвободныеконстантграмматикиКонтекстныйанализПотокДиагностикаАтрибутированноеАтрибутныеграмматикисимволовдерево +таблицаГенерацияформапромежуточногопредставленияидр.)Промежуточная(префиксная, постфиксная,тройкиСУ-трансляцияОптимизацияПромежуточная формаПотоковый(ориентированный граф)анализГенерация кодаТаблицы решений,Объектныймодульдинамическое16программирование и дрРис.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
