Интерпретация блок-схем (стр. 8 из 18)
ПолИЗ: x a + x b - * 3 +.
Построение ПолИЗа по дереву осуществляется обходом дерева по правилу левое поддерево, правое поддерево, корень.
4.3.4.2. ПолИЗ выражений, содержащих переменные синтаксиса
Кроме операций сложения и умножения любая программа содержит операции вычисляющие адреса элементов массива в зависимости от индексных выражений. Например:
a[i+1]-b[i,j-1]*a[2*i+1]
 |  |
 |
Индексные выражения.
Выведем формулы вычисления адресов элементов массива.
Для одномерного массива а, описание которого на Паскале и Си имеет вид:
a: array [1..n] of integer; // Pascal
int a[n]; // C/C++
и каждый элемент имеет массива занимает k-байт.
Адрес первого элемента равен A . Выясним чему будут равны адреса других элементов. Для этого рассмотрим расположение элементов массива в физической памяти ЭВМ.
A +k +2k +3k A+k*(i-1)…k байт
тогда a[i] А+k*(i-1) для языка программирования Паскаль, а для языка программирования C/C++ a[i] A+k*i. Тогда если элемент занимает k – байт, тоa[i] -----> A+k*(i-1) (1)
a[i] -----> A+k*i (1’)
Для двумерного массива:
b: array [1..m,1..n] of integer;// Pascal
int b[m][n];//Си
Адрес элемента с индексами i,j вычисляется по правилу:
b[i,j] -----> B+k*((i-1)*n+(j-1)) (2)
b[i,j] -----> B+k*(i*n+j) (2’)
Для формирования ПолИЗа введем операцию АЭМ (адрес элемента массива) с операндами:
1. Идентификатор массива, ему после распределения памяти транслятором будет соответствовать адрес первого элемента массива.
2. Индексное выражение.
Результат: адрес элемента массива вычисленный по формулам (1)-(2’).
ПолИЗ: a i 1 + А.Э.М. b i j 1 – А.Э.М. a 2 i * 1 + А.Э.М. * -
Анализ ПолИЗа говорит о том, что у операции АЭМ переменное число операндов и их количество надо задавать явно. Сделаем следующую замену: АЭМ – k], где k - количество операндов.
Тогда ПолИЗ: a i j + 2] b i j 1 – 3] a 2 i * 1 + 2] * -.
Изобразим дерево выражения: (смотри рисунок )
-  |  |
А.Э.М. *
 |  |  |  |
а + А.Э.М. А.Э.М.  |  |  |  |  |
i 1 b i – a +
 |  | |  |
i j * 1
 | |
2 i
Следовательно, алгоритм Дейкстры дополнится следующими правилами:
ПРАВИЛА:
1. [, имея приоритет 0 заносится в СТЕК [k, где k – минимальное число операндов операции А.Э.М.
2. , , имея приоритет 1 выталкивает из СТЕКа все ближайшие знаки до ближайшей [k и увеличивает k на 1: k=k+1; , никуда не заносится.
3. ], имея приоритет 1 выталкивает из СТЕКа все знаки до ближайшей [k, которая удаляется из СТЕКа, а в ПолИЗ заносится k].
4.3.4.3. Алгоритм перевода ПолИЗа в машинные команды
Известно, что в обратной польской записи операнды располагаются в том же порядке, что и в исходном выражении, а знаки операций при просмотре записи слева направо встречаются в том порядке, в котором нужно выполнять соответствующие действия. Отсюда вытекает основное преимущество обратной польской записи перед обычной записью выражений со скобками: выражение можно вычислить в процессе однократного просмотра слева направо.
Правило вычисления выражения в обратной польской записи состоит в следующем. Обратная польская запись просматривается слева направо. Если рассматриваемый элемент – операнд, то рассматривается следующий элемент. Если рассматриваемый элемент – знак операции, то выполняется эта операция над операндами, записанными левее знака операции. Результат операции записывается вместо первого (самого левого) операнда, участвовавшего в операции. Остальные элементы (операнды и знак операции), участвовавшие в операции, вычеркиваются из записи. Просмотр продолжается.
В результате последовательного выполнения этого правила будут выполнены все операции, имеющиеся в выражении, и запись сократится до одного элемента – результата вычисления выражения.
Рассмотрим пример: a+b*c-d/(a+b)
ПолИЗ: abc*+dab+/-
Выполнение правила для нашего примера приводит к последовательности строк, записанных во второй графе таблицы № 2 (смотрите следующую страницу). Рассматриваемый на каждом шаге процесса элемент строки отмечен курсивом. В третьей графе таблицы записаны соответствующие действия, а в четвертой графе – эквивалентные команды трехадресной машины.
Результат выполнения операции фиксируется в виде рабочей переменной вида 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 | - | - |
лишь заменить знаки операций машинными кодами операций, а операнды – адресами. Пример показывает, что в данном случае трансляция выполняется достаточно просто. Однако правило вычисления значения выражения по ПолИЗу, которое можно считать одновременно правилом трансляции выражения в машинные команды, недостаточно детализировано и формализовано для непосредственной реализацией на машине, хотя бы потому, что в нем не определен способ записи выражения в памяти машины и порядок использования рабочих ячеек. Для машинной реализации требуется более формальное правило.