ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->Листинг 4.1. Программа вычисления областей действий операторов определения переменных

Алгоритмы структуры данных

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

var

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

{ Предполагается, что GEN и KILL вычисляются

вне этой программы }

і: integer; changed: boolean;

procedure propagate( C, K, I: SET; var O: SET );

{ Вычисления по формуле (4.1), переменная changed принимает

значение true, если есть изменения в DEFOUT }

var

TEMP: SET;

begin

DIFFERENCE( I,   К,    ТЕМP);

UNION ( TEMP,   G,    TEMP);

if not EQUAL(TEMP,   O)   do begin

ASSIGN(0,    TEMP);

changed:=  true

end

end;   { propagate  }

 

begin

for i:to 8 do

ASSIGN(DEFOUT[i] , GEN[1]);

Repeat

changed: = false

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

для блок-схемы. рис. 4,1 }

MAKENULL(DBFJW[1]) ;

ASSIGN(DEFIN[2 ], DEFOUT[1]);

ASSIGN (DEFINES],DEFQUT[2]);

ASSIGN (DEFINE ], DEFOUT[3]);

UNION(DEFOUT[4] , DEFOUT[8] , DEFIN[5]);

UNION(DEFOUT[3], DEFOUT[5] , DEFIN[6]);

ASSIGN(DEFIN[7], DEFOUT[6]);

ASSIGN(DEFIW[8] , DEFOUT [ 6 ] ) ;

for і:= 1 to 8 do

propagate (GEN[i], KILL[i] , DEFIN[i], DEFOUТ[i]);

until

not changed

end

Таблица 4.1.

і

Проход 1

Проход 2

Проход 3

Проход 4

1

2

3

4

5

6

7

8

Ø

{1, 2, 3}

{4,5}

Ø

{6,9}

{7,8}

Ø

Ø

Ø

{1,2,3}

{1,4,5}

{4,5}

{6,9}

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

{7, 8}

{7,8}

Ø

{1,2,3}

{1.4.5}

{1,4,5}

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

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

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

Ø

{1,2,3}

{1,4,5}

{1,4,5}

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

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

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

 

44