Лекции по конструированию компиляторов глава 5 элементы теории перевода


Содержание

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

Автор Серебряков В.А. Галочкин М.П.
Издательство Едиториал УРСС
Год 1999
Формат PDF

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

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

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

Лекция 6: Элементы теории перевода

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

Определение. Пусть T — входной алфавит , а — выходной алфавит . Переводом (или трансляцией) с языка на язык называется отображение . Если , то цепочка y называется выходом для цепочки x .

Мы рассмотрим несколько формализмов для определения переводов: преобразователи с магазинной памятью, схемы синтаксически управляемого перевода и атрибутные грамматики

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

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

Преобразователем с магазинной памятью (МП-преоб- разователем) называется восьмерка , где все символы имеют тот же смысл, что и в определении МП-автомата, за исключением того, что — конечный выходной алфавит, а D — отображение множества в множество конечных подмножеств множества .

Определим конфигурацию преобразователя P как четверку (q, x, u, y) , где — состояние, — цепочка на входной ленте, — содержимое магазина, — цепочка на выходной ленте, выданная вплоть до настоящего момента.

Если множество D(q, a, Z) содержит элемент (r, u, z) , то будем писать для любых , и : Рефлексивно — транзитивное замыкание отношения будем обозначать .

Цепочку y назовем выходом для x , если для некоторых и . Переводом (или трансляцией), определяемым МП-преобразователем P (обозначается ), назовем множество

Будем говорить, что МП-преобразователь P является детерминированным (ДМП-преобразователем), если выполняются следующие условия:

  1. для всех и множество D(q, a, Z) содержит не более одного элемента,
  2. если , то для всех .

Пример 5.1. Рассмотрим перевод отображающий каждую цепочку , в которой число вхождений символа a равно числу вхождений символа b , в цепочку y = (ab) n , где n — число вхождений a или b в цепочку x . Например, .

Этот перевод может быть реализован ДМП-преобразователем P = (, qf>, , , , D, q, Z, f>) c функцией переходов:

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

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

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

Определение. Cхемой синтаксически управляемого перевода (или трансляции, сокращенно: СУ-схемой) называется пятерка , где

(1) N — конечное множество нетерминальных символов;

(2) T — конечный входной алфавит ;

— конечный выходной алфавит;

R — конечное множество правил перевода вида

где и вхождения нетерминалов в цепочку v образуют перестановку вхождений нетерминалов в цепочку u , так что каждому вхождению нетерминала B в цепочку u соответствует некоторое вхождение этого же нетерминала в цепочку v ; если нетерминал B встречается более одного раза, для указания соответствия используются верхние целочисленные индексы;

(5) S — начальный символ, выделенный нетерминал из N .

Определим выводимую пару в схеме Tr следующим образом:

(1) (S, S) — выводимая пара, в которой символы S соответствуют друг другу;

(2) если (xAy; x’Ay’) — выводимая пара, в цепочках которой вхождения A соответствуют друг другу, и A -> u, v — правило из R , то (xuy; x’vy’) — выводимая пара. Для обозначения такого вывода одной пары из другой будем пользоваться обозначением (xAy, x’Ay’) => (xuy, x’vy’) . Рефлексивно-транзитивное замыкание отношение обозначим => * .

Переводом , определяемым СУ-схемой Tr , назовем множество пар

Если через P обозначить множество входных правил вывода всех правил перевода, то G = (N, T, P, S) будет входной грамматикой для Tr .

СУ-схема называется простой, если для каждого правила A -> u, v из R соответствующие друг другу вхождения нетерминалов встречаются в u и v в одном и том же порядке.

Перевод, определяемый простой СУ-схемой, называется простым синтаксически управляемым переводом (простым СУ-переводом).

Пример 5.2. Перевод арифметических выражений в ПОЛИЗ ( польскую инверсную запись) можно осуществить простой СУ-схемой с правилами

E -> E + T ET+
E -> T T
T -> T * F TF+
T -> F F
F -> id id
F -> (E) E .

Найдем выход схемы для входа id * (id + id) . Нетрудно видеть, что существует последовательность шагов вывода

переводящая эту цепочку в цепочку id id id + * .

Рассмотрим связь между переводами, определяемыми СУ- схемами и осуществляемыми МП-преобразователями [2].

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

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

n1.doc 1251kb. 30.05.2012 00:24 скачать

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) лексема выдается при каждом обращении к

Илон Маск рекомендует:  Что такое код chr

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

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

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

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

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

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

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

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

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

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

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

Файл лексем «Дай лексему»
Рис. 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).

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

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

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

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

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

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

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

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

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

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

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

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

Лекции по конструированию компиляторов глава 5 элементы теории перевода

Описание Описание Раздел

типа переменной операторов

| | В то же время ясно, что первое

более эффективно, чем второе.

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

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

for, while и т.д.), а могут содержаться в виде переходов. В

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

самой структуры (например, для оператора for — информация о

переменной цикла, которую, может быть, разумно хранить на

регистре, для оператора case — информация о таблице меток и

т.д.). Во втором случае представление проще и унифицированней.

Некоторые формы промежуточного представления лучше годятся

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

для перемещения кода), некоторые — хуже (например, префиксная

запись для этого плохо подходит).

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

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

называется восьмерка P=(Q,T,Г,П,Ф,q0,Z0,F), где Q — множество

состояний, T — конечный входной алфавит, Г — конечный алфавит

магазинных символов, П — конечный выходной алфавит, Ф —

отображение множества Qx(T U )xГ в множество конечных

подмножеств множества QxГ*xП*, q0 Пример 5.1. Перевод арифметического выражения в ПОЛИЗ.
ПОЛИЗ — Польская инверсная запись или, что то же,

постфиксная запись арифметических выражений. Трансляция может

определяться следующим ДМП:
Q=;

T=<буквы,+,*,(,),$>, здесь $ — концевой маркер;

| Г | Q | T || Г* | Q | П |

| Z0 | q0 | буква || z | q0 | буква |

| Z0 | q0 | ( || z( | q0 | |

| Z0 | q0 | проч || z | проч | |

| Стек |Состояние| Вход |Выход|

Последовательность состояний автомата и магазина на строке

a*(b+c) изображены в таблице рис. 5.2.

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

сокращенно: СУ-схемой) называется пятерка Tr=(N,T,П,R,S), где
N — конечное множество нетерминальных символов;
T — конечный входной алфавит;
П — конечный выходной алфавит;
R — конечное множество правил перевода вида A->u, A1=v1,

A2=v2, . , Am=vm, удовлетворяющих следующим условиям:
— каждый символ, входящий в v1, . vm, либо принадлежит

П, либо является Bk для B u называют входным правилом вывода, Ai — переводом

нетерминала A и Ai=vi — элементом перевода, связанным с этим

правилом перевода. Если через P обозначить множество входных

правил вывода всех правил перевода, то G=(N,T,P,S) будет

входной грамматикой для Tr. Если в СУ-схеме Tr нет двух правил

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

семантически однозначной. Выход СУ-схемы определим снизу

вверх. С каждой внутренней вершиной n дерева разбора (во

входной грамматике), помеченной A, свяжем одну цепочку для

каждого Ai. Эта цепочка называется значением (или переводом)

символа Ai в вершине n. Каждое значение вычисляется

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

перевода Ai=vi, определенных в прямых потомках вершины n.

Переводом t(Tr), определяемым СУ-схемой Tr, назовем

для Tr и y — значение выделенного символа перевода S в корне

этого дерева>. Если Tr=(N,T,П,R,S) — СУ-схема, то т(Tr)

называется синтаксически управляемым переводом (СУ-переводом).
Пример 5.2. Рассмотрим формальное дифференцирование

выражений, включающих константы 0 и 1, переменную x и функции

sin, cos, + и *. Такие выражения порождает грамматика
E -> E+T | T

F -> (E) | sin(E) | cos(E) | x | 0 | 1

Свяжем с каждым из E, T и F два перевода, обозначенных

индексом 1 и 2. Индекс 1 указывает на то, что выражение не

дифференцировано, 2 — что выражение продифференцировано.

Формальная производная — это E2. Законы дифференцирования

Эти законы реализуются СУ-схемой:
E -> E+T E1=E1+T1 F -> cos(E) F1=cos(E1)

E -> T E1=T1 F -> x F1=x

T -> T*F T1=T1*F1 F -> 0 F1=0

F -> ( E ) F1=(E1) F -> 1 F1=1

F -> sin(E) F1=sin(E1)


Дерево вывода для sin(cos(x))+x приведено на рис. 5.3.
Теорема 5.1. Если число вхождений каждого нетерминала в слове

v не превосходит 1, то t(Tr) является КС-языком. Обратное не

Здесь входной язык =1>, выходной . Выходной

язык не КС.
Теорема 5.2. Для каждого магазинного преобразователя

существует эквивалентная СУ-схема [5].
Обратное, вообще говоря, не верно.
Определение. Семантически однозначная СУ-схема Tr=(N,T,П,R,S)

называется простой, если для каждого правила A->u,v из R

соответствующие друг другу вхождения нетерминалов встречаются

в u и v в одном и том же порядке.
E E1=sin(cos(x))+x

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

Назва Лекции по конструированию компиляторов
старонка 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) — при использовании систем

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лекции по конструированию компиляторов глава 5 элементы теории перевода

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

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

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

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

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

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

n1.doc 1251kb. 30.05.2012 00:24 скачать

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. Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. — М.: Вильямс, 2001.

  2. Карпов Ю. Г. Основы построения трансляторов. — М.: BHV, 2005.
  3. Свердлов С. З. Языки программирования и методы трансляции. — М.: Питер, 2007.
  4. Опалева Э. А., Самойленко В.П. Языки программирования и методы трансляции. — М.: BHV, 2005.

Лекция 1

Введение в компиляцию

Что такое компилятор. Исходный и целевой язык.

Разновидности компиляторов

  • Интерпретаторы
  • Форматтеры текста
  • Статические анализаторы кода
  • Препроцессоры
    • макросы define
    • включение файлов #include
    • условная компиляция #ifdef
    • расширения языка, которые препроцессор переводит в код на языке

Фазы компиляции

  • Лексический анализ (сканирование)
  • Синтаксический анализ (разбор, „парсинг“)
  • Семантический анализ

На примере выражения p := i + r * 60

  • Обнаружение ошибок. Лексические, синтаксические и семантические ошибки.
  • Генерация промежуточного кода

На примере трехадресного кода

  • Оптимизация кода
  • Генерация кода (основное — назначение переменных регистрам)

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

Математическим обеспечением фаз лексического и синтаксического анализа является теория формальных языков. Обычно лексические анализаторы генерируются с помощью регулярных выражений.

Синтаксический анализ основывается на теории контекстно-свободных (КС) грамматик. Общая форма КС-грамматики не позволяет разбирать язык достаточно простым (в частности, автоматически сгенерированным) парсером, потому языки программирования обычно принадлежат одному из нескольких специальных подклассов КС-языков (LL, LR, LALR), которые проще разбирать и некоторые из которых будут подробно изучены в курсе.

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

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

На этапе построения семантического дерева строится таблица символов — в нее заносятся имена, присутствовавшие в исходном тексте, к ним добавляются такие атрибуты как тип, отведённая память, область видимости.

Лекция 2

Группировка фаз

  • Front-end и back-end компиляторы.

Перечисленные выше фазы обычно группируются в два модуля — front-end и back-end, в зависимости от того, к какой стороне процесса компиляции они ближе, к исходному языку или к машинному коду для целевой платформы, соответственно. Возможность отдельно разрабатывать front-end и back-end повышает эффективность труда разработчиков компиляторов — насколько, зависит от эффективности используемого внутреннего представления, связывающего эти два модуля. В последнее время всё чаще выделяют middle-end — части компилятора, активно работающие с промежуточным представлением.

  • Проходы. Группировка фаз компилятора в проходы (например, объединение фаз лексического, синтаксического, семантического анализа и генерации кода).

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

  • Уменьшение количества проходов (на примере предварительного описания подпрограмм). Технология обратных поправок.

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

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

  • Генераторы лексических анализаторов (сканеров)
  • Генераторы синтаксических анализаторов (парсеров)
  • Автоматические генераторы кода

Компиляторы компиляторов

  • Lex + Yacc
  • Flex + Bison
  • CoCo
  • Antlr
  • Gold Parser Builder
  • GPLex + GPPG

Порождающие грамматики

Определение. Символы: терминалы и нетерминалы. Продукции (правила вывода). Стартовый символ.

Опр. формальной грамматики (порождающей грамматики Хомского)

V = Σ + N — множество всех нетерминалов и терминалов

X * — множество всех цепочек символов из X

Классификация формальных грамматик по Хомскому (1956 г.)

  • Грамматика типа 0 (общего вида). Правила имеют вид α→β
  • Грамматика типа 1 (контекстно зависимая, КЗ)

Правила имеют вид αAβ → αγβ. γ принадлежит V + , т.е. грамматика является неукорачивающей Добавляется также правило S → ε α,β называются левым и правым контекстом

  • Грамматика типа 2 (контекстно свободная, КС)

Правила имеют вид A → α. α ∊ V* Наиболее близкая к БНФ

  • Грамматика типа 3 (автоматная, регулярная)

Правила имеют вид A → aB, A → a, A → ε (правая регулярная грамматика) Автоматные языки содержатся в КС языках

Пример. Грамматика, порождающая язык правильных скобочных выражений.

Порождение (вывод)

Далее будем говорить только о КС-грамматиках.

Грамматика G порождает (выводит) цепочки из стартового символа, используя правила вывода.

Опр. Сентенциальной формой грамматики называется строка, которая может быть выведена из стартового символа.

Опр. Предложением (сентенцией) грамматики называется сентенциальная форма, состоящая из одних терминалов.

Опр. Языком над алфавитом (словарём) Σ называется подмножество L множества Σ * .

Опр. Языком L(G), порождаемым грамматикой G, называется множество всех ее предложений:

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

Утв. Проблема эквивалентности КС-грамматик алгоритмически неразрешима.

Левый, правый вывод (порождение). Деревья вывода (разбора)

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

Левый и правый вывод для предложения i + i * i

Дерево вывода (дерево разбора) строки предложения. В отличие от порождения, из него исключена информация о порядке вывода.

Крона дерева разбора — цепочка меток листьев слева направо

Неоднозначные грамматики

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

Пример неоднозначной грамматики. Грамматика арифметических выражений.

Два дерева разбора для цепочки i + i * i

Преобразование в эквивалентную однозначную грамматику:

Пример неоднозначной грамматики. Грамматика условного оператора

Два дерева разбора для цепочки if b then if b then a

Преобразование в эквивалентную однозначную грамматику:

Утверждение. Проблема неоднозначности произвольной КС-грамматики алгоритмически не разрешима

Леворекурсивные грамматики, их проблемы. Алгоритм устранения левой рекурсии.

Перевод (трансляция)

Ранее мы решали вопрос о принадлежности некоторой цепочки α интересующему нас языку L, задаваемому грамматикой G. Но задача компиляции шире: не только распознать входную цепочку, но и сгенерировать выходную.

Определение. Пусть Σ и Δ — два алфавита (называемые „входным“ и „выходным“ соответственно). L1 ⊂ Σ*, L2 ⊂ Δ*. Переводом с языка L1 на язык L2 называется отображение τ: L1 → L2.

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

Схема синтаксически управляемого перевода (СУ-схема)

Неформальное определение. СУ-схема это грамматика, в которую с каждым синтаксическим правилом встроен элемент перевода.

Пример. Перевод алгебраического выражения в ПОЛИЗ (польская инверсная запись). Запишем правила грамматика вместе с элементами перевода.

Правило Элемент перевода
E → E + T E = E T +
E → T E = T
T → T * P T = T P *
T → P T = P
P → (E) P = E
P → P =

Выведем цепочку a * (b + c) и одновременно переведём её в ПОЛИЗ: a b c + * (как обычно, используем левый вывод):

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

Причём α и β в каждом конкретном правиле содержат одни и те же нетерминалы с точностью до перестановки.

Далее считаем, что задана некоторая СУ-схема T = (N, Σ, Δ, R, S).

Определение. Входная грамматика, соответствующая СУ-схеме T, это четвёрка

Определение. Выходная грамматика, соответствующая СУ-схеме T, это четвёрка

Определение. СУ-перевод (СУ-трансляция) это множество

обозначаемое обычно τ(T).

СУ-перевод можно понимать как трансформацию синтаксических деревьев (соответствующих выводу входной и выходной цепочек).

Транслирующие грамматики

Позволяют решать задачу перевода в более сложных случаях, чем СУ-схемы. ТГ это разновидность КС-грамматик, где символы (терминалы) разделены на два множества, Σi и Σa (a от action), называемые „входными“ и „операционными“ соответственно. При использовании ТГ, чтобы различать элементы Σi и Σa, будем заключать последние в фигурные скобки, ‘<’, ‘>’, считая получившиеся на письме три символа одним символом алфавита.

Пример. Перевод простого алгебраического выражения в ПОЛИЗ .

Определение. Пусть α ∊ (Σi ∪ Σa)*. Тогда α называется активной цепочкой. Входные (операционные) символы активной цепочки, записанные отдельно в том же порядке, как они встречались в ней, образуют входную (операционную) цепочку.

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

Атрибутные грамматики и трансляция

В АГ с каждым символом грамматики может быть связан один или несколько атрибутов. Для каждого синтаксического правила вводятся семантические правила, устанавливающие функциональные зависимости между атрибутами.

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

Пример. Вычисление простого арифметического выражения .

  1. Синтезированные — значения таких атрибутов зависят только от значений атрибутов потомков в дереве разбора.
  2. Унаследованные — значения таких атрибутов зависят от значений атрибутов родительского узла, узлов-братьев и сестёр (дочерних для родительского), а также других атрибутов самого узла.

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

Понятие синтаксического анализатора.

Нисходящие (top-down) и восходящие (bottom-up) синтаксические анализаторы

Нисходящий синтаксический анализ

Опр. Синтаксический анализатор, работающий методом рекурсивного спуска и не требующий откатов, называется предиктивным синтаксическим анализатором.

Нерекурсивный предиктивный анализ

Схема работы со стеком, таблицей разбора, входным буфером

Алгоритм нерекурсивного предиктивного анализа

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

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

Определение LL(1) грамматики. Пояснение названия.

Утв. LL(1) грамматика не может быть леворекурсивной или неоднозначной.

Эквивалентное определение LL(1) грамматики.

Восстановление после ошибок в предиктивном анализе.

Восходящий синтаксический анализ

Наиболее распространенная разновидность — ПС-анализ (перенос-свертка — shift-reduce)

Понятие основы. Примеры.

Обращенное правое порождение и обрезка основ.

Стековая реализация ПС-анализа. Основные операции:

Утв. Основа всегда находится на вершине стека и никогда — внутри него. Доказательство.

Понятие активного префикса.

LR-анализаторы. SLR, канонический LR и LALR анализаторы.

Общая схема и алгоритм LR-анализа. Пример.

Неоднозначности вида shift-reduce и их разрешение.

Генераторы лексических и синтаксических анализаторов

Создание лексического анализатора (сканера) с помощью gplex

Общая структура .l файла

Особенности .l файла gplex

Возвращение типов лексем

Лексемы идентификаторов, чисел.

Начальные состояния сканера, их изменение, использование для вырезания комментариев:

Создание синтаксического анализатора с помощью gppg

Общая структура .y файла

Задание типов лексем

Таблица приоритетов и ассоциативности

Особенности .y файла gppg

  1. Простейший калькулятор
    • Простейший калькулятор с приоритетом операций
    • Создание дерева разбора программы
    • Преобразование в XML
    • Добавление переменных. Представление о таблице символов
    • Добавление присваивания
    • Добавление типов
    • Добавление управляющих конструкций

Лекции по конструированию компиляторов глава 5 элементы теории перевода

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

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

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

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

Илон Маск рекомендует:  Квадратный корень
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL