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

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

Числа в скобках - это указатели на тройки, а имена - это указатели на таблицу символов. На практике информация, необходимая для интерпретации различного типа входов в поля arg1 и arg2, кодируется в поле op или дополнительных полях. Тройки рис. 7.4.б соответствуют четверкам рис. 7.4.а.

op arg1 arg2 result op arg1 arg2

(0) - c t1 (0) - c
(1) * b t1 t2 (1) * b (0)
(2) - c t3 (2) - c
(3) * b t3 t4 (3) * b (2)
(4) + t2 t4 t5 (4) + (1) (3)
(5) := t5 a (5) := a (4)

а) четверки б) тройки

Рис. 7.4

Для представления тройками трехместной операции типа x[i]:=y требуется два входа, как это показано на рис. 7.5.а, представление x:=y[i] двумя операциями показано на рис. 7.5.б.

op arg1 arg2 op arg1 arg2

(0) []= x I (0) =[] y i
(1) := (0) y (1) := x (0)


а) x[i]:=y б) x:=y[i]

Рис. 7.5

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

оператор op arg1 arg2

(0) (14) (14) - c
(1) (15) (15) * b (14)
(2) (16) (16) - c
(3) (17) (17) * b (16)
(4) (18) (18) + (15) (17)
(5) (19) (19) := a (18)

Рис. 7.6

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

Более существенно преимущество четверок проявляется в оптимизирующих компиляторах, когда может возникнуть необходимость перемещать операторы. Если перемещается оператор, вычисляющий x, не требуется изменений в операторе, использующем x. В записи же тройками перемещение оператора, определяющего временное значение, требует изменения всех ссылок на этот оператор в массивах arg1 и arg2. Из-за этого тройки трудно использовать в оптимизирующих компиляторах.

В случае применения косвенных троек оператор может быть перемещен переупорядочиванием списка операторов. При этом не надо менять указатели на op, arg1 и arg2. Этим косвенные тройки похожи на четверки. Кроме того, эти два способа требуют примерно одинаковой памяти. Как и в случае простых троек, при использовании косвенных троек выделение памяти для временных значений может быть отложено на этап генерации кода. По сравнению с четверками при использование косвенных троек можно сэкономить память, если одно и то же временное значение используется более одного раза. Например, на рис. 7.6 можно объединить строки (14) и (16), после чего можно объединить строки (15) и (17).

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

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

Таким образом, постфиксная запись (обратная польская) - это список вершин дерева, в котором каждая вершина следует непосредственно за своими потомками. Дерево на рис. 7.1 в постфиксной записи может быть представлено следующим образом:

a b c - * b c * + :=

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

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

:= a + * b - c * b - c

Рассмотрим детальнее одну из реализаций префиксного представления - Лидер [4]. Лидер - это аббревиатура от 'ЛИнеаризованное ДЕРево'. Это машинно-независимая языково-ориентированная префиксная запись. В этом представлении сохраняются все объявления и каждому из них присваивается свой уникальный номер, который используется для ссылки на объявление. Рассмотрим пример (рис. 7.7).

module M;
var X,Y,Z: integer;
procedure DIF(A,B:integer):integer;
var R:integer;
begin R:=A-B;
return(R);
end DIF;
begin Z:=DIF(X,Y);
end M.

Рис. 7.7

Соответствующий образ в Лидере изображен на рис. 7.8.

program 'M'
var int
var int
var int
procbody proc int int end int
var int
begin assign var 1 7 end
int int mi par 1 5 end par 1 6 end
result 0 int var 1 7 end
return
end
begin assign var 0 3 end int
icall 0 4 int var 0 1 end
int var 0 2 end end
end

Рис. 7.8

Рассмотрим его более детально:

program 'M' Имя модуля используется для редактора
связей
var int Это образ переменных var X,Y,Z:integer;
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 и Y
int var 0 2 end
end Конец вызова
end Конец тела модуля

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

Программы на языке Java транслируются в специальное промежуточное представление, которое затем интерпретируется так называемой “Виртуальной машиной Java”. Виртуальная машина Java представляет собой стековую машину: она не имеет памяти прямого доступа, все операции выполняются над операндами, расположенными на верхушке стека. Чтобы, например, выполнить операцию с участием костанты или переменной, их предварительно необходимо загрузить на верхушку стека. Код операции - всегда один байт. Если операция имеет операнды, они располагаются в следующих байтах.

Элементарные типы данных, с которыми работает машина, - short, integer, long, float, double, все знаковые.

7.4.1. Организация памяти

Машина имеет следующие регистры:

pc - счетчик команд;

optop - указатель вершины стека операций;

frame - указатель на стэк-фрейм исполняемого метода;

vars - указатель на 0-ю переменную исполняемого метода.

Все регистры 32 разрядные. Других регистров нет.

Стэк-фрейм имеет три компоненты:

локальные переменные,

среда исполнения,

стэк операндов.

Локальные переменные отсчитываются от регистра vars.

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

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

Область методов содержит коды, таблицы символов и т.д.

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

7.4.2. Набор команд виртуальной машины

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

Помещение локальных переменных на стек.

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

Обработка массивов.

Управление стеком.

Арифметические команды.

Логические команды.

Преобразования типов.

Передачи управления.

Возврат из функции.

Табличный переход.

Обработка полей объектов.

Вызов метода.

Обработка исключительных ситуаций.

Прочие операции над объектами.

Мониторы.

Отладка.

Рассмотрим некоторые группы команд подробнее.

Помещение локальных переменных на стек.

iload - загрузить целое из локальной переменной.

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

Имеются аналогичные команды для помещения плавающих, двойных целых, двойных плавающих и т.д.

istore - сохранить целое в локальной переменной.

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

Имеются аналогичные команды для помещения плавающих, двойных целых, двойных плавающих и т.д.

Вызов метода

invokevirtual

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

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

interface I;
class C1 implrments I;
class C2 implements I;
I O;
C1 O1;
C2 O2;
...
O=O1;
...
O=O2;
...

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

Предполагается, что стек операндов содержит handle объекта или массива и некоторое количество аргументов. Операнд операции используется для конструирования индекса в область констант текущего класса. Элемент по этому индексу в области констант содержит полную сигнатуру метода. Сигнатура метода описывает типы параметров и возвращаемого значения. Из handle объекта извлекается указатель на таблицу методов объекта. Просматривается сигнатура метода в таблице методов. Результатом этого просмотра является индекс в таблицу методов именованного класса, для которого найден указатель на блок метода. Блок метода указывает тип метода (native, synchronized etc.) и число аргументов, ожидаемых на стеке операндов.

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

Обработка исключительных ситуаций

athrow (возбудить исключительную ситуацию)

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

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