Control flow graph: различия между версиями
KVN (обсуждение | вклад) (Создана новая страница размером То же, что Управляющий граф. Категория: Потоковый анализ программ) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Control flow graph'''— ''[[управляющий граф]], [[уграф]], [[граф потока управления]], [[граф переходов]].'' | |||
A program can be represented as a [[directed graph]] (called '''control flow graph''' or '''cf-graph'''), in which [[vertex|vertices]] (or '''[[node|nodes]]''') correspond to program statements and [[arc|arcs]] reflect possible transfers of control between the corresponding statements. There are '''initial''' (or '''entry''') and '''terminal''' (or '''exit''') | |||
nodes in the graph that correspond to input and output statements of the program. If there is an arc <math>\,(p,q)</math>, then <math>\,p</math> is called a '''predecessor''' of <math>\,q</math> and <math>\,q</math> is called a '''successor''' of <math>\,p</math>. | |||
It is assumed that a control flow graph <math>\,G</math> is a '''proper''' one, i.e. <math>\,G</math> has a single initial node without predecessors and a single terminal node without successors, and every node of <math>\,G</math> lies on at least one of the paths from the initial node to the terminal node. | |||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
[[Категория: Потоковый анализ программ]] | [[Категория: Потоковый анализ программ]] | ||
Текущая версия от 13:54, 5 октября 2016
Control flow graph— управляющий граф, уграф, граф потока управления, граф переходов.
A program can be represented as a directed graph (called control flow graph or cf-graph), in which vertices (or nodes) correspond to program statements and arcs reflect possible transfers of control between the corresponding statements. There are initial (or entry) and terminal (or exit) nodes in the graph that correspond to input and output statements of the program. If there is an arc [math]\displaystyle{ \,(p,q) }[/math], then [math]\displaystyle{ \,p }[/math] is called a predecessor of [math]\displaystyle{ \,q }[/math] and [math]\displaystyle{ \,q }[/math] is called a successor of [math]\displaystyle{ \,p }[/math].
It is assumed that a control flow graph [math]\displaystyle{ \,G }[/math] is a proper one, i.e. [math]\displaystyle{ \,G }[/math] has a single initial node without predecessors and a single terminal node without successors, and every node of [math]\displaystyle{ \,G }[/math] lies on at least one of the paths from the initial node to the terminal node.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.