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

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

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

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

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

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

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

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

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

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

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

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

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

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

Компилятор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тогда, например, для предыдущего выражения получим следующую

4: if >
5: if >
6: if >
3: if >
При каждом конкретном наборе данных эта программа превращается

в программу вычисления логического значения.
Утверждение 3. В каждой строке программы, сформированной

предыдущей атрибутной схемой, одна из меток совпадает с меткой

Действительно, по правилам наследования атрибутов TrueLab и

FalseLab, в правилах для дизъюнкции и конъюнкции либо

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

поддерева. Кроме того, как значение FalseLab, так и значение

TrueLab, передаются в правое поддерево от предка. Таким

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

TrueLab или FalseLab, равную метке правого брата

соответствующего поддерева. Учитывая порядок генерации команд,

Дополним теперь атрибутную грамматику следующим образом:
RULE

FalseLab :=False; TrueLab :=True;

BoolExpr ::= BoolExpr & BoolExpr

FalseLab :=FalseLab ; TrueLab :=NodeLab ;

FalseLab :=FalseLab ; TrueLab :=TrueLab ;

Sign :=false; Sign :=Sign .

BoolExpr ::= BoolExpr V BoolExpr

TrueLab :=TrueLab ; FalseLab :=NodeLab ;

FalseLab :=FalseLab ; TrueLab :=TrueLab ;

Sign :=true; Sign :=Sign .

BoolExpr ::= not BoolExpr

FalseLab :=TrueLab ; TrueLab :=FalseLab ;

then else GOTO FalseLab >

else else GOTO TrueLab >;

Правила наследования атрибута Sign приведены на рис. 8.24.
false | true | false | true |

true false true true false false false true

false true
Рис. 8.24

Программу желательно сформировать таким образом, чтобы else-

метка была как раз меткой следующей вершины. Как это можно

сделать, следует из утверждения 4.
Утверждение 4. В каждой терминальной вершине, метка ближайшего

правого для нее поддерева равна значению атрибута FalseLab

этой вершины, тогда и только тогда, когда значение атрибута

Sign этой вершины равно true, и наоборот, метка ближайшего

правого для нее поддерева равна значению атрибута TrueLab этой

вершины, тогда и только тогда, когда значение атрибута Sign

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

атрибутной грамматики следующим образом:
RULE

В свою очередь, при генерации машинных команд это правило
можно заменить на следующее:
RULE

Если элементом логического выражения является сравнение, то

генерируется команда, соответствующая знаку сравнения (beq для

=, bne для <>, bge для >= и т.д.), если атрибут sign

соответствующей вершины имеет значение true, и отрицание (bne

для =, beq для <>, blt для >= и т.д.), если атрибут sign имеет

Приведем несколько примеров. Выражение A AND (B OR C)

транслируется в последовательность команд рис. 8.25. Выражение

(NOT((A=B)OR(C<>D)))AND(not((E H))) транслируется в

последовательность команд рис. 8.26.
TST A CMP A,B

BEQ False BEQ False

BNE True BNE False

BEQ False BGE False

False:. . . BGT False

False:
Рис. 8.25 Рис. 8.26

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

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

1. Поскольку на линейном участке переменной может быть

несколько присваиваний, то при выделении общих подвыражений

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

присваивания. Для этого каждая переменная снабжается номером.

Вначале номера всех переменных устанавливаются равными 0. При

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

2. Выделение общих подвыражений осуществляется при обходе

дерева выражения снизу вверх слева направо. При достижении

очередной вершины (пусть операция, примененная в этой вершине,

есть бинарная ‘op’; в случае унарной операции рассуждения те

же) просматриваем общие подвыражения, связанные с op. Если

имеется выражение, связанное с op и такое, что его левый

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

выражения, а правый операнд — общее подвыражение с правым

операндом нового выражения, то объявляем новое выражение общим

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

найденное общее выражение. Базисом построения служит

переменная: если операндами обоих выражений являются

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

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

оно заносится в список операций, связанных с op (рис. 8.27).
| /\ /\ ].Count:=Table[Entry ].Count+1.

with Node ^ do with Table[Entry ] do

and Last^.VarCount = Count then

IntExpr ::= Op IntExpr IntExpr

var L:pointer to Listype;

if Node ^.Flag and Node ^.Flag then

and (Node =L^.Right)

включить данное в список для операции >

Рассмотрим теперь некоторые простые правила распределения

регистров при наличии общих подвыражений. Если число регистров

ограничено, можно выбрать один из следующих двух вариантов.

1. При обнаружении общего подвыражения с подвыражением в уже

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

регистрами) проверяем, расположено ли его значение на

регистре. Если да, и если регистр после этого не менялся,

заменяем вычисление поддерева на значение в регистре. Если

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

2. Вводим еще один проход. На первом проходе распределяем

регистры. Если в некоторой вершине обнаруживается, что ее

поддерево общее с уже вычисленным ранее, но значение регистра

потеряно, то в такой вершине на втором проходе необходимо

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

Выигрыш в коде будет, если стоимость команды сброса регистра +

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

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

стоимость команды MOVE известна, можно сравнить стоимости и

принять оптимальное решение: то ли метить предыдущую вершину

для сброса, то ли вычислять полностью поддерево.

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

анализа
8.9.1. Сопоставление образцов
Техника генерации кода, рассмотренная выше, основывалась на

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

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

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

изложенный в настоящей главе.

Этот подход основан на понятии «сопоставления образцов»:

командам машины сопоставляются некоторые «образцы», вхождения
которых ищутся в промежуточном представлении программы, и

делается попытка «покрыть» промежуточную программу такими

образцами. Если это удается, то по образцам восстанавливается

ПРОЕКТИРОВАНИЕ И КОНСТРУИРОВАНИЕ КОМПИЛЯТОРОВ

    Андрей Миллер 4 лет назад Просмотров:

1 Р.ХАНТЕР ПРОЕКТИРОВАНИЕ И КОНСТРУИРОВАНИЕ КОМПИЛЯТОРОВ Перевод с английского С. М. КРУГОВОЙ Под редакцией В. М. САВИНКОВА МОСКВА ФИНАНСЫ И СТАТИСТИКА

2 ББК X19 Хантер Р. XI9 Проектирование и конструирование компиляторов/ Пер. с англ.; Предисл. В. М. Савинкова. М.: Финансы и статистика, с., ил. В пер.: 1 р. 30 к экз. В книге известного английского автора рассматриваются проблемы проектирования и построения компиляторов для языков программирования высокого уровня, в частности Алгола 60, ПЛ/1, Алгола 68, Паскаля и Ады. Основное внимание уделяется целям проектирования надежных компиляторов и средствам их достижения. Практические вопросы разъясняются посредством упражнений. Для математиков, разработчиков программного обеспечения ЭВМ и АСУ, специалистов по алгоритмическим языкам, студентов к аспирантов вузов X ББК (01) 846Ф7! by John Wiley & Sons Ltd. Перевод на русский язык, предисловие, «Финансы и статистика»,

3 ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ Структурные изменения парка ЭВМ, быстро возрастающая роль малых и особенно персональных ЭВМ для массовых пользователей-непрограммистов не нарушили основополагающего значения алгоритмических языков в программировании. «Программистский бум» 80-х годов связывают прежде всего с такими алгоритмическими языками, как Паскаль, Си, Ада и др., с помощью которых развивается базовое программное обеспечение ЭЕГМ всех типов и разрабатываются программные средства для непрограммистов: системы запросов (простых и сложных), генераторы отчетов, графические интерпретаторы, генераторы прикладных программ, параметризованные пакеты прикладных программ, языки программирования сверхвысокого уровня. Развитие архитектуры вычислительных машин и систем и аппаратная поддержка многих функций традиционного «софтвера» сохранили алгоритмический уровень спецификации задач. Следовательно, такие алгоритмические языки, как Ада и Паскаль, и соответствующие компиляторы остаются инструментальным средством не только профессиональных программистов, но и других специалистов, занимающихся постановкой и решением задач на ЭВМ. Как известно, алгоритмические языки бесполезны без надежных и эффективных трансляторов. Преимущественное распространение языка Алгол 60 в нашей стране в е годы было связано, прежде всего, со своевременной разработкой трансляторов для основных типов отечественных ЭВМ. К сожалению, активная роль разработчиков компиляторов во внедрении новых перспективных алгоритмических языков заметно снизилась. Примером тому может служить язык Паскаль, опубликованный его автором еще в 1971 г. и ожидавший около 10 лет своего компилятора на ЕС ЭВМ. Советским специалистам в области программирования предлагается перевод новой книги Р. Хантера «Проектирование и конструирование компиляторов» не только для того, чтобы в какой-то мере обеспечить подготовку высококвалифицированных разработчиков компиляторов. В большей степени эта книга будет способствовать познанию специалистами процесса компиляции, пониманию работы компиляторов и как следствие лучшему применению языков программирования. Без познания этого процесса, без необходимого теоретического уровня и практического опыта в программировании нельзя рассчитывать на своевременную разработку нового поколения языков спецификации очень высокого уровня. Поскольку развитие программирования обеспечивается применяемыми алгоритмическими языками и компиляторами с этих языков, книга Р. Хантера, детально описывающая известные методы построения компиляторов, безусловно, сыграет свою положительную роль в этом процессе. Предлагаемая книга является первым практическим пособием, в котором все составные части компилятора и сам механизм их проектирования достаточно полно раскрыты с использованием средств, хорошо известных программистам. И хотя изложение материала опирается на еще не получивший широкого распространения Алгол 68, для чтения книги достаточно знания одного из массовых алгоритмических языков (Алгола 60, Фортрана или ПЛ/1). Основная часть книги посвящена контекстно-свободным грамматикам, применяемым для разбора текста исходных программ. Читателю становится понятно, почему грамматики алгоритмических языков, а следовательно, и сами языки не могут быть выбраны произвольно и должны быть предельно простыми. На примере LL(1)- 5

4 метода разбора автор показывает его преимущества: отсутствие возвратов, пропорциональность времени разбора длине программы хорошие диагностические возможности, минимальный размер таблиц разбора, применимость к широкому классу языков. Значительная роль отведена автором регулярной грамматике, или в иерархической классификации Хомского грамматике типа 3 и регулярным выражениям. Поскольку из регулярных выражений получают регулярные множества, с которыми устанавливаются алгоритмические соответствия строк языка, такие свойства регулярных множеств используются разработчиками компиляторов. Например, проверку строк языка в этом случае организуют конечным автоматом, так как существует полное соответствие между регулярными выражениями (грамматиками типа 3) и конечными автоматами. На этом основании лексический анализатор может быть представлен различными автоматами для распознавания идентификаторов, чисел, зарезервированных слов и т.п. О многих важных свойствах компиляторов читатель получит наглядное представление благодаря хорошо подобранным и простым примерам. Специально рассмотрен случай включения в грамматику вызовов действий не только для генерирования кода, но и для построения таблиц символов и обращения к ним, размещения объектной программы в соответствии с условием и др. Большой интерес представляет механизм распределения памяти для параллельной обработки, допускаемой в языке. Цели создания компилятора в некоторой степени противоречивы. Так, эффективность объектного кода зависит от размера программы, трудно сделать небольшой компилятор, работающий надежно и хорошо исправляющий ошибки. Общее количество проходов, выбор промежуточного языка эти и многие другие свойства компиляторов усложняют их разработку. Вот почему так важны четкие требования к определению исходного языка, включая уточнения грамматики, приведенные в книге Р. Хантера. Практически ни один из вопросов, связанных с проектированием компиляторов, не упущен автором. Доходчивость и строгость изложения позволяют отнести книгу Р. Хантера к числу практических и учебных пособий, способствующих общему повышению программистской грамотности. Такая книга необходима сегодня программистам, студентам и аспирантам вузов, а также разработчикам информационных систем. В. М. Савинков 6

5 ПРЕДИСЛОВИЕ В книге рассматриваются в первую очередь вопросы проектирования, а затем и построения компиляторов для языков программирования высокого уровня. Главное внимание уделяется целям разработки компиляторов и средствам их достижения. Освещаются также практические аспекты построения компиляторов. В основу книги легла работа» по созданию компиляторов, проводимая в последние годы на факультете вычислительных наук в Стратклайдском университете. Книга может служить учебным пособием для студентов старших курсов, и именно такое применение она нашла в Стратклайдском университете. В ней обсуждается реализация языков с блочной структурой (Алгола 60, ПЛ/1, Алгола 68, Паскаля и Ады) с учетом особенностей конкретных языков. Описание алгоритмов приводится на реальном языке программирования (Алголе 68), но это не препятствует их пониманию, даже если студент незнаком сданным языком. Каждая глава завершается упражнениями, цель которых помочь студентам лучше разобраться в построении компиляторов. В заключение книги читателю предлагаются схематические ответы на упражнения к гл. I 12. В гл. 1 рассматривается процесс компиляции в целом, а также связь между языками программирования высокого уровня и типичными ЭВМ. В Гл. 2 дается формальное определение языков программирования, Гл. 3 посвящается лексическому анализу, а Гл. 4 и 5 методам синтаксического анализа сверху вниз и снизу вверх. В гл. 6 описывается применение бесконтекстной грамматики в качестве рамок для действий компилятора, а в Гл. 7 — проектирование компиляторов, причем особое внимание уделяется проектированию многопроходных компиляторов. Структура таблиц символов и видов (или типов) для языков с комплексными типами обсуждается в Гл. 8. Гл. 9 знакомит читателя с локальным и глобальным распределением памяти. Гл. 10 и 11 посвящены вопросам генерирования кода и использования, не зависящего от машины промежуточного кода. В гл. 12 обсуждаются методы исправления и диагностики ошибок, а в гл. 13 высказываются некоторые соображения относительно построения надежных компиляторов. 7

6 Глава 1. ПРОЦЕСС КОМПИЛЯЦИИ Программы, написанные на языках программирования высокого уровня (или проблемно-ориентированных языках), перед выполнением на ЭВМ должны транслироваться1 в эквивалентные программы, написанные в машинном коде. Языки высокого уровня появились в середине 50-х годов, примерами первых таких языков могут служить Фортран и Кобол, а примерами недавно созданных Алгол 68, Паскаль и Ада. Программа, которая транслирует любую программу, написанную на конкретном языке высокого уровня, в эквивалентную программу на другом языке (обычно это код машины), называется компилятором. Компилирование программы включает анализ определение предусмотренного результата действия программы и последующий синтез генерирование эквивалентной программы в машинном коде. В процессе анализа компилятор должен выяснить, является ли входная программа недействительной в каком-либо смысле (т. е. принадлежит ли она к языку, для которого написан данный компилятор), и если она окажется недействительной, выдать соответствующее сообщение программисту. Этот аспект компиляции называется обнаружением ошибок. В построении компиляторов за последние двадцать пять лет достигнуты значительные успехи. Первые компиляторы использовали специальные методы, были медленными и не носили структурного характера. (Краткая история написания компиляторов изложена в [7].) В современных компиляторах применяются более системные методы; эти компиляторы относительно быстрые и строятся таким образом, чтобы как можно более четко выделять отдельные аспекты компиляции. Существует и другой подход. Он состоит в том, чтобы вместо трансляции каждой программы в машинный код и последующего ее выполнения программа сначала транслировалась на промежуточный язык, а — затем транслировался и выполнялся каждый оператор промежуточного языка (когда он встретится). Программа, транслирующая и выполняющая программу, написанную на таком языке высокого уровня, называется интерпретатором. Применение интерпретатора вместо компилятора имеет следующие преимущества: Передавать сообщения об ошибках пользователю часто бывает легче в терминах оригинальной программы. Версия программы на промежуточном языке нередко оказывается компактнее, чем машинный код, выданный компилятором. Изменение части программы не требует перекомпиляции всей программы. Диалоговые языки, такие, как Бейсик, часто реализуются посредством интерпретатора. Промежуточным языком обычно служит некая форма обратной польской записи (см. разд. 10.1). Хорошим пособием по реализации диалоговых языков может быть работа [13]. Основной недостаток интерпретаторов заключается в том, что эти программы обычно пропускаются относительно медленно, так как операторы промежуточного кода должны транслироваться всякий раз, когда они выполняются, хотя временные издержки не так уж велики (они зависят от конструкции промежуточного языка). Применяется метод смешанного кода [15], в котором наиболее часто выполняемая часть интерпретируется. При этом экономится память, поскольку часть программы, которая должна интерпретироваться, будет, по 8

7 всей вероятности, намного компактнее, чем скомпилированный код. Развитием этой идеи является «отбрасывающее» компилирование [12]. В настоящей книге речь идет в основном о компиляторах, а не об интерпретаторах, хотя многие рассматриваемые принципы применимы и к тем, и к другим. Говоря о компиляторах, мы будет называть компилируемую программу исходной программой (или исходным текстом), а выдаваемый машинный код объектным кодом (рис. 1.1). Аналогичным образом язык высокого уровня может называться исходным языком, а машинный объектным языком. В гл.. 1 мы изучим характеристики языков высокого уровня и типичных ЭВМ, а. также различные аспекты процесса компиляции. Для этого нам нужно иметь общее представление о построении компиляторов СВЯЗЬ МЕЖДУ ЯЗЫКАМИ И МАШИНАМИ Хотя с точки зрения пользователя (и разработчика) различия между языками высокого уровня могут быть весьма значительными, мы здесь хотим подчеркнуть сходные, черты этих языков, чтобы показать, какие задачи должен выполнять компилятор. Под типичными языками высокого уровня мы подразумеваем языки Бейсик, Фортран, ПЛ/1, Паскаль, Алгол 68 и (возможно, в несколько меньшей степени) Кобол. Фрагменты программ, которыми мы иллюстрируем основные положения, написаны на Алголе 68, но они в равной степени могли бы быть написаны на любом другом языке, поэтому у читателей, не знакомых с Алголом 68. не должно возникать в связи с этим никаких серьезных проблем. Языки Общими средствами большинства языков высокого уровня являются: 1. Выражения и присваивания Значение выражения обычно можно вычислить и (помимо прочего) присвоить какой-либо переменной, например где В, С, Е и F имеют соответствующие значения. 2. Условные выражения Значение выражения или результат действия оператора может зависеть от логического значения (истинности), например значением которого будет X+Y, если А =В> и X Y в противном случае. 9

8 3. Циклы Последовательность действий может выполняться несколько раз. Например Последовательность выполняется 10 раз. 4. Ввод-вывод Существуют обычно простые программы для чтения или печати значений, например: для чтения значений х, у и z и для печати значений a, b и с. 5. Процедуры, подпрограммы, функции Программе обычно можно задать определенную структуру, разделив ее на модули (и, возможно, подмодули и т.д.) и записывая каждый модуль в виде отдельной процедуры или подпрограммы. Так, если в программе время от времени производится вычисление среднего значения массива вещественных чисел, можно написать следующую процедуру: и, допуская, что а объявлено как можно вызвать процедуру average, например, следующим образом: 10

9 6. Блоки Всем программам нужна память для хранения значений переменных и т. п. Большинство языков дают возможность хранить переменные, появляющиеся в различных частях программы, в одной и той же памяти. В языках программирования это обычно обеспечивается с помощью блочной структуры, а блок определяется как часть программы, содержащая какие-либо объявления переменных, например причем объем памяти для а и Ь выделяется при вхождении в блок и забирается обратно при выходе из блока. Такие языки, как Бейсик и Фортран, не имеют блочной структуры, Паскаль же ее имеет, но в ограниченной форме. Более современные языки алголоподобные и язык министерства обороны США, Ада имеют блочную структуру. Здесь мы будем считать в основном, что исходный язык обладает блочной структурой. Языки, не имеющие блочной структуры, легче компилировать с точки зрения распределения памяти и т. п. На данном этапе нет смысла много говорить о различиях между языками высокого уровня, например, в отношении способов обеспечения циклов или условных выражений либо в типах обозначений операций. Различия в языках в представлении разработчика компиляторов хорошо показаны в работе [3]. Структура компилятора в значительной степени зависит от средств выражения типа в языке. В большинстве языков каждое возможное значение принадлежит одному из конечного или бесконечного количества типов, а каждый тип соответствует конечному или бесконечному количеству значений. Например, множество всех целых чисел, вещественных чисел или литер в каком-либо множестве литер может считаться типом. В Паскале есть подтип, соответствующий, например, целым числам в определенном диапазоне, а многие языки имеют типы-агрегаты, соответствующие массивам или записям. Виды в Алголе 68 приблизительно соответствуют типам, но являются более общими. Например, существует вид соответствующий процедуре с одним real параметром и одним real результатом. В данной книге мы употребляем оба термина: вид в основном в контексте Алгола 68 и тип в остальных случаях. Считается, что некоторые языки, такие, как Алгол 68 и Паскаль, имеют явно выраженные не статические типы, т.е. типы всех значений в программе известны во время компиляции. Это привносит избыточность в язык и увеличивает число проверок, выполняемых в процессе компиляции. Например, 11

10 будет определена компилятором как недопустимая. В ПЛ/1, который также имеет явно выраженные типы, эта «ошибка» останется необнаруженной, так как в этом языке есть много неявных преобразований типов (например, целое в литеру). О таких языках, как РОР-2, АПЛ и ЛИСП, говорят, что они имеют неявно выраженные, или динамические, типы, поскольку в них типы не известны до тех пор, пока не наступит время прогона программы. Например, в РОР-2 объявление означает, что X и Y могут принимать значения любого типа. Такое присваивание, как (в РОР-2 присваивания имеют направление слева направо), всегда является допустимым. Однако в применение обозначения бинарной операции «-Ь» к X и У может быть допустимым или нет в зависимости от текущих типов X и» Y. Это можно проверить только во время прохождения программы. Такая проверка должна включаться в объектный код, что неизбежна замедляет объектную программу. Возможно компромиссное решение: в основной части типы делают статическими, но вводят дополнительный тип (называемый, например, any type (любой тип) или general (универсальный)), который может принимать значения любых других типов языка. Это решение принято в CPL и ESPOL (подмножество Алгола 60 Барроуз). Третий метод определения типов применяется в BCPL. Здесь имеется только один тип, который можно считать набором битов, а означает сложение наборов битов. Программисту могут быть известны различные типы, но они неизвестны программе или реализации. Задача программиста не допустить попыток сложения логического значения и целого числа. Во время компиляции или прогона проверка типа невозможна. Машины В машинном коде, как ив BCPL, концепция типа или вида отсутствует. ЭВМ имеет дело с наборами двоичных чисел независимо от их значений. Подобно языкам ЭВМ существенно отличаются друг от друга в деталях; но, чтобы показать задачу компилятора, мы можем перечислить ряд их типичных характеристик. Эти характеристики для каждой конкретной машины отчасти определяются возможностью ее использования программистом и в гораздо большей степени стоимостными и скоростными показателями конструкции ЭВМ. Общими для большинства машин являются: 1. Линейное запоминающее устройство Это последовательность групп битов, в которых запоминается информация. Каждая группа битов называется словом и содержит 16, 24 или 32 бита (двоичных чисел). Место размещения слова в памяти называется его адресом. Адреса, как 12

11 правило, идут от 0 до 2″ 1; где п целое число. (В некоторых ЭВМ единицей памяти служит байт, который состоит из 8 бит и представляет собой поле, необходимое для записи одной литеры. Байты обычно имеют отдельные адреса). 2. Регистры Как и слово основного запоминающего устройства, регистр может служить для хранения данных. Регистры используются во всех арифметических операциях, выполняемых на ЭВМ. Время, необходимое для записи значения в регистр или выборки его из регистра, намного меньше времени записи или выборки слова из основной памяти. В ЭВМ, как правило, имеется несколько регистров (8 или 16). 3. Набор команд В любой машине есть набор команд, называемый машинным кодом. Каждая команда состоит из последовательности двоичных цифр и может принимать несколько параметров, которые /также являются последовательностями двоичных цифр. В эти параметры обычно входит имя регистра или адрес в основной памяти. Команда (включая параметры) занимает точное число слов (или, возможно, полуслов) и может храниться в основной памяти во время выполнения программы. В одних машинных кодах команды имеют фиксированную длину (например, в серии ICL 1900), в других переменную (например, в серии IBM 370). Используя вместо двоичных чисел мнемоническую запись кодов команд и десятичные числа вместо последовательностей двоичных цифр, можно представить типичные команды машинного кода в виде что значит «поместить содержимое адреса 4444 в регистр /». (Поскольку заранее может быть неизвестно, в какой части основной памяти будет храниться программа во время выполнения, адресные поля, как правило, бывают не абсолютными, а относительными какого-либо базового значения.) Так, означает «записать содержимое регистра 2 по адресу 2000», означает «сложить содержимое адреса 102 с содержимым регистра 2», «перейти к адресу 4000 и продолжать выполнение команд с этого адреса». Остальные (перечисленные ниже) устройства ЭВМ не имеют для нас особого значения с точки зрения компиляции. 4. Устройство управления Служит для интерпретации команд машинного кода и их размещения при выполнении. 13

12 5. Арифметическое устройство Здесь выполняются различные арифметические операции, тесты и т. п. Таким образом, назначение компилятора заключается в том, чтобы из исходного кода выработать выполнимый. В некоторых случаях компилятор выдает только, код сборки (ассемблера) для определенной машины, а окончательная выработка машинного кода осуществляется другой программой, называемой ассемблером. Код ассемблера аналогичен машинному коду, но в нем для команд и адресов используется мнемоника, метки же могут применяться в качестве адресов переходов. Ассемблер выполняет довольно простую задачу, в то время как компилятор должен транслировать сложные конструкции языка высокого уровня в относительно простой машинный код или код сборки соответствующей машины. Поэтому в работу компилятора вовлекаются два языка и, кроме них, язык, на котором написан сам компилятор. В простейших случаях это машинный код той ЭВМ, на которой он будет выполняться. Однако, как мы увидим далее, это не всегда так. Для представления компилятора можно воспользоваться Т-образной схемой. Например, компилятор для ПЛ/1, написанный в коде ICL 1900 с целью получения кода 1900, можно изобразить так, как показано на рис В верхнем левом углу схемы указывается исходный язык, в верхнем правом углу объектный язык, а внизу язык, на котором написан компилятор. Кросс-компилятор выдает код для какой-либо другой машины, а не основной машины. Например, на рис. 1.3 представлен компилятор, написанный в коде ЭВМ ICL 1900, для компиляции программ на Фортране в код машины PDP-11. С помощью такого компилятора программы, написанные на Фортране, могут компилироваться на ЭВМ 1900, а пропускаться на ЭВМ PDP-11. В настоящее время предпринимаются попытки как можно больше обособлять зависимые от машины части компилятора. Это особенно важно в тех случаях, когда компилятор предполагается перемещать из одной машины на другую. Так, если бы у нас был написанный на Фортране компилятор Паскаля, который должен выработать код, предназначенный для машины А (рис. 1.4), то, чтобы пропустить компилятор на машине А, нам прежде всего потребовалось бы транслировать его в А-код с помощью компилятора Фортрана, написанного в А-коде и выдающего А-код (рис. 1.5). 14

13 Из этих двух компиляторов мы смогли бы получить третий, используя второй компилятор для компиляции первого (рис. 1.6). Это можно показать, соединив вместе две Т-образные схемы в соответствии с простыми правилами (рис. 1.7); согласно которым ветви среднего звена Т должны показывать те же языки, что и корни смежных с ними соседних звеньев, а в двух верх- них звеньях в правых и левых углах должны быть записаны одинаковые языки. Можно также образовать более сложные Т-образные схемы (рис. 1.8). Идея создания Т — образной схемы принадлежит Брэтману [11]. Изменяя код, выдаваемый первоначальным компилятором в первом примере, скажем, в код для некой машины В (В-код) и допуская, что имеется компилятор Фортрана, работающий на машине В и вырабатывающий В-код, мы можем также создать для этой машины компилятор Паскаля. 15

14 1.2. НЕКОТОРЫЕ АСПЕКТЫ ПРОЦЕССА КОМПИЛЯЦИИ Рассмотрев некоторые типичные свойства машин и языков, мы получили общее представление о тех задачах, которые выполняет компилятор. Работа компилятора складывается из двух основных этапов. Сначала он распознает структуру и значение программы, которую должен компилировать, а затем выдает эквивалентную программу в машинном коде (или коде сборки). Эти два этапа анализ и синтез. По идее анализ должен проводиться перёд синтезом, но на практике они могут выполняться почти параллельно. Определив исходный язык, мы тем самым задаем значение его каждой допустимой конструкции (но не недопустимой). После того как анализатор распознает все конструкции в программе, он может установить, каким должен быть результат действия этой программы. Затем синтезатор вырабатывает соответствующий объектный код. Структуру программы удобно представлять в виде дерева. Так, для программы на рис. 1.9 приводится схема в виде дерева, поясняющая ее структуру. Представим, что анализатор строит такое дерево (обычно его называют деревом разбора), а синтезатор просматривает его (проходя по всем вершинам в некотором заданном порядке), чтобы затем выдать машинный код. Допустим, что конечными вершинами дерева разбора (вершинами, у которых нет ветвей) являются не отдельные литеры, а такие идентификаторы, как print, или такие слова языка, как begin. Конечную вершину с меткой print можно было бы заменить поддеревом, показанным на рис. 1.10, но читателю это помешает яснее представить себе структуру программы. Что касается компилятора, то в начальной фазе работы он объединяет литеры в так называемые символы, например 16

15 Эта фаза процесса компиляции называется лексическим анализом и рассматривается в гл. 3. Остальная часть анализа, т. е. построение дерева, называется синтаксическим анализом, или разбором. Для проверки определенных требований языков компилятор строит таблицы. Например, в большинстве языков допустимо только в том случае, если объявляется, что -х и у имеют согласованные типы. Из такого объявления, как в таблицу, обычно называемую таблицей символов вводится элемент, указывающий тип х. Вышеприведенная реализация х известна как определяющая. В присваивании реализация к носит название прикладной, а тип х выводится из таблицы символов. Таблицы символов обычно строятся параллельно с синтаксическим анализом. Они требуются во время генерирования кода, а также для проверки действенности программ. Могут оказаться необходимыми и некоторые другие таблицы. Во время лексического анализа идентификаторы переменной длины обычно заменяются символами фиксированной длины, а для нахождения соответствия между этими символами и первоначальными идентификаторами используется таблица идентификаторов. В таких языках, как Алгол 68, где комплексные виды могут определяться пользователем, подробная информация о них содержится в таблице видов. Однако во время компиляции может выделяться не весь объем памяти. Рассмотрим описание. В процессе компиляции, на этапе синтеза, требуется выделить память в объектной машине для записи значений, необходимых программе. Память выделяется для значений переменных, встречаемых в программе, и для рабочих операций, выполняемых, например, при вычислении выражений, подобных следующему: Допустив, что значения т и п неизвестны при компиляции, нельзя выделить соответствующий объем памяти для элементов А до начала прогона. Поэтому компилятор, вместо того чтобы выделить память для элементов А, выдаст код для выделения соответствующего объема памяти в ходе прогона. Объем памяти, выделяемый во время компиляции, обычно называется статическим, а объем памяти, выделяемый во время прогона, динамическим. 17

16 Запоминающее устройство, как правило, организуется по принципу магазина (первым считывается последнее записанное слово) и носит название стека (см. гл. 9). Генерирование кода описывается в гл. 10 и 11. В гл. 10 мы рассмотрим получение не зависящего от машины промежуточного кода, а в гл способы его отображения на реальной машине. Введение промежуточного языка связано с попыткой разделить зависимые и не Зависимые от машины аспекты генерирования кода. Промежуточный код может состоять из операторов вида что значит «сложить величины, записанные по адресам 1 и 2, и поместить результат по адресу «?». Промежуточный язык не является, по всей вероятности, не зависимым от исходного языка (хотя были предприняты попытки создания универсальных промежуточных языков, см. [48]). Он отражает основные действия исходного языка и имеет достаточно высокий уровень, чтобы его можно было эффективно реализовать на типичной ЭВМ. Во многих компиляторах нет явного разделения этих двух аспектов генерирования кода. Но если компилятор предполагается сделать переносимым, то желательно как можно полнее разделить его зависимые и не зависимые, от машины части. Конечно, выданный окончательный код должен иметь то же значение, что и программа. Однако выражения разобьются на основные компоненты, виды исчезнут, а все значения окажутся представленными как наборы двоичных знаков. Структура программы (условные выражения и циклы) будет представлена тестами, переходами и метками. Программа станет гораздо менее понятной, но появится возможность выполнять ее на какой-нибудь конкретной машине. В этом разделе мы попытались объяснить некоторые аспекты процесса компиляции. Подробнее организация различных фаз компилятора и их соответствие друг другу описываются в следующих главах. 1.3 ПРОЕКТИРОВАНИЕ КОМПИЛЯТОРА Как уже упоминалось выше, компилятор в некотором смысле определяется тем языком высокого уровня, который он принимает, и машинным кодом (в более общем смысле. другим языком), который он создает. Из этого, однако, не следует, что, например, все компиляторы Фортрана для машин серии PDP-11 должны быть одинаковыми. Конечно, вряд ли можно ожидать, что два компилятора, написанные разными разработчиками (или группами разработчиков), окажутся одинаковыми, хотя они и должны выдавать идентичный, или эквивалентный, объектный код из одного и того же исходного кода. Два компилятора, реализующие один и тот же язык на одной и той же машине, могут отличаться хотя бы потому, что разработчики преследовали различные цели при их построении. Этими целями могут быть: получение эффективного объектного кода; разработка небольших объектных программ; минимизация времени компиляции программ; разработка компилятора как можно меньшего размера; создание компилятора, обладающего широкими возможностями обнаружения и исправления ошибок; обеспечение надежности компилятора. 18

17 К сожалению, эти цели в какой-то степени противоречивы. Почти наверняка компилятор, который должен выдавать эффективный код, будет немного (и даже намного) медленней. Для осуществления некоторых стандартных методов оптимизации [20], таких, как устранение избыточности кода, исключение последовательностей кода из циклов и т. д., может потребоваться очень много времени. Компилятор, в котором выполняются сложные программы оптимизации, является также большим по объему. Размер компилятора может влиять и на время, необходимое ему для компиляции программы. В процессе работы часто невозможно оптимизировать время и объем памяти одновременно. Обычно одно осуществляется за счет другого. Разработчик компилятора должен заранее решить, что именно он предпочитает оптимизировать, а затем уже приступить к оптимизации, полностью отдавая себе отчет в том, к чему это может привести. Кроме того, у него может возникнуть желание потратить как можно меньше времени на написание компилятора, что само по себе является препятствием к включению некоторых сложных методов оптимизации. Программисты ожидают от компилятора вспомогательного сообщения об ошибке, когда они представляют недопустимую программу. Их не удовлетворит формальный ответ, что программа «написана не на том языке, для трансляции которого предназначен компилятор». Они также предполагают, что компилятор, обнаружив ошибку, не перестанет производить компиляцию программы, а будет продолжать анализировать ее в поисках дальнейших ошибок. Компиляторы крайне отличаются по своим возможностям обнаружения и исправления ошибок, хотя это их свойство не противоречит перечисленным выше целям проектирования. Конечно, компилятор, выдающий полезные сообщения и элегантно выходящий из ситуации ошибки, имеет как следствие несколько больший размер, но это вполне компенсируется повышением эффективности работы программиста. В результате для компиляции правильных программ такому компилятору не потребуется больше времени. Однако проблема исправления ошибок (особенно синтаксических) не проста и полностью пока еще не решена. Более подробно эта проблема рассматривается в гл. 12. Несомненно, обеспечение надежности должно быть первостепенной задачей при создании любого компилятора. Компиляторы часто представляют собой очень большие программы, а современное состояние этой области науки и техники не позволяет дать формальное подтверждение правильности компилятора. Наибольшее значение здесь имеет хороший общий проект. Если различные фазы процесса сделать относительно различимыми и каждую фазу построить как можно проще, то вероятность создания надежного компилятора должна возрасти. Надежность компилятора повышается и в том случае, если он базируется как можно полнее на ясном и однозначном формальном определении языка и если используются такие автоматические средства, как генераторы синтаксических анализаторов. Конечно, компилятор должен быть всесторонне проверен, причем не только в целом, но и его отдельные части до их сборки. Вопросы надежности обсуждаются также в гл. 13. Нередко фирмы-изготовители предлагают для какого-либо языка, применимого в серии машин, не один компилятор, а несколько. Так, компанией «Инглиш электрик» были предложены для ЭВМ KDF9 компиляторы Whetstone и Kidsgrove. Компилятор Whetstone является быстрым в компиляции и медленным в прогоне, a Kidsgrove медленным в компиляции, но выдает очень эффективный машинный код. Идея заключалась в том, чтобы пользователи разрабатывали свои программы с помощью компилятора Whetstone, а затем для работы перекомпилировали их с 19

18 помощью компилятора Kidsgrove. В ИБМ также создали несколько компиляторов ПЛ/I для машин серии 370. Цели проектирования компилятора часто зависят от той среды, в которой он должен использоваться. Если он предназначается в основном для студентов, которые редко пропускают свои программы после удовлетворительного завершения фазы их разработки, эффективность машинного кода будет, иметь меньшее значение, чем скорость компиляции и возможности обнаружения ошибок. В производственной сфере степень важности этих свойств может быть обратной. В учебной среде пакетный компилятор, который остается в основной памяти, пака ряд программ компилируется и прогоняется, позволяет эффективно применять имеющуюся аппаратуру. В построении компилятора большую роль играет решение о числе проходов, которое ему придется выполнять. Каждое прочитывание исходного текста или его версии компилятором считается проходом. Однопроходные компиляторы привлекательны из-за их простоты. Однако не все языки позволяют, выполнять однопроходную компиляцию. Со структурной точки зрения отдельные фазы компиляции могут быть выполнены аккуратнее и проще в разные проходы. Чтобы обеспечить возможность однопроходной компиляции, некоторые разработчики реализуют только какое-либо подмножество языка, настаивая, например, на том, чтобы идентификаторы описывались до их употребления в исходных программах. Создание многопроходного компилятора обычно связано с проектированием промежуточных языков для версий исходного текста, существующих между проходами. Строятся также таблицы какого-либо прохода, которые могут понадобиться для просмотра в последующем проходе или проходах. Поэтому организация многопроходного компилятора выглядит усложненной по сравнению с организацией однопроходного компилятора, хотя отдельные проходы могут быть относительно простыми. Они позволяют разделить задание между рядом исполнителей или групп и не требуют сложных взаимосвязей между ними. Наконец, следует отметить, что не все компиляторы имеют фиксированное число проходов. В некоторых из них число проходов, необходимых для выполнения программы, зависит от того, все ли идентификаторы были описаны до их употребления и т. д., или от степени оптимизации, затребованной программистом. Мы продолжим обсуждение этой темы в гл. 7. Создатель компилятора должен выбрать язык, на котором он будет писать свой компилятор. Все в большей степени для этого применяются языки высокого уровня, универсальные языки, такие как Алгол 68, Паскаль или ПЛ/1, либо так называемые языки программного обеспечения, например BCPL или ПЛ/360. Следует упомянуть и об идее создания компилятора для какого-либо языка на самом языке. В этом случае разработчик должен мыслить только в терминах одного языка, а компилятор можно использовать для самокомпиляции, что само по себе является хорошей проверкой. Кроме того, это путь для создания переносимого компилятора. 20

19 Упражнения 1. Приведите какие-нибудь другие типичные конструкции языков высокого уровня и укажите, какого типа команды в машинном коде будут генерироваться при их трансляции. 2. Компилятор транслирует Паскаль в машинный код ICL 1.900, а написан на Алголе 68.Какое еще программное обеспечение потребуется для того, чтобы пропускать программы Паскаля на ЭВМ ICL 1900? 3. Некоторые компиляторы генерируют код для проверки индексов массивов во время прогона, чтобы убедиться в том, что они находятся в объявленных границах массива. Рассмотрите аргументы за и против реализации таких проверок:. а) в процессе разработки программы; б) в процессе рабочих прогонов. 4. Требуется разработать компилятор Фортрана за относительно короткое время. Как вы думаете, какие из шести целей проектирования > перечисленных в разд. 1.3, будет труднее всего осуществить? 5. Какие из следующих средств языка высокого уровня, по вашему мнению, окажутся полезными для разработчика компилятора: а) массивы? б) арифметические действия с вещественными числами? в) процедуры? 6. Приведите доводы в пользу применения в учебной среде интерпретатора, а не компилятора. 7. Какие вероятные проблемы вы видите в методе KDF 9, предлагающем разные компиляторы для этапов трансляции и прогона рабочей программы? 8. Некоторые языки позволяют программисту присваивать относительный приоритет обозначениям операций. Как может это сказаться на дереве разбора конкретной программы? 9. Каковы, по вашему мнению, основные цели проектирования компилятора для языка, на котором реализуется программное обеспечение? 10. Какое средство вы ожидаете найти в компиляторе, предназначенном для такого диалогового языка, как Бейсик? 21

20 Глава 2. ОПРЕДЕЛЕНИЕ ЯЗЫКА Прежде чем приступить к созданию компилятора, необходимо (или по меньшей мере крайне желательно) иметь четкое и однозначное определение исходного языка. К сожалению, хотя и существуют хорошо разработанные методы спецификации некоторых аспектов языков программирования, полные и ясные определения реализуемых языков часто отсутствуют. Более того, формальное определение языка не обязательно используется создателем компилятора. В настоящей главе мы знакомим читателя с несколькими методами определения языков программирования. Подробнее эта тема освещена в [44]. Мы также рассматриваем здесь проблему разбора как выяснить, принадлежит ли какая-либо последовательность символов конкретному языку или нет СИНТАКСИС И СЕМАНТИКА Можно представить себе язык состоящим из ряда строк (последовательностей символов). В описании языка определяется, какие строки принадлежат этому языку (синтаксис языка), и значение этих строк (семантика языка). Синтаксис для конечного языка (т.е. состоящего только из конечного числа строк) можно специфицировать, задав список строк. Например, язык может содержать строки Строки, принадлежащие языку, обычно называются предложениями. Большинство представляющих для нас интерес языков включает бесконечное число предложений, так что их синтаксис нельзя определить путем перечисления этих предложений. К примеру, предложениями языка могут быть «все строки, состоящие только из нулей и единиц». Так, может принадлежать языку, и в этом случае цитируемая фраза представляется достаточным определением языка. Однако русский язык не очень годится для спецификации синтаксиса более сложных языков, поэтому, как правило, применяется более формальный метод определения синтаксиса языков программирования, о чем мы узнаем позже. Семантика задает значение всем предложениям языка. Например, является предложением Алгола 68, и исходя из семантики Этого языка можно вывести значение данной программы в терминах описания идентификатора, считывания значения для него, вычисления и печати выражения. Семантика языка, как и синтаксис, обычно описывается довольно формально. Однако методы определения семантики не так хорошо разработаны, как методы определения синтаксиса, и нужны дальнейшие исследования в этой области, чтобы получить полностью удовлетворительное формальное определение языков программирования. Развитие указанного направления может позволить создавать компиляторы автоматически на ‘основе формального определения семантики и синтаксиса языка. В следующем разделе мы рассмотрим задачу спецификации синтаксиса языка. 22

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

Тогда, например, для предыдущего выражения получим следующую

4: if >
5: if >
6: if >
3: if >
При каждом конкретном наборе данных эта программа превращается

в программу вычисления логического значения.
Утверждение 3. В каждой строке программы, сформированной

предыдущей атрибутной схемой, одна из меток совпадает с меткой

Действительно, по правилам наследования атрибутов TrueLab и

FalseLab, в правилах для дизъюнкции и конъюнкции либо

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

поддерева. Кроме того, как значение FalseLab, так и значение

TrueLab, передаются в правое поддерево от предка. Таким

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

TrueLab или FalseLab, равную метке правого брата

соответствующего поддерева. Учитывая порядок генерации команд,

Дополним теперь атрибутную грамматику следующим образом:
RULE

FalseLab :=False; TrueLab :=True;

BoolExpr ::= BoolExpr & BoolExpr

FalseLab :=FalseLab ; TrueLab :=NodeLab ;

FalseLab :=FalseLab ; TrueLab :=TrueLab ;

Sign :=false; Sign :=Sign .

BoolExpr ::= BoolExpr V BoolExpr

TrueLab :=TrueLab ; FalseLab :=NodeLab ;

FalseLab :=FalseLab ; TrueLab :=TrueLab ;

Sign :=true; Sign :=Sign .

BoolExpr ::= not BoolExpr

FalseLab :=TrueLab ; TrueLab :=FalseLab ;

then else GOTO FalseLab >

else else GOTO TrueLab >;

Правила наследования атрибута Sign приведены на рис. 8.24.
false | true | false | true |

true false true true false false false true

false true
Рис. 8.24

Программу желательно сформировать таким образом, чтобы else-

метка была как раз меткой следующей вершины. Как это можно

сделать, следует из утверждения 4.
Утверждение 4. В каждой терминальной вершине, метка ближайшего

правого для нее поддерева равна значению атрибута FalseLab

этой вершины, тогда и только тогда, когда значение атрибута

Sign этой вершины равно true, и наоборот, метка ближайшего

правого для нее поддерева равна значению атрибута TrueLab этой

вершины, тогда и только тогда, когда значение атрибута Sign

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

атрибутной грамматики следующим образом:
RULE

В свою очередь, при генерации машинных команд это правило
можно заменить на следующее:
RULE

Если элементом логического выражения является сравнение, то

генерируется команда, соответствующая знаку сравнения (beq для

=, bne для <>, bge для >= и т.д.), если атрибут sign

соответствующей вершины имеет значение true, и отрицание (bne

для =, beq для <>, blt для >= и т.д.), если атрибут sign имеет

Приведем несколько примеров. Выражение A AND (B OR C)

транслируется в последовательность команд рис. 8.25. Выражение

(NOT((A=B)OR(C<>D)))AND(not((E H))) транслируется в

последовательность команд рис. 8.26.
TST A CMP A,B

BEQ False BEQ False

BNE True BNE False

BEQ False BGE False

False:. . . BGT False

False:
Рис. 8.25 Рис. 8.26

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

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

1. Поскольку на линейном участке переменной может быть

несколько присваиваний, то при выделении общих подвыражений

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

присваивания. Для этого каждая переменная снабжается номером.

Вначале номера всех переменных устанавливаются равными 0. При

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

2. Выделение общих подвыражений осуществляется при обходе

дерева выражения снизу вверх слева направо. При достижении

очередной вершины (пусть операция, примененная в этой вершине,

есть бинарная ‘op’; в случае унарной операции рассуждения те

же) просматриваем общие подвыражения, связанные с op. Если

имеется выражение, связанное с op и такое, что его левый

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

выражения, а правый операнд — общее подвыражение с правым

операндом нового выражения, то объявляем новое выражение общим

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

найденное общее выражение. Базисом построения служит

переменная: если операндами обоих выражений являются

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

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

оно заносится в список операций, связанных с op (рис. 8.27).
| /\ /\ ].Count:=Table[Entry ].Count+1.

with Node ^ do with Table[Entry ] do

and Last^.VarCount = Count then

IntExpr ::= Op IntExpr IntExpr

var L:pointer to Listype;

if Node ^.Flag and Node ^.Flag then

and (Node =L^.Right)

включить данное в список для операции >

Рассмотрим теперь некоторые простые правила распределения

регистров при наличии общих подвыражений. Если число регистров

ограничено, можно выбрать один из следующих двух вариантов.

1. При обнаружении общего подвыражения с подвыражением в уже

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

регистрами) проверяем, расположено ли его значение на

регистре. Если да, и если регистр после этого не менялся,

заменяем вычисление поддерева на значение в регистре. Если

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

2. Вводим еще один проход. На первом проходе распределяем

регистры. Если в некоторой вершине обнаруживается, что ее

поддерево общее с уже вычисленным ранее, но значение регистра

потеряно, то в такой вершине на втором проходе необходимо

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

Выигрыш в коде будет, если стоимость команды сброса регистра +

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

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

стоимость команды MOVE известна, можно сравнить стоимости и

принять оптимальное решение: то ли метить предыдущую вершину

для сброса, то ли вычислять полностью поддерево.

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

анализа
8.9.1. Сопоставление образцов
Техника генерации кода, рассмотренная выше, основывалась на

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

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

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

изложенный в настоящей главе.

Этот подход основан на понятии «сопоставления образцов»:

командам машины сопоставляются некоторые «образцы», вхождения
которых ищутся в промежуточном представлении программы, и

делается попытка «покрыть» промежуточную программу такими

образцами. Если это удается, то по образцам восстанавливается

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

Название Лекции по конструированию компиляторов
страница 1/11
Дата 21.12.2012
Размер 2.15 Mb.
Тип Книга
Илон Маск рекомендует:  defined - проверяет, существует ли данная именованная константа

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

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

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

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

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

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

Илон Маск рекомендует:  translateZ() в CSS

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

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

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

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

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

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

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

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

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

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

Глава 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) — при использовании систем

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Название: Конструирование компиляторов
Автор: Свердлов С.З.
Издательство: Lambert Academic Publishing
Год: 2015
Страниц: 575
Формат: pdf
Размер: 10 mb
Качество: хорошее

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

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

Авторы: В. А. Серебряков ,
М. П. Галочкин
Издательство: Едиториал УРСС
ISBN: 978-5-8360-0242-8
Год издания: 2001 г.
показать еще параметры.
Тираж: 1 000 экз.
Страниц: 224

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

Предлагаемая вниманию читателя книга основана на курсе лекций, прочитанных на факультете вычислительной математики и кибернетики Московского государственного университета и факультете управления и прикладной математики Московского физико-технического института в 1991-1999 гг. Авторы надеются, что издание книги восполнит существенный пробел в литературе на русском языке по разработке компиляторов. Содержание книги представляет собой `классические` разделы предмета: лексический и синтаксический анализ, организация памяти транслятора (таблицы символов) и периода исполнения (магазина), генерация кода, в частности генерация арифметических и логических выражений. Рассматриваются некоторые средства автоматизации процесса разработки трансляторов, такие как LEX, YACC, СУПЕР, методы генерации оптимального кода. Сделана попытка на протяжении всего изложения провести единую `атрибутную` точку зрения на процесс разработки компилятора. Книга будет полезна как студентам и аспирантам программистских специальностей, так ипрофессионалам в этих областях.

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