Лекции по конструированию компиляторов литература


Содержание

Лекции по конструированию компиляторов литература

Вы выбрали книгу «Лекции по конструированию компиляторов (Серебряков В. А.)». Вы можете совершенно бесплатно скачать эту книгу, но только для ознакомления и личного, не коммерческого использования. Ссылка на скачивание расположена ниже на странице.

Для начала скачивания выберите сервер и нажмите ссылку «скачать»

Все книги запакованы архиватором RAR. Чем распаковать читайте тут. Внутри архива Вы найдёте файл(ы) книги, как открыть и просмотреть файл книги читайте здесь.

Все права на книги принадлежат их авторам. В случае если мы нарушаем авторские права, свяжитесь с нами через контакты

Лекции по конструированию компиляторов литература

Скидка 25% на все тарифы хостинга по промокоду STDCITF

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

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

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

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

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

Diplom Consult.ru

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

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

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

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

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

Место компилятора в программном

2 Языки и их представление

Алфавиты, цепочки и языки . . . . . . . . . . . . . . . . .

2.3 Грамматики . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3.1 Формальное определение грамматики . . . . . . . . 17

2.3.2 Типы грамматик и их свойства . . . . . . . . . . . . 18

3 Лексический анализ

Регулярные множества и выражения . . . . . . . . . . . .

3.3 Алгоритмы построения конечных автоматов . . . . . . . . 29

3.3.1 Построение недетерминированного конечного автомата по регулярному выражению . . . . . . . . . . 29

3.3.2 Построение детерминированного конечного автомата по недетерминированному . . . . . . . . . 31

3.3.3 Построение детерминированного конечного автомата по регулярному выражению . . . . . . . . 32

3.3.4 Построение детерминированного конечного автомата с минимальным числом состояний . . . . 36

Регулярные множества и их представления . . . . . . . .

Конструктор лексических анализаторов LEX . . . . . . .

4 Синтаксический анализ

4.1 КС-грамматики и МП-автоматы . . . . . . . . . . . . . . . 49

4.2 Преобразования КС-грамматик . . . . . . . . . . . . . . . 54

4.3 Предсказывающий разбор сверху-вниз . . . . . . . . . . . 56

4.3.1 Алгоритм разбора сверху-вниз . . . . . . . . . . . . 56

Функции F IRST и F OLLOW . . . . . . . . . . . . . 59

4.3.3 Конструирование таблицы предсказывающего анализатора . . . . . . . . . . . . . . . . . . . . . . . . 61

4.3.4 LL(1)-грамматики . . . . . . . . . . . . . . . . . . . 62

Удаление левой рекурсии . . . . . . . . . . . . . . .

4.3.8 Восстановление после синтаксических ошибок . . .

4.4 Разбор снизу-вверх типа сдвиг-свертка . . . . . . . . . . .

4.4.1 Основа . . . . . . . . . . . . . . . . . . . . . . . . . 67

4.4.2 LR(1)-анализаторы . . . . . . . . . . . . . . . . . . 69

4.4.3 Конструирование LR(1)-таблицы . . . . . . . . . . 73

4.4.4 LR(1)-грамматики . . . . . . . . . . . . . . . . . . . 76

4.4.5 Восстановление после синтаксических ошибок . . . 79

5 Элементы теории перевода

Преобразователи с магазинной памятью . . . . . . . . . .

Синтаксически управляемый перевод . . . . . . . . . . .

Схемы синтаксически управляемого перевода . . .

5.2.2 Обобщенные схемы синтаксически управляемого пе-

Определение атрибутных грамматик . . . . . . . .

5.3.2 Классы атрибутных грамматик и их реализация . . 92

5.3.3 Язык описания атрибутных грамматик . . . . . . . 94

6 Проверка контекстных условий

6.1 Описание областей видимости и блочной структуры . . . . 99

6.2 Занесение в среду и поиск объектов . . . . . . . . . . . . . 101

7 Организация таблиц символов

7.1 Таблицы идентификаторов . . . . . . . . . . . . . . . . . . 109

7.2 Таблицы расстановки . . . . . . . . . . . . . . . . . . . . . 111

Таблицы расстановки со списками . . . . . . . . . . . . .

7.5 Таблицы на деревьях . . . . . . . . . . . . . . . . . . . . . 116

7.6 Реализация блочной структуры . . . . . . . . . . . . . . . 120

7.7 Сравнение методов реализации таблиц . . . . . . . . . . . 121

8 Промежуточное представление программы

8.1 Представление в виде ориентированного графа . . . . . .

8.2 Трехадресный код . . . . . . . . . . . . . . . . . . . . . . . 124

8.3 Линеаризованные представления . . . . . . . . . . . . . . 128

8.4 Виртуальная машина Java . . . . . . . . . . . . . . . . . . 130

8.4.1 Организация памяти . . . . . . . . . . . . . . . . . 131

8.4.2 Набор команд виртуальной машины . . . . . . . . . 131

8.5 Организация информации

8.6 Уровень промежуточного представления . . . . . . . . . .

9 Генерация кода

9.1 Модель машины . . . . . . . . . . . . . . . . . . . . . . . . 135

9.2 Динамическая организация памяти . . . . . . . . . . . . . 138

9.2.1 Организация магазина со статической цепочкой . . 139

9.2.2 Организация магазина с дисплеем . . . . . . . . . . 143

9.3 Назначение адресов . . . . . . . . . . . . . . . . . . . . . . 144

9.4 Трансляция переменных . . . . . . . . . . . . . . . . . . . 146

9.5 Трансляция целых выражений . . . . . . . . . . . . . . . 148

9.6 Трансляция арифметических выражений . . . . . . . . . 149

9.7 Трансляция логических выражений . . . . . . . . . . . . 158

9.8 Выделение общих подвыражений . . . . . . . . . . . . . . 165

9.9 Генерация оптимального кода методами синтаксического

9.9.1 Сопоставление образцов . . . . . . . . . . . . . . .

9.9.2 Синтаксический анализ для T-грамматик . . . . . .

9.9.3 Выбор дерева вывода наименьшей стоимости . . . .

9.9.4 Атрибутная схема для алгоритма сопоставления об-

10 Системы автоматизации построения трансляторов

1.1 Место компилятора в программном обеспечении

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

Для некоторых языков имеется довольно много реализаций. Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа IBM PC на рынке десятки.

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

о микропроцессорах Motorola 68010, 68020, 68030, 68040.

В рамках традиционных последовательных машин возникает боль-

ГЛАВА 1. ВВЕДЕНИЕ

шое число различных направлений архитектур. Примерами могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как Intel, Motorola, Sun, начинают переходить на выпуск машин с RISC-архитектурами. Естественно, для каждой новой системы команд требуется полный набор новых компиляторов с распространенных языков.

Наконец, бурно развиваются различные параллельные архитектуры. Среди них отметим векторные, многопроцессорные, с широким командным словом (вариантом которых являются суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с параллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и другие), через рабочие станции (например, IBM RS/6000) и кончая персональными (например, на основе микропроцессора I-860). Естественно, для каждой из машин создаются новые компиляторы для многих языков программирования. Здесь необходимо также отметить, что новые архитектуры требуют разработки совершенно новых подходов к созданию компиляторов, так что наряду с собственно разработкой компиляторов ведется и большая научная работа по созданию новых методов трансляции.

1.2 Структура компилятора

Обобщенная структура компилятора и основные фазы компиляции показаны на рис. 1.1.

На фазе лексического анализа входная программа, представляющая собой поток литер, разбивается на лексемы – слова в соответствии с определениями языка. Основными формализмами, лежащим в основе реализации лексических анализаторов, являются конечные автоматы и регулярные выражения. Лексический анализатор может работать в двух основных режимах: либо как подпрограмма, вызываемая синтаксическим анализатором для получения очередной лексемы, либо как полный проход, результатом которого является файл лексем.

В процессе выделения лексем лексический анализатор может как самостоятельно строить таблицы объектов (идентификаторов, строк, чисел и т.д.), так и выдавать значения для каждой лексемы при очередном к нему обращении. В этом случае таблицы объектов строятся в последующих фазах (например, в процессе синтаксического анализа).

На этапе лексического анализа обнаруживаются некоторые (простейшие) ошибки (недопустимые символы, неправильная запись чисел, идентификаторов и др.).

Основная задача синтаксического анализа – разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящее время чаще всего используется либо LL(1)-анализ (и его вариант – рекурсивный спуск), либо LR(1)-анализ и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора, LR(1) – при исполь-

1.2. СТРУКТУРА КОМПИЛЯТОРА

Ijhf `mlhqgZy nhjfZ

nbdkgZy ljhcdb b ^j

Ijhf `mlhqgZy nhjfZ

ГЛАВА 1. ВВЕДЕНИЕ

зовании систем автоматического построения синтаксических анализаторов.

Результатом синтаксического анализа является синтаксическое дерево со ссылками на таблицы объектов. В процессе синтаксического анализа также обнаруживаются ошибки, связанные со структурой программы.

На этапе контекстного анализа выявляются зависимости между частями программы, которые не могут быть описаны контекстно-свободным синтаксисом. Это в основном связи “описание-использование”, в частности, анализ типов объектов, анализ областей видимости, соответствие параметров, метки и другие. В процессе контекстного анализа таблицы объектов пополняются информацией об описаниях (свойствах) объектов.

Основным формализмом, использующимся при контекстном анализе, является аппарат атрибутных грамматик. Результатом контекстного анализа является атрибутированное дерево программы. Информация об объектах может быть как рассредоточена в самом дереве, так и сосредоточена в отдельных таблицах объектов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов.

Затем программа может быть переведена во внутреннее представление. Это делается для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразования программы во внутреннее представление является желание иметь переносимый компилятор. Тогда только последняя фаза (генерация кода) является машинно-зависимой. В качестве внутреннего представления может использоваться префиксная или постфиксная запись, ориентированный граф, тройки, четверки и другие.

Фаз оптимизации может быть несколько. Оптимизации обычно делят на машинно-зависимые и машинно-независимые, локальные и глобальные. Часть машинно-зависимой оптимизации выполняется на фазе генерации кода. Глобальная оптимизация пытается принять во внимание структуру всей программы, локальная – только небольших ее фрагментов. Глобальная оптимизация основывается на глобальном потоковом анализе, который выполняется на графе программы и представляет по существу преобразование этого графа. При этом могут учитываться такие свойства программы, как межпроцедурный анализ, межмодульный анализ, анализ областей жизни переменных и т.д.

Наконец, генерация кода – последняя фаза трансляции. Результатом ее является либо ассемблерный модуль, либо объектный (или загрузочный) модуль. В процессе генерации кода могут выполняться некоторые локальные оптимизации, такие как распределение регистров, выбор длинных или коротких переходов, учет стоимости команд при выборе конкретной последовательности команд. Для генерации кода разработаны различные методы, такие как таблицы решений, сопоставление образцов, включающее динамическое программирование, различ-

Электронный каталог

Поиск :

  • Новые поступления
  • Простой поиск
  • Расширенный поиск
  • Поиск одной строкой
  • Авторы
  • Издательства
  • Серии
  • Тезаурус (Рубрики)
  • Учебная литература:
    • Список дисциплин
  • Информация о фонде
  • Помощь

Личный кабинет :

Электронный каталог: Серебряков В. А. — Лекции по конструированию компиляторов

Серебряков В. А. — Лекции по конструированию компиляторов

Книга
УДК 519 С325

Серебряков, В. А.
Лекции по конструированию компиляторов / В. А. Серебряков, Рос. акад. наук, Вычислительный центр . – М. : РАН. ВЦ им.А. А. Дородницына, 1994 . – 173 с. : 2000.00 .

Скачать бесплатно книги и журналы!

Название: Конструирование компиляторов
Автор: Свердлов С. З.
Издательство: Lambert Academic Publishing
Год: 2015
Страниц: 575
Формат: PDF
Размер: 10,43 МБ
Качество: Отличное

Конструирование компиляторов — В книге подробно рассматривается разработка компилятора языка программирования высокого уровня. Обсуждаются все этапы реализации от спецификации языка до формирования машинного кода. Приводится исходный код компилятора на нескольких языках программирования. Даются необходимые для создания компилятора сведения по теории формальных языков и грамматик. Изложение сопровождается многочисленными примерами.
Учебное пособие адресуется студентам вузов, специализирующимся по компьютерным технологиям и всем, кто интересуется программированием.

Языки программирования и их реализация
Компилятор, интерпретатор, конвертор
Метаязыки
Теоретические основы трансляции
Формальные языки и грамматики
Основные термины и определения
Примеры языков
Порождающие грамматики (грамматики Н. Хомского)
Еще несколько определений
Дерево вывода
Задача разбора
Для чего надо решать задачу разбора
Домино Де Ремера
Разновидности алгоритмов разбора
Эквивалентность и однозначность грамматик
Иерархия грамматик Н. Хомского
Автоматные грамматики и языки
Граф автоматной грамматики
Конечные автоматы
Преобразование недетерминированного конечного автомата (НКА) в детерминированный конечный автомат (ДКА)
Таблица переходов детерминированного конечного автомата
Программная реализация автоматного распознавателя
Дерево разбора в автоматной грамматике
Пример автоматного языка
Синтаксические диаграммы автоматного языка
Регулярные выражения и регулярные множества
Эквивалентность регулярных выражений и автоматных грамматик
Для чего нужны регулярные выражения
Регулярные выражения как языки
Расширенная нотация для регулярных выражений
КОНТЕКСТНО-СВОБОДНЫЕ (КС) ГРАММАТИКИ И ЯЗЫКИ
Однозначность КС-грамматики
Алгоритмы распознавания КС-языков
Распознающий автомат для КС-языков
Самовложение в КС-грамматиках
Синтаксические диаграммы КС-языков
Определение языка с помощью синтаксических диаграмм
Синтаксический анализ КС-языков методом рекурсивного спуска
Требование детерминированного распознавания
LL-грамматики
Левая и правая рекурсия
Синтаксический анализ арифметических выражений
Включение действий в синтаксис
Обработка ошибок при трансляции
Табличный LL(1)-анализатор
Рекурсивный спуск и табличный анализатор
Трансляция выражений
Польская запись
Алгоритм вычисления выражений в обратной польской записи
Перевод выражений в обратную польскую запись
Интерпретация выражений
Семантическое дерево выражения
Упражнения для самостоятельной работы
Трансляция языков программирования
Описание языков программирования
Метаязыки
БНФ
Синтаксические диаграммы
Расширенная форма Бэкуса-Наура (РБНФ)
Описания синтаксиса языков семейства Си
Описания синтаксиса языка Ада
Краткая характеристика языка «О»
Синтаксис «О»
Пример программы на «О»
Структура компилятора
Многопроходные и однопроходные трансляторы
Компилятор языка «о»
Вспомогательные модули компилятора
Лексический анализатор (сканер)
Виды и значения лексем
Лексический анализатор языка «О»
Синтаксический анализатор
Контекстный анализ
Таблица имен
Контекстный анализ модуля
Трансляция списка импорта
Трансляция описаний
Контекстный анализ выражений
Контекстный анализ операторов
Генерация кода
Виртуальная машина
Архитектура виртуальной машины
Программирование в коде виртуальной машины
Реализация виртуальной машины
Генератор кода
Распределение памяти
Генерация кода для выражений
Генерация кода для операторов
Завершение генерации
Назначение адресов переменным
Трансляция процедур
Расширенный набор команд виртуальной машины
Процедуры без параметров и локальных переменных
Процедуры с параметрами-значениями без локальных переменных
Процедуры с параметрами-значениями и локальными переменными
Простейшая оптимизация кода
Процедуры-функции с параметрами-значениями и локальными переменными
Трансляция оператора RETURN
Особенность трансляции параметров-переменных
Пример программы на языке «О с процедурами»
Конструкция простого ассемблера
Реализация ассемблера
Автоматизация построения и мобильность трансляторов
Автоматический анализ и преобразование грамматик
Автоматическое построение компилятора и его частей
Использование языков высокого уровня
Самокомпилятор. Раскрутка
Примеры раскрутки
Унификация промежуточного представления
Приложения
Определение терминов
Целые типы
Вещественные типы
Числовые типы
Одинаковые типы
Равные типы
Поглощение типов
Расширение типов (базовый тип)
Совместимость по присваиванию
Совместимость массивов
Совместимость выражений
Совпадение списков формальных параметров
Синтаксис Оберона-2
Модуль SYSTEM
Среда Оберон
Текст компилятора языка «о» на паскале
Текст компилятора языка «о» на обероне
Отличия версий для компиляторов job и xds
Изменение обозначений
Изменения в структуре компилятора
Текст компилятора языка «о» на си/си++
Текст компилятора «о» на языке программирования ява
Текст компилятора «о» на языке программирования си#
Литература

Электронный каталог

Поиск :

  • Новые поступления
  • Простой поиск
  • Расширенный поиск
  • Поиск одной строкой
  • Авторы
  • Издательства
  • Серии
  • Тезаурус (Рубрики)
  • Учебная литература:
    • Список дисциплин
  • Информация о фонде
  • Помощь

Личный кабинет :

Электронный каталог: Серебряков В. А. — Лекции по конструированию компиляторов

Серебряков В. А. — Лекции по конструированию компиляторов

Книга
УДК 519 С325

Серебряков, В. А.
Лекции по конструированию компиляторов / В. А. Серебряков, Рос. акад. наук, Вычислительный центр . – М. : РАН. ВЦ им.А. А. Дородницына, 1994 . – 173 с. : 2000.00 .

Лекции по конструированию компиляторов

29.04.2020, 21:52
Название Лекции по конструированию компиляторов
страница 1/11
Дата 21.12.2012
Размер 2.15 Mb.
Тип Книга

Предлагаемая вниманию читателя книга основана на курсе лекций,

прочитанных автором на факультете вычислительной математики и

кибернетики Московского государственного университета в 1991-

1993 гг. Автор надеется, что издание книги восполнит

существенный пробел в литературе на руссом языке по разработке

Содержание книги представляет собой «классические» разделы

предмета: лексический и синтаксический анализ, организация

памяти, генерация кода. Сделана попытка на протяжении всего

изложения провести единую «атрибутную» точку зрения на процесс

разработки компилятора. В книге не затрагиваются чрезвычайно

важные вопросы глобальной оптимизации и разработки

компиляторов для машин с параллельной архитектурой. Автор

надеется восполнить эти пробелы в будущем.

Книга будет полезной как студентам и аспирантам

программистских специальностей, так и профессионалам в этих

Глава 1. Введение 6

1.1. Место компилятора в программном обеспечении 6

1.2. Структура компилятора 7

Глава 2. Лексический анализ 11

2.1. Регулярные множества и регулярные выражения 13

2.2. Конечные автоматы 14

2.3. Построение детерминированного конечного

автомата по регулярному выражению 17

2.4. Построение детерминированного конечного

автомата с минимальным числом состояний 20

2.5. Программирование лексических анализаторов 22

2.6. Конструктор лексических анализаторов LEX 27

Глава 3. Синтаксический анализ 31

3.1. Основные понятия и определения 31

3.2. Таблично-управляемый предсказывающий разбор 33

3.2.1. Алгоритм разбора сверху-вниз 33

3.2.2. Множества FIRST и FOLLOW 37

3.2.3. Конструирование таблиц

предсказывающего анализатора 39

3.2.4. LL(1)-грамматики 40

3.2.5. Удаление левой рекурсии 41

3.2.6. Левая факторизация 43

3.2.7. Рекурсивный спуск 44

3.2.8. Диаграммы переходов для рекурсивного спуска 46

3.2.9. Восстановление после синтаксических ошибок 48

3.3. Разбор снизу-вверх типа сдвиг-свертка 49

3.3.2. LR(k)-анализаторы 51

3.3.3. LR грамматики 56

3.3.4. Конфликты разбора типа сдвиг-свертка 62


3.3.5. Восстановление после синтаксических ошибок 63

Глава 4. Промежуточные представления программы 64

4.1. Представление в виде ориентированного графа 64

4.2. Трехадресный код 64

4.3. Линеаризованные представления 69

4.4. Организация информации в генераторе кода 72

4.5. Уровень промежуточного представления 73

Глава 5. Элементы теории перевода 74

5.1. Преобразователи с магазинной памятью 74

5.2. Синтаксически управляемый перевод 76

5.3. Атрибутные грамматики 79

5.3.1. Определение атрибутных грамматик 79

5.3.2. Атрибутированное дерево разбора 80

5.3.3. Язык описания атрибутных грамматик 81

Глава 6. Контекстные условия языков программирования 85

6.1. Описание областей видимости и блочной структуры 85

6.2. Структура среды Модулы-2 86

6.3. Занесение в среду и поиск объектов 90

Глава 7. Организация таблиц символов компилятора 98

7.1. Таблицы идентификаторов и таблицы символов 98

7.2. Таблицы идентификаторов 99

7.3. Таблицы символов и таблицы расстановки 102

7.4. Функции расстановки 103

7.5. Таблицы на деревьях 104

7.6. Реализация блочной структуры 108

7.7. Сравнение различных методов реализации таблиц 109

Глава 8. Генерация кода 110

8.1. Модель машины 110

8.2. Динамическая организация памяти 113

8.3. Назначение адресов 122

8.4. Трансляция переменных 124

8.5. Трансляция целых выражений 130

8.6. Распределение регистров при вычислении

арифметических выражений 132

8.7. Трансляция логических выражений 143

8.8. Выделение общих подвыражений 151

8.9. Генерация оптимального кода методами

синтаксического анализа 155

8.9.1. Сопоставление образцов 155

8.9.2. Синтаксический анализ для Т-грамматик 158

8.9.3. Выбор дерева вывода наименьшей стоимости 165

Глава 9. Системы автоматизации построения трансляторов 169

9.1. Система Супер 169

9.2. Система Yacc 172

Глава 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-архитектурами. Естественно, для каждой новой системы

команд требуется полный набор новых компиляторов с

Наконец, бурно развиваются различные параллельные

архитектуры. Среди них отметим векторные, многопроцессорные, с

широким командным словом (вариантом которых являются

суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с

параллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и

другие), через рабочие станции (например, IBM/RS-6000) и

кончая персональными (например, на основе микропроцессора I-

860). Естественно, для каждой из машин создаются новые

компиляторы для многих языков программирования. Здесь

необходимо также отметить, что новые архитектуры требуют

разработки совершенно новых подходов к созданию компиляторов,

так что наряду с собственно разработкой компиляторов ведется и

большая научная работа по созданию новых методов трансляции.

1.2. Структура компилятора

Обобщенная структура компилятора и основные фазы компиляции

показаны на рис. 1.1.

На фазе лексического анализа (ЛА) входная программа,

представляющая собой поток символов, разбивается на лексемы —

слова в соответствии с определениями языка. Основным

формализмом, лежащим в основе реализации лексических

анализаторов, являются конечные автоматы и регулярные

выражения. Лексический анализатор может работать в двух

основных режимах: либо как подпрограмма, вызываемая

синтаксическим анализатором за очередной лексемой, либо как

полный проход, результатом которого является файл лексем.

В процессе выделения лексем ЛА может как самостоятельно

строить таблицы имен и констант, так и выдавать значения для

каждой лексемы при очередном обращении к нему. В этом случае

таблица имен строится в последующих фазах (например, в

процессе синтаксического анализа).

Вход | анализ | +————-+ || Поток лексем +||

| Конечные | || и констант || |

| анализ | +————-+ || Дерево разбора ||

| Контекстно-сво- | || имен и констант|||

| Атрибутные | || + таблица символов || |

| промежуточного | || Промежуточная форма ||

| представления | || (префиксная, пост- ||

| Потоковый | || (ориентированный граф)|| |

| Таблицы решений, | || Объектный ||

На этапе ЛА обнаруживаются некоторые (простейшие) ошибки

(недопустимые символы, неправильная запись чисел,

идентификаторов и др.).

Основная задача синтаксического анализа — разбор структуры

программы. Как правило, под структурой понимается дерево,

соответствующее разбору в контекстно-свободной грамматике

языка. В настоящее время чаще всего используется либо LL(1)-

анализ (и его вариант — рекурсивный спуск), либо LR(1)-анализ

и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный

спуск чаще используется при ручном программировании

синтаксического анализатора, LR(1) — при использовании систем

автоматизации построения синтаксических анализаторов.

Результатом синтаксического анализа является синтаксическое

дерево со ссылками на таблицу имен. В процессе синтаксического

анализа также обнаруживаются ошибки, связанные со структурой

На этапе контекстного анализа выявляются зависимости между

частями программы, которые не могут быть описаны контекстно-

свободным синтаксисом. Это в основном связи «описание-

использование», в частности анализ типов объектов, анализ

областей видимости, соответствие параметров, метки и другие. В

процессе контекстного анализа строится таблица символов,

которую можно рассматривать как таблицу имен, пополненную

информацией об описаниях (свойствах) объектов.

Основным формализмом, использующимся при контекстном

анализе, являются атрибутные грамматики. Результатом работы

фазы контекстного анализа является атрибутированное дерево

программы. Информация об объектах может быть как

рассредоточена в самом дереве, так и сосредоточена в отдельных

таблицах символов. В процессе контекстного анализа также могут

быть обнаружены ошибки, связанные с неправильным

Затем программа может быть переведена во внутреннее

представление. Это делается для целей оптимизации и/или

удобства генерации кода. Еще одной целью преобразования

программы во внутреннее представление является желание иметь

переносимый компилятор. Тогда только последняя фаза (генерация

кода) является машинно-зависимой. В качестве внутреннего

представления может использоваться префиксная или постфиксная

запись, ориентированный граф, тройки, четверки и другие.

Фаз оптимизации может быть несколько. Оптимизации обычно

делят на машинно-зависимые и машинно-независимые, локальные и

глобальные. Часть машинно-зависимой оптимизации выполняется на

фазе генерации кода. Глобальная оптимизация пытается принять

во внимание структуру всей программы, локальная — только

небольших ее фрагментов. Глобальная оптимизация основывается

на глобальном потоковом анализе, который выполняется на графе

программы и представляет по существу преобразование этого

графа. При этом могут учитываться такие свойства программы,

как межпроцедурный анализ, межмодульный анализ, анализ

областей жизни переменных и т.д.

Наконец, генерация кода — последняя фаза трансляции.

Результатом ее является либо ассемблерный модуль, либо

объектный (или загрузочный) модуль. В процессе генерации кода

могут выполняться некоторые локальные оптимизации, такие как

распределение регистров, выбор длинных или коротких переходов,

учет стоимости команд при выборе конкретной последовательности

команд. Для генерации кода разработаны различные методы, такие

как таблицы решений, сопоставление образцов, включающее

динамическое программирование, различные синтаксические

Конечно, те или иные фазы транслятора могут либо

отсутствовать совсем, либо объединяться. В простейшем случае

однопроходного транслятора нет явной фазы генерации

промежуточного представления и оптимизации, остальные фазы

объединены в одну, причем нет и явно построенного

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

Основные задачи компиляторов

Компьютеры сами по себе способны выполнять только очень ограниченный набор операций, называемых машинными кодами. В старые времена, когда появились первые компьютеры, программы писались в машинных кодах, представляющих собой последовательности двоичных чисел, однозначно воспринимаемых компьютером. В конце 50-х кодов прошлого века появились первые языки программирования, такие как язык ассемблера и Фортран. Для того, чтобы компьютер мог понять программу, написанную на каком-то языке программирования, необходим переводчик ( транслятор ) такой программы в машинные коды. Отметим, что, если оператор языка ассемблера отображается при трансляции чаще всего 1 Некоторые операторы языка ассемблера, например, такие, как операторы ввода/вывода, отображаются в несколько машинных команд. в одну машинную инструкцию, предложения языков более высокого уровня отображаются, вообще говоря, в несколько машинных инструкций.

Трансляторы бывают двух типов: компиляторы ( compiler ) и интерпретаторы ( interpreter ). Процесс компиляции состоит из двух частей: анализа ( analysis ) и синтеза ( synthesis ). Анализирующая часть компилятора разбивает исходную программу на составляющие ее элементы (конструкции языка) и создает промежуточное представление исходной программы. Синтезирующая часть из промежуточного представления создает новую программу, которую компьютер в состоянии понять. Такая программа называется объектной программой. Объектная программа может в дальнейшем выполняться без перетрансляции. В качестве промежуточного представления обычно используются деревья, в частности, так называемые деревья разбора. Под деревом разбора понимается дерево , каждый узел которого соответствует некоторой операции , а сыновья этого узла — операндам.

Интерпретатор

В отличие от компилятора, интерпретатор не создает никакой новой программы, а просто выполняет каждое предложение языка программирования. Можно сказать, что результатом работы интерпретатора является «число».

Вообще говоря, интерпретатор , так же, как и компилятор , анализирует программу на входном языке, создает промежуточное представление , а затем выполняет операции , содержащиеся в тексте этой программы. Например, интерпретатор может построить дерево разбора, а затем выполнить операции , которыми помечены узлы этого дерева.

В том случае, если исходный язык достаточно прост (например, если это язык ассемблера или Basic ), то никакое промежуточное представление не нужно, и тогда интерпретатор — это простой цикл . Он выбирает очередную инструкцию языка из входного потока, анализирует и выполняет ее. Затем выбирается следующая инструкция . Этот процесс продолжается до тех пор, пока не будут выполнены все инструкции, либо пока не встретится инструкция , означающая окончание процесса интерпретации.

Компилятор

Компилятор переводит программы с одного языка на другой. Входом компилятора служит цепочка символов , составляющая исходную программу на языке программирования . Выход компилятора (объектная программа ) также представляет собой цепочку символов, но принадлежащую другому языку , например, языку некоторого компьютера. При этом сам компилятор написан на языке , возможно, отличающемся от первых двух. Будем называть язык исходным языком, язык — целевым языком, а язык — языком реализации. Таким образом, можно говорить о компиляторе как об отображении множества в множество , т.е. .

Отметим, что далеко не всегда исходные программы корректны с точки зрения исходного языка. Более того, некорректные программы подаются на вход компилятору значительно чаще, чем корректные — таков уж современный процесс разработки программ. Поэтому крайне важной частью процесса трансляции является точная диагностика ошибок, допущенных во входной программе.

Существует огромное количество различных языков программирования, начиная с таких традиционных языков программирования как Fortran и Pascal и кончая современными объектно-ориентированными языками такими, как C# и Java . Практически каждый язык программирования имеет какие-то особенности с точки зрения создателя транслятора. Однако мы начнем с рассмотрения разнообразных целевых языков компиляторов.

Серебряков В.А. Лекции по конструированию компиляторов — файл n1.doc

Серебряков В.А. Лекции по конструированию компиляторов
скачать (1250.5 kb.)
Доступные файлы (1):

n1.doc 1251kb. 30.05.2012 00:24 скачать
    Смотрите также:
  • Хантер Р. Проектирование и конструирование компиляторов (Документ)
  • Хантер Р. Основные концепции компиляторов (Документ)
  • Руководство по расчету и конструированию железобетонных ферм покрытия (Стандарт)
  • Руководство по конструированию бетонных и ж.б. конструкций из тяжелого бетона (без предварительного напряжения) 1978 (Стандарт)
  • Конспект занятия по конструированию в подготовительной группе детского сада Мост для жителей волшебного города (Лекция)
  • Харламов С.В. Практикум по расчету и конструированию машин и аппаратов пищевых производств (Документ)
  • Буйлов Г.П., Доронин В.А., Серебряков Н.П. Автоматическое управление технологическими процессами целлюлозно-бумажного производства (Документ)
  • Гербер И.А. Лекции по конструированию спортивных изделий (Документ)
  • Свердлов С.З. Введение в методы трансляции (Документ)
  • (Документ)
  • Карунин А.Л. (ред.) Конструкция автомобиля. Шасси (Документ)
  • Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум (Документ)

n1.doc

Лекции по
конструированию компиляторов

Предлагаемая вниманию читателя книга основана на курсе лекций,

прочитанных автором на факультете вычислительной математики и

кибернетики Московского государственного университета в 1991-

1993 гг. Автор надеется, что издание книги восполнит

существенный пробел в литературе на руссом языке по разработке

Содержание книги представляет собой «классические» разделы

предмета: лексический и синтаксический анализ, организация

памяти, генерация кода. Сделана попытка на протяжении всего

изложения провести единую «атрибутную» точку зрения на процесс

разработки компилятора. В книге не затрагиваются чрезвычайно

важные вопросы глобальной оптимизации и разработки

компиляторов для машин с параллельной архитектурой. Автор

надеется восполнить эти пробелы в будущем.

Книга будет полезной как студентам и аспирантам


программистских специальностей, так и профессионалам в этих

областях.
Оглавление
Глава 1. Введение 6

1.1. Место компилятора в программном обеспечении 6

1.2. Структура компилятора 7

Глава 2. Лексический анализ 11

2.1. Регулярные множества и регулярные выражения 13

2.2. Конечные автоматы 14

2.3. Построение детерминированного конечного

автомата по регулярному выражению 17

2.4. Построение детерминированного конечного

автомата с минимальным числом состояний 20

2.5. Программирование лексических анализаторов 22

2.6. Конструктор лексических анализаторов LEX 27

Глава 3. Синтаксический анализ 31

3.1. Основные понятия и определения 31

3.2. Таблично-управляемый предсказывающий разбор 33

3.2.1. Алгоритм разбора сверху-вниз 33

3.2.2. Множества FIRST и FOLLOW 37

3.2.3. Конструирование таблиц

предсказывающего анализатора 39

3.2.4. LL(1)-грамматики 40

3.2.5. Удаление левой рекурсии 41

3.2.6. Левая факторизация 43

3.2.7. Рекурсивный спуск 44

3.2.8. Диаграммы переходов для рекурсивного спуска 46

3.2.9. Восстановление после синтаксических ошибок 48

3.3. Разбор снизу-вверх типа сдвиг-свертка 49

3.3.2. LR(k)-анализаторы 51

3.3.3. LR грамматики 56

3.3.4. Конфликты разбора типа сдвиг-свертка 62

3.3.5. Восстановление после синтаксических ошибок 63

Глава 4. Промежуточные представления программы 64

4.1. Представление в виде ориентированного графа 64

4.2. Трехадресный код 64

4.3. Линеаризованные представления 69

4.4. Организация информации в генераторе кода 72

4.5. Уровень промежуточного представления 73

Глава 5. Элементы теории перевода 74

5.1. Преобразователи с магазинной памятью 74

5.2. Синтаксически управляемый перевод 76

5.3. Атрибутные грамматики 79

5.3.1. Определение атрибутных грамматик 79

5.3.2. Атрибутированное дерево разбора 80

5.3.3. Язык описания атрибутных грамматик 81

Глава 6. Контекстные условия языков программирования 85

6.1. Описание областей видимости и блочной структуры 85

6.2. Структура среды Модулы-2 86

6.3. Занесение в среду и поиск объектов 90

Глава 7. Организация таблиц символов компилятора 98

7.1. Таблицы идентификаторов и таблицы символов 98

7.2. Таблицы идентификаторов 99

7.3. Таблицы символов и таблицы расстановки 102

7.4. Функции расстановки 103

7.5. Таблицы на деревьях 104

7.6. Реализация блочной структуры 108

7.7. Сравнение различных методов реализации таблиц 109

Глава 8. Генерация кода 110

8.1. Модель машины 110

8.2. Динамическая организация памяти 113

8.3. Назначение адресов 122

8.4. Трансляция переменных 124

8.5. Трансляция целых выражений 130

8.6. Распределение регистров при вычислении

арифметических выражений 132

8.7. Трансляция логических выражений 143

8.8. Выделение общих подвыражений 151

8.9. Генерация оптимального кода методами

синтаксического анализа 155

8.9.1. Сопоставление образцов 155

8.9.2. Синтаксический анализ для Т-грамматик 158

8.9.3. Выбор дерева вывода наименьшей стоимости 165

Глава 9. Системы автоматизации построения трансляторов 169

9.1. Система Супер 169

9.2. Система Yacc 172

Литература 175
Глава 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-архитектурами. Естественно, для каждой новой системы

команд требуется полный набор новых компиляторов с

Наконец, бурно развиваются различные параллельные

архитектуры. Среди них отметим векторные, многопроцессорные, с

широким командным словом (вариантом которых являются

суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с

параллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и

другие), через рабочие станции (например, IBM/RS-6000) и

кончая персональными (например, на основе микропроцессора I-

860). Естественно, для каждой из машин создаются новые

компиляторы для многих языков программирования. Здесь

необходимо также отметить, что новые архитектуры требуют

разработки совершенно новых подходов к созданию компиляторов,

так что наряду с собственно разработкой компиляторов ведется и

большая научная работа по созданию новых методов трансляции.

1.2. Структура компилятора
Обобщенная структура компилятора и основные фазы компиляции

показаны на рис. 1.1.

На фазе лексического анализа (ЛА) входная программа,

представляющая собой поток символов, разбивается на лексемы —

слова в соответствии с определениями языка. Основным

формализмом, лежащим в основе реализации лексических

анализаторов, являются конечные автоматы и регулярные

выражения. Лексический анализатор может работать в двух

основных режимах: либо как подпрограмма, вызываемая

синтаксическим анализатором за очередной лексемой, либо как

полный проход, результатом которого является файл лексем.

В процессе выделения лексем ЛА может как самостоятельно

строить таблицы имен и констант, так и выдавать значения для

каждой лексемы при очередном обращении к нему. В этом случае

таблица имен строится в последующих фазах (например, в

процессе синтаксического анализа).

Вход | анализ | +————-+ || Поток лексем +||

| Конечные | || и констант || |

| анализ | +————-+ || Дерево разбора ||

| Контекстно-сво- | || имен и констант|||

| Атрибутные | || + таблица символов || |

| промежуточного | || Промежуточная форма ||

| представления | || (префиксная, пост- ||

| Потоковый | || (ориентированный граф)|| |

| Таблицы решений, | || Объектный ||

+————————+ +————-+
Рис. 1.1
На этапе ЛА обнаруживаются некоторые (простейшие) ошибки

(недопустимые символы, неправильная запись чисел,

идентификаторов и др.).

Основная задача синтаксического анализа — разбор структуры

программы. Как правило, под структурой понимается дерево,

соответствующее разбору в контекстно-свободной грамматике

языка. В настоящее время чаще всего используется либо LL(1)-

анализ (и его вариант — рекурсивный спуск), либо LR(1)-анализ

и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный

спуск чаще используется при ручном программировании

синтаксического анализатора, LR(1) — при использовании систем

автоматизации построения синтаксических анализаторов.

Результатом синтаксического анализа является синтаксическое

дерево со ссылками на таблицу имен. В процессе синтаксического

анализа также обнаруживаются ошибки, связанные со структурой

На этапе контекстного анализа выявляются зависимости между

частями программы, которые не могут быть описаны контекстно-

свободным синтаксисом. Это в основном связи «описание-

использование», в частности анализ типов объектов, анализ

областей видимости, соответствие параметров, метки и другие. В

процессе контекстного анализа строится таблица символов,

которую можно рассматривать как таблицу имен, пополненную

информацией об описаниях (свойствах) объектов.

Основным формализмом, использующимся при контекстном

анализе, являются атрибутные грамматики. Результатом работы

фазы контекстного анализа является атрибутированное дерево

программы. Информация об объектах может быть как

рассредоточена в самом дереве, так и сосредоточена в отдельных

таблицах символов. В процессе контекстного анализа также могут

быть обнаружены ошибки, связанные с неправильным

Затем программа может быть переведена во внутреннее

представление. Это делается для целей оптимизации и/или

удобства генерации кода. Еще одной целью преобразования

программы во внутреннее представление является желание иметь

переносимый компилятор. Тогда только последняя фаза (генерация

кода) является машинно-зависимой. В качестве внутреннего

представления может использоваться префиксная или постфиксная

запись, ориентированный граф, тройки, четверки и другие.

Фаз оптимизации может быть несколько. Оптимизации обычно

делят на машинно-зависимые и машинно-независимые, локальные и

глобальные. Часть машинно-зависимой оптимизации выполняется на

фазе генерации кода. Глобальная оптимизация пытается принять

во внимание структуру всей программы, локальная — только

небольших ее фрагментов. Глобальная оптимизация основывается

на глобальном потоковом анализе, который выполняется на графе

программы и представляет по существу преобразование этого

графа. При этом могут учитываться такие свойства программы,

как межпроцедурный анализ, межмодульный анализ, анализ

областей жизни переменных и т.д.

Наконец, генерация кода — последняя фаза трансляции.

Результатом ее является либо ассемблерный модуль, либо

объектный (или загрузочный) модуль. В процессе генерации кода

могут выполняться некоторые локальные оптимизации, такие как

распределение регистров, выбор длинных или коротких переходов,

учет стоимости команд при выборе конкретной последовательности

команд. Для генерации кода разработаны различные методы, такие

как таблицы решений, сопоставление образцов, включающее

динамическое программирование, различные синтаксические

Конечно, те или иные фазы транслятора могут либо

отсутствовать совсем, либо объединяться. В простейшем случае

однопроходного транслятора нет явной фазы генерации

промежуточного представления и оптимизации, остальные фазы

объединены в одну, причем нет и явно построенного

Глава 2. Лексический анализ
Основная задача лексического анализа — разбить входной текст,

состоящий из последовательности одиночных символов, на


последовательность слов, или лексем, т.е. выделить эти слова

из непрерывной последовательности символов. Все символы

входной последовательности с этой точки зрения разделяются на

символы, принадлежащие каким-либо лексемам, и символы,

разделяющие лексемы (разделители). В некоторых случаях между

лексемами может и не быть разделителей. С другой стороны, в

некоторых языках лексемы могут содержать незначащие символы

(пробел в Фортране). В Си разделительное значение символов-

разделителей может блокироваться (‘\’ в конце строки внутри

Обычно все лексемы делятся на классы. Примерами таких

классов являются числа (целые, восьмеричные,

шестнадцатиричные, действительные и т.д.), идентификаторы,

строки. Отдельно выделяются ключевые слова и символы

пунктуации (иногда их называют символы-ограничители). Как

правило, ключевые слова — это некоторое конечное подмножество

идентификаторов. В некоторых языках (например, ПЛ/1) смысл

лексемы может зависеть от ее контекста и невозможно провести

лексический анализ в отрыве от синтаксического.

С точки зрения дальнейших фаз анализа лексический анализатор

выдает информацию двух сортов: для синтаксического

анализатора, работающего вслед за лексическим, существенна

информация о последовательности классов лексем, ограничителей

и ключевых слов, а для контексного анализа, работающего вслед

за синтаксическим, важна информация о конкретных значениях

отдельных лексем (идентификаторов, чисел и т.д.). Поэтому

общая схема работы лексического анализатора такова. Сначала

выделяем отдельную лексему (возможно, используя символы-

разделители). Если выделенная лексема — ограничитель, то он

(точнее, некоторый его признак) выдается как результат

лексического анализа. Ключевые слова распознаются либо явным

выделением непосредственно из текста, либо сначала выделяется

идентификатор, а затем делается проверка на принадлежность его

множеству ключевых слов. Если да, то выдается признак

соответствующего ключевого слова, если нет — выдается признак

идентификатора, а сам идентификатор сохраняется отдельно. Если

выделенная лексема принадлежит какому-либо из других классов

лексем (число, строка и т.д.), то выдается признак класса

лексемы, а значение лексемы сохраняется.

Лексический анализатор может работать или как

самостоятельная фаза трансляции, или как подпрограмма,

работающая по принципу «дай лексему». В первом случае (рис.

2.1) выходом лексического анализатора является файл лексем, во

втором (рис. 2.2) лексема выдается при каждом обращении к

лексическому анализатору (при этом, как правило, тип лексемы

возвращается как значение функции «лексический анализатор», а

значение передается через глобальную переменную). С точки

зрения формирования значений лексем, принадлежащих классам

лексем, лексический анализатор может либо просто выдавать

значение каждой лексемы и в этом случае построение таблиц

переносится на более поздние фазы, либо он может

самостоятельно строить таблицы объектов (идентификаторов,

строк, чисел и т.д.). В этом случае в качестве значения

лексемы выдается указатель на вход в соответствующую таблицу.

| Синт. анализатор | | Таблица | | Лекс. анализатор |——+

Файл лексем «Дай лексему»
Рис. 2.1 Рис. 2.2

Работа лексического анализатора описывается формализмом

конечных автоматов. Однако непосредственное описание конечного

автомата неудобно практически. Поэтому для описания

лексических анализаторов, как правило, используют либо

формализм регулярных выражений, либо формализм контекстно

свободных грамматик, а именно подкласса автоматных, или

регулярных, грамматик. Все три формализма (конечных автоматов,

регулярных выражений и автоматных грамматик) имеют одинаковую

выразительную мощность. По описанию лексического анализатора в

виде регулярного выражения или автоматной грамматики строится

конечный автомат, распознающий соответствующий язык.

2.1. Регулярные множества и регулярные выражения
Пусть T — конечный алфавит. Регулярное множество в алфавите T

определяется рекурсивно следующим образом (знаком ‘ || 3 ||

Такт автомата M представляется бинарным отношением |-,

определенным на конфигурациях: отношение имеет место, если

есть переход из конфигурации (q1,w1) в конфигурацию (q2,w2).

Отношения |-+ и |-* — это, соответственно, транзитивное и

рефлексивно-транзитивное замыкание отношения |-. Говорят, что

автомат M допускает цепочку w, если (q0,w)|-*(q,e) для

некоторого q p. На диаграмме выделяются

конечные состояния (в примерах выше двойным контуром).
Пример 2.2. Диаграмма для чисел языка Паскаль приведена на

2.3. Построение детерминированного конечного автомата по

регулярному выражению.
Приведем теперь алгоритм построения детерминированного

конечного автомата по регулярному выражению [1]. К регулярному

выражению (сокращенно РВ) r добавим маркер конца: (r)#. После

построения ДКА для расширенного РВ легко построить ДКА для

исходного РВ: все состояния ДКА из которых есть переход в

конечное с чтением символа «#», можно считать конечными, а

символ «#» и соответствующие переходы удалить.

Представим РВ в виде дерева, листья которого — терминальные

символы, а внутренние вершины — операции «.» (конкатенации),

«U» (объединение), «*» (итерация).

Каждому листу дерева (кроме e-листьев) припишем уникальный

номер и ссылаться на него будем, с одной стороны, как на

позицию в дереве и, с другой стороны, как на позицию символа,

Теперь, обходя дерево T сверху-вниз слева-направо, вычислим

четыре функции: nullable, firstpos, lastpos и followpos.

Функции nullable, firstpos и lastpos определены на узлах

дерева, а followpos — на множестве позиций. Значением всех

функций, кроме nullable, является множество позиций. Функция

followpos вычисляется через три остальные функции.

Функция firstpos(n) для каждого узла n синтаксического

дерева регулярного выражения дает множество позиций, которые

соответствуют первым символам в подцепочках, генерируемых

подвыражением с вершиной в n. Аналогично, lastpos(n) дает

множество позиций, которым соответствуют последние символы в

подцепочках, генерируемых подвыражениями с вершиной n. Для

узлов n, поддеревья которых (т.е. дерево, у которого узел n

является корнем) могут породить пустое слово, определим

nullable(n)=true, а для остальных узлов false.
узел n nullable(n) firstpos(n) lastpos(n)

лист е | true | 0 | 0

U | nullable(a) | firstpos(a) | lastpos(a)

a b | nullable(b) | firstpos(b) | lastpos(b)

. | nullable(a) | if nullable(a) |if nullable(b)

/ \ | and | then firstpos(a) |then lastpos(a)

| | U firstpos(b) | U lastpos(b)

a b | nullable(b) | else firstpos(a) |else lastpos(b)

| | true | firstpos(a) | lastpos(a)

на рис. 2.5. Вычисление функции lastpos строится аналогично.
<1,2,3>.

Рис. 2.6 Рис. 2.7
Пример 2.3. Функции firstpos и lastpos для выражения (a+b)abb#

приведены на рис. 2.6. Слева от каждой вершины значение

firstpos, справа — lastpos. Заметим, что эти функции могут

быть вычислены за один обход дерева.

Если i — позиция, то followpos(i) есть множество позиций j

таких, что существует некоторая строка . cd. входящая в

язык, описываемый РВ, такая, что i — соответствует этому

вхождению c, а j — вхождению d.

Функция followpos может быть вычислена также за один обход

дерева по следующим двум правилам
1. Пусть n — внутренний узел с операцией «.» (конкатенация),

a,b — его потомки. Тогда для каждой позиции i, входящей в

lastpos(a), добавляем к множеству значений followpos(i)

множество firstpos(b).
2. Пусть n — внутренний узел с операцией «*» (итерация), a —

его потомок. Тогда для каждой позиции i, входящей в

lastpos(a), добавляем к множеству значений followpos(i)

множество firstpos(а).
Для примера 2.3 значения функции followpos приведены на рис.

Функция followpos позволит теперь сразу построить

детерминированный конечный автомат с помощью следующего

алгоритма.
Алгоритм 2.1. Прямое построение ДКА по регулярному выражению.
Будем строить множество состояний автомата Dstates и помечать

их. Состояния ДКА соответствуют множествам позиций. Начальным

состоянием будет состояние firstpos(root), где root — вершина

синтаксического дерева регулярного выражения, конечными — все

состояния, содержащие позиции, связанные с символом «#».

Сначала в Dstates имеется только одно непомеченное состояние

firstpos(root).
while есть непомеченное состояние T в Dstates do

for каждого входного символа a Sb | <1,2,3> <4>

V | V a V | V V b | b | |

2.4. Построение детерминированного конечного автомата с

минимальным числом состояний
Рассмотрим теперь алгоритм построения ДКА с минимальным числом

состояний, эквивалентного данному ДКА [2].
Алгоритм 2.2. Построение ДКА с минимальным числом состояний.
Шаг 1. Строим начальное разбиение П множества состояний из

двух групп: заключительное состояние и остальные S-F.
Шаг 2. Применяем к П следующую процедуру и получаем новое

разбиение Пnew (рис. 2.11):
for каждой группы G в П do

разбиваем G на подгруппы так, чтобы

состояния s и t из G оказались в одной

группе тогда и только тогда, когда для каждого

входного символа a состояния s и t имеют

переходы по a в состояния из одной и той же

заменяем G в Пnew на множество всех

Проверки на принадлежность диапазону сравнениями можно

заменить проверками на принадлежность диапазону множества:
while (Insym in [‘0’..’9′]) do

end;
Однако с точки зрения качества кода эти программы примерно

эквивалентны. Программу можно значительно улучшить следующим

образом [2]. Пусть LETTER, DIGIT, BLANK, SLESS — элементы

перечислимого типа. Введем массив MAP, входами которого будут

символы, значениями — типы символов. Инициализируем массив MAP

следующим образом:
MAP[‘A’]:=LETTER;

+—+ f +—/не буква и не цифра | слово if |

+—+ Буква или цифра |

| Не буква и не цифра

| Ключевое слово int |

Для этого строится конечный автомат, описывающий множество

ключевых слов. На рис. 2.12 приведен фрагмент такого автомата.

Рассмотрим пример программирования этого конечного автомата на

языке Си, приведенный в [3]:
case ‘i’:

if (cp[0]==’f’ &&!(map[cp[1]] & (digit | letter)))

&&!(map[cp[2]] & (digit | letter)))

Здесь cp — указатель текущего символа. В массиве map классы

символов кодируются битами.

Поскольку ЛА анализирует каждый символ входного потока, его

скорость существенно зависит от скорости выборки очередного

символа входного потока. В свою очередь, эта скорость во

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

возможных эффективных схем буферизации.

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

длина блока обмена N (рис. 2.13).
N N

|Начало лексемы (cp) |Начало лексемы
Рис. 2.13 Рис. 2.14

Чтобы не читать каждый символ отдельно, в каждую из половин

буфера одной командой чтения считывается N символов. Если на

входе осталось меньше N символов, в буфер помещается

специальный символ (eof). На буфер указывают два указателя:

продвижение и начало. Между указателями размещается текущая

лексема. Вначале они оба указывают на первый символ выделяемой

лексемы. Один из них, продвижение, продвигается вперед, пока

не будет выделена лексема, и устанавливается на ее конец.

После обработки лексемы оба указателя устанавливаются на

символ, следующий за лексемой. Если указатель продвижение

переходит середину буфера, правая половина заполняется новыми

N символами. Если указатель продвижение переходит правую

границу буфера, левая половина заполняется N символами и

указатель продвижение устанавливается на начало буфера.

При каждом продвижении указателя необходимо проверять, не

достигли ли мы границы одной из половин буфера. Для всех

символов, кроме лежащих в конце половин буфера, требуются две

проверки. Число проверок можно свести к одной, если в конце

каждой половины поместить дополнительный ‘сторожевой’ символ
‘#’ (рис. 2.14).
В этом случае почти для всех символов делается единственная

проверка на совпадение с ‘#’ и только в случае совпадения

нужно проверить, достигли ли мы середины или правого конца.

В третьей схеме используются три указателя (рис. 2.15).

Непросмотренная часть буфера заключена между текущим и

границей (граница — это указатель на последний элемент

буфера). Анализ очередной лексемы начинается после

сканирования незначащих пробелов. Если после этого текущий

указывает на ‘#’ в конце буфера, делается перезагрузка буфера

(предполагается, что ‘#’ не может входить в состав лексемы).

Барьер выбирается таким образом, чтобы между барьером и

границей всегда помещалась любая лексема. Если начало

очередной лексемы оказывается правее барьера, то часть буфера

от текущего до границы переписывается левее буфера и буфер


перезагужается. Тем самым начало лексемы конкатенируется с ее

концом. Так обрабатывается ситуация, когда граница буфера

Лекции по конструированию компиляторов

Назва Лекции по конструированию компиляторов
старонка 1/11
Дата канвертавання 26.11.2012
Памер 2.15 Mb.
Тып Книга
В.А.Серебряков

Предлагаемая вниманию читателя книга основана на курсе лекций,

прочитанных автором на факультете вычислительной математики и

кибернетики Московского государственного университета в 1991-

1993 гг. Автор надеется, что издание книги восполнит

существенный пробел в литературе на руссом языке по разработке

Содержание книги представляет собой «классические» разделы

предмета: лексический и синтаксический анализ, организация

памяти, генерация кода. Сделана попытка на протяжении всего

изложения провести единую «атрибутную» точку зрения на процесс

разработки компилятора. В книге не затрагиваются чрезвычайно

важные вопросы глобальной оптимизации и разработки

компиляторов для машин с параллельной архитектурой. Автор

надеется восполнить эти пробелы в будущем.

Книга будет полезной как студентам и аспирантам

программистских специальностей, так и профессионалам в этих

Глава 1. Введение 6

1.1. Место компилятора в программном обеспечении 6

1.2. Структура компилятора 7

Глава 2. Лексический анализ 11

2.1. Регулярные множества и регулярные выражения 13

2.2. Конечные автоматы 14

2.3. Построение детерминированного конечного

автомата по регулярному выражению 17

2.4. Построение детерминированного конечного

автомата с минимальным числом состояний 20

2.5. Программирование лексических анализаторов 22

2.6. Конструктор лексических анализаторов LEX 27

Глава 3. Синтаксический анализ 31

3.1. Основные понятия и определения 31

3.2. Таблично-управляемый предсказывающий разбор 33

3.2.1. Алгоритм разбора сверху-вниз 33

3.2.2. Множества FIRST и FOLLOW 37

3.2.3. Конструирование таблиц

предсказывающего анализатора 39

3.2.4. LL(1)-грамматики 40

3.2.5. Удаление левой рекурсии 41

3.2.6. Левая факторизация 43

3.2.7. Рекурсивный спуск 44

3.2.8. Диаграммы переходов для рекурсивного спуска 46

3.2.9. Восстановление после синтаксических ошибок 48

3.3. Разбор снизу-вверх типа сдвиг-свертка 49

3.3.2. LR(k)-анализаторы 51

3.3.3. LR грамматики 56

3.3.4. Конфликты разбора типа сдвиг-свертка 62

3.3.5. Восстановление после синтаксических ошибок 63

Глава 4. Промежуточные представления программы 64

4.1. Представление в виде ориентированного графа 64

4.2. Трехадресный код 64

4.3. Линеаризованные представления 69

4.4. Организация информации в генераторе кода 72

4.5. Уровень промежуточного представления 73

Глава 5. Элементы теории перевода 74

5.1. Преобразователи с магазинной памятью 74

5.2. Синтаксически управляемый перевод 76

5.3. Атрибутные грамматики 79

5.3.1. Определение атрибутных грамматик 79

5.3.2. Атрибутированное дерево разбора 80

5.3.3. Язык описания атрибутных грамматик 81

Глава 6. Контекстные условия языков программирования 85

6.1. Описание областей видимости и блочной структуры 85

6.2. Структура среды Модулы-2 86

6.3. Занесение в среду и поиск объектов 90

Глава 7. Организация таблиц символов компилятора 98

7.1. Таблицы идентификаторов и таблицы символов 98

7.2. Таблицы идентификаторов 99

7.3. Таблицы символов и таблицы расстановки 102

7.4. Функции расстановки 103

7.5. Таблицы на деревьях 104

7.6. Реализация блочной структуры 108

7.7. Сравнение различных методов реализации таблиц 109

Глава 8. Генерация кода 110

8.1. Модель машины 110

8.2. Динамическая организация памяти 113

8.3. Назначение адресов 122

8.4. Трансляция переменных 124

8.5. Трансляция целых выражений 130

8.6. Распределение регистров при вычислении

арифметических выражений 132

8.7. Трансляция логических выражений 143

8.8. Выделение общих подвыражений 151

8.9. Генерация оптимального кода методами

синтаксического анализа 155

8.9.1. Сопоставление образцов 155

8.9.2. Синтаксический анализ для Т-грамматик 158

8.9.3. Выбор дерева вывода наименьшей стоимости 165

Глава 9. Системы автоматизации построения трансляторов 169

9.1. Система Супер 169

9.2. Система Yacc 172

Глава 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-архитектурами. Естественно, для каждой новой системы

команд требуется полный набор новых компиляторов с

Наконец, бурно развиваются различные параллельные

архитектуры. Среди них отметим векторные, многопроцессорные, с

широким командным словом (вариантом которых являются

суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с

параллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и

другие), через рабочие станции (например, IBM/RS-6000) и

кончая персональными (например, на основе микропроцессора I-

860). Естественно, для каждой из машин создаются новые

компиляторы для многих языков программирования. Здесь

необходимо также отметить, что новые архитектуры требуют

разработки совершенно новых подходов к созданию компиляторов,

так что наряду с собственно разработкой компиляторов ведется и

большая научная работа по созданию новых методов трансляции.

1.2. Структура компилятора

Обобщенная структура компилятора и основные фазы компиляции

показаны на рис. 1.1.

На фазе лексического анализа (ЛА) входная программа,

представляющая собой поток символов, разбивается на лексемы —

слова в соответствии с определениями языка. Основным

формализмом, лежащим в основе реализации лексических

анализаторов, являются конечные автоматы и регулярные

выражения. Лексический анализатор может работать в двух

основных режимах: либо как подпрограмма, вызываемая

синтаксическим анализатором за очередной лексемой, либо как

полный проход, результатом которого является файл лексем.

В процессе выделения лексем ЛА может как самостоятельно

строить таблицы имен и констант, так и выдавать значения для

каждой лексемы при очередном обращении к нему. В этом случае

таблица имен строится в последующих фазах (например, в

процессе синтаксического анализа).

Вход | анализ | +————-+ || Поток лексем +||

| Конечные | || и констант || |

| анализ | +————-+ || Дерево разбора ||

| Контекстно-сво- | || имен и констант|||

| Атрибутные | || + таблица символов || |

| промежуточного | || Промежуточная форма ||

| представления | || (префиксная, пост- ||

| Потоковый | || (ориентированный граф)|| |

| Таблицы решений, | || Объектный ||

На этапе ЛА обнаруживаются некоторые (простейшие) ошибки

(недопустимые символы, неправильная запись чисел,

идентификаторов и др.).

Основная задача синтаксического анализа — разбор структуры

программы. Как правило, под структурой понимается дерево,

соответствующее разбору в контекстно-свободной грамматике

языка. В настоящее время чаще всего используется либо LL(1)-

анализ (и его вариант — рекурсивный спуск), либо LR(1)-анализ

и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный

спуск чаще используется при ручном программировании

синтаксического анализатора, LR(1) — при использовании систем

автоматизации построения синтаксических анализаторов.

Результатом синтаксического анализа является синтаксическое

дерево со ссылками на таблицу имен. В процессе синтаксического

анализа также обнаруживаются ошибки, связанные со структурой

На этапе контекстного анализа выявляются зависимости между

частями программы, которые не могут быть описаны контекстно-

свободным синтаксисом. Это в основном связи «описание-

использование», в частности анализ типов объектов, анализ

областей видимости, соответствие параметров, метки и другие. В

процессе контекстного анализа строится таблица символов,

которую можно рассматривать как таблицу имен, пополненную

информацией об описаниях (свойствах) объектов.

Основным формализмом, использующимся при контекстном

анализе, являются атрибутные грамматики. Результатом работы

фазы контекстного анализа является атрибутированное дерево

программы. Информация об объектах может быть как

рассредоточена в самом дереве, так и сосредоточена в отдельных

таблицах символов. В процессе контекстного анализа также могут

быть обнаружены ошибки, связанные с неправильным

Затем программа может быть переведена во внутреннее

представление. Это делается для целей оптимизации и/или

удобства генерации кода. Еще одной целью преобразования

программы во внутреннее представление является желание иметь

переносимый компилятор. Тогда только последняя фаза (генерация

кода) является машинно-зависимой. В качестве внутреннего

представления может использоваться префиксная или постфиксная

запись, ориентированный граф, тройки, четверки и другие.

Фаз оптимизации может быть несколько. Оптимизации обычно

делят на машинно-зависимые и машинно-независимые, локальные и

глобальные. Часть машинно-зависимой оптимизации выполняется на

фазе генерации кода. Глобальная оптимизация пытается принять

во внимание структуру всей программы, локальная — только

небольших ее фрагментов. Глобальная оптимизация основывается

на глобальном потоковом анализе, который выполняется на графе

программы и представляет по существу преобразование этого

графа. При этом могут учитываться такие свойства программы,

как межпроцедурный анализ, межмодульный анализ, анализ

областей жизни переменных и т.д.

Наконец, генерация кода — последняя фаза трансляции.

Результатом ее является либо ассемблерный модуль, либо

объектный (или загрузочный) модуль. В процессе генерации кода

могут выполняться некоторые локальные оптимизации, такие как

распределение регистров, выбор длинных или коротких переходов,

учет стоимости команд при выборе конкретной последовательности

команд. Для генерации кода разработаны различные методы, такие

как таблицы решений, сопоставление образцов, включающее

динамическое программирование, различные синтаксические

Конечно, те или иные фазы транслятора могут либо

отсутствовать совсем, либо объединяться. В простейшем случае

однопроходного транслятора нет явной фазы генерации

промежуточного представления и оптимизации, остальные фазы

объединены в одну, причем нет и явно построенного

Илон Маск рекомендует:  Что такое код get_extension_funcs
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL