Primer pedido de profundidad en el diseño del compilador

La primera búsqueda en profundidad del gráfico visita todos los Nodes del gráfico una vez, comenzando por el punto de entrada y visitando los Nodes hasta el punto de entrada lo más rápido posible. La ruta de búsqueda para la búsqueda en profundidad crea el primer árbol expandible (DFST). Pre-orden visita el sitio antes de visitar a cualquiera de los niños locales, quienes también visitan repetidamente de izquierda a derecha. Además, el recorrido posterior al pedidovisita los hijos del Node, repetidamente en secuencia de izquierda a derecha, antes de visitar el sitio en sí. Hay un orden distinto que es importante en el análisis del diagrama de flujo: el orden de la primera profundidad es el retroceso del recorrido posterior al orden. Es decir, en una primera profundidad, visitamos el Node y luego cortamos su hijo a la derecha, a la izquierda, y así sucesivamente. Sin embargo, antes de construir un árbol de diagramas de flujo, tenemos que decidir qué Node seguidor se convierte en el hijo derecho del árbol, qué Node se convierte en el hijo izquierdo, y así sucesivamente.

Primer pedido de profundidad:

La complejidad del análisis de flujo de datos utilizando la estrategia de solución de flujo de datos se ha mostrado como una secuencia de Nodes. En este caso, se define un valor que se denomina profundidad del diagrama de flujo para determinar el número máximo de repeticiones necesarias. Esto requiere la consideración de bloques básicos en un cierto orden y no en una secuencia aleatoria. En primer lugar, a los Nodes del gráfico de flujo se les asigna un número, denominado primer número de profundidad . La profundidad de los primeros números (dfu) de los Nodes del gráfico es una distorsión de cómo visitamos por última vez cada Node en el bloque de pedido anticipado del gráfico.

Propiedades:

El primer orden de profundidad tiene las siguientes propiedades:

1. Vi € dominadores(j), dfn(i) <dfn(j),
2. Vbordes delanteros (i, j), dfn(i) < dfn(j) y
3. Bordes hacia atrás (i, j), dfn(j) < dfn(i).

La profundidad d del gráfico de flujo del sistema es el mayor número de aristas posteriores en cualquier camino acíclico en él. Cabe señalar que no es lo mismo que la profundidad del nido. Por ejemplo, en el gráfico de flujo anterior, la profundidad de anidamiento es 2, pero la profundidad d es igual a 1.

El resultado más importante del análisis repetido es el siguiente: 

Para el problema de flujo de datos hacia adelante, cuando los gráficos se visitan en una secuencia profunda, d + 1 repetido es suficiente para llegar a un punto fijo. Para el problema de la devolución de datos, los Nodes deben visitarse a la misma profundidad que el primer orden. El punto puede ser probado por las siguientes observaciones:

1. Para el problema del reenvío de datos, visitamos los Nodes en orden creciente con la profundidad de los números iniciales. Si no hay bucles en el sistema, que es d-0, entonces la información de flujo de datos ingresada por la computadora en la primera duplicación puede ser un punto fijo para las estadísticas de flujo de datos.
2. Si un bucle está presente en el sistema, entonces d-1. Ahora, para un nuevo valor de liberación de bucle, el Node enumerado en el primer duplicado puede afectar la propiedad del Node de entrada de bucle. Esto solo se puede lograr en repeticiones posteriores. Por lo tanto, se requieren dos repeticiones.

Representación algorítmica de DFS:

Bordes traseros y reducibilidad:

El borde posterior es el borde a -> b, donde su cabeza b domina la cola a. En un gráfico de flujo, todo el borde posterior se invierte, pero no todos los bordes posteriores se invierten. Se dice que el diagrama de flujo es irreversible si todos sus extremos reclinados en cualquier árbol de tramo profundo son los bordes posteriores. Sin embargo, si el gráfico no se puede minimizar, todos los backends son los bordes inclinados de cualquier DFST, pero cada DFST puede tener bordes inclinados adicionales además de los extremos traseros. Estos bordes retráctiles pueden diferir de un DFST a otro.

Por lo tanto, si eliminamos todos los bordes posteriores del gráfico que fluye y el gráfico restante es circular, el gráfico no se puede reducir y viceversa. Los diagramas de flujo que ocurren en el rendimiento casi siempre se reducen. El uso especial de sentencias de control de flujo sistemáticas como las sentencias then, while-doing, Continuous y Break produce sistemas cuyos gráficos de flujo se invierten constantemente. Incluso los programas que se escriben usando instrucciones goto a menudo parecen reducibles, ya que el editor piensa lógicamente en las trampas y bifurcaciones.

Para el gráfico de flujo anterior con el Node inicial como 1, el Node 1 domina a los Nodes 2 y 3, pero el 2 no gobierna al 3, o viceversa. Por lo tanto, este diagrama de flujo no tiene bordes posteriores , ya que no tiene la cabeza de un borde que gobierna su cola. Hay dos árboles que pueden ser la primera profundidad, dependiendo de si optamos por llamar primero a buscar (2) oa buscar (3), desde buscar (l). En el primer caso, el borde 3 ->2 es un borde inclinado pero no el trasero; en el segundo caso, el 2 -> 3 es un borde inclinado, pero no hacia atrás. Comprensiblemente, la razón por la que este gráfico de flujo no disminuye es que el Ciclo 2-3 se puede instalar en dos ubicaciones diferentes, los Nodes 2 y 3.