Разработка компиляторов

       

Иерархия вложенных зон


Как было отмечено выше, не любой сильно связный подграф является областью некоторой вершины при нумерации Post . Для того, чтобы конструктивно описать все сильно связные подграфы, используется понятие иерархии вложенных зон.

Иерархией вложенных зон называется совокупность сильно связных подграфов S , два любых из которых либо не пересекаются, либо один из них содержит другой, такая, что для произвольного сильно связного подграфа Z найдется содержащий его элемент S , который имеет с Z общую входную вершину.

Может быть показано, что набор областей всех вершин при нумерации Post является иерархией вложенных зон.

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



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