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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9.2. Система Yacc 172

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

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

Компиляторы составляют существенную часть программного

обеспечения ЭВМ. Это связано с тем, что языки высокого уровня

стали основным средством разработки программ. Только очень

незначительная часть программного обеспечения, требующая

особой эффективности, программируется с помощью ассемблеров. В

настоящее время распространено довольно много языков

программирования. Наряду с традиционными языками, такими, как

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

«универсальные языки» (Паскаль, Си, Модула-2, Ада и другие), а

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

списочных структур Лисп). Кроме того, большое распространение

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

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

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

Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа

IBM/PC на рынке десятки.

С другой стороны, постоянно растущая потребность в новых

компиляторах связана с бурным развитием архитектур ЭВМ. Это

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

старые архитектуры как в концептуальном отношении, так и по

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

примере микропроцессора Intel-80X86. Последовательные версии

этого микропроцессора 8086, 80186, 80286, 80386, 80486, 80586

отличаются не только техническими характеристиками, но и, что

более важно, новыми возможностями и, значит, изменением

(расширением) системы команд. Естественно, это требует новых

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

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

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

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

могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как

Intel, Motorola, Sun, DEC, начинают переходить на выпуск машин

с RISC-архитектурами. Естественно, для каждой новой системы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица символов для компилятора

10.07.2020, 16:54

Макрос для определения компилятора(С++)
Есть ли такое в природе?Что б можно было допустим, отличать майкрософтский от борландского внутри.

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

Ошибка компилятора fatal error C1091: ограничение компилятора: длина строки превышает 65535 байт
Компилируя программу вот такой командой: cl /O2 /Oi /GL /EHsc /MD /Gy main.cpp И компилятор.

Юзерская переменная для компилятора
Доброго юзаю MS Visual Studio Такой вопрос, мне нужна переменная в самой студии, что бы при.

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

10.07.2020, 21:17 2 10.07.2020, 22:58 [ТС] 3 10.07.2020, 23:10 4

И забыть о singleton’ах и прочих глупостях. Чем проще — тем лучше.

10.07.2020, 23:10
11.07.2020, 15:33 5
11.07.2020, 17:19 [ТС] 6

Вот как раз с областями видимости главная сложность. Захвата контекста пока не предвидится. Вообще исходный язык довольно прост, похож на Basic, имена переменных в одну букву, но при переходе по gosub, если я правильно понимаю, мне будет необходимо создать временную таблицу символов для подпрограммы. Но при этом каждая такая таблица должна быть в одном экземпляре, если этого не сделать, то при каждом добавлении символа, будет создаваться отдельная таблица в 1 элемент. И еще к ней должны иметь доступ другие классы при получении адреса переменных и констант, поэтому я не могу просто поместить таблицу как структуру данных в файл исходного кода. Синглтон я взяла, потому что у меня нет другой идеи, как это реализовать. При этом я не понимаю, как с синглтоном возможно реализовать таблицу символов для подпрограммы (может, с помощью дочернего класса от родительского синглтона?) Если вы знаете, как это можно сделать проще/сложнее/иначе я буду благодарна за идеи.

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

11.07.2020, 20:24 7

Решение

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

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

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

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

n1.doc

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

9.2. Система Yacc 172

Литература 175
Глава 1. Введение

1.1. Место компилятора в программном обеспечении
Компиляторы составляют существенную часть программного

обеспечения ЭВМ. Это связано с тем, что языки высокого уровня

стали основным средством разработки программ. Только очень

незначительная часть программного обеспечения, требующая

особой эффективности, программируется с помощью ассемблеров. В

настоящее время распространено довольно много языков

программирования. Наряду с традиционными языками, такими, как

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

«универсальные языки» (Паскаль, Си, Модула-2, Ада и другие), а

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

списочных структур Лисп). Кроме того, большое распространение

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

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

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

Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа

IBM/PC на рынке десятки.

С другой стороны, постоянно растущая потребность в новых

компиляторах связана с бурным развитием архитектур ЭВМ. Это

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

старые архитектуры как в концептуальном отношении, так и по

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

примере микропроцессора Intel-80X86. Последовательные версии

этого микропроцессора 8086, 80186, 80286, 80386, 80486, 80586

отличаются не только техническими характеристиками, но и, что

более важно, новыми возможностями и, значит, изменением

(расширением) системы команд. Естественно, это требует новых

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

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

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

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

могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как

Intel, Motorola, Sun, DEC, начинают переходить на выпуск машин

с RISC-архитектурами. Естественно, для каждой новой системы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

лист е | true | 0 | 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Яков Алфимов 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 приведен на рис

Конструирование компиляторов

Детерминированный нисходящий и восходящий синтаксический анализ (СА), устройство и конфигурация LL(1) анализатора, условия для грамматик. Функции FIRST и FOLLOW и их интерпретация. Вычисления FOLLOW для нетерминала при k=1. Грамматики предшествования.

Рубрика Программирование, компьютеры и кибернетика
Вид шпаргалка
Язык русский
Дата добавления 24.06.2009
Размер файла 296,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

1. Детерминированный нисходящий СА. Устройство LL(1) анализатора. Конфигурация LL(1) анализатора. Структура управляющей таблицы разбора. 1предсказывающий алгоритм разбора

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

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

LR(k) — грамматики-то же самое, только для правого разбора.

КС-грамматика называется LL(k) грамматикой для некоторого фиксированного k, если из существования двух левых выводов:

для которых FIRSTk(x) = FIRSTk(y), вытекает, что .

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

При чтении цепочки головка может заглядывать вперед только на один символ u (аванцепочки). В магазине: X — верхний символ магазина, $ — маркер дна. Алфавит магазинных символов обозначается Г.

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

1) x — неиспользованная часть входной цепочки.

2) — цепочка в магазине.

3) — цепочка на выходной ленте.

Работой 1-предсказывающего алгоритма руководит управляющая таблица M, задающая отображение множества в множество, в которое входят:

(1) , где , а i — номер правила ( — или правая часть этого правила, или некоторое его представление). (2) Выброс. (3) Допуск. (4) Ошибка.

На каждом такте считывается символ u и определяется верхний символ магазина Х. Потом рассматривается элемент управляющей таблицы M (u, X), который и подсказывает, что надо делать:

1) М (u, X)= , тогда (верхний символ магазина заменяется цепочкой, а в выход пишется номер правила).

2) М (u, X)=выброс и , тогда (символ в магазине совпал с входным символом — оба символа выбрасываются).

3) М (u, X)=допуск, значит, разбор завершен успешно и мы в конфигурации

4) М (u, X)=ошибка, значит, разбор не получится — выходим.

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

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

LR(k) — грамматики-то же самое, только для правого разбора.

Формально: КС-грамматика называется LL(k) грамматикой для некоторого фиксированного k, если из существования двух левых выводов:

для которых FIRSTk(x) = FIRSTk(y), вытекает, что .

Неформально: FIRSTk(a) — это множество всех терминальных префиксов длины k (или меньше, если из a выводится цепочка длины — конец основы, выполняется между последним символом цепочки b и первым символом цепочки w;

бXBb, что есть такие правила B=>+Yy;

б) X.>a: A=>бBYb; B=>+yX; Y=>*ab; (X.>a — всегда терминальный символ с права, так как конец основы)

в) X.=Y если в P есть правило A=>aXYb; XY — основа (элементы, между которыми имеется отношение эквивалентности)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9.2. Система Yacc 172

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

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

Компиляторы составляют существенную часть программного

обеспечения ЭВМ. Это связано с тем, что языки высокого уровня

стали основным средством разработки программ. Только очень

незначительная часть программного обеспечения, требующая

особой эффективности, программируется с помощью ассемблеров. В

настоящее время распространено довольно много языков

программирования. Наряду с традиционными языками, такими, как

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

«универсальные языки» (Паскаль, Си, Модула-2, Ада и другие), а

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

списочных структур Лисп). Кроме того, большое распространение

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

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

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

Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа

IBM/PC на рынке десятки.

С другой стороны, постоянно растущая потребность в новых

компиляторах связана с бурным развитием архитектур ЭВМ. Это

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

старые архитектуры как в концептуальном отношении, так и по

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

примере микропроцессора Intel-80X86. Последовательные версии

этого микропроцессора 8086, 80186, 80286, 80386, 80486, 80586

отличаются не только техническими характеристиками, но и, что

более важно, новыми возможностями и, значит, изменением

(расширением) системы команд. Естественно, это требует новых

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

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

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

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

могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как

Intel, Motorola, Sun, DEC, начинают переходить на выпуск машин

с RISC-архитектурами. Естественно, для каждой новой системы

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

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

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

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

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

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

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

кончая персональными (например, на основе микропроцессора I-

860). Естественно, для каждой из машин создаются новые

компиляторы для многих языков программирования. Здесь

необходимо также отметить, что новые архитектуры требуют

разработки совершенно новых подходов к созданию компиляторов,

так что наряду с собственно разработкой компиляторов ведется и

большая научная работа по созданию новых методов трансляции.

1.2. Структура компилятора


Обобщенная структура компилятора и основные фазы компиляции

показаны на рис. 1.1.

На фазе лексического анализа (ЛА) входная программа,

представляющая собой поток символов, разбивается на лексемы —

слова в соответствии с определениями языка. Основным

формализмом, лежащим в основе реализации лексических

анализаторов, являются конечные автоматы и регулярные

выражения. Лексический анализатор может работать в двух

основных режимах: либо как подпрограмма, вызываемая

синтаксическим анализатором за очередной лексемой, либо как

полный проход, результатом которого является файл лексем.

В процессе выделения лексем ЛА может как самостоятельно

строить таблицы имен и констант, так и выдавать значения для

каждой лексемы при очередном обращении к нему. В этом случае

таблица имен строится в последующих фазах (например, в

процессе синтаксического анализа).

Вход | анализ | +————-+ || Поток лексем +||

| Конечные | || и констант || |

| анализ | +————-+ || Дерево разбора ||

| Контекстно-сво- | || имен и констант|||

| Атрибутные | || + таблица символов || |

| промежуточного | || Промежуточная форма ||

| представления | || (префиксная, пост- ||

| Потоковый | || (ориентированный граф)|| |

| Таблицы решений, | || Объектный ||

На этапе ЛА обнаруживаются некоторые (простейшие) ошибки

(недопустимые символы, неправильная запись чисел,

идентификаторов и др.).

Основная задача синтаксического анализа — разбор структуры

программы. Как правило, под структурой понимается дерево,

соответствующее разбору в контекстно-свободной грамматике

языка. В настоящее время чаще всего используется либо LL(1)-

анализ (и его вариант — рекурсивный спуск), либо LR(1)-анализ

и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный

спуск чаще используется при ручном программировании

синтаксического анализатора, LR(1) — при использовании систем

автоматизации построения синтаксических анализаторов.

Результатом синтаксического анализа является синтаксическое

дерево со ссылками на таблицу имен. В процессе синтаксического

анализа также обнаруживаются ошибки, связанные со структурой

На этапе контекстного анализа выявляются зависимости между

частями программы, которые не могут быть описаны контекстно-

свободным синтаксисом. Это в основном связи «описание-

использование», в частности анализ типов объектов, анализ

областей видимости, соответствие параметров, метки и другие. В

процессе контекстного анализа строится таблица символов,

которую можно рассматривать как таблицу имен, пополненную

информацией об описаниях (свойствах) объектов.

Основным формализмом, использующимся при контекстном

анализе, являются атрибутные грамматики. Результатом работы

фазы контекстного анализа является атрибутированное дерево

программы. Информация об объектах может быть как

рассредоточена в самом дереве, так и сосредоточена в отдельных

таблицах символов. В процессе контекстного анализа также могут

быть обнаружены ошибки, связанные с неправильным

Затем программа может быть переведена во внутреннее

представление. Это делается для целей оптимизации и/или

удобства генерации кода. Еще одной целью преобразования

программы во внутреннее представление является желание иметь

переносимый компилятор. Тогда только последняя фаза (генерация

кода) является машинно-зависимой. В качестве внутреннего

представления может использоваться префиксная или постфиксная

запись, ориентированный граф, тройки, четверки и другие.

Фаз оптимизации может быть несколько. Оптимизации обычно

делят на машинно-зависимые и машинно-независимые, локальные и

глобальные. Часть машинно-зависимой оптимизации выполняется на

фазе генерации кода. Глобальная оптимизация пытается принять

во внимание структуру всей программы, локальная — только

небольших ее фрагментов. Глобальная оптимизация основывается

на глобальном потоковом анализе, который выполняется на графе

программы и представляет по существу преобразование этого

графа. При этом могут учитываться такие свойства программы,

как межпроцедурный анализ, межмодульный анализ, анализ

областей жизни переменных и т.д.

Наконец, генерация кода — последняя фаза трансляции.

Результатом ее является либо ассемблерный модуль, либо

объектный (или загрузочный) модуль. В процессе генерации кода

могут выполняться некоторые локальные оптимизации, такие как

распределение регистров, выбор длинных или коротких переходов,

учет стоимости команд при выборе конкретной последовательности

команд. Для генерации кода разработаны различные методы, такие

как таблицы решений, сопоставление образцов, включающее

динамическое программирование, различные синтаксические

Конечно, те или иные фазы транслятора могут либо

отсутствовать совсем, либо объединяться. В простейшем случае

однопроходного транслятора нет явной фазы генерации

промежуточного представления и оптимизации, остальные фазы

объединены в одну, причем нет и явно построенного

Основы конструирования компиляторов. В.А.Серебряков, М.П.Галочкин

    Яков Алфимов 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 приведен на рис

Серебряков В.А. Лекции по конструированию компиляторов — файл n1.doc

Серебряков В.А. Лекции по конструированию компиляторов
скачать (1250.5 kb.)
Доступные файлы (1):

n1.doc 1251kb. 30.05.2012 00:24 скачать
    Смотрите также:
  • Хантер Р. Проектирование и конструирование компиляторов (Документ)
  • Хантер Р. Основные концепции компиляторов (Документ)
  • Руководство по расчету и конструированию железобетонных ферм покрытия (Стандарт)
  • Руководство по конструированию бетонных и ж.б. конструкций из тяжелого бетона (без предварительного напряжения) 1978 (Стандарт)
  • Конспект занятия по конструированию в подготовительной группе детского сада Мост для жителей волшебного города (Лекция)
  • Харламов С.В. Практикум по расчету и конструированию машин и аппаратов пищевых производств (Документ)
  • Буйлов Г.П., Доронин В.А., Серебряков Н.П. Автоматическое управление технологическими процессами целлюлозно-бумажного производства (Документ)
  • Гербер И.А. Лекции по конструированию спортивных изделий (Документ)
  • Свердлов С.З. Введение в методы трансляции (Документ)
  • (Документ)
  • Карунин А.Л. (ред.) Конструкция автомобиля. Шасси (Документ)
  • Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум (Документ)

n1.doc

Лекции по
конструированию компиляторов

Предлагаемая вниманию читателя книга основана на курсе лекций,

прочитанных автором на факультете вычислительной математики и

кибернетики Московского государственного университета в 1991-

1993 гг. Автор надеется, что издание книги восполнит

существенный пробел в литературе на руссом языке по разработке

Содержание книги представляет собой «классические» разделы

предмета: лексический и синтаксический анализ, организация

памяти, генерация кода. Сделана попытка на протяжении всего

изложения провести единую «атрибутную» точку зрения на процесс

разработки компилятора. В книге не затрагиваются чрезвычайно

важные вопросы глобальной оптимизации и разработки

компиляторов для машин с параллельной архитектурой. Автор

надеется восполнить эти пробелы в будущем.

Книга будет полезной как студентам и аспирантам

программистских специальностей, так и профессионалам в этих

областях.
Оглавление
Глава 1. Введение 6

1.1. Место компилятора в программном обеспечении 6

1.2. Структура компилятора 7

Глава 2. Лексический анализ 11

2.1. Регулярные множества и регулярные выражения 13

2.2. Конечные автоматы 14

2.3. Построение детерминированного конечного

автомата по регулярному выражению 17

2.4. Построение детерминированного конечного

автомата с минимальным числом состояний 20

2.5. Программирование лексических анализаторов 22

2.6. Конструктор лексических анализаторов LEX 27

Глава 3. Синтаксический анализ 31

3.1. Основные понятия и определения 31

3.2. Таблично-управляемый предсказывающий разбор 33

3.2.1. Алгоритм разбора сверху-вниз 33

3.2.2. Множества FIRST и FOLLOW 37

3.2.3. Конструирование таблиц

предсказывающего анализатора 39

3.2.4. LL(1)-грамматики 40

3.2.5. Удаление левой рекурсии 41

3.2.6. Левая факторизация 43

3.2.7. Рекурсивный спуск 44

3.2.8. Диаграммы переходов для рекурсивного спуска 46

3.2.9. Восстановление после синтаксических ошибок 48

3.3. Разбор снизу-вверх типа сдвиг-свертка 49

3.3.2. LR(k)-анализаторы 51

3.3.3. LR грамматики 56

3.3.4. Конфликты разбора типа сдвиг-свертка 62

3.3.5. Восстановление после синтаксических ошибок 63

Глава 4. Промежуточные представления программы 64

4.1. Представление в виде ориентированного графа 64

4.2. Трехадресный код 64

4.3. Линеаризованные представления 69

4.4. Организация информации в генераторе кода 72

4.5. Уровень промежуточного представления 73

Глава 5. Элементы теории перевода 74

5.1. Преобразователи с магазинной памятью 74

5.2. Синтаксически управляемый перевод 76

5.3. Атрибутные грамматики 79

5.3.1. Определение атрибутных грамматик 79

5.3.2. Атрибутированное дерево разбора 80

5.3.3. Язык описания атрибутных грамматик 81

Глава 6. Контекстные условия языков программирования 85

6.1. Описание областей видимости и блочной структуры 85

6.2. Структура среды Модулы-2 86

6.3. Занесение в среду и поиск объектов 90

Глава 7. Организация таблиц символов компилятора 98

7.1. Таблицы идентификаторов и таблицы символов 98

7.2. Таблицы идентификаторов 99

7.3. Таблицы символов и таблицы расстановки 102

7.4. Функции расстановки 103

7.5. Таблицы на деревьях 104

7.6. Реализация блочной структуры 108

7.7. Сравнение различных методов реализации таблиц 109

Глава 8. Генерация кода 110

8.1. Модель машины 110

8.2. Динамическая организация памяти 113

8.3. Назначение адресов 122

8.4. Трансляция переменных 124

8.5. Трансляция целых выражений 130

8.6. Распределение регистров при вычислении

арифметических выражений 132

8.7. Трансляция логических выражений 143

8.8. Выделение общих подвыражений 151

8.9. Генерация оптимального кода методами

синтаксического анализа 155

8.9.1. Сопоставление образцов 155

8.9.2. Синтаксический анализ для Т-грамматик 158

8.9.3. Выбор дерева вывода наименьшей стоимости 165

Глава 9. Системы автоматизации построения трансляторов 169

9.1. Система Супер 169

9.2. Система Yacc 172

Литература 175
Глава 1. Введение

1.1. Место компилятора в программном обеспечении
Компиляторы составляют существенную часть программного

обеспечения ЭВМ. Это связано с тем, что языки высокого уровня

стали основным средством разработки программ. Только очень

незначительная часть программного обеспечения, требующая

особой эффективности, программируется с помощью ассемблеров. В

настоящее время распространено довольно много языков

программирования. Наряду с традиционными языками, такими, как

Фортран, широкое распространение получили так называемые

«универсальные языки» (Паскаль, Си, Модула-2, Ада и другие), а

также некоторые специализированные (например, язык обработки

списочных структур Лисп). Кроме того, большое распространение

получили языки, связанные с узкими предметными областями,

такие, как входные языки пакетов прикладных программ.

Для некоторых языков имеется довольно много реализаций.

Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа

IBM/PC на рынке десятки.

С другой стороны, постоянно растущая потребность в новых

компиляторах связана с бурным развитием архитектур ЭВМ. Это

развитие идет по различным направлениям. Совершенствуются

старые архитектуры как в концептуальном отношении, так и по

отдельным, конкретным линиям. Это можно проиллюстрировать на

примере микропроцессора Intel-80X86. Последовательные версии

этого микропроцессора 8086, 80186, 80286, 80386, 80486, 80586

отличаются не только техническими характеристиками, но и, что

более важно, новыми возможностями и, значит, изменением

(расширением) системы команд. Естественно, это требует новых

компиляторов (или модификации старых). То же можно сказать о

микропроцессорах Motorola 68010, 68020, 68030, 68040.

В рамках традиционных последовательных машин возникает

большое число различных направлений архитектур. Примерами

могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как

Intel, Motorola, Sun, DEC, начинают переходить на выпуск машин

с RISC-архитектурами. Естественно, для каждой новой системы

команд требуется полный набор новых компиляторов с

Наконец, бурно развиваются различные параллельные

архитектуры. Среди них отметим векторные, многопроцессорные, с

широким командным словом (вариантом которых являются

суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с

параллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и

другие), через рабочие станции (например, IBM/RS-6000) и

кончая персональными (например, на основе микропроцессора I-

860). Естественно, для каждой из машин создаются новые

компиляторы для многих языков программирования. Здесь

необходимо также отметить, что новые архитектуры требуют

разработки совершенно новых подходов к созданию компиляторов,

так что наряду с собственно разработкой компиляторов ведется и

большая научная работа по созданию новых методов трансляции.

1.2. Структура компилятора
Обобщенная структура компилятора и основные фазы компиляции

показаны на рис. 1.1.

На фазе лексического анализа (ЛА) входная программа,

представляющая собой поток символов, разбивается на лексемы —

слова в соответствии с определениями языка. Основным

формализмом, лежащим в основе реализации лексических

анализаторов, являются конечные автоматы и регулярные

выражения. Лексический анализатор может работать в двух

основных режимах: либо как подпрограмма, вызываемая

синтаксическим анализатором за очередной лексемой, либо как

полный проход, результатом которого является файл лексем.

В процессе выделения лексем ЛА может как самостоятельно

строить таблицы имен и констант, так и выдавать значения для

каждой лексемы при очередном обращении к нему. В этом случае

таблица имен строится в последующих фазах (например, в

процессе синтаксического анализа).

Вход | анализ | +————-+ || Поток лексем +||


| Конечные | || и констант || |

| анализ | +————-+ || Дерево разбора ||

| Контекстно-сво- | || имен и констант|||

| Атрибутные | || + таблица символов || |

| промежуточного | || Промежуточная форма ||

| представления | || (префиксная, пост- ||

| Потоковый | || (ориентированный граф)|| |

| Таблицы решений, | || Объектный ||

+————————+ +————-+
Рис. 1.1
На этапе ЛА обнаруживаются некоторые (простейшие) ошибки

(недопустимые символы, неправильная запись чисел,

идентификаторов и др.).

Основная задача синтаксического анализа — разбор структуры

программы. Как правило, под структурой понимается дерево,

соответствующее разбору в контекстно-свободной грамматике

языка. В настоящее время чаще всего используется либо LL(1)-

анализ (и его вариант — рекурсивный спуск), либо LR(1)-анализ

и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный

спуск чаще используется при ручном программировании

синтаксического анализатора, LR(1) — при использовании систем

автоматизации построения синтаксических анализаторов.

Результатом синтаксического анализа является синтаксическое

дерево со ссылками на таблицу имен. В процессе синтаксического

анализа также обнаруживаются ошибки, связанные со структурой

На этапе контекстного анализа выявляются зависимости между

частями программы, которые не могут быть описаны контекстно-

свободным синтаксисом. Это в основном связи «описание-

использование», в частности анализ типов объектов, анализ

областей видимости, соответствие параметров, метки и другие. В

процессе контекстного анализа строится таблица символов,

которую можно рассматривать как таблицу имен, пополненную

информацией об описаниях (свойствах) объектов.

Основным формализмом, использующимся при контекстном

анализе, являются атрибутные грамматики. Результатом работы

фазы контекстного анализа является атрибутированное дерево

программы. Информация об объектах может быть как

рассредоточена в самом дереве, так и сосредоточена в отдельных

таблицах символов. В процессе контекстного анализа также могут

быть обнаружены ошибки, связанные с неправильным

Затем программа может быть переведена во внутреннее

представление. Это делается для целей оптимизации и/или

удобства генерации кода. Еще одной целью преобразования

программы во внутреннее представление является желание иметь

переносимый компилятор. Тогда только последняя фаза (генерация

кода) является машинно-зависимой. В качестве внутреннего

представления может использоваться префиксная или постфиксная

запись, ориентированный граф, тройки, четверки и другие.

Фаз оптимизации может быть несколько. Оптимизации обычно

делят на машинно-зависимые и машинно-независимые, локальные и

глобальные. Часть машинно-зависимой оптимизации выполняется на

фазе генерации кода. Глобальная оптимизация пытается принять

во внимание структуру всей программы, локальная — только

небольших ее фрагментов. Глобальная оптимизация основывается

на глобальном потоковом анализе, который выполняется на графе

программы и представляет по существу преобразование этого

графа. При этом могут учитываться такие свойства программы,

как межпроцедурный анализ, межмодульный анализ, анализ

областей жизни переменных и т.д.

Наконец, генерация кода — последняя фаза трансляции.

Результатом ее является либо ассемблерный модуль, либо

объектный (или загрузочный) модуль. В процессе генерации кода

могут выполняться некоторые локальные оптимизации, такие как

распределение регистров, выбор длинных или коротких переходов,

учет стоимости команд при выборе конкретной последовательности

команд. Для генерации кода разработаны различные методы, такие

как таблицы решений, сопоставление образцов, включающее

динамическое программирование, различные синтаксические

Конечно, те или иные фазы транслятора могут либо

отсутствовать совсем, либо объединяться. В простейшем случае

однопроходного транслятора нет явной фазы генерации

промежуточного представления и оптимизации, остальные фазы

объединены в одну, причем нет и явно построенного

Глава 2. Лексический анализ
Основная задача лексического анализа — разбить входной текст,

состоящий из последовательности одиночных символов, на

последовательность слов, или лексем, т.е. выделить эти слова

из непрерывной последовательности символов. Все символы

входной последовательности с этой точки зрения разделяются на

символы, принадлежащие каким-либо лексемам, и символы,

разделяющие лексемы (разделители). В некоторых случаях между

лексемами может и не быть разделителей. С другой стороны, в

некоторых языках лексемы могут содержать незначащие символы

(пробел в Фортране). В Си разделительное значение символов-

разделителей может блокироваться (‘\’ в конце строки внутри

Обычно все лексемы делятся на классы. Примерами таких

классов являются числа (целые, восьмеричные,

шестнадцатиричные, действительные и т.д.), идентификаторы,

строки. Отдельно выделяются ключевые слова и символы

пунктуации (иногда их называют символы-ограничители). Как

правило, ключевые слова — это некоторое конечное подмножество

идентификаторов. В некоторых языках (например, ПЛ/1) смысл

лексемы может зависеть от ее контекста и невозможно провести

лексический анализ в отрыве от синтаксического.

С точки зрения дальнейших фаз анализа лексический анализатор

выдает информацию двух сортов: для синтаксического

анализатора, работающего вслед за лексическим, существенна

информация о последовательности классов лексем, ограничителей

и ключевых слов, а для контексного анализа, работающего вслед

за синтаксическим, важна информация о конкретных значениях

отдельных лексем (идентификаторов, чисел и т.д.). Поэтому

общая схема работы лексического анализатора такова. Сначала

выделяем отдельную лексему (возможно, используя символы-

разделители). Если выделенная лексема — ограничитель, то он

(точнее, некоторый его признак) выдается как результат

лексического анализа. Ключевые слова распознаются либо явным

выделением непосредственно из текста, либо сначала выделяется

идентификатор, а затем делается проверка на принадлежность его

множеству ключевых слов. Если да, то выдается признак

соответствующего ключевого слова, если нет — выдается признак

идентификатора, а сам идентификатор сохраняется отдельно. Если

выделенная лексема принадлежит какому-либо из других классов

лексем (число, строка и т.д.), то выдается признак класса

лексемы, а значение лексемы сохраняется.

Лексический анализатор может работать или как

самостоятельная фаза трансляции, или как подпрограмма,

работающая по принципу «дай лексему». В первом случае (рис.

2.1) выходом лексического анализатора является файл лексем, во

втором (рис. 2.2) лексема выдается при каждом обращении к

лексическому анализатору (при этом, как правило, тип лексемы

возвращается как значение функции «лексический анализатор», а

значение передается через глобальную переменную). С точки

зрения формирования значений лексем, принадлежащих классам

лексем, лексический анализатор может либо просто выдавать

значение каждой лексемы и в этом случае построение таблиц

переносится на более поздние фазы, либо он может

самостоятельно строить таблицы объектов (идентификаторов,

строк, чисел и т.д.). В этом случае в качестве значения

лексемы выдается указатель на вход в соответствующую таблицу.

| Синт. анализатор | | Таблица | | Лекс. анализатор |——+

Файл лексем «Дай лексему»
Рис. 2.1 Рис. 2.2

Работа лексического анализатора описывается формализмом

конечных автоматов. Однако непосредственное описание конечного

автомата неудобно практически. Поэтому для описания

лексических анализаторов, как правило, используют либо

формализм регулярных выражений, либо формализм контекстно

свободных грамматик, а именно подкласса автоматных, или

регулярных, грамматик. Все три формализма (конечных автоматов,

регулярных выражений и автоматных грамматик) имеют одинаковую

выразительную мощность. По описанию лексического анализатора в

виде регулярного выражения или автоматной грамматики строится

конечный автомат, распознающий соответствующий язык.

2.1. Регулярные множества и регулярные выражения
Пусть T — конечный алфавит. Регулярное множество в алфавите T

определяется рекурсивно следующим образом (знаком ‘ || 3 ||

Такт автомата M представляется бинарным отношением |-,

определенным на конфигурациях: отношение имеет место, если

есть переход из конфигурации (q1,w1) в конфигурацию (q2,w2).

Отношения |-+ и |-* — это, соответственно, транзитивное и

рефлексивно-транзитивное замыкание отношения |-. Говорят, что

автомат M допускает цепочку w, если (q0,w)|-*(q,e) для

некоторого q p. На диаграмме выделяются

конечные состояния (в примерах выше двойным контуром).
Пример 2.2. Диаграмма для чисел языка Паскаль приведена на

2.3. Построение детерминированного конечного автомата по

регулярному выражению.
Приведем теперь алгоритм построения детерминированного

конечного автомата по регулярному выражению [1]. К регулярному

выражению (сокращенно РВ) r добавим маркер конца: (r)#. После

построения ДКА для расширенного РВ легко построить ДКА для

исходного РВ: все состояния ДКА из которых есть переход в

конечное с чтением символа «#», можно считать конечными, а

символ «#» и соответствующие переходы удалить.

Представим РВ в виде дерева, листья которого — терминальные

символы, а внутренние вершины — операции «.» (конкатенации),

«U» (объединение), «*» (итерация).

Каждому листу дерева (кроме e-листьев) припишем уникальный

номер и ссылаться на него будем, с одной стороны, как на

позицию в дереве и, с другой стороны, как на позицию символа,

Теперь, обходя дерево T сверху-вниз слева-направо, вычислим

четыре функции: nullable, firstpos, lastpos и followpos.

Функции nullable, firstpos и lastpos определены на узлах

дерева, а followpos — на множестве позиций. Значением всех

функций, кроме nullable, является множество позиций. Функция

followpos вычисляется через три остальные функции.

Функция firstpos(n) для каждого узла n синтаксического

дерева регулярного выражения дает множество позиций, которые

соответствуют первым символам в подцепочках, генерируемых

подвыражением с вершиной в n. Аналогично, lastpos(n) дает

множество позиций, которым соответствуют последние символы в

подцепочках, генерируемых подвыражениями с вершиной n. Для

узлов n, поддеревья которых (т.е. дерево, у которого узел n

является корнем) могут породить пустое слово, определим

nullable(n)=true, а для остальных узлов false.
узел n nullable(n) firstpos(n) lastpos(n)

лист е | true | 0 | 0

U | nullable(a) | firstpos(a) | lastpos(a)

a b | nullable(b) | firstpos(b) | lastpos(b)

. | nullable(a) | if nullable(a) |if nullable(b)

/ \ | and | then firstpos(a) |then lastpos(a)

| | U firstpos(b) | U lastpos(b)

a b | nullable(b) | else firstpos(a) |else lastpos(b)

| | true | firstpos(a) | lastpos(a)

на рис. 2.5. Вычисление функции lastpos строится аналогично.
<1,2,3>.

Рис. 2.6 Рис. 2.7
Пример 2.3. Функции firstpos и lastpos для выражения (a+b)abb#

приведены на рис. 2.6. Слева от каждой вершины значение

firstpos, справа — lastpos. Заметим, что эти функции могут

быть вычислены за один обход дерева.

Если i — позиция, то followpos(i) есть множество позиций j

таких, что существует некоторая строка . cd. входящая в

язык, описываемый РВ, такая, что i — соответствует этому

вхождению c, а j — вхождению d.

Функция followpos может быть вычислена также за один обход

дерева по следующим двум правилам
1. Пусть n — внутренний узел с операцией «.» (конкатенация),

a,b — его потомки. Тогда для каждой позиции i, входящей в

lastpos(a), добавляем к множеству значений followpos(i)

множество firstpos(b).
2. Пусть n — внутренний узел с операцией «*» (итерация), a —

его потомок. Тогда для каждой позиции i, входящей в

lastpos(a), добавляем к множеству значений followpos(i)

множество firstpos(а).
Для примера 2.3 значения функции followpos приведены на рис.

Функция followpos позволит теперь сразу построить

детерминированный конечный автомат с помощью следующего

алгоритма.
Алгоритм 2.1. Прямое построение ДКА по регулярному выражению.
Будем строить множество состояний автомата Dstates и помечать

их. Состояния ДКА соответствуют множествам позиций. Начальным

состоянием будет состояние firstpos(root), где root — вершина

синтаксического дерева регулярного выражения, конечными — все

состояния, содержащие позиции, связанные с символом «#».

Сначала в Dstates имеется только одно непомеченное состояние

firstpos(root).
while есть непомеченное состояние T в Dstates do

for каждого входного символа a Sb | <1,2,3> <4>

V | V a V | V V b | b | |

2.4. Построение детерминированного конечного автомата с

минимальным числом состояний
Рассмотрим теперь алгоритм построения ДКА с минимальным числом

состояний, эквивалентного данному ДКА [2].
Алгоритм 2.2. Построение ДКА с минимальным числом состояний.
Шаг 1. Строим начальное разбиение П множества состояний из

двух групп: заключительное состояние и остальные S-F.
Шаг 2. Применяем к П следующую процедуру и получаем новое

разбиение Пnew (рис. 2.11):
for каждой группы G в П do

разбиваем G на подгруппы так, чтобы

состояния s и t из G оказались в одной

группе тогда и только тогда, когда для каждого

входного символа a состояния s и t имеют

переходы по a в состояния из одной и той же

заменяем G в Пnew на множество всех

Проверки на принадлежность диапазону сравнениями можно

заменить проверками на принадлежность диапазону множества:
while (Insym in [‘0’..’9′]) do

end;
Однако с точки зрения качества кода эти программы примерно

эквивалентны. Программу можно значительно улучшить следующим

образом [2]. Пусть LETTER, DIGIT, BLANK, SLESS — элементы

перечислимого типа. Введем массив MAP, входами которого будут

символы, значениями — типы символов. Инициализируем массив MAP

следующим образом:
MAP[‘A’]:=LETTER;

+—+ f +—/не буква и не цифра | слово if |

+—+ Буква или цифра |

| Не буква и не цифра

| Ключевое слово int |

Для этого строится конечный автомат, описывающий множество

ключевых слов. На рис. 2.12 приведен фрагмент такого автомата.

Рассмотрим пример программирования этого конечного автомата на

языке Си, приведенный в [3]:
case ‘i’:

if (cp[0]==’f’ &&!(map[cp[1]] & (digit | letter)))

&&!(map[cp[2]] & (digit | letter)))

Здесь cp — указатель текущего символа. В массиве map классы

символов кодируются битами.

Поскольку ЛА анализирует каждый символ входного потока, его

скорость существенно зависит от скорости выборки очередного

символа входного потока. В свою очередь, эта скорость во

многом определяется схемой буферизации. Рассмотрим несколько

возможных эффективных схем буферизации.

В первой схеме используется буфер, размер которого — двойная

длина блока обмена N (рис. 2.13).
N N

|Начало лексемы (cp) |Начало лексемы
Рис. 2.13 Рис. 2.14

Чтобы не читать каждый символ отдельно, в каждую из половин

буфера одной командой чтения считывается N символов. Если на

входе осталось меньше N символов, в буфер помещается

специальный символ (eof). На буфер указывают два указателя:

продвижение и начало. Между указателями размещается текущая

лексема. Вначале они оба указывают на первый символ выделяемой

лексемы. Один из них, продвижение, продвигается вперед, пока

не будет выделена лексема, и устанавливается на ее конец.

После обработки лексемы оба указателя устанавливаются на

символ, следующий за лексемой. Если указатель продвижение

переходит середину буфера, правая половина заполняется новыми

N символами. Если указатель продвижение переходит правую

границу буфера, левая половина заполняется N символами и

указатель продвижение устанавливается на начало буфера.

При каждом продвижении указателя необходимо проверять, не

достигли ли мы границы одной из половин буфера. Для всех

символов, кроме лежащих в конце половин буфера, требуются две

проверки. Число проверок можно свести к одной, если в конце

каждой половины поместить дополнительный ‘сторожевой’ символ
‘#’ (рис. 2.14).
В этом случае почти для всех символов делается единственная

проверка на совпадение с ‘#’ и только в случае совпадения

нужно проверить, достигли ли мы середины или правого конца.

В третьей схеме используются три указателя (рис. 2.15).

Непросмотренная часть буфера заключена между текущим и

границей (граница — это указатель на последний элемент

буфера). Анализ очередной лексемы начинается после

сканирования незначащих пробелов. Если после этого текущий

указывает на ‘#’ в конце буфера, делается перезагрузка буфера

(предполагается, что ‘#’ не может входить в состав лексемы).

Барьер выбирается таким образом, чтобы между барьером и

границей всегда помещалась любая лексема. Если начало

очередной лексемы оказывается правее барьера, то часть буфера

от текущего до границы переписывается левее буфера и буфер

перезагужается. Тем самым начало лексемы конкатенируется с ее

концом. Так обрабатывается ситуация, когда граница буфера

Илон Маск рекомендует:  Что такое код udm_free_agent
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL