这是维基百科上 CFG 的定义,我知道你已经知道了,但为了完整起见,我将其放在这里
计算机科学中的控制流图(CFG)是一种表示,
使用图形表示法,列出可能经过的所有路径
程序在执行过程中。
Ref: https://en.wikipedia.org/wiki/Control_flow_graph https://en.wikipedia.org/wiki/Control_flow_graph
以下是 Path 的定义
路径:CFG上的节点序列(静态),包括入口节点
和一个退出节点;路径段:沿路径的节点子序列
Ref: http://web.cs.iastate.edu/~weile/cs513x/4.ControlFlowAnalysis.pdf http://web.cs.iastate.edu/%7Eweile/cs513x/4.ControlFlowAnalysis.pdf
因此,绘制一个的原因是确定程序所采取的所有可能路径,这可以帮助我们在不实际运行程序的情况下确定测试覆盖率之类的事情(静态分析)。
以下是我们绘制 CFG 时可以遵循的简单规则
- 任何语句都将是图中的一个节点
- 所有节点都有一条有向边,要么到达它们,要么离开它们,或者两者兼而有之。入口节点(第一个语句)仅具有传出边,出口节点仅具有传入边。
- 仅条件语句,如
if/else if
, switch
, loops
将有多个传出边缘。
- 从节点出来的所有路径都会在某个点汇聚,在最坏的情况下,它们会在退出处汇聚。
这是一个备忘单,可以更好地解释它
现在让我们将程序中的每个语句映射到一个数字,我们将使用该数字来表示 CFG 节点
int main() {
1. int i, grade = 0;
2. printf (" Enter points: \n");
3. scanf ("%d", &i);
4. if (i >= 50 && i <= 60)
5. grade = 5;
6. else if (i > 50 && i <= 60)
7. grade = 6;
8. else if (i > 60 && i <= 70)
9. grade = 7;
10. else if (i > 70 && i <= 80)
11. grade = 8;
12. else if (i > 80 && i <= 90)
13. grade = 9;
14. else if (i > 90 && i <= 100)
15. grade = 10;
16. char sign = ' ';
17. if (grade) {
18. int p = i % 10;
19. if (grade != 5) {
20. if (p >= 1 && p <= 3)
21. sign = '-';
22. else if (grade != 10 && (p >= 8 || p == 0))
23. sign = '+';
}
24. printf (" The grade is %d%c. \n", grade, sign);
}
25. return 0;
}
这是按照上面备忘单图中的指示创建的输出。请注意,节点 16 和 24 之前充当了许多条件节点的连接节点。
信用:我用过draw.io https://www.draw.io/创建上面发布的图像。
Note:绘制 CFG 的秘诀是对待独立于程序的每个语句,绘制它,然后将其入口和出口链接到图的其余部分。
以下是我遵循的一些初始步骤
- Statement 1, 2, and 3 are non conditional so I created three blocks linking them together.
- Statement 4 is a conditional statement. So I have to create 4 blocks for it. First for for statement 4, second and third for TRUE, FALSE edges, and lastly one for JOIN node. If true then statement 5 is run if not then we go to statement 6. From statement 5 we directly go to statement 16, which is our join node. Finally we link block 4 to bock 3's out going edge.
- Now statement 6 itself is a conditional statement so we again need 4 blocks for it. We already have one for itself block 6. Join node for it will be statement 16 as if it's condition is true then statement 7 is run and it directly goes to 16. Now we already have block 6 and 16 so we just need blocks for TRUE, FALSE branches which are statement 7 and 8.
依此类推,我们不断检查备忘单中适用的节点并单独创建它们,然后与以前的节点链接。