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



         

Простейшие свойства


Граф называется сводимым тогда и только тогда, когда множество обратных дуг совпадает с множеством обратных дуг относительно глубинного остовного дерева для любого такого дерева.

Простейшие свойства нумераций Pre и Post:

  • если вершина v обязательно предшествует вершине w , то Pre(v)<Pre(w), Post(v)<Post(w)
  • прямые в смысле нумерации Pre дуги являются прямыми или деревянными относительно дерева
  • обратные в смысле нумерации Pre дуги являются обратными или поперечными относительно дерева
  • обратные в смысле нумерации Post дуги являются обратными в смысле дерева; остальные дуги являются прямыми относительно нумерации Post
  • если Pre(v)>Pre(w) , то произвольный путь в графе от v до w содержит общего предка v и w в дереве
  • граф сводим тогда и только тогда, когда отношение обязательного предшествования в нем и его каркасе совпадают

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




Содержание  Назад  Вперед