6.2. Генерация команд для присваиваний и арифметических выражений

Рассмотрим генерацию машинной программы для простейшей системы команд – одноадресной.

Пример 20. Определим модель процессора. Пусть в нем имеется специальный регистр (регистр сумматора, или просто сумматор), который участвует при выполнении каждой команды. В этом регистре может быть записано числовое значение. Каждая команда будет иметь следующий вид:

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

При этом одним из операндов всегда является сумматор, другим – операнд, записанный в команде. Результат выполнения операции (если он будет вычислен) всегда находится в сумматоре. Операнд в команде на самом деле представляет собой номер ячейки памяти, где находится операнд (переменная или константа). Команды будем записывать для наглядности в символьном виде, как код операции, так и номер ячейки памяти.

Набор команд, достаточный для реализации четырех арифметических действий, будет таким:

Add <операнд> – сложение содержимого сумматора с содержимым

операнда;

Sub <операнд> – вычитание из содержимого сумматора содержимого

операнда;

Mul <операнд> – умножение содержимого сумматора на содержимое

операнда;

Div <операнд> – деление содержимого сумматора на содержимое

операнда;

Load <операнд> – запись содержимого операнда в сумматор;

St <операнд> – запись содержимого сумматора в операнд.

Генератор команд по заданной ОПС можно реализовать в виде интерпретатора, использующего магазин. В магазин записываются операнды (номера ячеек памяти), в которых находятся значения переменных и результаты вычислений. Если результат выполнения некоторой команды находится в сумматоре, то в магазин записывается нуль. Кроме того, в генераторе имеется вспомогательная переменная k, которая напрямую ссылается на тот элемент магазина, который содержит нуль.

Принцип работы генератора команд следующий. ОПС просматривается слева направо. Если очередной элемент в ОПС – операнд, то он записывается в магазин. Если очередной элемент в ОПС – операция, то из магазина считываются операнды для этой операции, после чего генерируются команды, выполняющие данную операцию. Если результат операции находится в сумматоре, то в магазин записывается нуль, а в переменную k – ссылка на верхний элемент магазина. Обозначим два верхних операнда в магазине как a и b. Генерируемые команды зависят не только от операции ОПС, но и от содержимого k, a и b. Перед работой генератора команд k := 0, магазин пуст.

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

Load a

Op b

где Op – команда Add, Sub, Mul или Div, в зависимости от операции. После этого в магазин записывается нуль, а в переменную k – ссылка на верхний элемент магазина.

2. Если k ≠ 0, a = 0, то генерируется команда:

Op b

где Op – команда Add, Sub, Mul или Div, в зависимости от операции. После этого в магазин записывается нуль, а в переменную k – ссылка на верхний элемент магазина.

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

Op b

где Op – команда Add или Mul, в зависимости от операции, или команды:

St t

Load a

Op t

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

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

St t

Load a

Op b

где Op – команда Add, Sub, Mul или Div, в зависимости от операции, t – дополнительная временная переменная. После этого в магазин записывается нуль, в элемент магазина с номером k записывается t, после чего в переменную k – ссылка на верхний элемент магазина.

5. Для операции :=.

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

Load b

St a

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

St t

Load b

St a

где t – дополнительная временная переменная. При этом в элемент магазина с номером k записывается t.

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

St a

После этого переменной k присваивается нуль, в магазин ничего не записывается.

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

x a b – c d e / + * :=

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

x := (a – b)*(c + d / e)

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

Операция – , k = 0, в магазине:

x

a

b

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

Sub b

k := 2

Операция / , k = 2, в магазине:

x

0

c

d

e

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

Load d

Div e

2-я ячейка магазина := t, k := 4

Операция + , k = 4, в магазине:

x

t

c

0

генерируемая команда: Add c

k := 3

Операция * , k = 3, в магазине:

x

t

0

генерируемая команда: Mul t

k := 2

Операция := , k = 2, в магазине:

x

0

генерируемая команда: St x

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

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

Load a

Sub b

St t

Load d

Div e

Add c

Mul t

St x

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

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

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