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

Так же ПолИЗу соответствует так называемое дерево ПолИЗа.

Пример:(x+a)*(x-b)+3;

Дерево:

xa xb

ПолИЗ: 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’).

ПолИЗ: 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] * -.

Изобразим дерево выражения: (смотри рисунок )

-

А.Э.М. *

а + А.Э.М. А.Э.М.

i1 b i– a +

i j * 1

2i

Следовательно, алгоритм Дейкстры дополнится следующими правилами:

ПРАВИЛА:

[, имея приоритет 0 заносится в СТЕК [k, где k – минимальное число операндов операции А.Э.М.

, , имея приоритет 1 выталкивает из СТЕКа все ближайшие знаки до ближайшей [k и увеличивает k на 1: k=k+1; , никуда не заносится.

], имея приоритет 1 выталкивает из СТЕКа все знаки до ближайшей [k, которая удаляется из СТЕКа, а в ПолИЗ заносится k].

4.3.4.3. Алгоритм перевода ПолИЗа в машинные команды

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

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

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

Рассмотрим пример: a+b*c-d/(a+b)

ПолИЗ: abc*+dab+/-

Выполнение правила для нашего примера приводит к последовательности строк, записанных во второй графе таблицы № 2 (смотрите следующую страницу). Рассматриваемый на каждом шаге процесса элемент строки отмечен курсивом. В третьей графе таблицы записаны соответствующие действия, а в четвертой графе – эквивалентные команды трехадресной машины.