Интерпретация блок-схем

Результат выполнения операции фиксируется в виде рабочей переменной вида rj . После очередной операции рабочая переменная r1 или r2 вычеркивается, освободившуюся рабочую переменную можно использовать вновь для записи результата операции. Использование каждый раз свободной рабочей переменной с минимальным номером экономит количество занятых рабочих переменных. Такой пример экономии рабочих ячеек приведен в таблице № 2. Это же правило используют в трансляторах.

Аналогичным способом можно записывать и вычислять булевские выражения.

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

Таблица № 2

Состояние строки

Действие

Машинная команда

1

2

3

4

1

a bc*+dab+/-

Просмотреть следующий элемент

-

2

a b c*+dab+/-

Просмотреть следующий элемент

-

3

ab c *+dab+/-

Просмотреть следующий элемент

-

4

abc * +dab+/-

r1=b*c

* b c r1

5

ar1+dab+/-

r1=a+ r1

+ a r1 r1

6

r1 d ab+/-

Просмотреть следующий элемент

-

7

r1d a b+/-

Просмотреть следующий элемент

-

8

r1da b +/-

Просмотреть следующий элемент

-

9

r1dab + /-

r2=a+b

+ a b r2

10

r1dr2/ -

r2= d/r2

/ d r2 r2

11

r1 r2 -

r1 =r1 –r2

- r1 r2 r1

12

rl

-

-

лишь заменить знаки операций машинными кодами операций, а операнды – адресами. Пример показывает, что в данном случае трансляция выполняется достаточно просто. Однако правило вычисления значения выражения по ПолИЗу, которое можно считать одновременно правилом трансляции выражения в машинные команды, недостаточно детализировано и формализовано для непосредственной реализацией на машине, хотя бы потому, что в нем не определен способ записи выражения в памяти машины и порядок использования рабочих ячеек. Для машинной реализации требуется более формальное правило.

В рассмотренном примере встречались двухместные операции. Каждая такая операция, как правило, заменяется одной или двумя машинными командами (в зависимости от адресации машины). В общем случае операция R может иметь k операндов (k(1). На ЭВМ такая операция должна заменяться группой машинных команд. Будем считать, что к моменту генерирования машинных команд проведено распределение памяти, и каждый операнд представлен соответствующей ссылкой на таблицу имен, содержащую адрес операнда. Аналогично, для каждой рабочей переменной известен ее адрес.

Для трансляции выражений из обратной польской записи в машинные команды используется стек операндов(СО) с указателем i. В исходном состоянии стек операндов пуст, а указатель i=1. Будем также считать, что в исходном состоянии номер первой свободной рабочей переменной j=1.

Алгоритм трансляции состоит в следующем.

1. Взять очередной символ S из обратной польской записи выражения.

2. Если S – операнд, то занести S в СО[i] , выполнить i=i+1 и перейти к пункту 1, иначе к пункту 3.

3. Если S – не знак операции, то перейти к пункту 4, иначе, если S – знак операции R, выполнить следующее

Среди элементов стека СО[i-k], где k – число операндов операции R, найти рабочую переменную с минимальным номером l. Если в рассматриваемых элементах стека нет рабочих переменных, то положить l=j.

Записать машинные команды, реализующие оператор присваивания rl=R(СО[i-k],…,СО[i-1]). Здесь R(x1, … , xk) – результат выполнения операции R над операндами x1, … , xk.

Занести символ rl в СО[i-k].

Выполнить: i=i-k+1 и j=l+1. Перейти к пункту 1.

Если запись выражения исчерпана, то трансляция закончена. Стек операндов должен содержать только переменную rl, в противном случае нужно записать информацию об ошибке в таблицу ошибок.

Вход

Рис.4. Блок-схема перевода обратной польской записи в машинные команды.

Для реализации пункта 3.2. приведенного алгоритма используются заранее подготовленные заготовки групп машинных команд, в которые требуется лишь подставить адреса операндов, взятые из стека операндов. Эту подстановку выполняет подпрограмма, соответствующая рассматриваемой операции R.