Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 17
Текст из файла (страница 17)
Лидер - это аббревиатура от 'ЛИнеаризованное ДЕРево'. Этомашинно-независимая языково-ориентированная префиксная запись. Вэтом представлении сохраняются все объявления и каждому из нихприсваивается свой уникальный номер, который используется для ссылкина объявление. Рассмотрим пример (рис. 7.7).module M;var X,Y,Z: integer;procedure DIF(A,B:integer):integer;var R:integer;106begin R:=A-B;return(R);end DIF;begin Z:=DIF(X,Y);end M.Рис. 7.7Соответствующий образ в Лидере изображен на рис.
7.8.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Рис. 7.8Рассмотрим его более детально:program 'M'Имя модуля используется для редакторасвязейvar intЭто образ переменных var X,Y,Z:integer;var intпеременным X,Y,Z присваиваются номераvar int1,2,3 на уровне 0procbody proc Объявление процедуры с двумяint int endцелыми параметрами, возвращающей целое.intПроцедура получает номер 4 на уровне 0 ипараметры имеют номера 5, 6 на уровне 1.var intЛокальная переменная R имеет номер 7на уровне 1beginНачало тела процедурыassignОператор присваиванияvar 1 7 endЛевая часть присваивания (R)intТип присваиваемого значенияint miЦелое вычитаниеpar 1 5 endУменьшаемое (A)107par 1 6 endВычитаемое (B)result 0Результат процедуры уровня 0intРезультат имеет тип целыйvar 1 7 endРезультат - переменная RreturnОператор возвратаendКонец тела процедурыbeginНачало тела модуляassignОператор присваиванияvar 0 3 endЛевая часть - переменная ZintТип присваиваемого значенияicall 0 4Вызов локальной процедуры DIFint var 0 1 end Фактические параметры X и Yint var 0 2 endendКонец вызоваendКонец тела модуля1087.4.
Виртуальная машина JavaПрограммы на языке Java транслируются в специальноепромежуточное представление, которое затем интерпретируется такназываемой “Виртуальной машиной Java”. Виртуальная машина Javaпредставляет собой стековую машину: она не имеет памяти прямогодоступа, все операции выполняются над операндами, расположенными наверхушке стека. Чтобы, например, выполнить операцию с участиемкостанты или переменной, их предварительно необходимо загрузить наверхушку стека. Код операции - всегда один байт. Если операция имеетоперанды, они располагаются в следующих байтах.Элементарные типы данных, с которыми работает машина, - short,integer, long, float, double, все знаковые.7.4.1. Организация памятиМашина имеет следующие регистры:pc - счетчик команд;optop - указатель вершины стека операций;frame - указатель на стэк-фрейм исполняемого метода;vars - указатель на 0-ю переменную исполняемого метода.Все регистры 32 разрядные.
Других регистров нет.Стэк-фрейм имеет три компоненты:локальные переменные,среда исполнения,стэк операндов.Локальные переменные отсчитываются от регистра vars.Среда исполнения служит для поддержания самого стэка. Онавключает указатель на предыдущий фрейм, указатель на собственныелокальные переменные, на базу стека операций и на верхушку стека.Кроме того, здесь же хранится некоторая дополнительная информация,например, для отладчика.Куча сборки мусора содержит экземпляры объектов, которыесоздаются и уничтожаются автоматически.Область методов содержит коды, таблицы символов и т.д.С каждым классом связана область констант.
Она содержит именаполей, методов и другую подобную информацию, которая исползуетсяметодами.7.4.2. Набор команд виртуальной машиныПомещение констант на стек.Помещение локальных переменных на стек.Запоминание значений из стека в локальных переменных.Обработка массивов.Управление стеком.109Арифметические команды.Логические команды.Преобразования типов.Передачи управления.Возврат из функции.Табличный переход.Обработка полей объектов.Вызов метода.Обработка исключительных ситуаций.Прочие операции над объектами.Мониторы.Отладка.Рассмотрим некоторые группы команд подробнее.Помещение локальных переменных на стек.iload - загрузить целое из локальной переменной.Операндом операции является смещение переменной в областилокальных переменных. Указываемое значение копируется на верхушкустека операций.Имеются аналогичные команды для помещения плавающих,двойных целых, двойных плавающих и т.д.istore - сохранить целое в локальной переменной.Операндом операции является смещение переменной в областилокальных переменных.
Значение с верхушки стека операций копируется вуказываемую область локальных переменных.Имеются аналогичные команды для помещения плавающих,двойных целых, двойных плавающих и т.д.Вызов методаinvokevirtualПритрансляцииобъектноориентированныхязыковпрограммирования из-за возможности перекрытия виртуальных методоввообще говоря статически нельзя протранслировать вызов метода объекта,Это связано с тем, что если метод перекрыт в производном классе, ивызывается метод объекта-переменной, то статически неизвестно, объекткакого класса (базового или производного) хранится в переменной.Поэтому с каждым объектом связывается таблица всех его виртуальныхметодов: для каждого метода там помещается указатель на его реализациюв соответствии с принадлежностью самого объекта классу в иерархииклассов.В языке Java различные классы могут реализовывать один и тот жеинтерфейс.
Если объявлена переменная или параметр типа интерфейс, то110динамическипеременной:нельзяопределитьобъекткакогоклассаприсвоен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 и первые локальные переменные нового фрейма параметрамивызова. Определяется общее число локальных переменных, используемыхметодом, и после того, как отводится необходимое место для локальныхпеременных, окружение исполнения нового фрейма помещается на стек.База стека операндов для этого вызова метода устанавливается на первоеслово после окружения исполнения.
Наконец исполнение продолжается спервой инструкции вызванного метода.111Обработка исключительных ситуацийathrow (возбудить исключительную ситуацию)С каждым методом связан список операторов catch. Каждыйоператор catch описывает диапазон инструкций, для которых он активен,тип исключения, который он обрабатывет, и с ним связан наборинструкций, которые его реализуют. При возникновении исключительнойситуации просматривается список операторов catch, чтобы установитьсоответствие. Исключительная ситуация соответствует оператору catch,если инструкция, вызавшая исключительную ситуацию, лежит всоответствующем диапазоне и исключительная ситуация принадлежитподтипу типа ситуации, которые обарабатывает оператор catch.
Еслисоответствующий оператор catch найден, управление передаетсяобработчику. Если нет, текущий стэк-фрейм удаляется, и и сключительнаяситуация возбуждается вновь.Порядок операторов catch в списке важен. Интерпретатор передаютуправление первому подходящему оператору catch.7.5. Организация информации в генераторе кодаЧисто синтаксическое дерево несет только информацию о структурепрограммы. На самом деле в процессе генерации кода требуется такжеинформация о переменных (например, их адреса), процедурах (такжеадреса, уровни), метках и т.д. Для представления этой информациивозможны различные решения. Наиболее распространены два. 1) всю этуинформацию можно хранить в таблицах генератора кода; 2) информацияхранится в вершинах дерева с соответствующими указателями.Рассмотрим, например, структуру таблиц, которые могут бытьиспользованы в сочетании с Лидер-представлением.
Поскольку Лидерпредставление не содержит информации об адресах переменных, значит,эту информацию нужно формировать в процессе обработки объявлений ихранить в таблицах. Это касается и описаний массивов, записей и т.д.Кроме того, в таблицах также должна содержаться информация опроцедурах (адреса, уровни, модули, в которых процедуры описаны, ит.д.). Таким образом структура таблиц может быть такой, как этоизображено на рис. 7.9.112Таблица уровнейпроцедурТаблица описанийДля типа:размерДля переменной:указатель натип и адрес (смещение)Для процедуры: адрес,................................Рис.
7.9При входе в процедуру в таблице уровней процедур заводится новыйвход - указатель на таблицу описаний. При выходе указательвосстанавливается на старое значение. Если промежуточное представление- дерево, то информация может храниться в вершинах самого дерева.Например, та же информация может быть представлена, как на рис. 7.10.Раздел описанийОписаниетипаОписаниепеременнойРазделоператоровРис. 7.107.6. Уровень промежуточного представленияКак видно из приведенных примеров, промежуточное представлениепрограммы может в различной степени быть близким либо к исходнойпрограмме, либо к машине.
Например, промежуточное представлениеможет содержать адреса переменных, и тогда оно уже не может быть113перенесено на другую машину. С другой стороны, промежуточноепредставление может содержать раздел описаний программы, и тогдаинформацию об адресах можно извлечь из обработки описаний. В то жевремя ясно, что первое более эффективно, чем второе. Операторыуправления в промежуточном представлении могут быть представлены висходном виде (в виде операторов языка if, for, while и т.д.), а могутсодержаться в виде переходов. В первом случае некоторая информацияможет быть извлечена из самой структуры (например, для оператора for информация о переменной цикла, которую, может быть, разумно хранитьна регистре, для оператора case - информация о таблице меток и т.д.).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
