Бауэр Ф.Л., Гооз Г. Информатика. Том 1

Подождите немного. Документ загружается.

3.7. Декомпозиция формул

26!

магазинных. Такое незначительное видоизменение потребует

„загрузки" в магазин всех величин, входящих в формулу,— в

порядке их появления слева направо. В результате получим

формулировку, представленную на рис. 137 (справа — вариант

ГА[1]:=я;

А[2]:=6;

A[l];=A[l]xA[2];

А[2]:=а;

A[2]:=A[2I+A[3]J

A[2J:=A[2IxA[3]j

A[1]:-A[1]+A[2J5

A[2J>a;

Гсо/=0

со

li- lJ:=Ap-1] x

АИ;

/:-«-1;

Ap-l]:=Ap—Ц+AMs

i:=/-l;

AP-1J:-AP-JJ+AM;

/Vi-f;

h [i -f*

]

;«=

о t

11^

~t*

Ар~1]:-Л[/-11хЛЮ;

/:=/-!;

Ap-lJ:=Ap~l]/A[/J;

/:=i-l;

со<

со ЛИ -1

Рис.

137.

с изменением указателя верхушки, слева — без изменения этого

указателя).

Встречающиеся здесь присваивания вида

AM :=МЛ У h[k],

где 7 — какая-то из двуместных основных операций, называют-

ся

трёхадресными

командами;

(относительные) адреса /, k —

это

адреса

операндов,

i —

адрес

результата.

Вместе с

двухадресными

командами

вида

h\i] :=ст Л[/],

где а — одноместная основная операция, а также

командами

засылки

вида

h[i] := >значение<

трёхадресные команды образуют костяк ассортимента основных

команд многих машин и появляются поэтому в соответствую-

щих языках ассемблера. Однако при работе по принципу ма-

газина

двух-

и трёхадресные команды встречаются только в

форме

h[i] :=a h[i] и

h[i—\\

:=h[i—

1] 7 А [О

262 Гл. 3. Машинно-ориентированные алгоритмические языки

соответственно,

которой один

из

адресов операндов совпа-

дает

адресом результата,

адрес

другого

операнда получается

как

следующий адрес.

Трёхадресную форму можно получить

непосредственно

из

дерева Канторовича

(см. рис. 136);

проще всего

это

сделать.

Рис.

138. Дерево Канторовича для формулы (а X b +(а + d)X с)/(а + Ь X 6)

указанием порядка

обхода.

записав рассматриваемую формулу

постфиксной форме (обра-

щенная

функциональная запись):

(((a,b)f

((a,d)f

,c)f

(a,(b,b)f

или,

без

скобок',

+ + bb+ \.

Если каждому знаку операнда сопоставить соответствующую

команду засылки,

каждому знаку операции

—

соответствую-

щую

трёхадресную

команду,

то

(бесскобочная) польская инверс-

ная

запись перейдёт

в ту

приведённую выше последователь-

ность команд, которая была получена

при

декомпозиции

формулы

соответствии

принципом магазина. Перевод

в (бес-

скобочную) польскую инверсную запись

декомпозиция

фор-

мулы

соответствии

принципом магазина оказываются

экви-

валентными

Таким образом, алгоритмический метод перевода дерева

Канторовича

польскую инверсную запись основан

на

следую-

Бесскобочная префиксная запись, называемая также „варшавской

нормальной формой"

или

„польской записью" (англ.: polish notation), была

введена

школе польского логика Лукасевича около

1925 г.

Приведённая

здесь бесскобочная постфиксная запись называется

польской инверсной

записью

(ПОЛИЗ).

Ангстль и Бауэр (1950 г.). Этот принцип был реализован в вычисли»

теле формул Stanislaus.

3.7. Декомпозиция формул 263

щем рекурсивном способе

обхода

дерева

в так называемом

концевом

порядке

(англ.: post-order):

Назовём дерево Канторовича

атомарным,

если оно состоит

из

одного-едипственного знака операнда. Польская инверсная

запись неатомарного дерева Канторовича получается последо-

вательным выписыванием слева направо польских инверсных

записей

всех

его поддеревьев с последующим выписыванием

знака

операции, указанного в корне дерева. Польской инверс-

ной

записью атомарного дерева Канторовича является знак

операнда.

В нашем примере все операции двуместны, так что дерево

Канторовича — бинарное; концевой порядок отвечает такой по-

следовательности прохождения:

левое поддерево — правое поддерево — корень.

На

рис. 138 показан ход исполнения алгоритма для нашего

примера.

3.7.4.

Перевод

одноадресную

форму

В большинстве машин для основных операций предусмот-

рено не три адреса, а всего лишь один; для операций, в которых

один из адресов операндов совпадает с адресом результата,

используется специальная переменная АС (называемая

сумма-

тором

которая и выступает в качестве соответствующего

операнда, например

АС := AC-f a.

Стандартное обозначение АС, как указывает уже сам выбор

шрифта для него, только для этих целей и

будет

использовать-

ся.

При этом мы

будем

далее считать, что речь идёт о пере-

менных какого-то вполне определенного сорта; строго говоря,

следует

различать сумматоры

rea

Для вычислений над веще-

ственными числами, АС^для целочисленных вычислений и т. д.

Таким образом,

одноадресные

команды

для двуместных

операций имеют такой вид:

АС:= АС у h[i];

сюда же относятся команды для одноместных операций

АС:=<тАС,

команды засылки в сумматор

АС : = >значение<

и АС : = h [i],

Соответствующий английский термин — accumulator. Отсюда обозначе-

ние

АС. —

Прим.

перев.

В некоторых машинах нет команд типа АС:— >значение< и АС: =

АС у )значение< с явным указанием объекта в команде.

264

Гл.

Машинно-ориентированные алгоритмические языки

а также специальная команда обращения к памяти, называе-

мая „присваиванием из сумматора",

Л [»]:= АС.

Результат,

вырабатываемый формулой, попадает теперь в АС.

Перевод декомпозированной формы (см.

3.7.2)

в одноадресную

АС:*

АСх Ъ

МП

:=AQ

АС:=

АС;«

AC + d

АС:*

АСх

АС:=

МП

tAC

МП

>АС

АС:=

h[2)

:=АС

АС:=

AC;«ACxi

АС:=

ftUl

+АС

АС!=

ЛП]

/АС

АС:=

Рис.

139.

Получение одноадресной формы исходя

из

дерева Канторовича.

можно осуществить чисто механически, заменяя каждое оди-

ночное присваивание а := bye на последовательность одно-

адресных команд

АС:=Ь;

АС := АС у с; а := АС.

Правда, иногда при этом появляются излишние команды, кото-

рые можно вычеркнуть. Скажем, в

случае

примера, рассматри-

ваемого в

3.7.2,

мы получаем

(*)

ГАС:=д;

АС:=АСх6;

Л1Ц:=АС;

АС:=а

;

AC:=AC+rf;

ЛГ*-ЛС;

ACi*#p]

;

АС;=АСхс;

А[2]:=АС;

АС:=А[1]; АС:=АС+А[2]; А[1]:=АС;

"T""""l"r"""V]"C'3

АС:=а;

AC:AC+A[2];!*l2]^AC

AC"-Aif]";~AC"-АС/АЙ;"

А[1]:=

АС;

МП

Последовательность п[2] :— АС; АС:=/г[2] является излиш-

ней,

и её можно вычеркнуть. Можно также заменить на АС

заключительную последовательность h[l) := AC; h[\].

Однако этот способ получения одноадресной формы — всё же

окольный путь. Более простой способ состоит в том, чтобы за-

писать дерево Канторовича для заданной формулы (см. рис. 136

137) в одну строку (рис. 139) в соответствии с принципом ма-

газина („в топологическом порядке"), а затем „прочитать"

одноадресные операции.

3.7. Декомпозиция формул 265

результате

получим

ГАС;-д; AC:=ACxftj А[1]:=АС;

ACi-a;

AC:=

АС:=М1]

+ АС; Л[»]:=АС;

(**) !

АС^ЙГ

А"И;=АС"П

j AC:-fc; АС:=АСх6,- |

* AC:-

[2]

+ АС; ]

AC J

Некоторое упрощение по сравнению с (*) объясняется тем, что

здесь наряду с командами

АС: = АС у h [i]

употребляются также

обращенные

команды

\C;=h[i]

vAC.

Так,

фигурирующая в конце (*) последовательность команд

А [2] :=АС; АС:=А[1]; АС:=АС//г[2]

заменена на

AC:=/i[l]/AC.'

Конечно,

для коммутативных двуместных операций обра-

щенная

форма команды не нужна. Поскольку сложение комму-

тативно (даже для вычислений над машинными вещественными

числами), последовательность команд

А [2] :=АС; АС:=А[1]; АС:=АС + /г[2]

в (*) можно сократить не только до

АС:=А[1] + АС,

но

и до

АС:= АС + А[1].

Обратите также внимание на заключённые в рамку пять

команд в (**) для реализации вычисления АС := а + Ь X Ь.

Им

отвечает в (*)

другая

версия, также с пятью командами;

разница связана с тем, что в одном

случае

употребляется

АС := h [2] + АС, а в

другом

АС := АС + Л |2].

Если отказаться от жёсткого порядка „слева направо", диктуемого

принципом

магазина, то можно обойтись и без обращенных команд, обращая

порядок

подготовки операндов для совместных операций.

266 Гл. 3. Машинно-ориентированные алгоритмические языки

3.7.5.

Границы

применимости

принципа

магазина

Принцип

магазина благодаря его прозрачности и простоте

технической реализации получил широкое распространение,,

прежде всего при построении трансляторов. Обычно он обеспе-

чивает весьма экономное распределение памяти, хотя в отдель-

ных случаях вспомогательные переменные используются черес-

чур расточительно. К числу недостатков принципа магазина

следует

отнести его несимметричность. Так, если обрабатывать

формулу

fHa + ЬХЬ)

слева направо в соответствии с принципом магазина, то полу-

чится одноадресная форма

?/; _

Й_[1]:=АС;

АС:-а;

Л[2]1-А5~;

АС:=6;

АС:=АСх6;

АС:=А[2

AC J

при обработке

же

справа налево

мы

получили

бы

Г.

АС:=й;

АС:=йхАС;

[

_АС:=а

+ АС; J

"АС--7/АС"

Г "

AC J

В современных больших вычислительных машинах не только

действительно применяют специализированные по сортам сум-

маторы, но и стараются иметь в распоряжении побольше сум-

маторов вместе с независимо работающими устройствами обра-

ботки для выполнения основных операций. Мы ещё поговорим

ниже о появляющихся за счёт этого возможностях параллель-

ной

работы и о трудностях их оптимального использования.

3.7.6.

Обработка

разбора

случаев

В настоящем разделе мы рассмотрим условные формулы.

Если

такая формула образует правую часть некоторого присваи-

вания,

то можно перейти к условному оператору, в остальных

случаях нужно ввести вспомогательную переменную; присваива-

ние

шеременнаж := if >условие< then >да-формула<

else

>нет-формула< fi

3.7. Декомпозиция формул 267

перейдёт в оператор

if >условие<

then

теременнаж

:==

>да-формула<

else

шеременнаж := >нет-формула< fi.

В паскале и без того приходится обходиться одними условны-

ми

операторами '.

Однако условный оператор можно свести к

условным,

переходам

if >условие<

then

goto

>метка<

else

skip

fi.

Для этого из оператора альтернативы вида

if >условие<

then

>да-оператор<

else

>нет-оператор< fi; ~~

сначала вычленяются >да-оператор< и >нет-оператор<:

if >условие<

then

goto

else

goto

mn fi;

mn: [>нет-оператор< J;

goto

my. Г>да-оператор<_|;

goto

m: —.

Это можно сократить до формулировки с „обходом" нет-опера-

тора:

if >условие<

then

goto

else

skip

fi;

[>нет-оператор< J;

goto

mj: Г>да-оператор<_|;

m: -~

Если

>да-оператор< пуст, т. е.

if >условие<

then

skip

else

>нет-оператор< fi,

то метки т и mj отождествляются:

if >условие<

then

goto

else

skip

fi;

Г>нет-оператор<_|;

m: —

Если

же пуст >нет-оператор<, т. е.

if >условие<

then

>да-оператор(

else

skip

fi; —,

Поскольку паскалевские формулировки в этом разделе лишь тривиаль-

ным

образом отличаются от алгольных, мы не стали их здесь явно при-

водить.

Ниже j и п — от немецких ja (да) и nein (нет). — Прим.

перев

268 Гл. 3. Машинно-ориентированные алгоритмические языки

то лучше поменять >да-оператор< и >нет-оператор< ролями; в

результате получится формулировка без „перепрыгивания" че-

рез >да-оператор<:

—1

>условие<

then

goto

else

skip

fi;

[>да-оператор< J;

m: ~

Итак,

в результате получаются условные переходы, в которых

>условие< представляет собой формулу, вырабатывающую не-

которое значение истинности. Если результат попадает в не-

который

сумматор

ACbooi,

то нужно проверить каждый из

•случаев

ACbooi

= Т и

AC=F.

Перестановка ветвей в

операторе альтернативы позволяет сводить один из этих слу-

чаев к

другому.

Таким образом, можно обойтись

командой

условного

перехода

ACbooi

then

goto

>метка<

else

skip

fi.

Если

же последняя операция при вычислении условия — это

одна из операций сравнения

для целых или вещественных чисел, то при помощи вычитания

её можно свести к одному из шести случаев:

>o,

AC^O,

AC<0,

AC<0.

Возможность перестановки операндов вычитания делает опера-

ции

из нижней строчки ненужными.

Перестановка ветвей в операторе альтернативы сводится к

отрицанию и делает излишними операции из правого столбика;

принципе для целых и вещественных чисел можно обойтись

следующими двумя формами условного перехода по содержи-

мому сумматора:

if AC = 0

then

goto

>метка<

else

skip

if AC ^ 0

then

goto

>метка<

else

skip

fi.

Пример

(ср. с примером (с) из

3.5.2).

proc

o«/s(var

int и, v):

и=51>

then

skip

D u£v

then

exch(u,

v) f!

3.7. Декомпозиция формул 269

Представляется разумным сузить второе условие-страж до

и < v; при помощи вычитания получим

proc

ord= (varmt и, v):

ГАС:=н;

AC:=AC-t>:

if ACaOthenskfp

elsee.vcA(«,

v) fj J

а отсюда

proc

oft/s(var

int м, с) :

ГАС:=«;

AC:=AC-y;

ACfeO

then

goto

else

skip

fi;

exch

(u, v) ;

skip

Аналогичную постепенную обработку допускает и последо-

вательный разбор случаев. То же самое справедливо для охра-

няемого разбора случаев. Скажем,

if х > 0

then

х := 1 П х = 0

then

skip

• х < 0

then

х := —

f i,.

применяя

линеаризацию, можно преобразовать в

if х > 0

then

if x — 0

then

skip

else

x := 1 f i

else

x := —

f i

откуда получаем

^С:=х;

If AC

ihen

goto

tnj

else skip fi;

x:=~l;goto»j;

mj: if AC «0 then

goto

else skip fi;

:sklp

Здесь неявно подразумевается, что (условный или безуслов-

ный)

переход никогда не меняет содержимого сумматора.

3.7.7.

Исключение

логических

операций

2.2.3.4

уже говорилось о том, что конъюнкцию .Л. (соотв.

.and.)

и дизъюнкцию .V. (соотв. .or.) можно заменять подходя-

щим

разбором случаев, причём иногда это приводит к упроще-

ниям,

поскольку при определённых условиях вычисления второ-

го операнда проводить не обязательно (последовательная

конъюнкция,

последовательная дизъюнкция). Предпосылкой для

этого является, разумеется, отсутствие побочных эффектов, на

что в стандартном алголе-68

следует

обращать особое внимание.

•270

Гл. 3. Машинно-ориентированные

алгоритмические

языки

Получающиеся таким образом операторы с разбором слу-

чаев можно затем снова свести к условным переходам.

Пример.

x:=U х^О А х <\ then

sqrt

((I —x)Y.x)

else

0 fi; ~

Прежде всего, условие О 0 Л J: < 1 можно заменить на

if х < 1 then x^zO

else

false

fi.

•аёт

<f (if x < 1 then x>0

else

false

fi) then

x:=sqrt{{\

— x) X x)

else

x :=0 fi; -™,

что можно записать подробно так:

if (ifx<i

then[ifxbO !

then truo i

| else false -fi «

else

false

" fi) then x

sqrt

((1

-x)

else

x:=0 fi; /w\.

Отсюда получается следующее упрощение:

then

if.vuO then x:=.«?rt((l-,v)xx)

elsex:=0

От двойного написания присваивания х :— 0 мы избавимся за

счёт выделения обоих вхождений этого присваивания:

х <

then

if x >

then

goto

else

goto

mn fi

else

goto mn fi;

:x:=0;

goto m;

m/ :x\**sqrt((\ -x) xx); goto m ;

Тем самым получим окончательно

АС:=х;

АС:=АС-1;

AC>0

then

goto

else

skip fi:

AC:=x;

AC>0

then

goto

else

skip fi;

mn : AC»0; x.=AC ; goto m ;

:AC:-x;

AC:=1-AC;

AC:=ACxx;

AC:=^r/(AC);

x;= AC ;