Разработка компиляторов
Обязательное предшествование
Вершина v обязательно предшествует вершине w , если v принадлежит каждому пути в графе от start до w . В частности, любая вершина обязательно предшествует себе самой. Отношение обязательного предшествования будем обозначать символом '<'. Легко видеть, что это отношение рефлексивно и транзитивно, но не симметрично. Таким образом, отношение обязательного предшествования задает частичный порядок на множестве вершин графа.
Вершина v строго обязательно предшествует вершине w , если она обязательно ей предшествует, но не совпадает с ней. Отношение строгого обязательного предшествования будем обозначать символом sdom .
Вершина v непосредственно предшествует вершине w , если она является ближайшей к w вершиной, которая ей строго предшествует.
Можно показать, что множество строгих обязательных предшественников для данной вершины линейно упорядочено, а непосредственный предшественник - это максимальный элемент в этом множестве. Таким образом, отношение непосредственного предшествования - это дерево. Легко показать, что корнем этого дерева является start .
Дуга (v, w) называется обратной в том и только том случае, когда w<v .
Отношение обязательного предшествования играет чрезвычайно важную роль в задачах анализа потока управления. Например, с его помощью могут быть решены задачи проверки сводимости (см. ниже), построения статической формы единственного присваивания (в этой лекции не рассматривается) и т.д.
