Лекция 9: Промежуточное представление программы
В качестве промежуточных представлений весьма распространены линеаризованные представления деревьев. Линеаризованное представление позволяет относительно легко хранить промежуточное представление во внешней памяти и обрабатывать его. Наиболее распространенной формой линеаризованного представления является польская запись - префиксная (прямая) или постфиксная (обратная).
Постфиксная запись - это список вершин дерева, в котором каждая вершина следует (при обходе снизу-вверх слева-направо) непосредственно за своими потомками. Дерево на рис. 8.1, а, в постфиксной записи может быть представлено следующим образом:
В постфиксной записи вершины синтаксического дерева явно не присутствуют. Они могут быть восстановлены из порядка, в котором следуют вершины и из числа операндов соответствующих операций. Восстановление вершин аналогично вычислению выражения в постфиксной записи с использованием стека.
В префиксной записи сначала указывается операция, а затем ее операнды. Например, для приведенного выше выражения имеем
Рассмотрим детальнее одну из реализаций префиксного представления - Лидер [12]. Лидер - это аббревиатура от "ЛИнеаризованное ДЕРево". Это машинно-независимая префиксная запись. В Лидере сохраняются все объявления и каждому из них присваивается свой уникальный номер, который используется для ссылки на объявление. Рассмотрим пример.
Этот фрагмент имеет следующий образ в Лидере.
Рассмотрим его более детально:
program 'M' Имя модуля нужно для редактора связей. var int Это образ переменных X, Y, Z ; var int переменным X, Y, Z присваиваются var int номера 1, 2, 3 на уровне 0 . procbody proc Объявление процедуры с двумя int int end целыми параметрами, возвращающей целое. int Процедура получает номер 4 на уровне 0 и параметры имеют номера 5, 6 на уровне 1 . var int Переменная R имеет номер 7 на уровне 1 . begin Начало тела процедуры. assign Оператор присваивания. var 1 7 end Левая часть присваивания (R) . int Тип присваиваемого значения. int mi Целое вычитание. par 1 5 end Уменьшаемое (A) par 1 6 end Вычитаемое (B) result 0 Результат процедуры уровня 0 int Результат имеет целый тип var 1 7 end Результат - переменная R return Оператор возврата end Конец тела процедуры begin Начало тела модуля. assign Оператор присваивания. var 0 3 end Левая часть - переменная Z . int Тип присваиваемого значения. icall 0 4 Вызов локальной процедуры DIF int var 0 1 end Фактические параметры X int var 0 2 end и Y end Конец вызова. end Конец тела модуля Виртуальная машина JavaПрограммы на языке Java транслируются в специальное промежуточное представление, которое затем интерпретируется так называемой "виртуальной машиной Java ". Виртуальная машина Java представляет собой стековую машину: она не имеет памяти прямого доступа, все операции выполняются над операндами, расположенными на верхушке стека. Чтобы, например, выполнить операцию с участием константы или переменной, их предварительно необходимо загрузить на верхушку стека. Код операции - всегда один байт. Если операция имеет операнды, они располагаются в следующих байтах.
К элементарным типам данных, с которыми работает машина, относятся short, integer , long, float, double (все знаковые).
Организация памятиМашина имеет следующие регистры: pc - счетчик команд; optop - указатель вершины стека операций; frame - указатель на стек-фрейм исполняемого метода; vars - указатель на 0 -ю переменную исполняемого метода. Все регистры 32-разрядные. Стек-фрейм имеет три компоненты: локальные переменные, среду исполнения, стек операндов. Локальные переменные отсчитываются от адреса в регистре vars. Среда исполнения служит для поддержания самого стека. Она включает указатель на предыдущий фрейм, указатель на собственные локальные переменные, на базу стека операций и на верхушку стека. Кроме того, здесь же хранится некоторая дополнительная информация, например, для отладчика.
Куча сборки мусора содержит экземпляры объектов, которые создаются и уничтожаются автоматически. Область методов содержит коды, таблицы символов и т.д. С каждым классом связана область констант. Она содержит имена полей, методов и другую подобную информацию, которая используется методами.