Порядок в глубину в дизайне компилятора
Первый поиск в глубину графа посещает все узлы в графе один раз, начиная с точки входа и посещая узлы до точки входа как можно быстрее. Маршрут поиска для углубленного поиска создает первое расширяемое дерево (DFST). Предварительный заказ посещает сайт перед посещением любого из местных детей, которые также посещают неоднократно слева направо. Кроме того, обход в обратном порядке многократно посещает дочерние узлы слева направо, прежде чем посетить сам сайт. Существует один отчетливый порядок, который важен при анализе потокового графа: порядок первой глубины — это отступление обратного обхода. То есть на первой глубине мы посещаем узел, а затем разрезаем его дочерний элемент вправо, влево и так далее. Однако перед построением дерева потокового графа у нас есть решения о том, какой узел-последователь станет правым дочерним элементом в дереве, какой узел станет левым дочерним элементом и так далее.
Порядок в глубину:
Сложность анализа потока данных с использованием стратегии решения потока данных была отображена в виде последовательности узлов. В этом случае определяется значение, которое называется глубиной графа потока, чтобы определить максимальное количество требуемых повторений. Это требует рассмотрения базовых блоков в определенном порядке, а не в произвольной последовательности. Во-первых, узлам потокового графа присваивается номер, называемый первым номером глубины . Глубина первых номеров (dfu) узлов графа — это искажение того, как мы последний раз посещали каждый узел в блоке предварительного заказа графа.
Характеристики:
Порядок в глубину обладает следующими свойствами:
- Вы € доминатор(ы), dfn(i) <dfn(s),
- Vпрямые ребра (i, j), dfn(i) < dfn(j) и
- Vобратные ребра (i, j), dfn(j) < dfn(i).
Глубина d системного потокового графа — это наибольшее число апостериорных ребер на любом ациклическом пути в нем. Можно отметить, что это не то же самое, что глубина гнезда. Например, на приведенном выше блок-схеме глубина вложенности равна 2, а глубина d равна 1.
Наиболее важным результатом повторного анализа является следующее:
Для задачи прямого потока данных, когда графы посещаются в глубокой последовательности, d + 1 повторений достаточно для достижения фиксированной точки. Для проблемы возврата данных узлы должны быть посещены на той же глубине, что и в первом порядке. Это можно подтвердить следующими наблюдениями:
- Для задачи пересылки данных мы посещаем узлы в порядке возрастания глубины исходных номеров. Если в системе нет петель, что равно d-0, то информация о потоке данных, введенная компьютером при первом дублировании, может быть фиксированной точкой для статистики потока данных.
- Если в системе присутствует одна петля, то d-1. Теперь для нового значения освобождения цикла узел, указанный в первом дубликате, может влиять на свойство узла входа в цикл. Этого можно добиться только в последующих повторениях. Поэтому требуется два повторения.
Алгоритмическое представление DFS:
Задние грани и сводимость:
Заднее ребро — это ребро a -> b, где его начало b доминирует над хвостом a. На потоковом графике переворачивается вся задняя грань, но не все задние кромки переворачиваются. Потоковый граф называется необратимым, если все его наклонные концы на любом глубоком дереве являются задними ребрами. Однако, если граф не может быть минимизирован, все обратные стороны являются наклонными ребрами любого DFST, но каждый DFST может иметь дополнительные наклонные ребра, отличные от задних концов. Эти убирающиеся края могут отличаться от одного DFST к другому.
Таким образом, если мы удалим все задние ребра текущего графа, а оставшийся граф будет круговым, граф не может быть уменьшен, и наоборот. Графы потока, которые встречаются в производительности, почти всегда сокращаются. Специальное использование систематических операторов управления потоком, таких как then, while-doing, continue и break, создает системы, графы потоков которых постоянно меняются местами. Даже программы, написанные с использованием операторов goto, часто кажутся легкосократимыми, поскольку редактор логически думает о ловушках и ответвлениях.
Для приведенного выше потокового графа с начальным узлом 1 узел 1 доминирует над узлами 2 и 3, но 2 не управляет узлами 3 или наоборот. Следовательно, этот потоковый граф не имеет задних ребер , так как у него нет головы ребра, которое управляет его хвостом. Есть два дерева, которые могут быть первой глубиной, в зависимости от того, выберем ли мы сначала вызов поиска (2) или поиска (3) из поиска (l). В первом случае ребро 3 -> 2 является наклонным, а не задним; во втором случае 2 -> 3 является наклонным краем, но не обратным. Понятно, что этот блок-схема не уменьшается, потому что цикл 2-3 может быть установлен в двух разных местах, узлах 2 и 3.