В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 20
Текст из файла (страница 20)
Поля arg1 и arg2 – это либо указатели на таблицусимволов (для имен, определенных программистом, или констант), либо указатели на тройки (для временных значений). Такой способ представления трехадресного кода называют тройками. Тройки соответствуют представлению синтаксического дерева или ОАГ с помощью массивавершин.Числа в скобках – это указатели на тройки, а имена – это указателина таблицу символов.
На практике информация, необходимая для интерпретации различного типа входов в поля arg1 и arg2, кодируется вполе op или дополнительных полях. Тройки рис. 8.4, б, соответствуютчетверкам рис. 8.4, а.Для представления тройками трехместной операции типа x[i] := yтребуется два входа, как это показано на рис. 8.5, а, представление x :=y[i] двумя операциями показано на рис. 8.5, б.8.2. ТРЕХАДРЕСНЫЙ КОД(0)(1)op[ ]=:=arg1x(0)127arg2iy(0)(1)а) x[i] := yop=[ ]:=arg1yxarg2i(0)б ) x := y[i]Рис. 8.5:Трехадресный код может быть представлен не списком троек, а списком указателей на них. Такая реализация обычно называется косвенными тройками.
Например, тройки рис. 8.4, б, могут быть реализованытак, как это изображено на рис. 8.6.(0)(1)(2)(3)(4)(5)оператор(14)(15)(16)(17)(18)(19)(14)(15)(16)(17)(18)(19)op**+:=arg1cbcb(15)aarg2(14)(16)(17)(18)Рис. 8.6:При генерации объектного кода каждой переменной, как временной,так и определенной в исходной программе, назначается память периодаисполнения, адрес которой обычно хранится в таблице генератора кода.При использовании четверок этот адрес легко получить через эту таблицу.Более существенно преимущество четверок проявляется в оптимизирующих компиляторах, когда может возникнуть необходимость перемещать операторы. Если перемещается оператор, вычисляющий x, нетребуется изменений в операторе, использующем x.
В записи же тройками перемещение оператора, определяющего временное значение, требует изменения всех ссылок на этот оператор в массивах arg1 и arg2.Из-за этого тройки трудно использовать в оптимизирующих компиляторах.В случае применения косвенных троек оператор может быть перемещен переупорядочиванием списка операторов.
При этом не надо менятьуказатели на op, arg1 и arg2. Этим косвенные тройки похожи на четверки. Кроме того, эти два способа требуют примерно одинаковой памяти.Как и в случае простых троек, при использовании косвенных троек выделение памяти для временных значений может быть отложено на этапгенерации кода. По сравнению с четверками при использование косвенных троек можно сэкономить память, если одно и то же временное значение используется более одного раза.
Например, на рис. 8.6 можно объ-128 ГЛАВА 8. ПРОМЕЖУТОЧНОЕ ПРЕДСТАВЛЕНИЕ ПРОГРАММЫединить строки (14) и (16), после чего можно объединить строки (15) и(17).8.3Линеаризованные представленияВ качестве промежуточных представлений весьма распространены линеаризованные представления деревьев. Линеаризованное представление позволяет относительно легко хранить промежуточное представление во внешней памяти и обрабатывать его. Наиболее распространеннойформой линеаризованного представления является польская запись –префиксная (прямая) или постфиксная (обратная).Постфиксная запись – это список вершин дерева, в котором каждаявершина следует (при обходе снизу-вверх слева-направо) непосредственно за своими потомками.
Дерево на рис. 8.1, а, в постфиксной записиможет быть представлено следующим образом:a b c - * b c - * + :=В постфиксной записи вершины синтаксического дерева явно не присутствуют. Они могут быть восстановлены из порядка, в котором следуют вершины и из числа операндов соответствующих операций. Восстановление вершин аналогично вычислению выражения в постфикснойзаписи с использованием стека.В префиксной записи сначала указывается операция, а затем ее операнды. Например, для приведенного выше выражения имеем:= a + * b - c * b - cРассмотрим детальнее одну из реализаций префиксного представления – Лидер [9]. Лидер – это аббревиатура от “ЛИнеаризованное ДЕРево”.
Это машинно-независимая префиксная запись. В Лидере сохраняются все объявления и каждому из них присваивается свой уникальныйномер, который используется для ссылки на объявление. Рассмотримпример.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.Этот фрагмент имеет следующий образ в Лидере.8.3. ЛИНЕАРИЗОВАННЫЕ ПРЕДСТАВЛЕНИЯprogram ’M’var intvar intvar intprocbody 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Рассмотрим его более детально:129130 ГЛАВА 8. ПРОМЕЖУТОЧНОЕ ПРЕДСТАВЛЕНИЕ ПРОГРАММЫprogram ’M’var intvar intvar intprocbody procint int endintvar intbeginassignvar 1 7 endintint mipar 1 5 endpar 1 6 endresult 0intvar 1 7 endreturnendbeginassignvar 0 3 endinticall 0 4int var 0 1 endint var 0 2 endendend8.4Имя модуля нужно для редактора связей.Это образ переменных X, Y, Z;переменным X, Y, Z присваиваются номера1, 2, 3 на уровне 0.Объявление процедуры с двумяцелыми параметрами, возвращающей целое.Процедура получает номер 4 на уровне 0 ипараметры имеют номера 5, 6 на уровне 1.Переменная R имеет номер 7 на уровне 1.Начало тела процедуры.Оператор присваивания.Левая часть присваивания (R).Тип присваиваемого значения.Целое вычитание.Уменьшаемое (A).Вычитаемое (B).Результат процедуры уровня 0.Результат имеет целый тип.Результат – переменная R.Оператор возврата.Конец тела процедуры.Начало тела модуля.Оператор присваивания.Левая часть – переменная Z.Тип присваиваемого значения.Вызов локальной процедуры DIF.Фактические параметры Xи Y.Конец вызова.Конец тела модуля.Виртуальная машина JavaПрограммы на языке Java транслируются в специальное промежуточное представление, которое затем интерпретируется так называемой “виртуальной машиной Java”.
Виртуальная машина Java представляет собой стековую машину: она не имеет памяти прямого доступа, все операции выполняются над операндами, расположенными на верхушке стека. Чтобы, например, выполнить операцию с участием константы илипеременной, их предварительно необходимо загрузить на верхушку стека. Код операции – всегда один байт. Если операция имеет операнды,они располагаются в следующих байтах.К элементарным типам данных, с которыми работает машина, относятся short, integer, long, float, double (все знаковые).8.4. ВИРТУАЛЬНАЯ МАШИНА JAVA8.4.1131Организация памятиМашина имеет следующие регистры:pc – счетчик команд;optop – указатель вершины стека операций;frame – указатель на стек-фрейм исполняемого метода;vars – указатель на 0-ю переменную исполняемого метода.Все регистры 32-разрядные.
Стек-фрейм имеет три компоненты: локальные переменные, среду исполнения, стек операндов. Локальные переменные отсчитываются от адреса в регистре vars. Среда исполнения служит для поддержания самого стека. Она включает указатель на предыдущий фрейм, указатель на собственные локальные переменные, на базу стека операций и на верхушку стека. Кроме того, здесь же хранитсянекоторая дополнительная информация, например, для отладчика.Куча сборки мусора содержит экземпляры объектов, которые создаются и уничтожаются автоматически. Область методов содержит коды,таблицы символов и т.д.С каждым классом связана область констант. Она содержит именаполей, методов и другую подобную информацию, которая используетсяметодами.8.4.2Набор команд виртуальной машиныВиртуальная Java-машина имеет следующие команды:помещение констант на стек,помещение локальных переменных на стек,запоминание значений из стека в локальных переменных,обработка массивов,управление стеком,арифметические команды,логические команды,преобразования типов,передача управления,возврат из функции,табличный переход,обработка полей объектов,вызов метода,обработка исключительных ситуаций,прочие операции над объектами,мониторы,отладка.Рассмотрим некоторые команды подробнее.132 ГЛАВА 8.
ПРОМЕЖУТОЧНОЕ ПРЕДСТАВЛЕНИЕ ПРОГРАММЫПомещение локальных переменных на стекКоманда iload – загрузить целое из локальной переменной. Операндомявляется смещение переменной в области локальных переменных. Указываемое значение копируется на верхушку стека операций. Имеютсяаналогичные команды для помещения плавающих, двойных целых, двойных плавающих и т.д.Команда istore – сохранить целое в локальной переменной. Операндом операции является смещение переменной в области локальных переменных.
Значение с верхушки стека операций копируется в указываемую область локальных переменных. Имеются аналогичные команды для помещения плавающих, двойных целых, двойных плавающих ит.д.Вызов методаКоманда invokevirtual.При трансляции объектно-ориентированных языков программирования из-за возможности перекрытия виртуальных методов, вообще говоря, нельзя статически протранслировать вызов метода объекта. Этосвязано с тем, что если метод перекрыт в производном классе, и вызывается метод объекта-переменной, то статически неизвестно, объект какого класса (базового или производного) хранится в переменной. Поэтому с каждым объектом связывается таблица всех его виртуальных методов: для каждого метода там помещается указатель на его реализациюв соответствии с принадлежностью самого объекта классу в иерархииклассов.В языке Java различные классы могут реализовывать один и тот жеинтерфейс.
Если объявлена переменная или параметр типа интерфейс,то динамически нельзя определить объект какого класса присвоен переменной:interface I;class C1 implements I;class C2 implements I;I O;C1 O1;C2 O2;...O=O1;...O=O2;...В этой точке программы, вообще говоря, нельзя сказать, какого типазначение хранится в переменной O. Кроме того, при работе программына языке Java имеется возможность использования методов из других8.4. ВИРТУАЛЬНАЯ МАШИНА JAVA133пакетов.
Для реализации этого механизма в Java-машине используетсядинамическое связывание.Предполагается, что стек операндов содержит handle объекта или массива и некоторое количество аргументов. Операнд операции используется для конструирования индекса в области констант текущего класса. Элемент по этому индексу в области констант содержит полную сигнатуру метода. Сигнатура метода описывает типы параметров и возвращаемого значения. Из handle объекта извлекается указатель на таблицуметодов объекта. Просматривается сигнатура метода в таблице методов.Результатом этого просмотра является индекс в таблицу методов именованного класса, для которого найден указатель на блок метода. Блокметода указывает тип метода (native, synchronized и т.д.) и число аргументов, ожидаемых на стеке операндов.Если метод помечен как synchronized, запускается монитор, связанный с handle.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
