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


Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Название Лекции по конструированию компиляторов
Дата публикации 08.02.2014
Размер 91.59 Kb.
Тип Книга

skachate.ru > Информатика > Книга

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3. Атрибутные грамматики 70

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

4.3.2. Атрибутированное дерево разбора 71

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

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

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

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

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

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

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

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

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

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

6.4. Функции расстановки 94

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

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

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

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

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

7.2. Трехадресный код 102

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

7.4. Виртуальная машина Java 109

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

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

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

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

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

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

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

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

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

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

8.6. Распределение регистров при вычислении
арифметических выражений 136

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Системы автоматизации построения трансляторов (САПТ) предназначены для автоматизации процесса разработки трансляторов. Очевидно, что для того, чтобы описать транслятор, необходимо иметь формализм для описания. Этот формализм затем реализуется в виде входного языка САПТ. Как правило, формализмы основаны на атрибутных грамматиках. Ниже описаны две САПТ, получившие распространение: СУПЕР [3] и Yacc. В основу первой системы положены LL(1)-грамматики и L-атрибутные вычислители, в основу второй — LALR(1)-грамматики и S-атрибутные вычислители.

10.1 Система СУПЕР

Программа на входном языке СУПЕР («метапрограмма») состоит из следующих разделов:

Заголовок определяет имя атрибутной грамматики, первые три буквы имени задают расширение имени входного файла для реализуемого транслятора.

Раздел констант содержит описание констант, раздел типов — описание типов.

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

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

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

Раздел файлов содержит описание файловых переменных, используемых в формулах атрибутной грамматики. Файловые переменные можно рассматривать как атрибуты аксиомы.

Атрибутная схема состоит из списка синтаксических правил и сопоставленных им семантических правил. Для описания синтаксиса языка используется расширенная форма Бэкуса-Наура. Терминальные символы в правой части заключаются в кавычки, классы лексем и нетерминалы задаются их именами. Для задания в правой части необязательных символов используются скобки [ ], для задания повторяющихся конструкций используются скобки ( ). В этом случае может быть указан разделитель символов (после /). Например,

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

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

Исполнение операторов семантической части правила привязывается к обходу дерева разбора сверху вниз слева направо. Для этого каждый оператор может быть помечен меткой, состоящей из номера ветви правила, к выполнению которой должен быть привязан оператор, и, возможно, одного из суффиксов A, B, E, M.

Суффикс A задает выполнение оператора перед каждым вхождением синтаксической конструкции, заключенной в скобки повторений ( ). Суффикс B задает выполнение оператора после каждого вхождения синтаксической конструкции, заключенной в скобки повторений ( ). Суффикс M задает выполнение оператора между вхождениями синтаксической конструкции, заключенной в скобки повторений ( ). Суффикс E задает выполнение оператора в том случае, когда конструкция, заключенная в скобки [ ], отсутствует.

Пример использование меток атрибутных формул:

Процедура writeln напечатает число вхождений символа C в C-список, если D опущено. В противном случае напечатанное число будет на единицу больше.

10.2 Система Yacc

В основу системы Yacc положен синтаксический анализатор типа LALR(1), генерируемый по входной (мета) программе. Эта программа состоит из трех частей:

Си-текст (который вместе с окружающими скобками % < и %>может отсутствовать) обычно содержит Си-объявления (включая #include и #define), используемые в тексте ниже. Этот Си-текст может содержать и объявления (или предобъявления) функций.

Список имен лексем содержит имена, которые преобразуются Yacc-препроцессором в объявления констант (#define). Как правило, эти имена используются как имена классов лексем и служат для определения интерфейса с лексическим анализатором.

Каждое правило трансляции имеет вид

Каждое семантическое действие — это последовательность операторов Си. При этом каждому нетерминалу может быть сопоставлен один синтезируемый атрибут. На атрибут нетерминала левой части ссылка осуществляется посредством значка $$, на атрибуты символов правой части — посредством значков $1, $2 , . $n, причем номер соответствует порядку элементов правой части, включая семантические действия. Каждое семантическое действие может вырабатывать значение в результате выполнения присваивания $$=Выражение. Исполнение текого оператора в последнем семантическом действии определяет значение атрибута символа левой части.

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

— конфликты типа свертка/свертка разрешаются выбором правила, предшествующего во входной метапрограмме;

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

определяет + и -, имеющими одинаковый приоритет и имеющими левую ассоциативность. Операцию можно определить как правоассоциативную в результате объявления:

Бинарную операцию можно определить как неассоциативную (т.е. не допускающую появления объединения двух подряд идущих знаков операции):

Принципы построения трансляторов

Трансляторы, компоновщики и загрузчики.

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

Например, предложение вида

компилятор может преобразовать в следующую последовательность машинных кодов:

A1 52 00 03 06 54 00 A3 50 00

mov ax,[0052h] add ax,[0054h] mov [0050h],ax

где [0050h], [0052h], [0054h] – адреса переменных X,Y,Z

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

Слова объединяются в предложения. Простейшим предложением является оператор (присваивания, сложения, умножения и т.д). Предложения из одного и более простых слов строятся по правилам синтаксиса. Синтаксис – это описание конструкций правильных предложений. Например, оператор присваивания имеет синтаксис

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

var MyStr : string[5];

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

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

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

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

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

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

грамматический разбор состоит в том, чтобы убедиться, что вслед за лексемой IF следует правильное выражение, за этим выражением следует лексема THEN, за которой в свою очередь правильное предложение, оканчивающееся точкой с запятой. Синтаксический анализатор формирует промежуточную программу в форме синтаксического дерева программы.

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

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

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

Хотя в состав любого компилятора входят три описанных выше компонента, их взаимодействие может осуществляться разнообразными способами. Наиболее распространенными вариантами являются: одно-, двух- и трехпроходная структура компиляторов (рис.1–3).

Рис.1. Трехпроходный компилятор. Компилятор фактически состоит из трех программ. Лексический анализатор считывает текст программы и представляет его в форме файла лексем. Синтаксический анализатор читает этот файл и выдает представление программы в виде файла с описанием синтаксического дерева. Наконец, этот файл считывается генератором кода, который создает объектный код программы. Компилятор такого вида назван трехпроходным, так как программа с диска считывается трижды. Недостатки: медленно работает (из-за обращений к диску). Преимущества: нетребователен к объему памяти, гибкость (при модификации компилятора достаточно изменить одну из программ), легко можно добавить программу для оптимизации кодов, вызывая ее между синтаксическим анализатором и генератором кодов.

Рис.2. Однопроходный компилятор. Лексический анализатор и генератор кода являются подпрограммами, которые по необходимости вызывает синтаксический анализатор, который выступает в роли основной управляющей программы. Синтаксический анализатор постоянно обращается к лексическому анализатору, получая от него лексему за лексемой, пока не построит новое предложение, после чего он обращается к генератору кода, который создает объектный код для этого фрагмента программы. Достоинства: быстрота. Недостатки: создаваемый код не оптимален, при загрузке компилятор требует большого объема памяти.

Рис.3. Двухпроходный компилятор – собрал лучшее от трёх- и однопроходной моделей. Синтаксический анализатор, вызывая лексический анализатор, получает лексему за лексемой и строит файл с синтаксическим деревом программы. Генератор кода считывает этот файл и создает объектный код программы. Достоинства: быстрота, возможность добавить блок оптимизации.

Существует ряд компиляторов, которые выполняются на одной машине, а генерируют объектный код для другой ЭВМ. Эти компиляторы получили название «кроссовых» или кросс-компиляторов (от англ. cross – «перекрестный»). Кросс-компиляторы часто используют для создания программ для небольших специализированных ЭВМ, управляющих работой технологического оборудования и т.п.

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

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

Не нашли то, что искали? Воспользуйтесь поиском:

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

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

Цели и задачи дисциплины

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

Несмотря на то, что к настоящему времени разработаны тысячи различных языков и их трансляторов, процесс создания новых приложений в этой области не прекращается. Это связно как с развитием технологии производства вычислительных систем, так и с необходимостью решения все более сложных прикладных задач. Кроме того, элементы теории языков и формальных грамматик применимы и в других разнообразных областях, например, при описании структур данных, файлов, изображений, представленных не в текстовом, а двоичном формате. Эти методы полезны и при разработке своих трансляторов даже там, где уже имеются соответствующие аналоги. Такая разработка может быть обусловлена различными причинами, в частности, функциональными ограничениями, отсутствием локализации, низкой эффективностью. Например, одной из последних разработок компании Microsoft является язык программирования C#, а одной из причин его создания является стремление к снижению популярности языка программирования Java. Можно привести множество других примеров, когда разработка своего транслятора может оказаться актуальной. Поэтому, основы теории языков и формальных грамматик, а также практические методы разработки трансляторов лежат в фундаменте инженерного образования по информатике и вычислительной технике.

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

Цель дисциплины: предоставить знания по основам теории языков и формальных грамматик, теории автоматов, методам разработки трансляторов.

Для достижения поставленной цели в ходе преподавания дисциплины решаются следующие задачи:

В ходе лекционного курса рассматриваются общие принципы организации процесса трансляции и структуры трансляторов. Изучаются основы теории построения трансляторов.

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

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

Транслятор — обслуживающая программа, преобразующая исходную программу, предоставленную на входном языке программирования, в рабочую программу, представленную на объектном языке .

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

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

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

Компилятор — это обслуживающая программа, выполняющая трансляцию на машинный язык программы, записанной на исходном языке программирования . Также как и ассемблер, компилятор обеспечивает преобразование программы с одного языка на другой (чаще всего, в язык конкретного компьютера). Вместе с тем, команды исходного языка значительно отличаются по организации и мощности от команд машинного языка. Существуют языки, в которых одна команда исходного языка транслируется в 7-10 машинных команд. Однако есть и такие языки, в которых каждой команде может соответствовать 100 и более машинных команд (например, Пролог). Кроме того, в исходных языках достаточно часто используется строгая типизация данных, осуществляемая через их предварительное описание. Программирование может опираться не на кодирование алгоритма, а на тщательное обдумывание структур данных или классов. Процесс трансляции с таких языков обычно называется компиляцией, а исходные языки обычно относятся к языкам программирования высокого уровня (или высокоуровневым языкам). Абстрагирование языка программирования от системы команд компьютера привело к независимому созданию самых разнообразных языков, ориентированных на решение конкретных задач. Появились языки для научных расчетов, экономических расчетов, доступа к базам данных и другие.

Интерпретатор — программа или устройство, осуществляющее пооператорную трансляцию и выполнение исходной программы . В отличие от компилятора, интерпретатор не порождает на выходе программу на машинном языке. Распознав команду исходного языка, он тут же выполняет ее. Как в компиляторах, так и в интерпретаторах используются одинаковые методы анализа исходного текста программы. Но интерпретатор позволяет начать обработку данных после написания даже одной команды. Это делает процесс разработки и отладки программ более гибким. Кроме того, отсутствие выходного машинного кода позволяет не «захламлять» внешние устройства дополнительными файлами, а сам интерпретатор можно достаточно легко адаптировать к любым машинным архитектурам, разработав его только один раз на широко распространенном языке программирования. Поэтому, интерпретируемые языки, типа Java Script, VB Script, получили широкое распространение. Недостатком интерпретаторов является низкая скорость выполнения программ. Обычно интерпретируемые программы выполняются в 50-100 раз медленнее программ, написанных в машинных кодах.

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

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

Очень часто эмулятор используется для выполнения старых программ на новых вычислительных машинах. Обычно новые компьютеры обладают более высоким быстродействием и имеют более качественное периферийное оборудование. Это позволяет эмулировать старые программы более эффективно по сравнению с их выполнением на старых компьютерах. Примером такого подхода является разработка эмуляторов домашнего компьютера ZX Spectrum с микропроцессором Z80. До сих пор находятся любители поиграть на эмуляторе в устаревшие, но все еще не утратившие былой привлекательности, игровые программы. Эмулятор может также использоваться как более дешевый аналог современных компьютерных систем, обеспечивая при этом приемлемую производительность, эквивалентную младшим моделям некоторого семейства архитектур. В качестве примера можно привести эмуляторы IBM PC совместимых компьютеров, реализованные на более мощных компьютерах фирмы Apple. Ряд эмуляторов, написанных для IBM PC, с успехом заменяют различные игровые приставки.

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

Перекодировщик — программа или программное устройство, переводящие программы, написанные на машинном языке одной ЭВМ в программы на машинном языке другой ЭВМ . Если эмулятор является менее интеллектуальным аналогом интерпретатора, то перекодировщик выступает в том же качестве по отношению к компилятору. Точно также исходный (и обычно двоичный) машинный код или промежуточное представление преобразуются в другой аналогичный код по одной команде и без какого-либо общего анализа структуры исходной программы. Перекодировщики бывают полезны при переносе программ с одних компьютерных архитектур на другие. Они могут также использоваться для восстановления текста программы на языке высокого уровня по имеющемуся двоичному коду.

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

Макропроцессоры используются и с языками высокого уровня. Они увеличивают функциональные возможности таких языков как PL/1, C, C++. Особенно широко макропроцессоры применяются в C и C++, позволяя упростить написание программ. Примером широкого использования макропроцессоров является библиотека классов Microsoft Foundation Classes (MFC). Через макровставки в ней реализованы карты сообщений и другие программные объекты. При этом, макропроцессоры повышают эффективность программирования без изменения синтаксиса и семантики языка.

Синтаксис — совокупность правил некоторого языка, определяющих формирование его элементов. Иначе говоря, это совокупность правил образования семантически значимых последовательностей символов в данном языке . Синтаксис задается с помощью правил, которые описывают понятия некоторого языка. Примерами понятий являются: переменная, выражение, оператор, процедура. Последовательность понятий и их допустимое использование в правилах определяет синтаксически правильные структуры, образующие программы. Именно иерархия объектов, а не то, как они взаимодействуют между собой, определяются через синтаксис. Например, оператор может встречаться только в процедуре, а выражение в операторе, переменная может состоять из имени и необязательных индексов и т.д. Синтаксис не связан с такими явлениями в программе как «переход на несуществующую метку» или «переменная с данным именем не определена». Этим занимается семантика.

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

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

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

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

Языки программирования являются инструментами для решения задач в разных предметных областях, что определяет специфику их организации и различия по назначению. В качестве примера можно привести такие языки как Фортран, ориентированный на научные расчеты, C, предназначенный для системного программирования, Пролог, эффективно описывающий задачи логического вывода, Лисп, используемый для рекурсивной обработки списков. Эти примеры можно продолжить. Каждая из предметных областей предъявляет свои требования к организации самого языка. Поэтому можно отметить разнообразие форм представления операторов и выражений, различие в наборе базовых операций, снижение эффективности программирования при решении задач, не связанных с предметной областью. Языковые различия отражаются и в структуре трансляторов. Лисп и Пролог чаще всего выполняются в режиме интерпретации из-за того, что используют динамическое формирование типов данных в ходе вычислений. Для трансляторов с языка Фортран характерна агрессивная оптимизация результирующего машинного кода, которая становится возможной благодаря относительно простой семантике конструкций языка — в частности, благодаря отсутствию механизмов альтернативного именования переменных через указатели или ссылки. Наличие же указателей в языке C предъявляет специфические требования к динамическому распределению памяти.

Структура языка характеризует иерархические отношения между его понятиями, которые описываются синтаксическими правилами. Языки программирования могут сильно отличаться друг от друга по организации отдельных понятий и по отношениям между ними. Язык программирования PL/1 допускает произвольное вложение процедур и функций, тогда как в C все функции должны находиться на внешнем уровне вложенности. Язык C++ допускает описание переменных в любой точке программы перед первым ее использованием, а в Паскале переменные должны быть определены в специальной области описания. Еще дальше в этом вопросе идет PL/1, который допускает описание переменной после ее использования. Или описание можно вообще опустить и руководствоваться правилами, принятыми по умолчанию. В зависимости от принятого решения, транслятор может анализировать программу за один или несколько проходов, что влияет на скорость трансляции.

Семантика языков программирования изменяется в очень широких пределах. Они отличаются не только по особенностям реализации отдельных операций, но и по парадигмам программирования, определяющим принципиальные различия в методах разработки программ. Специфика реализации операций может касаться как структуры обрабатываемых данных, так и правил обработки одних и тех же типов данных. Такие языки, как PL/1 и APL поддерживают выполнение матричных и векторных операций. Большинство же языков работают в основном со скалярами, предоставляя для обработки массивов процедуры и функции, написанные программистами. Но даже при выполнении операции сложения двух целых чисел такие языки, как C и Паскаль могут вести себя по-разному.

Наряду с традиционным процедурным программированием, называемым также императивным, существуют такие парадигмы как функциональное программирование, логическое программирование и объектно-ориентированное программирование. Надеюсь, что в этом ряду займет свое место и предложенная мною процедурно-параметрическая парадигма программирования [Легалов2000]. Структура понятий и объектов языков сильно зависит от избранной парадигмы, что также влияет на реализацию транслятора.

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

Вместе с тем, все языки программирования обладают рядом общих характеристик и параметров. Эта общность определяет и схожие для всех языков принципы организации трансляторов.

Языки программирования предназначены для облегчения программирования. Поэтому их операторы и структуры данных более мощные, чем в машинных языках.

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

Для любого языка определяется:

Множество символов, которые можно использовать для записи правильных программ (алфавит), основные элементы.

Множество правильных программ (синтаксис).

«Смысл» каждой правильной программы (семантика).

Независимо от специфики языка любой транслятор можно считать функциональным преобразователем F, обеспечивающим однозначное отображение X в Y, где X — программа на исходном языке, Y — программа на выходном языке. Поэтому сам процесс трансляции формально можно представить достаточно просто и понятно:

Формально каждая правильная программа X — это цепочка символов из некоторого алфавита A, преобразуемая в соответствующую ей цепочку Y, составленную из символов алфавита B.

Язык программирования, как и любая сложная система, определяется через иерархию понятий, задающую взаимосвязи между его элементами. Эти понятия связаны между собой в соответствии с синтаксическими правилами. Каждая из программ, построенная по этим правилам, имеет соответствующую иерархическую структуру.

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

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

В качестве примера рассмотрим зависимость между иерархической структурой и цепочкой символов, определяющей следующее арифметическое выражение:

В большинстве языков программирования данное выражение определяет иерархию программных объектов, которую можно отобразить в виде дерева (рис. 1.1.):

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

::= a | b | c | d | i | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

Примечание . Знак «::=» читается как «это есть». Вертикальная черта «|» читается как «или».

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

::= a | b | c | d | i | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

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

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

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

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

Его синтаксическая структура описывается правилами:

::= a | b | c | d | i | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

Иерархическое дерево, определяющее синтаксическую структуру, представлено на рис. 1.3.

Другой характерной особенностью всех языков является их семантика. Она определяет смысл операций языка, корректность операндов. Цепочки, имеющие одинаковую синтаксическую структуру в различных языках программирования, могут различаться по семантике (что, например, наблюдается в C++, Pascal, Basic для приведенного выше фрагмента арифметического выражения).

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

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

Обобщенная структура транслятора

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

Учитывая схожесть компилятора и интерпретатора, рассмотрим фазы, существующие в компиляторе. В нем выделяются:

  1. Фаза лексического анализа.
  2. Фаза синтаксического анализа, состоящая из:
    • распознавания синтаксической структуры;
    • семантического разбора, в процессе которого осуществляется работа с таблицами, порождение промежуточного семантического представления или объектной модели языка.

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


      2а. Фаза исследования и оптимизации промежуточного представления, состоящая из:

    2а.1. анализа корректности промежуточного представления;
    2а.2. оптимизации промежуточного представления.

      3а. Фаза оптимизации объектного кода.

    Интерпретатор отличается тем, что фаза генерации кода обычно заменяется фазой эмуляции элементов промежуточного представления или объектной модели языка. Кроме того, в интерпретаторе обычно не проводится оптимизация промежуточного представления, а сразу же осуществляется его эмуляция.

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

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

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

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

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

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

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

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

    Таким образом, синтаксический анализатор является достаточно сложным блоком транслятора. Поэтому его можно разбить на следующие составляющие:

    блок семантического анализа;

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

    Обобщенная структура синтаксического анализатора приведена на рис. 1.6.

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

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

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

    Варианты взаимодействия блоков транслятора

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

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

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

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

    Многопроходная организация взаимодействия блоков транслятора

    Данный вариант взаимодействия блоков, на примере компилятора, представлен на рис 1.7.

    Лексический анализатор полностью обрабатывает исходный текст, формируя на выходе цепочку, состоящую из всех полученных лексем. Только после этого управление передается синтаксическому анализатору. Синтаксический анализатор получает сформированную цепочку лексем и на ее основе формирует промежуточное представление или объектную модель. После получения всей объектной модели он передает управление генератору кода. Генератор кода, на основе объектной модели языка, строит требуемый машинный код

    К достоинствам такого подхода можно отнести:

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

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

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

    К недостаткам следует отнести.

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

    Замедление скорости трансляции из-за последовательного выполнения фаз и использования для экономии оперативной памяти внешних запоминающих устройств.

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

    Однопроходная организация взаимодействия блоков транслятора

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

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

    Генератор кода функционирует аналогичным образом. По полученному фрагменту промежуточного представления он создает соответствующий фрагмент объектного кода. После этого управление возвращается синтаксическому анализатору.

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

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

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

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

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

    Такая схема часто применяется для простых по семантической и синтаксической структурам языков программирования, как в компиляторах, так и в интерпретаторах. Примерами таких языков могут служить Basic и Pascal. Классический интерпретатор обычно строится по однопроходной схеме, так как непосредственное исполнение осуществляется на уровне отдельных фрагментов промежуточного представления. Организация взаимодействия блоков такого интерпретатора представлена на рис. 1.10.

    Комбинированные взаимодействия блоков транслятора

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

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

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

    Наряду со схемами, предполагающими замену генератора кода на эмулятор, существуют трансляторы, допускающие их совместное использование. Одна из таких схем представлена на рис. 1.13.

    Процесс трансляции, включая и генерацию кода, может быть выполнен за любое число проходов (в примере используется однопроходная трансляция, представленная ранее на рис 1.9). Однако сформированный объектный код не исполняется на соответствующей ему вычислительной системе, а эмулируется на компьютере с другой архитектурой. Такая схема применяется в среде построенной вокруг языка программировании Java. Сам транслятор генерирует код виртуальной Java-машины, эмуляция которого осуществляется специальными средствами как автономно, так и в среде Internet браузера.

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

    Контрольные вопросы и задания

    интерпретатора от компилятора;

    компилятора от ассемблера;

    перекодировщика от транслятора;

    эмулятора от интерпретатора;

    синтаксиса от семантики.

    Расскажите об известных Вам последних разработках языков программирования. Приведите основные характеристики названных языков.

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

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

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

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

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

    Основные достоинства и недостатки интерпретаторов.

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

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

    Назовите основные фазы процесса трансляции и их назначение.

    Назовите специфические особенности однопроходной трансляции.

    Назовите специфические особенности многопроходной трансляции.

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

    4. Основные принципы построения трансляторов. Трансляторы, компиляторы и интерпретаторы – общая схема работы. Современные компиляторы и интерпретаторы.

    Основные принципы построения трансляторов.

    Трансляторы, компиляторы, интерпретаторы – общая схема работы.

    Определение транслятора, компилятора, интерпретатора

    Для начала дадим несколько определений — что же все-таки такое есть уже мно­гократно упоминавшиеся трансляторы и компиляторы.

    Формальное определение транслятора

    Транслятор — это программа, которая переводит входную программу на исход­ном (входном) языке в эквивалентную ей выходную программу на результирую­щем (выходном) языке. В этом определении слово «программа» встречается три раза, и это не ошибка и не тавтология. В работе транслятора, действительно, уча­ствуют всегда три программы.

    Во-первых, сам транслятор является программой 1 — обычно он входит в состав системного программного обеспечения вычислительной системы. То есть транс­лятор — это часть программного обеспечения (ПО), он представляет собой на­бор машинных команд и данных и выполняется компьютером, как и все прочие программы в рамках операционной системы (ОС). Все составные части трансля­тора представляют собой фрагменты или модули программы со своими входны­ми и выходными данными.

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

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

    Итак, чтобы создать транслятор, необходимо прежде всего выбрать входной и выходной языки. С точки зрения преобразования предложений входного язы­ка в эквивалентные им предложения выходного языка транслятор выступает как переводчик. Например, трансляция программы с языка С в язык ассемблера по сути ничем не отличается от перевода, скажем, с русского языка на английский, с той только разницей, что сложность языков несколько иная (почему не суще­ствует трансляторов с естественных языков — см. раздел «Классификация язы­ков и грамматик», глава 9). Поэтому и само слово «транслятор» (английское: translator) означает «переводчик».

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

    Теоретически возможна реализация транслятора с помощью аппаратных средств. Автору встречались такого рода разработки, однако широкое практическое применение их не из­вестно. В таком случае и все составные части транслятора могут быть реализованы в виде аппаратных средств и их фрагментов — вот тогда схема распознавателя может получить вполне практическое воплощение!

    Отличие компилятора от транслятора

    Кроме понятия «транслятор» широко употребляется также близкое ему по смыс­лу понятие «компилятор».

    Компилятор — это транслятор, который осуществляет перевод исходной програм­мы в эквивалентную ей объектную программу на языке машинных команд или на языке ассемблера.

    Таким образом, компилятор отличается от транслятора лишь тем, что его ре­зультирующая программа всегда должна быть написана на языке машинных ко­дов.или на языке ассемблера. Результирующая программа транслятора, в общем случае, может быть написана на любом языке — возможен, например, транслятор программ с языка Pascal на язык С. Соответственно, всякий компилятор являет­ся транслятором, но не наоборот — не всякий транслятор будет компилятором. Например, упомянутый выше транслятор с языка Pascal на С компилятором яв­ляться не будет 1 .

    Само слово «компилятор» происходит от английского термина «compiler» («со­ставитель», «компоновщик»). Видимо, термин обязан своему происхождению способности компиляторов составлять объектные программы на основе исход­ных программ.

    Результирующая программа компилятора называется «объектной программой» или «объектным кодом». Файл, в который она записана, обычно называется «объ­ектным файлом». Даже в том случае, когда результирующая программа порож­дается на языке машинных команд, между объектной программой (объектным файлом) и исполняемой программой (исполняемым файлом) есть существенная разница. Порожденная компилятором программа не может непосредственно выполняться на компьютере, так как она не привязана к конкретной области па­мяти, где должны располагаться ее код и данные (более подробно — см. раздел «Принципы функционирования систем программирования», глава 15) 2 .

    Компиляторы, безусловно, самый распространенный вид трансляторов (многие считают их вообще единственным видом трансляторов, хотя это не так). Они име­ют самое широкое практическое применение, которым обязаны широкому рас­пространению всевозможных языков программирования. Далее всегда будем говорить о компиляторах, подразумевая, что выходная программа написана на

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

    Определение интерпретатора. Разница между интерпретаторами и трансляторами

    Кроме схожих между собой понятий «транслятор» и «компилятор» существует принципиально отличное от них понятие интерпретатора.

    Интерпретатор — это программа, которая воспринимает входную программу на исходном языке и выполняет ее.

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

    Конечно, чтобы исполнить исходную программу, интерпретатор так или иначе должен преобразовать ее в язык машинных кодов, поскольку иначе выполнение программ на компьютере невозможно. Он и делает это, однако полученные ма­шинные коды не являются доступными — их не видит пользователь интерпрета­тора. Эти машинные коды порождаются интерпретатором, исполняются и унич-

    1 Следует особо упомянуть, что сейчас в современных системах программирования стали появляться компиляторы, в которых результирующая программа создается не на языке машинных команд и не на языке ассемблера, а на некотором промежуточном языке. Сам по себе этот промежуточный язык не может непосредственно исполняться на компьюте­ре, а требует специального промежуточного интерпретатора для выполнения написан­ных на нем программ. Хотя в данном случае термин «транслятор» был бы, наверное, более правильным, в литературе употребляется понятие «компилятор», поскольку про­межуточный язык является языком очень низкого уровня, будучи родственным машин­ным командам и языкам ассемблера.

    Здесь возникает извечный вопрос «о курице и яйце». Конечно, в первом поколении са­мые первые компиляторы писались непосредственно на машинных командах, но потом, с появлением компиляторов, от этой практики отошли. Даже самые ответственные части компиляторов создаются, как минимум, с применением языка ассемблера — а он тоже об­рабатывается компилятором. тожаются по мере надобности — так, как того требует конкретная реализа) интерпретатора. Пользователь же видит результат выполнения этих кодов -есть результат выполнения исходной программы (требование об эквивалент сти исходной программы и порожденных машинных кодов и в этом случае, ( условно, должно выполняться).

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

    Назначение трансляторов, компиляторов и интерпретаторов. Примеры реализации

    Первые программы, которые создавались еще для ЭВМ первого поколения, сались непосредственно на языке машинных кодов. Это была поистине аде работа. Сразу стало ясно, что человек не должен и не может говорить на яз машинных команд, даже если он специалист по вычислительной технике. О; ко и все попытки научить компьютер говорить на языках людей успехов увенчались и вряд ли когда-либо увенчаются (на что есть определенные o6i тивные причины, рассмотренные в первой главе этого пособия).

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

    Первыми компиляторами были компиляторы с языков ассемблера или, как назывались, мнемокодов. Мнемокоды превратили «филькину грамоту» яз машинных команд в более-менее доступный пониманию специалиста язык ^ монических (преимущественно англоязычных) обозначений этих команд. ( давать программы уже стало значительно проще, но исполнять сам мнемс (язык ассемблера) ни один компьютер неспособен, соответственно, возникла обходимость в создании компиляторов. Эти компиляторы элементарно про но они продолжают играть существенную роль в системах программировани сей день. Более подробно о языке ассемблера и компиляторах с него расска: далее в соответствующем разделе.

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

    Появление языков высокого уровня существенно упростило процесс програи рования, хотя и не свело его до «уровня домохозяйки», как самонадеянно п гали некоторые авторы на заре рождения языков программирования 1 . Снатаких языков были единицы, затем десятки, сейчас, наверное, их насчитывается более сотни. Процессу этому не видно конца. Тем не менее по-прежнему преоб­ладают компьютеры традиционной, «неймановской», архитектуры, которые уме­ют понимать только машинные команды, поэтому вопрос о создании компилято­ров продолжает быть актуальным.

    Как только возникла массовая потребность в создании компиляторов, стала раз­виваться и специализированная теория. Со временем она нашла практическое приложение во множестве созданных компиляторов. Компиляторы создавались и продолжают создаваться не только для новых, но и для давно известных язы­ков. Многие производители от известных, солидных фирм (таких, как Microsoft или Inprise) до мало кому знакомых коллективов авторов выпускают на рынок все новые и новые образцы компиляторов. Это обусловлено рядом причин, кото­рые будут рассмотрены далее.

    Наконец, с тех пор как большинство теоретических аспектов в области ком­пиляторов получили свою практическую реализацию (а это, надо сказать, про­изошло довольно быстро, в конце 60-х годов), развитие компиляторов пошло по пути их дружественности человеку — пользователю, разработчику программ на языках высокого уровня. Логичным завершением этого процесса стало создание систем программирования — программных комплексов, объединяющих в себе кроме непосредственно компиляторов множество связанных с ними компонен­тов программного обеспечения. Появившись, системы программирования быстро завоевали рынок и ныне в массе своей преобладают на нем (фактически, обособ­ленные компиляторы — это редкость среди современных программных средств). О том, что представляют собой и как организованы современные системы про­граммирования, см. в главе «Современные системы программирования». Ныне компиляторы являются неотъемлемой частью любой вычислительной сис­темы. Без их существования программирование любой прикладной задачи было бы затруднено, а то и просто невозможно. Да и программирование специали­зированных системных задач, как правило, ведется если не на языке высокого уровня (в этой роли в настоящее время чаще всего применяется язык С), то на языке ассемблера, следовательно, применяется соответствующий компилятор. Программирование непосредственно на языках машинных кодов происходит ис­ключительно редко и только для решения очень узких вопросов. Несколько слов о примерах реализации компиляторов и интерпретаторов, а также о том, как они соотносятся с другими существующими программными средствами. Компиляторы, как будет показано далее, обычно несколько проще в реализации, чем интерпретаторы. По эффективности они также превосходят их — очевидно, что откомпилированный код будет исполняться всегда быстрее, чем происходит интерпретация аналогичной исходной программы. Кроме того, не каждый язык программирования допускает построение простого интерпретатора. Однако ин­терпретаторы имеют одно существенное преимущество — откомпилированный код всегда привязан к архитектуре вычислительной системы, на которую он ори­ентирован, а исходная программа — только к семантике языка программирова­ния, которая гораздо легче поддается стандартизации. Этот аспект первоначаль­но не принимали во внимание. Первыми компиляторами были компиляторы с мнемокодов. Их потомки — со­временные компиляторы с языков ассемблера — существую практически для всех известных вычислительных систем. Они предельно жестко ориентированы на архитектуру. Затем появились компиляторы с таких языков, как FORTRAN, ALGOL-68, PL/1. Они были ориентированы на большие ЭВМ с пакетной обра­боткой задач. Из вышеперечисленных только FORTRAN, пожалуй, продолжает использоваться по сей день, поскольку имеет огромное количество библиотек различного назначения [7]. Многие языки, родившись, так и не получили широ­кого распространения — ADA, Modula, Simula известны лишь узкому кругу спе­циалистов. В то же время на рынке программных систем доминируют компиля­торы языков, которым не прочили светлого будущего. В первую очередь, сейчас это С и C++. Первый из них родился вместе с операционными системами типа UNIX, вместе с нею завоевал свое «место под солнцем», а затем перешел под ОС других типов. Второй удачно воплотил в себе пример реализации идей объектно-ориентированного программирования на хорошо зарекомендовавшей себя прак­тической базе 1 . Еще можно упомянуть довольно распространенный Pascal, кото­рый неожиданно для многих вышел за рамки чисто учебного языка для универ­ситетской среды.

    История интерпретаторов не столь богата (пока!). Как уже было сказано, изна­чально им не предавали существенного значения, поскольку почти по всем пара­метрам они уступают компиляторам. Из известных языков, предполагавших интерпретацию, можно упомянуть разве что Basic, хотя большинству сейчас из­вестна его компилируемая реализация Visual Basic, сделанная фирмой Microsoft [3, 63]. Тем не менее сейчас ситуация несколько изменилась, поскольку вопрос о переносимости программ и их аппаратно-платформенной независимости приоб­ретает все большую актуальность с развитием сети Интернет. Самый известный сейчас пример — это язык Java (сам по себе он сочетает компиляцию и интерпре­тацию), а также связанный с ним JavaScript. В конце концов, язык HTML, на ко­тором зиждется протокол HTTP, давший толчок столь бурному развитию Все­мирной сети, — это тоже интерпретируемый язык. По мнению автора, в области появления новых интерпретаторов всех еще ждут сюрпризы, и появились уже первые из них — например, язык С# («си-диез», но название везде идет как «Си шарп»), анонсируемый фирмой Microsoft.

    О б истории языков программирования и современном состоянии рынка компи­ляторов можно говорить долго и много. Автор считает возможным ограничиться уже сказанным, поскольку это не является целью данного пособия. Желающие могут обратиться к литературе [7, 8, 14, 23, 30, 45, 66, 77, 81].

    Этапы трансляции. Общая схема работы транслятора

    На рис. 13.1 представлена общая схема работы компилятора. Из нее видно, что ъ целом процесс компиляции состоит из двух основных этапов — синтеза и анализа.

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

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

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

    Эти этапы, в свою Очередь, состоят из более мелких этапов, называемых фазами компиляции. Состав фаз компиляции приведен в самом общем виде, их конкрет­ная реализация и процесс взаимодействия

    Во-первых, он является распознавателем для языка исходной программы. То ее он должен получить на вход цепочку символов входного языка, проверить принадлежность языку и, более того, выявить правила, по которым эта цепоч была построена (поскольку сам ответ на вопрос о принадлежности «да» и. «нет» представляет мало интереса). Интересно, что генератором цепочек входи го языка выступает пользователь — автор входной программы.

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

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

    Лексический анализ (сканер) — это часть компилятора, которая читает лите] программы на исходном языке и строит из них слова (лексемы) исходного яз ка. На вход лексического анализатора поступает текст исходной программ а выходная информация передаётся для дальнейшей обработки компилятор на этапе синтаксического разбора. С теоретической точки зрения лексическ анализатор не является обязательной, необходимой частью компилятора. Од1 ко существует причины, которые определяют его присутствие практически всех компиляторах. Более подробно см. раздел «Лексические анализаторы (а неры). Принципы построения сканеров».

    Синтаксический разбор — это основная часть компилятора на этапе анализа. О выполняет выделение синтаксических конструкций в тексте исходной прогре мы, обработанном лексическим анализатором. На этой же фазе компиляц проверяется синтаксическая правильность программы. Синтаксический раз£ играет главную роль — роль распознавателя текста входного языка програмл рования (см. раздел «Синтаксические анализаторы. Синтаксически управл; мый перевод» этой главы).

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

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

    Генерация кода — это фаза, непосредственно связанная с порождением кома составляющих предложения выходного языка и в целом текст результируюи

    могут, конечно, различаться в зави­симости от версии компилятора. Однако в том или ином виде все представлен­ные фазы практически всегда присутствуют в каждом конкретном компиляторе [26, 40].

    Компилятор в целом с точки зрения теории формальных языков выступает в «двух ипостасях», выполняет две основные функции. программы. Это основная фаза на этапе синтеза результирующей программы. Кроме непосредственного порождения текста результирующей программы, гене­рация обычно включает в себя также оптимизацию — процесс, связанный с обра­боткой уже порожденного текста. Иногда оптимизацию выделяют в отдельную фазу компиляции, так как она оказывает существенное влияние на качество и эффективность результирующей программы (см. разделы «Генерация кода. Ме­тоды генерации кода» и « Оптимизация кода. Основные методы оптимизации», глава 14).

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

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

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

    Понятие прохода. Многопроходные и однопроходные компиляторы

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

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

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

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

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

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

    Однако сократить число проходов не всегда удается. Количество необходимых проходов определяется прежде всего грамматикой и семантическими правилами исходного языка. Чем сложнее грамматика языка и чем больше вариантов пред­полагают семантические правила — тем больше проходов будет выполнять ком­пилятор (конечно, играет свою роль и квалификация разработчиков компилято­ра). Например, именно поэтому обычно компиляторы с языка Pascal работают быстрее, чем компиляторы с языка С — грамматика языка Pascal более проста, а семантические правила более жесткие. Однопроходные компиляторы — редкость, они возможны только для очень про­стых языков. Реальные компиляторы выполняют, как правило, от двух до пяти проходов. Таким образом, реальные компиляторы являются многопроходными. Наиболее распространены двух- и трехпроходные компиляторы, например: пер­вый проход — лексический анализ, второй — синтаксический разбор и семанти­ческий анализ, третий — генерация и оптимизация кода (варианты исполнения, конечно, зависят от разработчика). В современных системах программирования нередко первый проход компилятора (лексический анализ кода) выполняется параллельно с редактированием кода исходной программы (такой вариант по­строения компиляторов рассмотрен далее в этой главе).

    Интерпретаторы. Особенности построения интерпретаторов

    Интерпретатор — это программа, которая воспринимает входную программу на исходном языке и выполняет ее. Как уже было сказано выше, основное отличие интерпретаторов от трансляторов и компиляторов заключается в том, что интер­претатор не порождает результирующую программу, а просто выполняет исход­ную программу.

    Термин «интерпретатор» (interpreter), как и «транслятор», означает «перевод­чик». С точки зрения терминологии эти понятия схожи, но с точки зрения тео­рии формальных языков и компиляции между ними большая принципиальная разница. Если понятия «транслятор» и «компилятор» почти неразличимы, то с понятием «интерпретатор» их путать никак нельзя.

    Простейшим способом реализации интерпретатора можно было бы считать ва­риант, когда исходная программа сначала полностью транслируется в машинные команды, а затем сразу же выполняется. В такой реализации интерпретатор, по сути, мало бы чем отличался от компилятора с той лишь разницей, что результи­рующая программа в нем была бы недоступна пользователю. Недостатком тако­го интерпретатора было бы то, что пользователь должен был бы ждать компиля­ции всей исходной программы прежде, чем начнется ее выполнение. По сути, в таком интерпретаторе не было бы никакого особого смысла — он не давал бы никаких преимуществ по сравнению с аналогичным компилятором 1 . Поэтому подавляющее большинство интерпретаторов действует так, что испол­няет исходную программу последовательно, по мере ее поступления на вход ин­терпретатора. Тогда пользователю не надо ждать завершения компиляции всей исходной программы. Более того, он может последовательно вводить исходную программу и тут же наблюдать результат ее выполнения по мере ввода команд [82].

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

    Отсутствие шага оптимизации определяет еще одну особенность, характерную для многих интерпретаторов: в качестве внутреннего представления программы в них очень часто используется обратная польская запись (см. раздел «Генера­ция кода. Методы генерации кода», глава 14). Эта удобная форма представления операций обладает только одним существенным недостатком — она плохо подда­ется оптимизации. Но в интерпретаторах именно это как раз и не требуется.

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

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

    Преимуществом интерпретатора является независимость выполнения програм мы от архитектуры целевой вычислительной системы. В результате компиляци: получается объектный код, который всегда ориентирован на определенную архн тектуру. Для перехода на другую архитектуру целевой вычислительной систем] программу требуется откомпилировать заново. А для интерпретации программ] необходимо иметь только ее исходный текст и интерпретатор с соответствующе го языка.

    Интерпретаторы долгое время значительно уступали в распространенности коь пиляторам. Как правило, интерпретаторы существовали для ограниченного крз га относительно простых языков программирования (таких, например, как Basic Высокопроизводительные профессиональные средства разработки программш го обеспечения строились на основе компиляторов.

    Новый импульс развитию интерпретаторов придало распространение глобал] ных вычислительных сетей. Такие сети могут включать в свой состав ЭВМ ра: личной архитектуры, и тогда требование единообразного выполнения на каждс из них текста исходной программы становится определяющим. Поэтому с разв] тием глобальных сетей и распространением всемирной сети Интернет появило 1 .

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

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

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

    Например, следующий текст определяет макрокоманду push_0 в языке ассембле­ра процессора типа Intel 8086:

    хог ах,ах ■ push ax endm

    Семантика этой макрокоманды заключается в записи числа «0» в стек через ре­гистр процессора ах. Тогда везде в тексте программы, где встретится макроко­манда

    она будет заменена в результате макроподстановки на последовательность ко­манд:

    хог ах,ах ■ push ax

    Это самый простой вариант макроопределения. Существует возможность созда­вать более сложные макроопределения с параметрами. Одно из таких макрооп­ределений описано ниже:

    Глубина такой рекурсии, как правило, сильно ограничена. На последовательность рекур­сивных вызовов макрокоманд налагаются обычно существенно более жесткие ограниче­ния, чем на последовательность рекурсивных вызовов процедур и функций, которая при стековой организации дисплея памяти ограничена только размером стека передачи пара­метров. add_abx macro xl,x2

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

    add_abx4,8 будет в результате макроподстановки заменена на последовательность команд:

    add ах,4 add bx.4 add ex,8 push ax

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

    loop_ax macro xl,x2,yl

    хог bx.bx loopax: add bx.yl

    Здесь метка 1 oopax является локальной, определенной только внутри данного мак­роопределения. В этом случае уже не может быть выполнена простая текстовая подстановка макрокоманды в текст программы, поскольку если данную макро­команду выполнить дважды, то это приведет к появлению в тексте программы двух одинаковых меток 1 оорах. В таком варианте макрогенератор должен исполь­зовать более сложные методы текстовых подстановок, аналогичные тем, что ис­пользуются в компиляторах при идентификации лексических элементов вход­ной программы, чтобы дать всем возможным локальным переменным и меткам макрокоманд уникальные имена в пределах всей программы. Макроопределения и макрокоманды нашли применение не только в языках ас­семблера, но и во многих языках высокого уровня. Там их обрабатывает специ­альный модуль, называемый препроцессором языка (например, широко известен препроцессор языка С). Принцип обработки остается тем же самым, что и для программ на языке ассемблера — препроцессор выполняет текстовые подстанов­ки непосредственно над строками самой исходной программы. В языках высокого уровня макроопределения должны быть отделены от текста самой исходной программы, чтобы препроцессор не мог спутать их с синтаксиче­скими конструкциями входного языка. Для этого используются либо специаль­ные символы и команды (команды препроцессора), которые никогда не могут встречаться в тексте исходной программы, либо макроопределения встречаются

    внутри незначащей части исходной программы — входят в состав комментариев (такая реализация существует, например, в компиляторе с языка Pascal, создан­ном фирмой Borland). Макрокоманды, напротив, могут встречаться в произволь­ном месте исходного текста программы, и синтаксически их вызов может не от­личаться от вызова функций во входном языке.

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

    Рассмотрим пример на языке С. Если описана функция

    int fKint a) < return a + а: >и аналогичная ей макрокоманда

    #define f2(a) ((a) + (а)) то результат их вызова не всегда будет одинаков.

    Действительно, вызовы j=fl(i) и j=f2(i) (где i и j — некоторые целочисленные переменные) приведут к одному и тому же результату. Но вызовы j=fl(++i) и j=f2(++i) дадут разные значения переменной j. Дело в том, что поскольку f2 — это макроопределение, то во втором случае будет выполнена текстовая подста­новка, которая приведет к последовательности операторов j=((++i) + (++i)). Видно, что в этой последовательности операция ++i будет выполнена дважды, в отличие от вызова функции fl(++i), где она выполняется только один раз.

    5. Таблицы идентификаторов. Организация таблиц идентификаторов. Назначение и особенности построения таблиц идентификаторов. Простейшие методы построения таблиц идентификаторов. Хэш-функция и хэш-адресация.

    Таблицы идентификаторов. Организация таблиц идентификаторов

    Назначение и особенности построения таблиц идентификаторов

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

    компиляции. Для этой цели, как было сказано выше, в компиляторах использу­ются специальные хранилища данных, называемые таблицами символов или таблицами идентификаторов.

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

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

    О имя переменной;

    О тип данных переменной;

    О область памяти, связанная с переменной;

    О название константы (если оно имеется);

    О значение константы;

    О тип данных константы (если требуется);

    О количество и типы формальных аргументов функции;

    О тип возвращаемого результата;

    О адрес кода функции.

    Приведенный выше состав хранимой информации, конечно же, является только примерным. Другие примеры такой информации указаны в [23, 42, 74]. Конкрет­ное наполнение таблиц идентификаторов зависит от реализации компилятора. Кроме того, не вся информация, хранимая в таблице идентификаторов, заполняется компилятором сразу — он может несколько раз выполнять обращение к данным в таблице идентификаторов на различных фазах компиляции. Например, имена переменных могут быть выделены на фазе лексического анализа, типы данных для переменных — на фазе синтаксического разбора, а область памяти связыва­ется с переменной только на фазе подготовки к генерации кода.

    Вне зависимости от реализации компилятора принцип его работы с таблицей идентификаторов остается одним и тем же — на различных фазах компиляции компилятор вынужден многократно обращаться к таблице для поиска информа­ции и записи новых данных. Как правило, каждый элемент в исходной програм­ме однозначно идентифицируется своим именем (вопросы идентификации более подробно рассмотрены в разделе «Семантический анализ и подготовка к генера­ции кода», глава 14). Поэтому компилятору приходится часто выполнять поиск

    необходимого элемента в таблице идентификаторов по его имени, в то время как процесс заполнения таблицы выполняется нечасто — новые идентификаторы описываются в программе гораздо реже, чем используются. Отсюда можно сде­лать вывод, что таблицы идентификаторов должны быть организованы таким об­разом, чтобы компилятор имел возможность максимально быстрого поиска нуж­ного ему элемента [33].

    Простейшие методы построения таблиц идентификаторов

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

    Поиск нужного элемента в таблице будет в этом случае заключаться в последо­вательном сравнении искомого элемента с каждым элементом таблицы, пока не будет найден подходящий. Тогда, если за единицу принять время, затрачиваемое компилятором на сравнение двух элементов (как правило, это сравнение двух строк), то для таблицы, содержащей N элементов, в среднем будет выполнено N/2 сравнений [14].

    Заполнение такой таблицы будет происходить элементарно просто — добавлени­ем нового элемента в ее конец, и время, требуемое на добавление элемента (Т3), не будет зависеть от числа элементов в таблице N. Но если N велико, то поиск потребует значительных затрат времени. Время поиска (Т„) в такой таблице можно оценить как Тп = O(N). Поскольку поиск в таблице идентификаторов является чаще всего выполняемой компилятором операцией, а количество раз­личных идентификаторов даже в реальной исходной программе достаточно ве­лико (от нескольких сотен до нескольких тысяч элементов), то такой способ организации таблиц идентификаторов является неэффективным.

    Поиск может быть выполнен более эффективно, если элементы таблицы упоря­дочены (отсортированы) согласно некоторому естественному порядку.

    В нашем случае, когда поиск будет осуществляться по имени идентификатора, наиболее естественно расположить элементы таблицы в прямом или обратном алфавитном порядке. Эффективным методом поиска в упорядоченном списке из N элементов является бинарный или логарифмический поиск. Символ, который следует найти, сравнивается с элементом (N+l)/2 в середине таблицы. Если этот элемент не является искомым, то мы должны просмотреть только блок элемен­тов, пронумерованных от 1 до (N+l)/2-l, или блок элементов от (N+l)/2+l до N в зависимости от того, меньше или больше искомый элемент того, с кото­рым его сравнили. Затем процесс повторяется над нужным блоком в два раза меньшего размера. Так продолжается до тех пор, пока либо элемент не будет найден, либо алгоритм не дойдет до очередного блока, содержащего один или два элемента (с которыми уже можно выполнить прямое сравнение искомого элемента).

    Так как на каждом шаге число элементов, которые могут содержать искомый эле­мент, сокращается наполовину, то максимальное число сравнений равно l+log2(N).

    Тогда время поиска элемента в таблице идентификаторов можно оценить как Тп = O(log2 N). Для сравнения: при N=128 бинарный поиск требует самое боль­шее 8 сравнений, а поиск в неупорядоченной таблице — в среднем 64 сравнения. Метод называют «бинарным поиском», поскольку на каждом шаге объем рас­сматриваемой информации сокращается в два раза, а «логарифмическим» — по­скольку время, затрачиваемое на поиск нужного элемента в массиве, имеет лога­рифмическую зависимость от общего количества элементов в нем.

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

    При добавлении каждого нового элемента в таблицу сначала надо определить место, куда поместить новый элемент, а потом выполнить перенос части инфор­мации в таблице, если элемент добавляется не в ее конец. Если пользоваться стандартными алгоритмами, применяемыми для организации упорядоченных массивов данных [14], а поиск места включения вести с помощью алгоритма би­нарного поиска, то среднее время, необходимое на помещение всех элементов в таблицу, можно оценить следующим образом:

    Здесь к — некоторый коэффициент, отражающий соотношение между времена­ми, затрачиваемыми компьютером на выполнение операции сравнения и опера­ции переноса данных.

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

    Построение таблиц идентификаторов по методу бинарного дерева

    Можно сократить время поиска искомого элемента в таблице идентификато­ров, не увеличивая значительно время, необходимое на ее заполнение. Для этого надо отказаться от организации таблицы в виде непрерывного массива данных.

    Как минимум при добавлении нового идентификатора в таблицу компилятор должен проверить, существует или нет там такой идентификатор, так как в большинстве языков программирования ни один идентификатор не может быть описан более одного раза. Следовательно, каждая операция добавления нового элемента влечет, как правило, не менее одной операции поиска. Существует метод построения таблиц, при котором таблица имеет форму бинар­ного дерева. Каждый узел дерева представляет собой элемент таблицы, причем корневой узел является первым элементом, встреченным при заполнении табли­цы. Дерево называется бинарным, так как каждая вершина в нем может иметь не более двух ветвей (и, следовательно, не более двух нижележащих вершин). Для определенности будем называть две ветви «правая» и «левая».

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

    Шаг 1. Выбрать очередной идентификатор из входного потока данных. Если оче­редного идентификатора нет, то построение дерева закончено.

    Шаг 2. Сделать текущим узлом дерева корневую вершину. Шаг 3. Сравнить очередной идентификатор с идентификатором, содержащемся в текущем узле дерева.

    Шаг 4. Если очередной идентификатор меньше, то перейти к шагу 5, если ра­вен — сообщить об ошибке и прекратить выполнение алгоритма (двух одинако­вых идентификаторов быть не должно!), иначе — перейти к шагу 7. Шаг 5. Если у текущего узла существует левая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе — перейти к шагу 6.

    Шаг 6. Создать новую вершину, поместить в нее очередной идентификатор, сде­лать эту новую вершину левой вершиной текущего узла и вернуться к шагу 1.

    Шаг 7. Если у текущего узла существует правая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе — перейти к шагу 8.

    Шаг 8. Создать новую вершину, поместить в нее очередной идентификатор, сде­лать эту новую вершину правой вершиной текущего узла и вернуться к шагу 1.

    Рассмотрим в качестве примера последовательность идентификаторов GA, Dl, М22, Е, А12, ВС, F. На рис. 13.2 проиллюстрирован весь процесс построения бинарного дерева для этой последовательности идентификаторов.

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

    Шаг 1. Сделать текущим узлом дерева корневую вершину. Шаг 2. Сравнить искомый идентификатор с идентификатором, содержащемся в текущем узле дерева.

    Шаг 4. Если идентификаторы совпадают, то искомый идентификатор найден, ал­горитм завершается, иначе — надо перейти к шагу 5.

    Шаг 5. Если очередной идентификатор меньше, то перейти к шагу 6, иначе — пе­рейти к шагу 7.

    Шаг 6. Если у текущего узла существует левая вершина, то сделать ее текущим узлом и вернуться к шагу 2, иначе искомый идентификатор не найден, алгоритм завершается.

    Шаг 7. Если у текущего узла существует правая вершина, то сделать ее текущим узлом и вернуться к шагу 2, иначе искомый идентификатор не найден, алгоритм завершается.

    Например, произведем поиск в дереве, изображенном на рис. 13.2, идентифи­катора А12. Берем корневую вершину (она становится текущим узлом), сравни­ваем идентификаторы GA и А12. Искомый идентификатор меньше — текущим узлом становится левая вершина D1. Опять сравниваем идентификаторы. Иско­мый идентификатор меньше — текущим узлом становится левая вершина А12. При следующем сравнении искомый идентификатор найден.

    Если искать отсутствующий идентификатор — например, АН, — то поиск опять пойдет от корневой

    Если искать отсутствующий идентификатор — например, АН, — то поиск опять пойдет от корневой вершины. Сравниваем идентификаторы GA и АН. Искомый идентификатор меньше — текущим узлом становится левая вершина D1. Опять сравниваем идентификаторы. Искомый идентификатор меньше — текущим уз­лом становится левая вершина А12. Искомый идентификатор меньше, но левая вершина у узла А12 отсутствует, поэтому в данном случае искомый идентифика­тор не найден.

    Для данного метода число требуемых сравнений и форма получившегося дерева во многом зависят от того порядка, в котором поступают идентификаторы. Сравниваем идентификаторы GA и АН. Искомый идентификатор меньше — текущим узлом становится левая вершина D1. Опять сравниваем идентификаторы. Искомый идентификатор меньше —

    текущим уз­лом становится левая вершина А12. Искомый идентификатор меньше, но левая вершина у узла А12 отсутствует, поэтому в данном случае искомый идентифика­тор не найден.

    Для данного метода число требуемых сравнений и форма получившегося дерева во многом зависят от того порядка, в котором поступают идентификаторы. На­пример, если в рассмотренном выше примере вместо последовательности идеи-тификаторов GA, Dl, M22, E, A12, ВС, F взять последовательность А12, GA, Dl, M22, E, ВС, F, то полученное дерево будет иметь иной вид. А если в качестве при­мера взять последовательность идентификаторов А, В, С, D, E, F, то дерево вы­родится в упорядоченный однонаправленный связный список. Эта особенность является недостатком данного метода организации таблиц идентификаторов. Дру­гим недостатком является необходимость работы с динамическим выделением памяти при построении дерева.

    Если предположить, что последовательность идентификаторов в исходной про­грамме является статистически неупорядоченной (что в целом соответствует действительности), то можно считать, что построенное бинарное дерево будет невырожденным. Тогда среднее время на заполнение дерева (Т3) и на поиск эле­мента в нем (Т„) можно оценить следующим образом [6, т. 2]:

    В целом метод бинарного дерева является довольно удачным механизмом для организации таблиц идентификаторов. Он нашел свое применение в ряде ком­пиляторов. Иногда компиляторы строят несколько различных деревьев для идентификаторов разных типов и разной длины [23, 74].

    Хэш-функции и хэш-адресация

    Принципы работы хэш-функций

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

    Лучших результатов можно достичь, если применить методы, связанные с ис­пользованием хэш-функций и хэш-адресации.

    Хэш-функцией F называется некоторое отображение множества входных элемен­тов R на множество целых неотрицательных чисел Z: F(r) = n, reR, neZ. Сам термин «хэш-функция» происходит от английского термина «hash function» (hash — «мешать», «смешивать», «путать»). Вместо термина «хэширование» ино­гда используются термины «рандомизация», «переупорядочивание».

    Множество допустимых входных элементов R называется областью определе­ния хэш-функции. Множеством значений хэш-функции F называется подмно­жество М из множества целых неотрицательных чисел Z: McZ, содержащее все возможные значения, возвращаемые функцией F: VreR: F(r)eM. Процесс ото­бражения области определения хэш-функции на множество значений называет­ся «хэшированием».

    При работе с таблицей идентификаторов хэш-функция должна выполнять ото­бражение имен идентификаторов на множество целых неотрицательных чисел.

    Областью определения хэш-функции будет множество всех возможных имен идентификаторов.

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

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

    На рис. 13.3 проиллюстрирован метод организации таблиц идентификаторов с использованием хэш-адресации. Трем различным идентификаторам Alf A2, А3 со­ответствуют на рисунке три значения хэш-функции nlf n2, п3. В ячейки, адресуе­мые щ, п2, п3, помещается информация об идентификаторах А,, А2, А3. При поис­ке идентификатора А3 вычисляется значение адреса п3 и выбираются данные из соответствующей ячейки таблицы.

    Рис. 13.3. Организация таблицы идентификаторов с использованием хэш-адресации

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

    Метод имеет два очевидных недостатка. Первый из них — неэффективное ис­пользование объема памяти под таблицу идентификаторов: размер массива для ее хранения должен соответствовать области значений хэш-функции, в то вре­мя как реально хранимых в таблице идентификаторов может быть существенно меньше. Второй недостаток — необходимость соответствующего разумного вы­бора хэш-функции. Этому существенному вопросу посвящены следующие два подраздела.

    Построение таблиц идентификаторов на основе хэш-функций

    Существуют различные варианты хэш-функций. Получение результата хэш-функции — «хэширование» — обычно достигается за счет выполнения над це­почкой символов некоторых простых арифметических и логических операций. Самой простой хэш-функцией для символа является код внутреннего представ­ления в ЭВМ литеры символа. Эту хэш-функцию можно использовать и для це­почки символов, выбирая первый символ в цепочке. Так, если двоичное ASCII представление символа А есть 00100001, то результатом хэширования идентифи­катора АТаЫе будет код 00100001.

    Хэш-функция, предложенная выше, очевидно не удовлетворительна: при ис­пользовании такой хэш-функции возникнет новая проблема — двум различным идентификаторам, начинающимся с одной и той же буквы, будет соответство­вать одно и то же значение хэш-функции. Тогда при хэш-адресации в одну ячей­ку таблицы идентификаторов по одному и тому же адресу должны быть помеще­ны два различных идентификатора, что явно невозможно. Такая ситуация, когда двум или более идентификаторам соответствует одно и то же значение функции, называется коллизией. Возникновение коллизии проиллюстрировано на рис. 13.4 — двум различным идентификаторам At и А2 соответствуют два совпадающих зна­чения хэш-функции, п, = п2.

    Рис. 13.4. Возникновение коллизии при использовании хэш-адресации

    Естественно, что хэш-функция, допускающая коллизии, не может быть напря­мую использована для хэш-адресации в таблице идентификаторов. Причем дос­таточно получить хотя бы один случай коллизии на всем множестве идентифи­каторов, чтобы такой хэш-функцией нельзя было пользоваться непосредственно. Но в примере взята самая элементарная хэш-функция. А возможно ли построить нетривиальную хэш-функцию, которая бы полностью исключала возникновение коллизий?

    Очевидно, что для полного исключения коллизий хэш-функция должна быть взаимно однозначной: каждому элементу из области определения хэш-функции должно соответствовать одно значение из ее множества значений, но и каждому значению из множества значений этой функции должен соответствовать только один элемент из области ее определения. Тогда любым двум произвольным эле­ментам из области определения хэш-функции будут всегда соответствовать два различных ее значения. Теоретически для идентификаторов такую хэш-функ­цию построить можно, так как и область определения хэш-функции (все воз­можные имена идентификаторов), и область ее значений (целые неотрицатель­ные числа) являются бесконечными счетными множествами. Теоретически мож­но организовать взаимно однозначное отображение одного счетного множества на другое, но практически это сделать исключительно сложно 1 .

    Практически существует ограничение, делающее создание взаимно однозначной хэш-функции для идентификаторов невозможным. Дело в том, что в реальности область значений любой хэш-функции ограничена размером доступного адрес­ного пространства в данной архитектуре компьютера. При организации хэш-ад­ресации значение, используемое в качестве адреса таблицы идентификаторов, не может выходить за пределы, заданные адресной сеткой компьютера 2 . Множество адресов любого компьютера с традиционной архитектурой может быть велико, но всегда конечно, то есть ограничено. Организовать взаимно однозначное ото­бражение бесконечного множества на конечное даже теоретически невозможно. Можно учесть, что длина принимаемой во внимание строки идентификатора в реальных компиляторах также практически ограничена — обычно она лежит в пределах от 32 до 128 символов (то есть и область определения хэш-функции конечна). Но и тогда количество элементов в конечном множестве, составляю­щем область определения функции, будет превышать их количество в конечном множестве области значений функции (количество всех возможных идентифи­каторов все равно больше количества допустимых адресов в современных ком­пьютерах). Таким образом, создать взаимно однозначную хэш-функцию практи-чески ни в каком варианте невозможно. Следовательно, невозможно избежать возникновения коллизий.

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

    Для решения проблемы коллизии можно использовать много способов. Одним из них является метод «рехэширования» (или «расстановки»). Согласно этому методу, если для элемента А адрес h(A), вычисленный с помощью хэш-функции, указывает на уже занятую ячейку, то необходимо вычислить значение функции ni=ht(A) и проверить занятость ячейки по адресу щ. Если и она занята, то вы­числяется значение Ь2(А), и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение h;(A) совпадет с h(A). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет — выдается информация об ошибке размещения идентификатора в таблице. Осо­бенностью метода является то, что первоначально таблица идентификаторов должна быть заполнена информацией, которая позволила бы говорить о том, что все ее ячейки являются пустыми (не содержат данных). Например, если исполь­зуются указатели для хранения имен идентификаторов, то таблицу надо предва­рительно заполнить пустыми указателями.

    Такую таблицу идентификаторов можно организовать по следующему алгорит­му размещения элемента.

    Шаг 1. Вычислить значение хэш-функции n = h(A) для нового элемента А.

    Шаг 2. Если ячейка по адресу п пустая, то поместить в нее элемент А и завер­шить алгоритм, иначе i:=l и перейти к шагу 3.

    Шаг 3. Вычислить n; = hj(A). Если ячейка по адресу П| пустая, то поместить в нее элемент А и завершить алгоритм, иначе перейти к шагу 4.

    Шаг 4. Если п = щ, то сообщить об ошибке и завершить алгоритм, иначе i:-i+l и вернуться к шагу 3.

    Тогда поиск элемента А в таблице идентификаторов, организованной таким об­разом, будет выполняться по следующему алгоритму.

    Шаг 1. Вычислить значение хэш-функции n = h(A) для нового элемента А.

    Шаг 2. Если ячейка по адресу п пустая, то элемент не найден, алгоритм завер­шен, иначе сравнить имя элемента в ячейке п с именем искомого элемента А. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:= 1 и перей­ти к шагу 3.

    Шаг 3. Вычислить П] = h;(A). Если ячейка по адресу п, пустая или п = щ, то эле­мент не найден и алгоритм завершен, иначе сравнить имя элемента в ячейке П; с именем искомого элемента А. Если они совпадают, то элемент найден и алго­ритм завершен, иначе i:=i+l и повторить к шаг 3.

    Алгоритмы размещения и поиска элемента схожи по выполняемым операциям. Поэтому они будут совпадать и по оценкам времени, необходимого для их вы­полнения. При такой организации таблиц идентификаторов в случае возникновения кол­лизии алгоритм размещает элементы в пустых ячейках таблицы, выбирая их оп­ределенным образом. При этом элементы могут попадать в ячейки с адресами, которые потом будут совпадать со значениями хэш-функции, что приведет к воз­никновению новых, дополнительных коллизий. Таким образом, количество опе­раций, необходимых для поиска или размещения в таблице элемента, зависит от заполненности таблицы. Естественно, функции hj(A ) должны вычисляться еди­нообразно на этапах размещения и поиска элемента. Вопрос только в том, как организовать вычисление функций h;(A).

    Самым простым методом вычисления функции hj(A) является ее организация в виде hi(A) = (h(A) + pj) mod Nm, где pj — некоторое вычисляемое целое число, a Nm — максимальное число элементов в таблице идентификаторов. В свою оче­редь, самым простым подходом здесь будет положить pj = i. Тогда получаем формулу h;(A) = (h(A)+i) mod Nm. В этом случае при совпадении значений хэш-функции для каких-либо элементов поиск свободной ячейки в таблице начина­ется последовательно от текущей позиции, заданной хэш-функцией h(A).

    Этот способ нельзя признать особенно удачным — при совпадении хэш-адресов элементы в таблице начинают группироваться вокруг них, что увеличивает чис­ло необходимых сравнений при поиске и размещении. Среднее время поиска элемента в такой таблице в зависимости от числа операций сравнения можно оценить следующим образом [23]:

    Здесь Lf — (load factor) степень заполненности таблицы идентификаторов — от­ношение числа занятых ячеек таблицы к максимально допустимому числу эле­ментов в ней: Lf = N/Nm.

    Рассмотрим в качестве примера ряд последовательных ячеек таблицы п(, п2, п3, п4, п5 и ряд идентификаторов, которые надо разместить в ней: А(, А2, А3, А4, А5 при условии, что h(Aj) = h(A2) = h(A5) = n^ h(A3) = n2; h(A4) = n4. Последова­тельность размещения идентификаторов в таблице при использовании простей­шего метода рехэширования показана на рис. 13.5. В итоге после размещения в таблице для поиска идентификатора А) потребуется 1 сравнение, для А2 — 2 сравнения, для А3 — 2 сравнения, для А4 — 1 сравнение и для А5 — 5 сравнений.

    Даже такой примитивный метод рехэширования является достаточно эффектив­ным средством организации таблиц идентификаторов при неполном заполнении таблицы. Имея, например, даже заполненную на 90 % таблицу для 1024 иденти­фикаторов, в среднем необходимо выполнить 5,5 сравнений для поиска одного идентификатора, в то время как даже логарифмический поиск дает в среднем от 9 до 10 сравнений. Сравнительная эффективность метода будет еще выше при росте числа идентификаторов и снижении заполненности таблицы.

    Среднее время на помещение одного элемента в таблицу и на поиск элемента в таблице можно снизить, если применить более совершенный метод рехэширо­вания. Одним из таких методов является использование в качестве р, для функ­ции h,(A) — (h(A)+pi)modNm последовательности псевдослучайных целых чисел ри р2, . Рк- При хорошем выборе генератора псевдослучайных чисел длина по-

    следовательности к будет k=Nm. Тогда среднее время поиска одного элемента в таблице можно оценить следующим образом [23]:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Название Лекции по конструированию компиляторов
    Дата публикации 08.02.2014
    Размер 91.59 Kb.
    Тип Книга

    skachate.ru > Информатика > Книга

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    4.3. Атрибутные грамматики 70

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

    4.3.2. Атрибутированное дерево разбора 71

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

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

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

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

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

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

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

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

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

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

    6.4. Функции расстановки 94

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

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

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

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

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

    7.2. Трехадресный код 102

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

    7.4. Виртуальная машина Java 109

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

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

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

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

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

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

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

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

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

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

    8.6. Распределение регистров при вычислении
    арифметических выражений 136

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

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

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

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

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

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

    Глава 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. Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. — М.: Вильямс, 2001.
    2. Карпов Ю. Г. Основы построения трансляторов. — М.: BHV, 2005.
    3. Свердлов С. З. Языки программирования и методы трансляции. — М.: Питер, 2007.
    4. Опалева Э. А., Самойленко В.П. Языки программирования и методы трансляции. — М.: BHV, 2005.

    Лекция 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Лекция 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Основы конструирования компиляторов. В.А.Серебряков, М.П.Галочкин

      Яков Алфимов 2 лет назад Просмотров:

    1 Основы конструирования компиляторов В.А.Серебряков, М.П.Галочкин

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

    3 Оглавление 1 Введение Место компилятора в программном обеспечении Структура компилятора Языки и их представление Алфавиты, цепочки и языки Представление языков Грамматики Формальное определение грамматики Типы грамматик и их свойства Лексический анализ Регулярные множества и выражения Конечные автоматы Алгоритмы построения конечных автоматов Построение недетерминированного конечного автомата по регулярному выражению Построение детерминированного конечного автомата по недетерминированному Построение детерминированного конечного автомата по регулярному выражению Построение детерминированного конечного автомата с минимальным числом состояний Регулярные множества и их представления Программирование лексического анализа Конструктор лексических анализаторов LEX Синтаксический анализ КС-грамматики и МП-автоматы Преобразования КС-грамматик Предсказывающий разбор сверху-вниз Алгоритм разбора сверху-вниз

    4 4 ОГЛАВЛЕНИЕ Функции FIRST и F OLLOW Конструирование таблицы предсказывающего анализатора LL(1)-грамматики Удаление левой рекурсии Левая факторизация Рекурсивный спуск Восстановление после синтаксических ошибок Разбор снизу-вверх типа сдвиг-свертка Основа LR(1)-анализаторы Конструирование LR(1)-таблицы LR(1)-грамматики Восстановление после синтаксических ошибок Варианты LR-анализаторов Элементы теории перевода Преобразователи с магазинной памятью Синтаксически управляемый перевод Схемы синтаксически управляемого перевода Обобщенные схемы синтаксически управляемого перевода Атрибутные грамматики Определение атрибутных грамматик Классы атрибутных грамматик и их реализация Язык описания атрибутных грамматик Проверка контекстных условий Описание областей видимости и блочной структуры Занесение в среду и поиск объектов Организация таблиц символов Таблицы идентификаторов Таблицы расстановки Таблицы расстановки со списками Функции расстановки Таблицы на деревьях Реализация блочной структуры Сравнение методов реализации таблиц Промежуточное представление программы Представление в виде ориентированного графа Трехадресный код Линеаризованные представления Виртуальная машина Java Организация памяти

    5 ОГЛАВЛЕНИЕ Набор команд виртуальной машины Организация информации в генераторе кода Уровень промежуточного представления Генерация кода Модельмашины Динамическая организация памяти Организация магазина со статической цепочкой Организация магазина с дисплеем Назначение адресов Трансляция переменных Трансляция целых выражений Трансляция арифметических выражений Трансляция логических выражений Выделение общих подвыражений Генерация оптимального кода методами синтаксического анализа Сопоставление образцов Синтаксический анализ для T-грамматик Выбор дерева вывода наименьшей стоимости Атрибутная схема для алгоритма сопоставления образцов Системы автоматизации построения трансляторов СистемаСУПЕР СистемаYacc

    7 Глава 1 Введение 1.1 Место компилятора в программном обеспечении Компиляторы составляют существенную часть программного обеспечения ЭВМ. Это связано с тем, что языки высокого уровня стали основным средством разработки программ. Только очень незначительная часть программного обеспечения, требующая особой эффективности, программируется с помощью ассемблеров. В настоящее время распространено довольно много языков программирования. Наряду с традиционными языками, такими, как Фортран, широкое распространение получили так называемые универсальные языки (Паскаль, Си, Модула-2, Ада и другие), а также некоторые специализированные (например, язык обработки списочных структур Лисп). Кроме того, большое распространение получили языки, связанные с узкими предметными областями, такие, как входные языки пакетов прикладных программ. Для некоторых языков имеется довольно много реализаций. Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа IBM PC на рынке десятки. С другой стороны, постоянно растущая потребность в новых компиляторах связана с бурным развитием архитектур ЭВМ. Это развитие идет по различным направлениям. Совершенствуются старые архитектуры как в концептуальном отношении, так и по отдельным, конкретным линиям. Это можно проиллюстрировать на примере микропроцессора Intel- 80X86. Последовательные версии этого микропроцессора 8086, 80186, 80286, 80386, 80486, отличаются не только техническими характеристиками, но и, что более важно, новыми возможностями и, значит, изменением (расширением) системы команд. Естественно, это требует новых компиляторов (или модификации старых). То же можно сказать о микропроцессорах Motorola 68010, 68020, 68030, В рамках традиционных последовательных машин возникает боль- 7

    8 8 ГЛАВА 1. ВВЕДЕНИЕ шое число различных направлений архитектур. Примерами могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как Intel, Motorola, Sun, начинают переходить на выпуск машин с RISC-архитектурами. Естественно, для каждой новой системы команд требуется полный набор новых компиляторов с распространенных языков. Наконец, бурно развиваются различные параллельные архитектуры. Среди них отметим векторные, многопроцессорные, с широким командным словом (вариантом которых являются суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с параллельной архитектурой, начиная от супер-эвм (Cray, CDC и другие), через рабочие станции (например, IBM RS/6000) и кончая персональными (например, на основе микропроцессора I-860). Естественно, для каждой из машин создаются новые компиляторы для многих языков программирования. Здесь необходимо также отметить, что новые архитектуры требуют разработки совершенно новых подходов к созданию компиляторов, так что наряду с собственно разработкой компиляторов ведется и большая научная работа по созданию новых методов трансляции. 1.2 Структура компилятора Обобщенная структура компилятора и основные фазы компиляции показаны на рис На фазе лексического анализа входная программа, представляющая собой поток литер, разбивается на лексемы слова в соответствии с определениями языка. Основными формализмами, лежащим в основе реализации лексических анализаторов, являются конечные автоматы и регулярные выражения. Лексический анализатор может работать в двух основных режимах: либо как подпрограмма, вызываемая синтаксическим анализатором для получения очередной лексемы, либо как полный проход, результатом которого является файл лексем. В процессе выделения лексем лексический анализатор может как самостоятельно строить таблицы объектов (идентификаторов, строк, чисел и т.д.), так и выдавать значения для каждой лексемы при очередном к нему обращении. В этом случае таблицы объектов строятся в последующих фазах (например, в процессе синтаксического анализа). На этапе лексического анализа обнаруживаются некоторые (простейшие) ошибки (недопустимые символы, неправильная запись чисел, идентификаторов и др.). Основная задача синтаксического анализа разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящее время чаще всего используется либо LL(1)-анализ (и его вариант рекурсивный спуск), либо LR(1)-анализ и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора, LR(1) при исполь-

    9 1.2. СТРУКТУРА КОМПИЛЯТОРА 9 E_dkbq_kdbc ZgZeba Dhg_qgu_ Z\lhfZlu >bz]ghklbdz Ihlhde_dk_f lz[ebpuh[t_dlh\ KbglZdkbq_kdbc ZgZeba DK]jZffZlbdb >bz]ghklbdz >_j_\hjza[hjz lz[ebpuh[t_dlh\ Dhgl_dklguc ZgZeba :ljb[mlgu_ ]jzffzlbdb >bz]ghklbdz :ljb[mlbjh\zggh_^_j_\h lz[ebpuh[t_dlh\ =_g_jzpby ijhf_`mlhqgh]h ij_^klz\e_gby KMljZgkeypby Ijhf_`mlhqgZynhjfZ ij_nbdkgzyihkl nbdkgzyljhcdbb ^j HilbfbaZpby Ihlhdh\uc ZgZeba Ijhf_`mlhqgZynhjfZ hjb_glbjh\zgguc]jzn =_g_jzpbydh^z LZ[ebpuj_r_gbc ^bgzfbq_kdh_ ijh]jzffbjh\zgb_ H[t_dlgucfh^mev Рис. 1.1:

    10 10 ГЛАВА 1. ВВЕДЕНИЕ зовании систем автоматического построения синтаксических анализаторов. Результатом синтаксического анализа является синтаксическое дерево со ссылками на таблицы объектов. В процессе синтаксического анализа также обнаруживаются ошибки, связанные со структурой программы. На этапе контекстного анализа выявляются зависимости между частями программы, которые не могут быть описаны контекстно-свободным синтаксисом. Это в основном связи описание-использование, в частности, анализ типов объектов, анализ областей видимости, соответствие параметров, метки и другие. В процессе контекстного анализа таблицы объектов пополняются информацией об описаниях (свойствах) объектов. Основным формализмом, использующимся при контекстном анализе, является аппарат атрибутных грамматик. Результатом контекстного анализа является атрибутированное дерево программы. Информация об объектах может быть как рассредоточена в самом дереве, так и сосредоточена в отдельных таблицах объектов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов. Затем программа может быть переведена во внутреннее представление. Это делается для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразования программы во внутреннее представление является желание иметь переносимый компилятор. Тогда только последняя фаза (генерация кода) является машинно-зависимой. В качестве внутреннего представления может использоваться префиксная или постфиксная запись, ориентированный граф, тройки, четверки и другие. Фаз оптимизации может быть несколько. Оптимизации обычно делят на машинно-зависимые и машинно-независимые, локальные и глобальные. Часть машинно-зависимой оптимизации выполняется на фазе генерации кода. Глобальная оптимизация пытается принять во внимание структуру всей программы, локальная только небольших ее фрагментов. Глобальная оптимизация основывается на глобальном потоковом анализе, который выполняется на графе программы и представляет по существу преобразование этого графа. При этом могут учитываться такие свойства программы, как межпроцедурный анализ, межмодульный анализ, анализ областей жизни переменных и т.д. Наконец, генерация кода последняя фаза трансляции. Результатом ее является либо ассемблерный модуль, либо объектный (или загрузочный) модуль. В процессе генерации кода могут выполняться некоторые локальные оптимизации, такие как распределение регистров, выбор длинных или коротких переходов, учет стоимости команд при выборе конкретной последовательности команд. Для генерации кода разработаны различные методы, такие как таблицы решений, сопоставление образцов, включающее динамическое программирование, различ-

    11 1.2. СТРУКТУРА КОМПИЛЯТОРА 11 ные синтаксические методы. Конечно, те или иные фазы транслятора могут либо отсутствовать совсем, либо объединяться. В простейшем случае однопроходного транслятора нет явной фазы генерации промежуточного представления и оптимизации, остальные фазы объединены в одну, причем нет и явно построенного синтаксического дерева.

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

    13 Глава 2 Языки и их представление 2.1 Алфавиты, цепочки и языки Алфавит, или словарь это конечное множество символов. Для обозначения символов мы будем пользоваться цифрами, латинскими буквами и специальными литерами типа #, $. Пусть V алфавит. Цепочка в алфавите V это любая строка конечной длины, составленная из символов алфавита V. Синонимом цепочки являются предложение, строка и слово. Пустая цепочка (обозначается e) это цепочка, в которую не входит ни один символ. Конкатенацией цепочек x и y называется цепочка xy. Заметим, что xe = ex = x для любой цепочки x. Пусть x, y, z произвольные цепочки в некотором алфавите. Цепочка y называется подцепочкой цепочки xyz. Цепочки x и y называются, соответственно, префиксом и суффиксом цепочки xy. Заметим, что любой префикс или суффикс цепочки является подцепочкой этой цепочки. Кроме того, пустая цепочка является префиксом, суффиксом и подцепочкой для любой цепочки. Пример 2.1. Для цепочки abbba префиксом является любая цепочка из множества L 1 = , суффиксом является любая цепочка из множества L 2 = , подцепочкой является любая цепочка из множества L 1 L 2. Длиной цепочки w (обозначается w ) называется число символов в ней. Например, abababa =7, а e =0. Язык в алфавите V это некоторое множество цепочек в алфавите V. Пример 2.2. Пусть дан алфавит V = . Вот некоторые языки в алфавите V : а) L 1 = пустой язык; 13

    14 14 ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ б) L 2 = язык, содержащий только пустую цепочку (заметим, что L 1 и L 2 различные языки); в) L 3 = язык, содержащий цепочки из a и b, длина которых не превосходит 2; г) L 4 язык, включающий всевозможные цепочки из a и b, содержащие четное число a и четное число b; д) L 5 = 0> язык цепочек из a, длины которых представляют собой квадраты натуральных чисел. Два последних языка содержат бесконечное число цепочек. Введем обозначение V для множества всех цепочек в алфавите V, включая пустую цепочку. Каждый язык в алфавите V является подмножеством V. Для обозначения множества всех цепочек в алфавите V, кроме пустой цепочки, будем использовать V +. Пример 2.3. Пусть V = <0, 1>. Тогда V = , V + = <0, 1, 00, 01, 10, 11, 000. >. Введем некоторые операции над языками. Пусть L 1 и L 2 языки в алфавите V. Конкатенацией языков L 1 и L 2 называется язык L 1 L 2 = . Пусть L язык в алфавите V. Итерацией языка L называется язык L, определяемый следующим образом: (1) L 0 = ; (2) L n = LL n 1, n 1; (3) L = n=0 L n. Пример 2.4. Пусть L 1 = и L 2 = . Тогда L 1L 2 = ,и L 1 = . Большинство языков, представляющих интерес, содержат бесконечное число цепочек. При этом возникают три важных вопроса. Во-первых, как представить язык (т.е. специфицировать входящие в него цепочки)? Если язык содержит только конечное множество цепочек, ответ прост. Можно просто перечислить его цепочки. Если язык бесконечен, необходимо найти для него конечное представление. Это конечное представление, в свою очередь, будет строкой символов над некоторым алфавитом вместе с некоторой интерпретацией, связывающей это представление с языком.

    15 2.2. ПРЕДСТАВЛЕНИЕ ЯЗЫКОВ 15 Во-вторых, для любого ли языка существует конечное представление? Можно предположить, что ответ отрицателен. Мы увидим, что множество всех цепочек над алфавитом счетно. Язык это любое подмножество цепочек. Из теории множеств известно, что множество всех подмножеств счетного множества несчетно. Хотя мы и не дали строгого определения того, что является конечным представлением, интуитивно ясно, что любое разумное определение конечного представления ведет только к счетному множеству конечных представлений, поскольку нужно иметь возможность записать такое конечное представление в виде строки символов конечной длины. Поэтому языков значительно больше, чем конечных представлений. В-третьих, можно спросить, какова структура тех классов языков, для которых существует конечное представление? 2.2 Представление языков Процедура это конечная последовательность инструкций, которые могут быть механически выполнены. Примером может служить машинная программа. Процедура, которая всегда заканчивается, называется алгоритмом. Один из способов представления языка дать алгоритм, определяющий, принадлежит ли цепочка языку. Более общий способ состоит в том, чтобы дать процедуру, которая останавливается с ответом да для цепочек, принадлежащих языку, и либо останавливается с ответом нет, либо вообще не останавливается для цепочек, не принадлежащих языку. Говорят, что такая процедура или алгоритм распознает язык. Такой метод представляет язык с точки зрения распознавания. Язык можно также представить методом порождения. А именно, можно дать процедуру, которая систематически порождает в определенном порядке цепочки языка. Если мы можем распознать цепочки языка над алфавитом V либо с помощью процедуры, либо с помощью алгоритма, то мы можем и генерировать язык, поскольку мы можем систематически генерировать все цепочки из V, проверять каждую цепочку на принадлежность языку и выдавать список только цепочек языка. Но если процедура не всегда заканчивается при проверке цепочки, мы не сдвинемся дальше первой цепочки, на которой процедура не заканчивается. Эту проблему можно обойти, организовав проверку таким образом, чтобы процедура никогда не продолжала проверять одну цепочку бесконечно. Для этого введем следующую конструкцию. Предположим, что V имеет p символов. Мы можем рассматривать цепочки из V как числа, представленные в базисе p, плюс пустая цепочка e. Можно занумеровать цепочки в порядке возрастания длины и в числовом порядке для цепочек одинаковой длины. Такая нумерация для цепочек языка приведена на рис. 2.1, а.

    16 16 ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ Пусть P процедура для проверки принадлежности цепочки языку L. Предположим, что P может быть представлена дискретными шагами, так что имеет смысл говорить об i-ом шаге процедуры для любой данной цепочки. Прежде чем дать процедуру перечисления цепочек языка L, дадим процедуру нумерации пар положительных чисел. Все упорядоченные пары положительных чисел (x, y) можно отобразить на множество положительных чисел следующей формулой: z =(x + y 1)(x + y 2)/2+y Пары целых положительных чисел можно упорядочить в соответствии со значением z (рис. 2.1, б). 1 e 2 a 3 b 4 c 5 aa 6 ab 7 ac 8 ba 9 bb а y x z(x, y) б Рис. 2.1: Теперь можно дать процедуру перечисления цепочек L. Нумеруем упорядоченные пары целых положительных чисел (1,1), (2,1), (1,2), (3,1), (2,2). При нумерации пары (i, j) генерируем i-ю цепочку из V и применяем к цепочке первые j шагов процедуры P. Как только мы определили, что сгенерированная цепочка принадлежит L, добавляем цепочку к списку элементов L. Если цепочка i принадлежит L, это будет определено P за j шагов для некоторого конечного j. При перечислении (i, j) будет сгенерирована цепочку с номером i. Легко видеть, что эта процедура перечисляет все цепочки L. Если мы имеем процедуру генерации цепочек языка, то мы всегда можем построить процедуру распознавания предложений языка, но не всегда алгоритм. Для определения того, принадлежит ли x языку L, просто нумеруем предложения L и сравниваем x с каждым предложением. Если сгенерировано x, процедура останавливается, распознав, что x принадлежит L. Конечно, если x не принадлежит L, процедура никогда не закончится. Язык, предложения которого могут быть сгенерированы процедурой, называется рекурсивно перечислимым. Язык рекурсивно перечислим, если имеется процедура, распознающая предложения языка. Говорят,

    17 2.3. ГРАММАТИКИ 17 что язык рекурсивен, если существует алгоритм для распознавания языка. Класс рекурсивных языков является собственным подмножеством класса рекурсивно перечислимых языков. Мало того, существуют языки, не являющиеся даже рекурсивно перечислимыми. 2.3 Грамматики Формальное определение грамматики Для нас наибольший интерес представляет одна из систем генерации языков грамматики. Понятие грамматики изначально было формализовано лингвистами при изучении естественных языков. Предполагалось, что это может помочь при их автоматической трансляции. Однако, наилучшие результаты в этом направлении достигнуты при описании не естественных языков, а языков программирования. Примером может служить способ описания синтаксиса языков программирования при помощи БНФ формы Бэкуса-Наура. Определение. Грамматика это четверка G =(N,T,P,S), где (1) N алфавит нетерминальных символов; (2) T алфавит терминальных символов, N T = ; (3) P конечное множество правил вида α β, где α (N T ) +, β (N T ) ; (4) S N начальный символ (или аксиома) грамматики. Мы будем использовать большие латинские буквы для обозначения нетерминальных символов, малые латинские буквы из начала алфавита для обозначения терминальных символов, малые латинские буквы из конца алфавита для обозначения цепочек из T и, наконец, малые греческие буквы для обозначения цепочек из (N T ). Будем использовать также сокращенную запись A α 1 α 2. α n для обозначения группы правил A α 1,A α 2. A α n. Определим на множестве (N T ) бинарное отношение выводимости следующим образом: если δ γ P,тоαδβ αγβ для всех α, β (N T ). Если α 1 α 2, то говорят, что цепочка α 2 непосредственно выводима из α 1. Мы будем использовать также рефлексивно-транзитивное и транзитивное замыкания отношения, а также его степень k 0 (обозначаемые соответственно, + и k ). Если α 1 α 2 (α 1 + α 2, α 1 k α 2 ), то говорят, что цепочка α 2 выводима (нетривиально выводима, выводима за k шагов)изα 1. Если α k β (k 0), то существует последовательность шагов γ 0 γ 1 γ 2. γ k 1 γ k

    18 18 ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ где α = γ 0 и β = γ k. Последовательность цепочек γ 0,γ 1,γ 2. γ k в этом случае называют выводом β из α. Сентенциальной формой грамматики G называется цепочка, выводимая из ее начального символа. Языком, порождаемым грамматикой G (обозначается L(G)), называется множество всех ее терминальных сентенциальных форм, т.е. L(G) = Грамматики G 1 и G 2 называются эквивалентными, если они порождают один и тот же язык, т.е. L(G 1 )=L(G 2 ). Пример 2.5. Грамматика G =(, , P, S), где P = , порождает язык L(G) =0>. Действительно, применяем n 1 раз правило 1 и получаем a n 1 S(BC) n 1, затем один раз правило 2 и получаем a n (BC) n, затем n(n 1)/2 раз правило 3 и получаем a n B n C n. Затем используем правило 4 и получаем a n bb n 1 C n. Затем применяем n 1 раз правило 5 и получаем a n b n C n. Затем применяем правило 6 и n 1 раз правило 7 и получаем a n b n c n. Можно показать, что язык L(G) состоит из цепочек только такого вида. Пример 2.6. Рассмотрим грамматику G =(, <0, 1>, , S). Легко видеть, что цепочка L(G), так как существует вывод S 0S1 00S Нетрудно показать, что грамматика порождает язык L(G) =<0 n 1>0>. Пример 2.7. Рассмотрим грамматику G = (, <0, 1>, ,S). Нетрудно показать, что грамматика порождает язык L(G) = <0 n 1 m n,>0> Типы грамматик и их свойства Рассмотрим классификацию грамматик (предложенную Н.Хомским), основанную на виде их правил. Определение. Пусть дана грамматика G =(N,T,P,S). Тогда (1) если правила грамматики не удовлетворяют никаким ограничениям, то ее называют грамматикой типа 0, или грамматикой без ограничений. (2) если а) каждое правило грамматики, кроме S e, имеет вид α β, где α β,и

    19 2.3. ГРАММАТИКИ 19 б) в том случае, когда S e P, символ S не встречается в правых частях правил, то грамматику называют грамматикой типа 1, или неукорачивающей. (3) если каждое правило грамматики имеет вид A β, где A N, β (N T ), то ее называют грамматикой типа 2, или контекстносвободной (КС-грамматикой). (4) если каждое правило грамматики имеет вид либо A xb, либо A x, где A, B N, x T то ее называют грамматикой типа 3, или праволинейной. Легко видеть, что грамматика в примере 2.5 неукорачивающая, в примере 2.6 контекстно-свободная, в примере 2.7 праволинейная. Язык, порождаемый грамматикой типа i, называют языком типа i. Язык типа 0 называют также языком без ограничений, язык типа 1 контекстно-зависимым (КЗ), язык типа 2 контекстно-свободным (КС), язык типа 3 праволинейным. Теорема 2.1. Каждый контекстно-свободный язык может быть порожден неукорачивающей грамматикой. Доказательство. Пусть L контекстно-свободный язык. Тогда существует контекстно-свободная грамматика G = (N,T,P,S), порождающая L. Построим новую грамматику G =(N,T,P,S ) следующим образом: 1. Если в P есть правило вида A α 0 B 1 α 1. B k α k, где k 0, B i + e для 1 i k, и ни из одной цепочки α j (0 j k) не выводится e, то включить в P все правила (кроме A e) вида A α 0 X 1 α 1. X k α k где X i это либо B i, либо e. 2. Если S + e, то включить в P правила S S, S e и положить N = N . В противном случае положить N = N и S = S. Легко видеть, что G неукорачивающая грамматика. Можно показать по индукции, что L(G )=L(G). Пусть K i класс всех языков типа i. Доказано, что справедливо следующее (строгое) включение: K 3 K 2 K 1 K 0. Заметим, что если язык порождается некоторой грамматикой, это не означает, что он не может быть порожден грамматикой с более сильными ограничениями на правила. Приводимый ниже пример иллюстрирует этот факт.

    20 20 ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ Пример 2.8. Рассмотрим грамматику G = (, <0, 1>, , S). Эта грамматика является контекстносвободной. Легко показать, что L(G) = <0 n 1 m n,>0>. Однако, в примере 2.7 приведена праволинейная грамматика, порождающая тот же язык. Покажем что существует алгоритм, позволяющий для произвольного КЗ-языка L в алфавите T, и произвольной цепочки w T определить, принадлежит ли w языку L. Теорема 2.2. Каждый контекстно-зависимый язык является рекурсивным языком. Доказательство. Пусть L контекстно-зависимый язык. Тогда существует некоторая неукорачивающая грамматика G =(N, T, P, S), порождающая L. Пусть w T и w = n. Если n =0, т.е. w = e, то принадлежность w L проверяется тривиальным образом. Так что будем предполагать, что n>0. Определим множество T m как множество строк u (N T ) + длины не более n таких, что вывод S u имеет не более m шагов. Ясно, что T 0 = . Легко показать, что T m можно получить из T m 1 просматривая, какие строки с длиной, меньшей или равной n можно вывести из строк из T m 1 применением одного правила, т.е. T m = T m 1 . Если S u и u n, тоu T m для некоторого m. Если из S не выводится u или u >n,тоuне принадлежит T m ни для какого m. Очевидно, что T m T m 1 для всех m 1. Поскольку T m зависит только от T m 1, если T m = T m 1,тоT m = T m+1 = T m+2 =. Процедура будет вычислять T 1, T 2, T 3. пока для некоторого m не окажется T m = T m 1. Если w не принадлежит T m, то не принадлежит и L(G), поскольку для j>mвыполнено T j = T m. Если w T m,тоs w. Покажем, что существует такое m, что T m = T m 1. Поскольку для каждого i 1 справедливо T i T i 1, то если T i T i 1, то число элементов в T i по крайней мере на 1 больше, чем в T i 1. Пусть N T = k. Тогда число строк в (N T ) + длины меньшей или равной n равно k + k k n nk n. Только эти строки могут быть в любом T i. Значит, T m = T m 1 для некоторого m nk n. Таким образом, процедура, вычисляющая T i для всех i 1 до тех пор, пока не будут найдены два равных множества, гарантированно заканчивается, значит, это алгоритм.

    21 Глава 3 Лексический анализ Основная задача лексического анализа разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, т.е. выделить эти слова из непрерывной последовательности символов. Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители). В некоторых случаях между лексемами может и не быть разделителей. С другой стороны, в некоторых языках лексемы могут содержать незначащие символы (например, символ пробела в Фортране). В Си разделительное значение символов-разделителей может блокироваться ( \ в конце строки внутри «. «). Обычно все лексемы делятся на классы. Примерами таких классов являются числа (целые, восьмеричные, шестнадцатиричные, действительные и т.д.), идентификаторы, строки. Отдельно выделяются ключевые слова и символы пунктуации (иногда их называют символы-ограничители). Как правило, ключевые слова это некоторое конечное подмножество идентификаторов. В некоторых языках (например, ПЛ/1) смысл лексемы может зависеть от ее контекста и невозможно провести лексический анализ в отрыве от синтаксического. С точки зрения дальнейших фаз анализа лексический анализатор выдает информацию двух сортов: для синтаксического анализатора, работающего вслед за лексическим, существенна информация о последовательности классов лексем, ограничителей и ключевых слов, а для контекстного анализа, работающего вслед за синтаксическим, важна информация о конкретных значениях отдельных лексем (идентификаторов, чисел и т.д.). Таким образом, общая схема работы лексического анализатора такова. Сначала выделяется отдельная лексема (возможно, используя символыразделители). Ключевые слова распознаются либо явным выделением непосредственно из текста, либо сначала выделяется идентификатор, а затем делается проверка на принадлежность его множеству ключевых 21

    22 22 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ слов. Если выделенная лексема является ограничителем, то он (точнее, некоторый его признак) выдается как результат лексического анализа. Если выделенная лексема является ключевым словом, то выдается признак соответствующего ключевого слова. Если выделенная лексема является идентификатором выдается признак идентификатора, а сам идентификатор сохраняется отдельно. Наконец, если выделенная лексема принадлежит какому-либо из других классов лексем (например, лексема представляет собой число, строку и т.д.), то выдается признак соответствующего класса, а значение лексемы сохраняется отдельно. Лексический анализатор может быть как самостоятельной фазой трансляции, так и подпрограммой, работающей по принципу дай лексему. В первом случае (рис. 3.1, а) выходом анализатора является файл лексем, во втором (рис. 3.1, б) лексема выдается при каждом обращении к анализатору (при этом, как правило, признак класса лексемы возвращается как результат функции лексический анализатор, а значение лексемы передается через глобальную переменную). С точки зрения обработки значений лексем, анализатор может либо просто выдавать значение каждой лексемы, и в этом случае построение таблиц объектов (идентификаторов, строк, чисел и т.д.) переносится на более поздние фазы, либо он может самостоятельно строить таблицы объектов. В этом случае в качестве значения лексемы выдается указатель на вход в соответствующую таблицу. LbiAgZq_gb_ KbglZgZebaZlhj Lbi e_dk_fu AgZq_gb_ LZ[ebpZ E_dkZgZebaZlhj Z [ Рис. 3.1: Работа лексического анализатора задается некоторым конечным автоматом. Однако, непосредственное описание конечного автомата неудобно с практической точки зрения. Поэтому для задания лексического анализатора, как правило, используется либо регулярное выражение, либо праволинейная грамматика. Все три формализма (конечных автоматов,

    24 24 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ (б) (pq) регулярное выражение, обозначающее регулярное множество PQ, (в) (p ) регулярное выражение, обозначающее регулярное множество P ; (5) ничто другое не является регулярным выражением в алфавите T. Мы будем опускать лишние скобки в регулярных выражениях, договорившись о том, что операция итерации имеет наивысший приоритет, затем идет операции конкатенации, наконец, операция объединения имеет наименьший приоритет. Кроме того, мы будем пользоваться записью p + для обозначения pp. Таким образом, запись (a ((ba)(a ))) эквивалентна a ba +. Наконец, мы будем использовать запись L(r) для регулярного множества, обозначаемого регулярным выражением r. Пример 3.1. Несколько примеров регулярных выражений и обозначаемых ими регулярных множеств: а) a(e a) b обозначает множество ; б) a(a b) обозначает множество всевозможных цепочек, состоящих из a и b, начинающихся с a; в) (a b) (a b)(a b) обозначает множество всех непустых цепочек, состоящих из a и b, т.е. множество + ; г) ((0 1)(0 1)(0 1)) обозначает множество всех цепочек, состоящих из нулей и единиц, длины которых делятся на 3. Ясно, что для каждого регулярного множества можно найти регулярное выражение, обозначающее это множество, и наоборот. Более того, для каждого регулярного множества существует бесконечно много обозначающих его регулярных выражений. Будем говорить, что регулярные выражения равны или эквивалентны (=), если они обозначают одно и то же регулярное множество. Существует ряд алгебраических законов, позволяющих осуществлять эквивалентное преобразование регулярных выражений. Лемма. Пусть p, q и r регулярные выражения. Тогда справедливы следующие соотношения: (1) p q = q p; (7) pe = ep = p; (2) = e; (8) p = p = ; (3) p (q r) =(p q) r; (9) p = p p ; (4) p(qr) =(pq)r; (10) (p ) = p ; (5) p(q r) = pq pr; (11) p p = p; (6) (p q)r = pr qr; (12) p = p. Следствие. Для любого регулярного выражения существует эквивалентное регулярное выражение, которое либо есть, либо не содержит в своей записи.

    25 3.2. КОНЕЧНЫЕ АВТОМАТЫ 25 В дальнейшем будем рассматривать только регулярные выражения, не содержащие в своей записи. При практическом описании лексических структур бывает полезно сопоставлять регулярным выражениям некоторые имена, и ссылаться на них по этим именам. Для определения таких имен мы будем использовать запись вида d 1 = r 1 d 2 = r 2. d n = r n где d i различные имена, а каждое r i регулярное выражение над символами T , т.е. символами основного алфавита и ранее определенными символами (именами). Таким образом, для любого r i можно построить регулярное выражение над T, повторно заменяя имена регулярных выражений на обозначаемые ими регулярные выражения. Пример 3.2. Использование имен для регулярных выражений. а) Регулярное выражение для множества идентификаторов. Letter = a b c. x y z Digit = >

    26 26 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ (5) F Q множество заключительных состояний. Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо (рис. 3.2). Khklhygb_ IjhqblZggZyqZklv \oh^ghcp_ihqdb D L_dmsbc \oh^ghc kbf\he G_ijhqblZggZyqZklv \oh^ghcp_ihqdb Рис. 3.2: Недетерминизм автомата заключается в том, что, во-первых, находясь в некотором состоянии и обозревая текущий символ, автомат может перейти в одно из, вообще говоря, нескольких возможных состояний, и во-вторых, автомат может делать переходы по e. Пусть M = (Q,T,D,q 0,F) НКА. Конфигурацией автомата M называется пара (q, w) Q T, где q текущее состояние управляющего устройства, а w цепочка символов на входной ленте, состоящая из символа под головкой и всех символов справа от него. Конфигурация (q 0,w) называется начальной, а конфигурация (q, e), где q F заключительной (или допускающей). Пусть M =(Q,T,D,q 0,F) НКА. Тактом автомата M называется бинарное отношение, определенное на конфигурациях M следующим образом: если p D(q, a), где a T , то(q, aw) (p, w) для всех w T. Будем обозначать символом + ( ) транзитивное (рефлексивнотранзитивное) замыкание отношения. Говорят, что автомат M допускает цепочку w, если (q 0,w) (q, e) для некоторого q F. Языком, допускаемым (распознаваемым, определяемым) автоматом M, (обозначается L(M)), называется множество входных цепочек, допускаемых автоматом M. Т.е. L(M) =.

    27 3.2. КОНЕЧНЫЕ АВТОМАТЫ 27 Важным частным случаем недетерминированного конечного автомата является детерминированный конечный автомат, который на каждом такте работы имеет возможность перейти не более чем в одно состояние и не может делать переходы по e. Пусть M =(Q,T,D,q 0,F) НКА. Будем называть M детерминированным конечным автоматом (ДКА), если выполнены следующие два условия: (1) D(q, e) = для любого q Q,и (2) D(q, a) содержит не более одного элемента для любых q Q и a T. Так как функция переходов ДКА содержит не более одного элемента для любой пары аргументов, для ДКА мы будем пользоваться записью D(q, a) =p вместо D(q, a) =

    . Конечный автомат может быть изображен графически в виде диаграммы, представляющей собой ориентированный граф, в котором каждому состоянию соответствует вершина, а дуга, помеченная символом a T , соединяет две вершины p и q, если p D(q, a). На диаграмме выделяются начальное и заключительные состояния (в примерах ниже, соответственно, входящей стрелкой и двойным контуром). Пример 3.3. Пусть L = L(r), где r =(a b) a(a b)(a b). а) Недетерминированный конечный автомат M, допускающий язык L: M = <<1, 2, 3, 4>, ,d,1, <4>>, где функция переходов D определяется так: D(1,a)=<1, 2>, D(3,a)=<4>, D(2,a)=<3>, D(3,b)=<4>, D(2,b)=<3>. Диаграмма автомата приведена на рис. 3.3, а. б) Детерминированный конечный автомат M, допускающий язык L: M = <<1, 2, 3, 4, 5, 6, 7, 8>, ,d,1, <3, 5, 6, 8>>, где функция переходов D определяется так: D(1,a)=2, D(5,a)=8, D(1,b)=1, D(5,b)=6, D(2,a)=4, D(6,a)=2, D(2,b)=7, D(6,b)=1, D(3,a)=3, D(7,a)=8, D(3,b)=5, D(7,b)=6, D(4,a)=3, D(8,a)=4, D(4,b)=5, D(8,b)=7. Диаграмма автомата приведена на рис. 3.3, б. Пример 3.4. Диаграмма ДКА, допускающего множество чисел в десятичной записи, приведена на рис. 3.4.

    28 28 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ E D D DE E DE D E E D D D D E E E D E D D E Z [ Рис. 3.3: Пример 3.5. Анализ цепочек. а) При анализе цепочки w = ababa автомат из примера 3.3, а, может сделать следующую последовательность тактов: (1, ababa) (1, baba) (1, aba) (2,ba) (3,a) (4,e). Состояние 4 является заключительным, следовательно, цепочка w допускается этим автоматом. б) При анализе цепочки w = ababab автомат из примера 3.3, б, должен сделать следующую последовательность тактов: (1, ababab) (2, babab) (7, abab) (8, bab) (7,ab) (8,b) (7,e). Так как состояние 7 не является заключительным, цепочка w не допускается этим автоматом. ( ‘LJLW ‘LJLW ‘LJLW ( ‘LJLW ‘LJLW ‘LJLW ‘LJLW Рис. 3.4:

    29 3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ Алгоритмы построения конечных автоматов Построение недетерминированного конечного автомата по регулярному выражению Рассмотрим алгоритм построения по регулярному выражению недетерминированного конечного автомата, допускающего тот же язык. Алгоритм 3.1. Построение недетерминированного конечного автомата по регулярному выражению. Вход. Регулярное выражение r в алфавите T. Выход. НКА M, такой что L(M) =L(r). Метод. Автомат для выражения строится композицией из автоматов, соответствующих подвыражениям. На каждом шаге построения строящийся автомат имеет в точности одно заключительное состояние, в начальное состояние нет переходов из других состояний и нет переходов из заключительного состояния в другие. 1. Для выражения e строится автомат L H I Рис. 3.5: 2. Для выражения a (a T ) строится автомат L D I Рис. 3.6: 3. Пусть M(s) и M(t) НКА для регулярных выражений s и t соответственно. а) Для выражения s t автомат M(s t) строится как показано на рис Здесь i новое начальное состояние и f новое заключительное состояние. Заметим, что имеет место переход по e из i в начальные состояния M(s) и M(t) и переход по e из заключительных состояний M(s) и M(t) в f. Начальное и заключительное состояния автоматов M(s) и M(t) не являются таковыми для автомата M(s t).

    30 30 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ H 0V H L I H 0W H Рис. 3.7: б) Для выражения st автомат M(st) строится следующим образом: L 0V 0W I Рис. 3.8: Начальное состояние M(s) становится начальным для нового автомата, а заключительное состояние M(t) становится заключительным для нового автомата. Начальное состояние M(t) и заключительное состояние M(s) сливаются, т.е. все переходы из начального состояния M(t) становятся переходами из заключительного состояния M(s). В новом автомате это объединенное состояние не является ни начальным, ни заключительным. в) Для выражения s автомат M(s ) строится следующим образом: L H H 0V H I H Рис. 3.9:

    31 3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ 31 Здесь i новое начальное состояние, а f новое заключительное состояние Построение детерминированного конечного автомата по недетерминированному Рассмотрим алгоритм построения по недетерминированному конечному автомату детерминированного конечного автомата, допускающего тот же язык. Алгоритм 3.2. Построение детерминированного конечного автомата по недетерминированному. Вход. НКА M =(Q,T,D,q 0,F). Выход. ДКА M =(Q,T,D,q 0,F ), такой что L(M) =L(M ). Метод. Каждое состояние результирующего ДКА это некоторое множество состояний исходного НКА. В алгоритме будут использоваться следующие функции: e-closure(r) (R Q) множество состояний НКА, достижимых из состояний, входящих в R, посредством только переходов по e, т.е. множество S =

    q R move(r, a) (R Q) множество состояний НКА, в которые есть переход на входе a для состояний из R, т.е. множество S =

    q R Вначале Q и D пусты. Выполнить шаги 1-4: (1) Определить q 0 = e-closure(). (2) Добавить q 0 в Q как непомеченное состояние. (3) Выполнить следующую процедуру: while (в Q есть непомеченное состояние R)< пометить R; for (каждого входного символа a T )< S = e-closure(move(r, a)); if (S )< if (S / Q ) добавить S в Q как непомеченное состояние; определить D (R, a) =S;

    32 32 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ > > > (4) Определить F = . Пример 3.6. Результат применения алгоритма 3.2 приведен на рис H H H D H H D E E H E H H D $ D % E D & D E D E ‘ E ( E Рис. 3.10: Построение детерминированного конечного автомата по регулярному выражению Приведем теперь алгоритм построения по регулярному выражению детерминированного конечного автомата, допускающего тот же язык [10]. Пусть дано регулярное выражение r в алфавите T. К регулярному выражению r добавим маркер конца: (r)#. Такое регулярное выражение будем называть пополненным. В процессе своей работы алгоритм будет использовать пополненное регулярное выражение.

    33 3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ 33 Алгоритм будет оперировать с синтаксическим деревом для пополненного регулярного выражения (r)#, каждый лист которого помечен символом a T , а каждая внутренняя вершина помечена знаком одной из операций: (конкатенация), (объединение), (итерация). Каждому листу дерева (кроме e-листьев) припишем уникальный номер, называемый позицией, и будем использовать его, с одной стороны, для ссылки на лист в дереве, и, с другой стороны, для ссылки на символ, соответствующий этому листу. Заметим, что если некоторый символ используется в регулярном выражении несколько раз, он имеет несколько позиций. Теперь, обходя дерево T снизу-вверх слева-направо, вычислим четыре функции: nullable, f irstpos, lastpos и f ollowpos. Функции nullable, firstpos и lastpos определены на узлах дерева, а followpos на множестве позиций. Значением всех функций, кроме nullable, является множество позиций. Функция f ollowpos вычисляется через три остальные функции. Функция f irstpos(n) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют первым символам в подцепочках, генерируемых подвыражением с вершиной в n. Аналогично, lastpos(n) дает множество позиций, которым соответствуют последние символы в подцепочках, генерируемых подвыражениями с вершиной n. Для узла n, поддеревья которого (т.е. деревья, у которых узел n является корнем) могут породить пустое слово, определим nullable(n) =true, а для остальных узлов nullable(n)=f alse. Таблица для вычисления функций nullable, f irstpos и lastpos приведена на рис узел n nullable(n) firstpos(n) lastpos(n) лист e true лист i false (не e) nullable(u) /\ or f irstpos(u) f irstpos(v) lastpos(u) lastpos(v) uv nullable(v) nullable(u) if nullable(u) then if nullable(v) then /\ and f irstpos(u) f irstpos(v) lastpos(u) lastpos(v) u v nullable(v) else f irstpos(u) else lastpos(v) true f irstpos(v) lastpos(v) v Рис. 3.11: Пример 3.7. Синтаксическое дерево для пополненного регулярного выражения (a b) abb# с результатом вычисления функций firstpos и lastpos приведено

    34 34 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ ^` ^` ^` ^` ^` ^` ^` ^` ^`E ^` ^` ^` ^`E ^` ^`^` ^`D ^` ^` _ ^` ^`D ^` ^`E ^` Рис. 3.12: позиция f ollowpos 1 <1, 2, 3>2 <1, 2, 3>3 <4>4 <5>5 <6>6 Рис. 3.13: на рис Слева от каждого узла расположено значение firstpos, справа от узла значение lastpos. Заметим, что эти функции могут быть вычислены за один обход дерева. Если i позиция, то followpos(i) есть множество позиций j таких, что существует некоторая строка. cd. входящая в язык, описываемый регулярным выражением, такая, что позиция i соответствует этому вхождению c, а позиция j вхождению d. Функция f ollowpos может быть вычислена также за один обход дерева снизу-вверх по следующим двум правилам. 1. Пусть n внутренний узел с операцией (конкатенация), u и v его потомки. Тогда для каждой позиции i, входящей в lastpos(u), добавляем к множеству значений f ollowpos(i) множество f irstpos(v). 2. Пусть n внутренний узел с операцией (итерация), u его потомок. Тогда для каждой позиции i, входящей в lastpos(u), добавляем к множеству значений f ollowpos(i) множество f irstpos(u).

    35 3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ 35 Пример 3.8. Результат вычисления функции followpos для регулярного выражения из предыдущего примера приведен на рис Алгоритм 3.3. Прямое построение ДКА по регулярному выражению. Вход. Регулярное выражение r в алфавите T. Выход. ДКА M =(Q,T,D,q 0,F), такой что L(M) =L(r). Метод. Состояния ДКА соответствуют множествам позиций. Вначале Q и D пусты. Выполнить шаги 1-6: (1) Построить синтаксическое дерево для пополненного регулярного выражения (r)#. (2) Обходя синтаксическое дерево, вычислить значения функций nullable, f irstpos, lastpos и f ollowpos. (3) Определить q 0 = firstpos(root), где root корень синтаксического дерева. (4) Добавить q 0 в Q как непомеченное состояние. (5) Выполнить следующую процедуру: while (в Q есть непомеченное состояние R) < пометить R; for (каждого входного символа a T, такого, что в R имеется позиция, которой соответствует a)< пусть символ a в R соответствует позициям p 1. p n, и пусть S = followpos(p i ); 1 i n if (S )< if (S / Q) добавить S в Q как непомеченное состояние; определить D(R, a) =S; >> > (6) Определить F как множество всех состояний из Q, содержащих позиции, связанные с символом #. Пример 3.9. Результат применения алгоритма 3.3 для регулярного выражения (a b) abb приведен на рис

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