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

       

Потоковый граф


Для представления программы используется потоковый граф. Перечислим его особенности.

1.  Граф строится отображением управляющей структуры программы. В ходе отображения закрывающие скобки условных операторов и операторов циклов (end if; end loop) рассматриваются как отдельные (фиктивные) операторы.

2. Узлы (вершины) потокового графа соответствуют линейным участкам программы, включают один или несколько операторов программы.

3. Дуги потокового графа отображают поток управления в программе (передачи управления между операторами). Дуга — это ориентированное ребро.

4. Различают операторные и предикатные узлы. Из операторного узла выходит одна дуга, а из предикатного — две дуги.

4.      Предикатные узлы соответствуют простым условиям в программе. Составное условие программы отображается в несколько предикатных узлов. Составным называют условие, в котором используется одна или несколько булевых операций (OR, AND).

5.      Например, фрагмент программы

if a OR b

then x

else у

end if;

вместо прямого отображения в потоковый граф вида, показанного на рис. 6.4, отображается в преобразованный потоковый граф (рис. 6.5).



Рис. 6.4. Прямое отображение в потоковый граф

Рис. 6.5. Преобразованный потоковый граф

6. Замкнутые области, образованные дугами и узлами, называют регионами.

7. Окружающая граф среда рассматривается как дополнительный регион. Например, показанный здесь граф имеет три региона — Rl, R2, R3.

Пример 1. Рассмотрим процедуру сжатия:

процедура сжатие

1                  выполнять пока нет EOF

1                               читать запись;

2                              если запись пуста

3                              то удалить запись:

4                              иначе если поле а >= поля b

5                                          то удалить b;

6                                          иначе удалить а;

7а                            конец если;

7а                конец если;

7b                конец выполнять;

8      конец сжатие;

Рис. 6.6. Преобразованный потоковый граф процедуры сжатия

Она отображается в потоковый граф, представленный на рис. 6.6. Видим, что этот потоковый граф имеет четыре региона.

 



Содержание раздела