Kontrollflussgraph

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Lückenhaft In diesem Artikel oder Abschnitt fehlen noch folgende wichtige Informationen:
Anwendungen fehlen bzw. sind nicht detailliert ausgeführt (bspw.: Elimination toten Codes), Beispiele sind unzureichend (Aussehen gängiger Kontrollflusselemente wie if/while/goto fehlt völlig)
Hilf der Wikipedia, indem du sie recherchierst und einfügst.

Ein Kontrollflussgraph ist ein Begriff aus der Informatik und bezeichnet einen gerichteten Graphen der dazu dient, den Kontrollfluss eines Computerprogramms zu beschreiben. Sie werden unter anderem zur Programmoptimierung eingesetzt.[1]

Aufbau[Bearbeiten | Quelltext bearbeiten]

Jeder Kontrollflussgraph besteht aus

  • einer Menge von Knoten , die die Grundblöcke des beschriebenen Programms darstellen, sowie
  • einer Menge von gerichteten Kanten , die mögliche Übergänge, d. h. Programmabläufe darstellen.

Üblicherweise fügt man zur Knotenmenge zusätzlich einen speziellen Eingangs- und Ausgangsknoten hinzu, für die im Programm keine Anweisungen existieren. Diese entsprechen dem Betreten bzw. Verlassen des entsprechenden Programmabschnitts.[2]

Wenn von einem Knoten mehrere Kanten wegführen (der Knoten also Quelle mehrerer gerichteter Kanten ist), so entspricht das einer Verzweigung. Schleifen finden sich als Zyklen in Kontrollflussgraphen wieder. Beispielsweise zeigt der Zyklus im unten abgebildeten Graph an, dass im zugrundeliegenden Computer-Programm eine Schleife enthalten ist.

Beispiele[Bearbeiten | Quelltext bearbeiten]

Kontrollflussgraph mit unerreichbarem Code
Kontrollflussgraph mit Schleife

Im abgebildeten Graphen mit Eingangsknoten und Ausgangsknoten existiert kein Pfad vom Eingangsknoten zum Knoten . Der Grundblock stellt damit toten Code dar.

Graph enthält einen Zyklus. Das zugrundeliegende Programm enthält damit eine (implizite oder explizite) Schleife.

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. : Masking wrong-successor Control Flow Errors employing data redundancy. IEEE, S. 201–205. doi:10.1109/ICCKE.2015.7365827
  2. Aho, Alfred V., Aho, Alfred V.: Compilers : principles, techniques, & tools. 2nd ed. Pearson/Addison Wesley, Boston 2007, ISBN 0-321-48681-1.