Главная Промышленная автоматика.

Хотя в этом примере введено много новых понятий, мы не будем обобщать этот материал для написания общих алгоритмов вычисления областей действия определений в произвольных блок-схемах. Вместо этого мы напишем часть программы вычисления множеств DEFINfi] и DEFOUT[i\(i =1, 8) для блок-схемы рис. 4.1, предполагая, что множества GEN[i] и KILL[i] определены заранее. Отметим, что предлагаемый фрагмент программы предполагает существование АТД SET (Множество) с операторами UNION, INTERSECTION, DIFFERENCE, EQUAL, ASSIGN и MAKENULL, позднее мы покажем, как реализовать этот АТД.

В создаваемом программном фрагменте (листинг 4.1) процедура propagate(GEN, KILL, DEFIN, DEFOUT) использует формулу (4.1) для вычисления множества f/Dt/r указанного блока. Если программа свободна от циклов и повторяющихся структур, то в этом случае множества DEFOUT можно вычислить непосредственно. При наличии в программе циклов или повторяющихся структур для вычисления DEFOUT применяются итерационные процедуры. Сначала для всех i положим DEFINfiJ = О и DEFOUTfiJ = GENfiJ, затем последовательно применим формулы (4.1) и (4.2) несколько раз, пока не "стабилизируются" (не перестанут изменяться) множества DEFIN и DEFOUT. Поскольку каждое новое значение множеств DEFIN[i]n OEFOC/T[i]содержит свои предыдущие значения, а количество всех определений в программе ограничено, то процесс должен сходиться к решению уравнений (4.1) и (4.2).

Последовательные значения множеств DEFIN[i] после каждой итерации цикла показаны в табл. 4.1. Заметим, что операторы 1, 2 и 3 присваивания переменным "неопределенных" значений не распространяются на блоки, где эти переменные используются. Отметим также, что в листинге 4.2 сначала выполняются вычисления по формуле (4.2), а затем по формуле (4.1); в общем случае это обеспечивает сходимость процесса вычисления DEFIN[i\BC£ro за несколько итераций. □

Листинг 4.1. Программа вычисления областей действий операторов определения переменных

GEN, KILL, DEFIN, DEEOUT: array[1..8] of SET;

{ Предполагается, что GEN и KILL вычисляются вне этой программы } i: integer; changed: boolean;

procedure propagate{ G, K, I: SET; var 0: SET ) ;

.{- Вычисления no формуле (4.1), переменная сЛалдесЗ принимает значение true, если есть изменения в DEEOUT }

TEMP: SET; begin

DIFFERENCE (I, K, TEMP) ;

UNION ( TEMP, G, TEMP);

If not EQUAL (TEMP, O) do begin

ASSIGN (O, TEMP);

changed:- true

end; { propagate }

begin

for i;= • 1 to 8 do

ASSIGN (DEFOOTd] , GHW[i]); repeat



changed:= false;

{ далее 8 операторов реализуют формулу (4.2), но только

для блок-схемы рис. 4.1 } MAKENULL (DEFINl 1 ] ) ; ASSIGN(DEFIJV[2] , DEFOUTll] ) ASSIGN {DEFIN[3] ASSIGN (DEFIJV[4] , UNION (DEFOUT[4] UNION (DEFOOTLS] , ASSIGN (DEFIN[ 7] ASSIGN (DEFIW[ 8]

DEF0OT[2] ) , DEF0UT[3]: DEFOUT[8] , DEFIN[S] ) ; DEFOUT[5] , DEFIN[ 6] ) ; DFF0UT[6]) ;

DEFOUT[6] ) ; for i; = 1 to 8 do

propagate (.GEN[i], KILLli] , DEFIN[i], DEFOUT[i]) ;

until

not changed

end.

Таблица 4.1. Значения ОЕРЩ!\ после каждой итерации

Проход 1

Проход 2

Проход 3

Проход 4

о •

{1- 2, 3}

{1,2, 3)

{1.2, 3)

(1,2, 3)

{4, 5}

{1.4, 5}

{1-4, 5)

{1,4, 5}

{4, 5)

(1, 4, 5}

{1.4, 5}

{6, 9)

{6, 9)

(4,5,6, 7, 8,9}

(4, 5, 6, 7, 8, 9}

{7. 8}

{4, 5, 6, 7, 8, 9}

(1,4, 5, 6, 7, 8, 9)

{1, 4, 5, 6, 7, 8, 9}

{7, 8)

(4, 5, 6, 7, 8, 9}

{1,4,5,6, 7, 8, 9}

и, 8}

(4, 5, 6, 7, 8, 9}

{1,4,5,6, 7,8,9)

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

Наилучшая конкретная реализация абстрактного типа данных SET (Множество) выбирается исходя из набора выполняемых операторов и размера множества. Если все рассматриваемые множества будут подмножествами небольшого универсального множества целых чисел 1, для некоторого фиксированного JV, тогда можно

применить реализацию АТД SET посредством двоичного (булева) вектора. В этой реализации множество представляется двоичным вектором, в котором i-й бит равен 1 (или true), если i является элементом множества. Елавное преимушество этой реализации состоит в том, что здесь операторы MEMBER, INSERT и DELETE можно выполнить за фиксированное время (независимо от размера множества) путем прямой адресации к соответствуюшему биту. Но операторы UNION, INTERSECTION и DIFFERENCE выполняются за время, пропорциональное размеру универсального множества.

Если универсальное множество так мало, что двоичный вектор занимает не более одного машинного слова, то операторы UNION, INTERSECTION и DIFFERENCE можно выполнить с помошью простых логических операций (конъюнкции и дизъюнкции), выполняемых над двоичными векторами. В языке Pascal для представления небольших множеств можно использовать встроенный тип данных set. Максимальный размер таких множеств зависит от конкретного применяемого компилятора

4.3. РЕАЛИЗАЦИЯ МНОЖЕСТВ ПОСРЕДСТВОМ ДВОИЧНЫХ ВЕКТОРОВ



и поэтому не формализуем. Однако при написании программ мы не хотим быть связаны ограничением максимального размера множеств по крайней мере до тех пор, пока наши множества можно трактовать как подмножества некоего универсального множества {1, N}. Поэтому в данном разделе будем придерживаться представления множества в виде булевого массива, где A[i] = true тогда и только тогда, когда i является элементом множества. С помошью объявлений языка Pascal АТД SET можно определить следующим образом:

const

W = { подходящее числовое значение ) ;

type

SET = packed array[l..N] of boolean;

Реализация оператора UNION приведена в листинге 4.2. Для реализации операторов INTERSECTION и DIFFERENCE надо в листинге 4.2 заменить логический оператор ог на операторы and и and not соответственно. В качестве простого упражнения читатель может самостоятельно написать код для реализации других операторов, перечисленных в разделе 4.1 (за исключением операторов MERGE и FIND, которые не имеют практического смысла при данном представлении множеств).

Листинг4.2. Реализация оператора UNION

procedure UNION < А, В: SET; var С: SET ) ; var

i: integer; begin

for i; = 1 to N do

C[i] -.= A[i] or B[i]

Представление множеств в виде двоичных векторов можно применить не только тогда, когда универсальное множество состоит из последовательных целых чисел, но и в более обшей ситуации, когда универсальное множество конечно. Для этого достаточно установить взаимно однозначное соответствие между элементами этого множества и целыми числами 1, N. Например, так, как это сделано в примере 4.1, где вер определения данных мы пронумеровали числами от 1 до 9. В общем случае для реализации такого отображения используется АТД MAPPING (Отображение), описанный в главе 2. На практике обратное отображение из множества целых чисел в множество элементов универсального множества проще выполнить с помощью массива А, где A[i] будет элементом универсального множества, соответствующим числу i.

4.4. Реализация множеств посредством связанных списков

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

При реализации оператора INTERSECTION (Пересечение) в рамках представления множеств посредством связанных списков есть несколько альтернатив. Если универсальное множество линейно упорядочено, то в этом случае множество можно представить в виде сортированного списка, т.е. предполагая, что все элементы множества сравнимы посредством отношения "<", можно ожидать, что эти элементы в списке





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 [32] 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.002