В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 29
Текст из файла (страница 29)
8.2 соответствуют четверкам табл. 8.1.Для представления тройками трехместной операции типа x[i] := y требуется два входа, как это показано в табл. 8.3, представление x := y[i] двумяоперациями показано в табл. 8.4.Т а б л и ц а 8.3oparg 1 arg 2(0) [ ]=xi(1) :=(0)yТрехадресный код может быть представлен не списком троек, а списком указателей на них. Такая реализация обычно называется косвеннымитройками. Например, тройки табл. 8.2 могут быть реализованы так, как этопредставлено в табл. 8.5.1538.2. Трехадресный кодТ а б л и ц а 8.4oparg 1 arg 2(0) =[ ]yi(1)x(0):=Т а б л и ц а 8.5оператор op arg 1 arg 2(0)(14)-c(1)(15)*b(2)(16)-c(3)(17)*b(16)(4)(18)+(15)(17)(5)(19):=a(18)(14)При генерации объектного кода каждой переменной, как временной, таки определенной в исходной программе, назначается память периода исполнения, адрес которой обычно хранится в таблице генератора кода.
При использовании четверок этот адрес легко получить через эту таблицу.Более существенно преимущество четверок проявляется в оптимизирующих компиляторах, когда может возникнуть необходимость перемещатьоператоры. Если перемещается оператор, вычисляющий x, то не требуетсяизменений в операторе, использующем x. В записи же тройками перемещение оператора, определяющего временное значение, требует изменения всехссылок на этот оператор в массивах arg 1 и arg 2.
Из-за этого тройки трудноиспользовать в оптимизирующих компиляторах.В случае применения косвенных троек оператор может быть перемещенпереупорядочиванием списка операторов. При этом не надо менять указателина op, arg 1 и arg 2. Этим косвенные тройки похожи на четверки. Крометого, эти два способа требуют примерно одинаковой памяти. Как и в случаепростых троек, при использовании косвенных троек выделение памяти длявременных значений может быть отложено на этап генерации кода. По сравнению с четверками при использовании косвенных троек можно сэкономитьпамять, если одно и то же временное значение используется более одногораза.
Например, в табл. 8.5 можно объединить строки (14) и (16), после чегоможно объединить строки (15) и (17).154Глава 8. Промежуточное представление программы8.3. Линеаризованные представленияВ качестве промежуточных представлений весьма распространены линеаризованные представления деревьев. Линеаризованное представление позволяет сравнительно легко хранить промежуточное представление во внешнейпамяти и обрабатывать его. Наиболее распространенной формой линеаризованного представления является польская запись — префиксная (прямая) илипостфиксная (обратная).Постфиксная запись — это список вершин дерева, в котором каждаявершина следует (при обходе снизу-вверх слева-направо) непосредственноза своими потомками.
Дерево на рис. 8.1, а в постфиксной записи может бытьпредставлено следующим образом:a b c - * b c - * + :=В постфиксной записи вершины синтаксического дерева не присутствуютявно. Они могут быть восстановлены из порядка, в котором следуют вершины,и из числа операндов соответствующих операций. Восстановление вершинаналогично вычислению выражения в постфиксной записи с использованиеммагазина.В префиксной записи сначала указывается операция, а затем ее операнды.Например, для приведенного выше выражения имеем:= a + * b - c * b - cРассмотрим детальнее одну из реализаций префиксного представления —Лидер [12]. Лидер — это аббревиатура от «ЛИнеаризованное ДЕРево».
Этомашинно-независимая префиксная запись. В Лидере сохраняются все объявления и каждому из них присваивается свой уникальный номер, которыйиспользуется для ссылки на объявление. Рассмотрим пример: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.Этот фрагмент имеет следующий образ в Лидере:program ’M’var intvar intvar int8.3.
Линеаризованные представленияprocbody proc int int end intvar intbegin assign var 1 7 endint int mi par 1 5 end par 1 6 endresult 0 int var 1 7 endreturnendbegin assign var 0 3 end inticall 0 4 int var 0 1 endint var 0 2 end endendРассмотрим его более детально:program ’M’var intvar intvar intprocbody procint int endintvar intbeginassignvar 1 7 endintint mipar 1 5 endpar 1 6 endresult 0intvar 1 7 endreturnИмя модуля нужно для редакторасвязей.Это образ переменных X, Y, Z;переменным X, Y, Z присваиваютсяномера 1, 2, 3 на уровне 0.Объявление процедуры с двумяцелыми параметрами, возвращающей целое.Процедура получает номер 4 науровне 0, и параметры имеют номера 5, 6 на уровне 1.Переменная R имеет номер 7 науровне 1.Начало тела процедуры.Оператор присваивания.Левая часть присваивания (R).Тип присваиваемого значения.Целое вычитание.Уменьшаемое (A).Вычитаемое (B).Результат процедуры уровня 0.Результат имеет целый тип.Результат — переменная R.Оператор возврата.155156endbeginassignvar 0 3inticall 0int varint varendendГлава 8.
Промежуточное представление программыend40 1 end0 2 endКонец тела процедуры.Начало тела модуля.Оператор присваивания.Левая часть — переменная Z.Тип присваиваемого значения.Вызов локальной процедуры DIF.Фактические параметры Xи Y.Конец вызова.Конец тела модуля.8.4. Виртуальная машина JavaПрограммы на языке Java транслируются в специальное промежуточноепредставление, которое затем интерпретируется так называемой «виртуальноймашиной Java».
Виртуальная машина Java представляет собой магазиннуюмашину: она не имеет памяти прямого доступа, все операции выполняютсянад операндами, расположенными на верхушке магазина. Чтобы, например,выполнить операцию с участием константы (или переменной), ее необходимопредварительно загрузить на верхушку магазина. Код операции — всегда одинбайт. Если операция имеет операнды, то они располагаются в следующихбайтах.К элементарным типам данных, с которыми работает машина, относятсяshort, integer, long, float, double (все знаковые).8.4.1.
Организация памяти. Машина имеет следующие регистры:pc — счетчик команд;optop — указатель вершины магазина операций;frame — указатель на область исполняемого метода в магазине;vars — указатель на 0-ю переменную исполняемого метода.Все регистры 32-разрядные. Магазинный фрейм имеет три компоненты: локальные переменные, среду исполнения, магазин операндов.
Локальные переменные отсчитываются от адреса в регистре vars. Среда исполнения служитдля поддержания самого магазина. Она включает указатель на предыдущийфрейм, указатель на собственные локальные переменные, на базу стекаопераций и на верхушку магазина.
Кроме того, здесь же хранится некотораядополнительная информация, например, для отладчика.Куча сбора мусора содержит экземпляры объектов, которые создаютсяи уничтожаются автоматически. Область методов содержит коды, таблицысимволов и т. п.С каждым классом связана область констант. Она содержит имена полей,методов и другую подобную информацию, которая используется методами.8.4. Виртуальная машина Java1578.4.2.
Набор команд виртуальной машины. Виртуальная Java-машинаимеет следующие команды:помещение констант в магазин,помещение локальных переменных в магазин,запоминание значений из магазина в локальных переменных,обработка массивов,управление магазином,арифметические команды,логические команды,преобразования типов,передача управления,возврат из функции,табличный переход,обработка полей объектов,вызов метода,обработка исключительных ситуаций,прочие операции над объектами,мониторы,отладка.Рассмотрим некоторые команды подробнее.8.4.2.1. Помещение локальных переменных в магазин.
Команда iload—загрузить целое из локальной переменной.Операндом является смещение переменной в области локальных переменных. Указываемое значение копируется на верхушку магазина операций.Имеются аналогичные команды для помещения плавающих, двойных целых,двойных плавающих и т. п.Команда istore— сохранить целое в локальной переменной.Операндом операции является смещение переменной в области локальныхпеременных. Значение с верхушки магазина операций копируется в указываемую область локальных переменных.
Имеются аналогичные команды дляпомещения плавающих, двойных целых, двойных плавающих и т. п.8.4.2.2. Вызов метода. Команда invokevirtual.При трансляции объектно-ориентированных языков программированияиз-за возможности перекрытия виртуальных методов, вообще говоря, нельзястатически протранслировать вызов метода объекта. Это связано с тем, чтоесли метод перекрыт в производном классе и вызывается метод объектапеременной, то статически неизвестно, объект какого класса (базового илипроизводного) хранится в переменной.
Поэтому с каждым объектом связывается таблица всех его виртуальных методов: для каждого метода там158Глава 8. Промежуточное представление программыпомещается указатель на его реализацию в соответствии с принадлежностьюсамого объекта классу в иерархии классов.В языке Java различные классы могут реализовывать один и тот же интерфейс. Если объявлена переменная или параметр типа интерфейс, то динамически нельзя определить, объект какого класса присвоен переменной:interface I;class C1 implements I;class C2 implements I;I O;C1 O1;C2 O2;...O=O1;...O=O2;...В этой точке программы, вообще говоря, нельзя сказать, какого типазначение хранится в переменной O.
Кроме того, при работе программы на языке Java имеется возможность использования методов из других пакетов.Для реализации этого механизма в Java-машине используется динамическоесвязывание.Предполагается, что магазин операндов содержит handle (указательна описание) объекта или массива и некоторое количество аргументов. Операнд операции используется для конструирования индекса в области константтекущего класса. Элемент по этому индексу в области констант содержитполную сигнатуру метода. Сигнатура метода описывает типы параметрови возвращаемого значения.
Из handle объекта извлекается указатель на таблицу методов объекта. Просматривается сигнатура метода в таблице методов.Результатом этого просмотра является индекс в таблицу методов именованного класса, для которого найден указатель на блок метода. Блок методауказывает тип метода (native, synchronized и т. п.) и число аргументов,ожидаемых в магазине операндов.Если метод помечен как synchronized, то запускается монитор, связанный с handle.
Базис массива локальных переменных для нового магазинного фрейма устанавливается так, что он указывает на handle в магазине.Определяется общее число локальных переменных, используемых методом,и, после того как отведено необходимое место для локальных переменных,окружение исполнения нового фрейма помещается в магазин. База магазинаоперандов для этого вызова метода устанавливается на первое слово послеокружения исполнения. Затем исполнение продолжается с первой инструкциивызванного метода.8.5. Организация информации в генераторе кода1598.4.2.3. Обработка исключительных ситуаций. Команда athrow — возбудить исключительную ситуацию.С каждым методом связан список операторов catch.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
