сист пр об ч 3 (1085772), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

8.1.5.3. Фаза сборки

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

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

1. Генерирование кода.

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

8.1.6. ОБЩАЯ СХЕМА КОМПИЛЯТОРА

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

1. Лексический анализ — распознавание базовых элементов, и создание стандартных символов.

2. Синтаксический анализ — распознавание базовых синтак­сических конструкций с использованием редукций.

3. Интерпретация — определение точного смыслового значе­ния, создание матрицы и таблиц при помощи программ интер­претации.

4. Машинно-независимая оптимизация — создание более оп­тимальной матрицы.

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

6. Генерация кода — использование макропроцессора для по­лучения более оптимального кода сборки.

7. Сборка и выдача — разрешение символических адресов к генерирование программы на машинном языке.

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

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

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

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

А. Исходный код — в нашем примере это простая программа на языке ПЛ/1, изображенная на рис. 8.1.

Б. Таблица стандартных символов — состоит из полного или частичного списка лексических единиц, расположенных в том порядке, в каком они встречаются в программе. Она создается при лексическом анализе и используется для синтаксического анализа и интерпретации (рис. 8.3).

В. Таблица терминальных символов — постоянная таблица, в которой записаны все ключевые слова и специальные символы языка в символьной форме (на них ссылаются стандартные сим­волы на рис. 8.3).

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

Д. Таблица литералов — содержит все константы программы (две в нашем примере). Создается и используется аналогично таблице идентификаторов.

Е. Редукции — постоянная таблица решающих правил в фор­ме образцов для сравнения с таблицей стандартных символов в целях распознавания синтаксической структуры.

Ж. Матрица — промежуточная форма, которая создается программами интерпретации, оптимизируется и потом исполь­зуется для генерации кода (рис. 8.6).

3. Кодовые продукции — постоянная таблица определений. В таблице имеется отдельный элемент, определяющий код для каждой возможной операции матрицы (рис. 8.9).

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

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

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

Часть 2

8.2. ФАЗЫ КОМПИЛЯТОРА

В данном разделе подробно рассматриваются семь фаз ком­пилятора. Каждая фаза (рис. 8.13) описывается хронологически, и базы данных вводятся по мере того, как компилятор создает их или впервые обращается к ним. В целях эффективности или из-за особых свойств исходных языков фактические реализации могут в той или иной степени отходить от предлагаемых баз данных и алгоритмов. Например, языки, подобные ФОРТРАНу или КОБОЛу, могут не требовать того, чтобы компилятор уста­навливал столько же атрибутов в таблице идентификаторов, сколько необходимо для языков типа ПЛ/1 или АЛГОЛ. Пред­ложенные алгоритмы также могут оказаться не лучшими для отдельных частных ситуаций. Однако нашей схемой мы хотим показать основные принципы, которым необходимо следовать при разработке компиляторов. Мы полагаем, что читатель мо­жет расширить базы данных для того, чтобы учесть исключения и специальные случаи, с которыми он столкнется при реализа­ции своего собственного компилятора.

8.2.1. ЛЕКСИЧЕСКАЯ ФАЗА

8.2.1.1. Задачи

При выполнении фазы лексического анализа решаются сле­дующие задачи:

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

2. Построение таблиц литералов и идентификаторов,

3. Построение таблицы стандартных символов,

8.2.1.2. Базы данных

При решении этих задач используются следующие базы дан­ных:

1. Исходная программа — программа в ее первоначальном формате; воспринимается компилятором как строка символов,

2. Таблица терминальных символов — постоянная база дан­ных, которая имеет отдельный элемент для каждого терминаль­ного символа (например, арифметические операции, ключевые слова, символы, не являющиеся буквами или цифрами). Каждый элемент состоит из терминального символа, указателя его клас­сификации (операция, разделитель) и его старшинства (исполь­зуемого в последующих фазах). Смотри упражнение 1 в гл. 7„ Ниже представлен элемент таблицы терминальных символов:

Символ

Указатель

Старшинство \

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

Литерал I Основание

Формат

Точность

Другая информация I Адрес

4. Таблица идентификаторов — создается при лексическом анализе для того, чтобы описать все идентификаторы, имеющие­ся в исходной программе. Каждому идентификатору соответ­ствует отдельный элемент таблицы. Во время лексического ана­лиза в этот элемент помещается имя идентификатора. Так как во многих языках длина идентификатора может меняться от 1 до 31, то лексическая фаза для эффективного использования памяти записывает в таблицу идентификаторов указатель. Ука­затель указывает на имя в таблице имен. Атрибуты данных и адрес для каждого идентификатора записываются последующи­ми фазами. Элемент таблицы идентификаторов выглядит так:

Имя:

Атрибуты \ Адрес \

5. Таблица стандартных символов — создается при лексиче­ском анализе для того, чтобы представить программу строкой

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

8.2.1.3. Алгоритм

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

Существует много способов реализации фазы лексического анализа. На рис. 8.14 представлен результат работы лексиче­ской фазы для нашего примера программы на ПЛ/1.

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

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

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

1 2 3 4 5 € 7 8 9 10

Таблица, терминальных символов Символ Разделитель Другие

Таблица стандартных символов
Тип Индекс Лексические

Характеристики

Список файлов лекций