Интерпретация блок-схем
Результат выполнения операции фиксируется в виде рабочей переменной вида 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.