Генерация команд с индексными выражениями

Вначале рассмотрим генерацию команд, реализующих операцию выделения памяти для динамических массивов.

Пример 21. Пусть, кроме рассмотренных команд, в процессоре имеется команда прерывания, которая передает управление в особую область оперативной памяти, где располагается операционная система. Пусть также, кроме регистра сумматора, имеется еще один регистр, называемый регистром адреса. Формат команды прерывания:

Itr <номер прерывания>

Вместо операнда в команде записан код – номер прерывания. Эта команда передает управление в операционную систему, причем в ту ее область, которая определяется номером прерывания. Кроме того, при этом в регистре адреса запоминается адрес команды, которая расположена следом за командой прерывания. Это необходимо для того, чтобы после обработки прерывания операционная система вернула управление в программу. Перед тем, как выполнить команду прерывания, необходимо, чтобы в регистр сумматора был записан параметр, смысл которого определяется номером прерывания. Так, для прерывания, требующего выделение памяти, в регистре сумматора должен быть записан размер области в байтах, а после обработки прерывания и возврата в программу – в регистре сумматора будет находиться адрес начала выделенной области памяти.

Рассмотрим генерацию команд, реализующей операцию выделения памяти для одномерного массива. Пусть имеется ОПС:

M n <m1>

где M – ссылка на таблицу, содержащую описание массива M, а n – количество элементов. Паспорт массива должен содержать:

M1 – адрес нулевого элемента массива;

d – длину одного элемента массива;

n1 – количество элементов массива.

Все эти три части паспорта располагаются в памяти подряд, и тогда вместо d надо писать операнд в команде M1 + v, а вместо n1 – M1 + 2v, где v – длина в байтах целого значения.

При работе генератора команд в магазин будут последовательно записаны M и n, после чего будет интерпретироваться операция <m1>. В результате будут генерироваться команды:

Load n

St M1 + 2v

Mul <длина элемента>

Itr <выделение памяти>

St M1

Load <длина элемента>

St M1 + v

Операнд <длина элемента> – константа, определяемая типом таблицы, содержащей описание массива M.

Аналогично, ОПС с операцией выделения памяти для двумерного массива:

M n m <m2>

где M – ссылка на таблицу с описанием массива M, а n, m – количество строк и столбцов в массиве. Паспорт двумерного массива содержит:

M2 – адрес нулевого элемента массива;

d – длина одного элемента массива (M1 + v);

n1 – количество строк в массиве (M1 + 2v);

n2 – количество столбцов в массиве (M1 + 3v).

При работе генератора команд будет создана последовательность:

Load n

St M2 + 2v

Mul m

Mul <длина элемента>

Itr <выделение памяти>

St M2

Load <длина элемента>

St M1 + v

Load m

St M1 + 3v

Конец примера.

А теперь рассмотрим генерацию команд, реализующих операцию индексирования.

Пример 22. Расширим модель процессора. Пусть в командах, кроме кода операции и операнда, записывается признак косвенной адресации, который может быть нулем или единицей:

<код операции> <признак> <операнд>

Если этот признак равен 0, то команда выполняется обычным образом, а если 1, то используется косвенная адресация, когда операнд в команде – это адрес в памяти, где находится адрес, ссылающийся на другую ячейку памяти, содержащую значение операнда.

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

Правила генерации команд, реализующих операцию <i1>, следующие. Обозначим два верхних операнда в магазине как a и b. В переменной k находится ссылка на элемент магазина, содержащий 0. Операнд а содержит ссылку на паспорт массива, b – индекс элемента массива. В командах используются t1, t2 – дополнительные временные переменные.

Если b = 0, то генерируются команды:

Mul 0 a + v

Add 0 a

St 0 t1

Если b ≠ 0, k = 0, то генерируются команды:

Load 0 b

Mul 0 a + v

Add 0 a

St 0 t1

В обоих случаях после генерации команд в магазин записывается t1 и признак для нее 1, а в переменную k – нуль.

Если b ≠ 0, k ≠ 0, то генерируются команды:

St 0 t1

Load 0 b

Mul 0 a + v

Add 0 a

St 0 t2

После генерации команд в элемент магазина по ссылке k записывается t1, в верхний элемент магазина записывается t2 и признак для него 1, а в переменную k – нуль.

А теперь рассмотрим правила генерации команд, реализующих операцию <i2>. Обозначим три верхних операнда в магазине как a, b и c. В переменной k находится ссылка на элемент магазина, содержащий 0. Операнд а содержит ссылку на паспорт массива, b – 1-й индекс элемента массива, c – 2-й индекс элемента массива. В командах используются t1, t2 – дополнительные временные переменные.

Если b = 0, то генерируются команды:

Mul 0 a + 3v

Add 0 c

Mul 0 a + v

Add 0 a

St 0 t1

Если c = 0, то генерируются команды:

St 0 t1

Load 0 b

Mul 0 a + 3v

Add 0 t1

Mul 0 a + v

Add 0 a

St 0 t1

Если b ≠ 0, c ≠ 0, k = 0, то генерируются команды:

Load 0 b

Mul 0 a + 3v

Add 0 c

Mul 0 a + v

Add 0 a

St 0 t1

Во всех случаях после генерации команд в магазин записывается t1 и признак для нее 1, а в переменную k – нуль.

Если b ≠ 0, c ≠ 0, k ≠ 0, то генерируются команды:

St 0 t1

Load 0 b

Mul 0 a + 3v

Add 0 с

Mul 0 a + v

Add 0 a

St 0 t2

После генерации команд в элемент магазина по ссылке k записывается t1, в верхний элемент магазина записывается t2 и признак для него 1, а в переменную k – нуль.

Рассмотрим пример генерации команд. Пусть задана ОПС:

M i j a + <i2> L i d – <i1> :=

что соответствует оператору:

M[i, j + a] := L[i – d]

Шаги работы генератора команд будут такими (пропущены действия по записи в магазин операндов):

генерируемые команды: Load 0 j

Add 0 a

k := 3

генерируемые команды: St 0 t1

Load 0 i

Mul 0 M + 3v

Add 0 t1

Mul 0 M + v

Add 0 M

St 0 t1

k := 0

генерируемые команды: Load 0 i

Sub 0 d

k := 3

генерируемые команды: Mul 0 L + v

Add 0 L

St 0 t2

k := 0

генерируемые команды: Load 1 t2

St 1 t1

k := 0, магазин пуст.

В результате получится такая программа:

Load 0 j

Add 0 a

St 0 t1

Load 0 i

Mul 0 M + 3v

Add 0 t1

Mul 0 M + v

Add 0 M

St 0 t1

Load 0 i

Sub 0 d

Mul 0 L + v

Add 0 L

St 0 t2

Load 1 t2

St 1 t1

Конец примера.

Замечания.

1. По аналогии с рассмотренными примерами реализации операций индексации одно и двумерных массивов можно реализовать индексацию массивов большей размерности.

2. Перед вычислением величины смещения относительно адреса нулевого элемента массива, для безопасности, желательно генерировать также команды проверки того, что индекс неотрицателен и меньше количества элементов по соответствующему измерению. И если такая проверка даст отрицательный результат, то нужно предусмотреть команду прерывания, которая бы передала в операционную систему признак ошибки «неверный индекс», так как при этом дальнейшее исполнение программы невозможно.

Дата добавления: 2015-07-26; просмотров: 118; Нарушение авторских прав

Мы поможем в написании ваших работ!