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

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

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

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

:= 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 (возбудить исключительную ситуацию)

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

Порядок операторов catch в списке важен. Интерпретатор передают управление первому подходящему оператору catch.

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

Чисто синтаксическое дерево несет только информацию о структуре программы. На самом деле в процессе генерации кода требуется также информация о переменных (например, их адреса), процедурах (также адреса, уровни), метках и т.д. Для представления этой информации возможны различные решения. Наиболее распространены два. 1) всю эту информацию можно хранить в таблицах генератора кода; 2) информация хранится в вершинах дерева с соответствующими указателями.

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

Т аблица уровней Таблица описаний
процедур

Для типа:размер

Для переменной:указатель на
тип и адрес (смещение)

Для процедуры: адрес,...


.............................

Рис. 7.9

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

Раздел описаний




Описание Описание Раздел
типа переменной операторов

Рис. 7.10

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

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

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

117

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

Список файлов ответов (шпаргалок)