Теория языков программирования методов трансляции (стр. 42 )

Рис. 8.13. Бинарное дерево в конце обхода

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

Контрольные вопросы

1.  Стек времени прогона, структура и программная реализация.

2.  Технология распределения статической и динамической части стека.

3.  Методы вызова параметров в процедурах, их достоинства и недостатки.

4.  Организация распределения памяти при выполнении процедур.

5.  Организация памяти для структур типа список (куча).

6.  Освобождение памяти в «куче». Счетчик ссылок.

7.  Сборка мусора. Алгоритмы MARK1 и MARK2. Их преимущества и недостатки.

8.  Сборка мусора. Алгоритмы Кнута, Шорра и Уэйта.

10.  Генерация кода

10.1.  Генерация промежуточного кода.

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

1)  генерация не зависящего от машины промежуточного кода;

2)  генерация машинного кода для конкретной ЭВМ.

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

Обычно промежуточный код получается разбиением сложной структуры исходного языка на более удобные для обращения элементы.

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

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

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

Другой вариант кода – тройки (двухадресный код). Каждая тройка состоит из двух адресов операндов и знака операции.

Выражение

можно представить в виде четверок:

и виде троек:

Если сам операнд является тройкой, то используется ее позиция (регистр) для хранения результата.

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

в виде четверки представляется как

,

а в виде тройки – как

.

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

Префиксная нотация известна также как польская запись, а постфиксная - как обратная польская запись (запись Лукашевича). Например, выражение

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

,

а в постфиксной так:

.

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

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

1)  напечатать идентификатор, когда он встретится при чтении инфиксного выражения слева направо;

2)  поместить в стек знак операции, когда он встретится;

3)  когда встретится конец выражения (или подвыражения), выдать на печать этот знак операции, который находится в стеке.

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

Пример:

Рис. 9.1. Бинарное дерево

Чтобы получить представление префиксного выражения дерево обходят сверху в порядке:

-  посещение корня;

-  обход левого поддерева сверху;

-  обход правого поддерева сверху,

что дает .

Для получения постфиксного представления дерево обходят снизу:

-  обход левого поддерева снизу;

-  обход правого поддерева снизу;

-  посещение корня.

В результате имеем: .

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

тип - команды параметры

Тип команды может быть, например, вызовом стандартного обозначения операции:

.

Здесь II+ - сложение двух целых чисел A, B и C служат во время прогона адресами двух операндов и результата. Для того чтобы в промежуточном коде можно было воспользоваться адресами во время прогона, распределение памяти к этому моменту должно быть уже закончено.

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

Адрес на время прогона соотносится со стеком, и каждый адрес можно представить тройкой вида

(тип – адреса, номер - блока, смещение).

Тип – адреса может быть прямым или косвенным (т. е. содержать значение или указывать на значение) и ссылаться на рабочий стек или стек идентификаторов.

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

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

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

Кроме трехадресной команды существуют другие команды промежуточного кода:

для установки метки и

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

10.2.  Структура данных для генерации кода

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

-  адрес времени прогона;

-  тип данных;

-  область действия (номер рамки).

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

При трансляции A+B первыми помещаются в нижний стек статические свойства A. Любой элемент нижнего стека можно представить в виде структуры, имеющей поле для каждой из своих аналитических характеристик. Для идентификаторов аналитические характеристики находятся из таблицы символов. Затем в стек знаков операции помещается «+», и в нижний стек добавляются аналитические характеристики B. Знак операции берется из стека знаков операции, а его два операнда - из нижнего стека. Типы операндов используются для идентификации знака операции, после чего генерируется код. И, наконец, в нижний стек помещаются статические характеристики результата.