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



         

Обязательное предшествование


Вершина v обязательно предшествует вершине w , если v принадлежит каждому пути в графе от start до w . В частности, любая вершина обязательно предшествует себе самой. Отношение обязательного предшествования будем обозначать символом '<'. Легко видеть, что это отношение рефлексивно и транзитивно, но не симметрично. Таким образом, отношение обязательного предшествования задает частичный порядок на множестве вершин графа.

Вершина v строго обязательно предшествует вершине w , если она обязательно ей предшествует, но не совпадает с ней. Отношение строгого обязательного предшествования будем обозначать символом sdom .

Вершина v непосредственно предшествует вершине w , если она является ближайшей к w вершиной, которая ей строго предшествует.

Можно показать, что множество строгих обязательных предшественников для данной вершины линейно упорядочено, а непосредственный предшественник - это максимальный элемент в этом множестве. Таким образом, отношение непосредственного предшествования - это дерево. Легко показать, что корнем этого дерева является start .

Дуга (v, w) называется обратной в том и только том случае, когда w<v .

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




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