如何从此代码绘制控制流图? [英] How to draw a Control Flow Graph from this code?

问题描述

int main() {int i, 等级 = 0;printf("输入点数:\n");scanf ("%d", &i);如果 (i >= 50 && i <= 60) 等级 = 5;否则如果 (i > 50 && i <= 60) 等级 = 6;否则如果 (i > 60 && i <= 70) 等级 = 7;否则如果 (i > 70 && i <= 80) 等级 = 8;否则如果 (i > 80 && i <= 90) 等级 = 9;否则如果 (i > 90 && i <= 100) 等级 = 10;字符符号 = ' ';如果(等级){int p = i % 10;如果(等级！= 5){如果 (p >= 1 && p <= 3)符号 = '-';否则如果(等级 != 10 && (p >= 8 || p == 0))符号 = '+';}printf(" 成绩为 %d%c.\n", grade, sign);}返回0；}

如何从这段代码中绘制控制流图?如果有人可以展示这个过程，我将不胜感激.我能够从一个非常简单的案例中绘制 CFG，但我无法做到这一点.我还需要确定基本路径和多条件标准的测试.这不是一个家庭作业问题，我只是试图理解课程材料.谢谢.

解决方案

这是维基百科对 CFG 的定义，我知道你已经知道了，但为了完整起见，我把它放在这里

<块引用>

计算机科学中的控制流图 (CFG) 是一种表示，使用图形符号，所有可能通过一个路径的路径程序在执行过程中.

参考:

现在让我们将程序中的每个语句映射到一个数字，我们将用它来表示 CFG 节点

 int main() {1. int i，等级=0；2. printf("输入点数:\n");3. scanf(%d", &i);4. 如果 (i >= 50 && i <= 60)5. 等级=5；6. else if (i > 50 && i <= 60)7. 等级 = 6;8. else if (i > 60 && i <= 70)9. 等级 = 7;10. else if (i > 70 && i <= 80)11. 等级 = 8;12. else if (i > 80 && i <= 90)13. 等级 = 9;14. else if (i > 90 && i <= 100)15.等级=10；16. 字符符号 = ' ';17.如果(等级){18. int p = i % 10;19.如果(等级！= 5){20. 如果 (p >= 1 && p <= 3)21. 符号 = '-';22. else if (grade != 10 && (p >= 8 || p == 0))23. 符号 = '+';}24. printf("成绩为%d%c.\n",grade, sign);}25.返回0；}

这是按照上面备忘单图表中的说明创建的输出.请注意，节点 16 和 24 之前充当了许多条件节点的连接节点.

致谢:我已使用

语句 4 是条件语句.所以我必须为它创建 4 个块.第一个用于语句 4，第二个和第三个用于 TRUE、FALSE 边，最后一个用于 JOIN 节点.如果为真，则运行语句 5，否则，我们转到语句 6.从语句 5，我们直接转到语句 16，它是我们的连接节点.最后，我们将块 4 链接到块 3 的输出边缘.

现在语句 6 本身是一个条件语句，因此我们再次需要 4 个块.我们已经有一个自己的块 6.它的加入节点将是语句 16，就好像它的条件为真然后语句 7 运行，它直接进入 16.现在我们已经有了块 6 和 16，所以我们只需要块为 TRUE, FALSE 分支是语句 7 和 8.

依此类推，我们不断检查适用节点的备忘单，并单独创建它们，然后与之前的节点链接.

int main() {
    int i, grade = 0;
    printf (" Enter points: \n");
    scanf ("%d", &i);
    if (i >= 50 && i <= 60) grade = 5;
    else if (i > 50 && i <= 60) grade = 6;
    else if (i > 60 && i <= 70) grade = 7;
    else if (i > 70 && i <= 80) grade = 8;
    else if (i > 80 && i <= 90) grade = 9;
    else if (i > 90 && i <= 100) grade = 10;
    char sign = ' ';
    if (grade) {
        int p = i % 10;
        if (grade != 5) {
            if (p >= 1 && p <= 3)
                sign = '-';
            else if (grade != 10 && (p >= 8 || p == 0))
                sign = '+';
        }
        printf (" The grade is %d%c. \n", grade, sign);

    }
    return 0;
}

How do I draw Control Flow Graph from this code? I'll appreciate if someone can show the process. I am able to draw CFG from a very simple cases but I cannot do this one. Also I need to determine the basis paths and the tests for Multiple Condition criteria. It's not a homework question, I just try to understand the course material. Thanks.

解决方案

Here's the definition of CFG from Wikipedia, I know you already know this but for the sake of completeness I'm putting it here

A control flow graph (CFG) in computer science is a representation, using graph notation, of all paths that might be traversed through a program during its execution.

Ref: https://en.wikipedia.org/wiki/Control_flow_graph

Following is the definition of a Path

Path: a sequence of node on the CFG (static), including an entry node and an exit node; path segment: a subsequence of nodes along the path

Ref: http://web.cs.iastate.edu/~weile/cs513x/4.ControlFlowAnalysis.pdf

So the reason for drawing one would be to determine all possible paths taken by the program, which may help us determine things like test coverage without actually running the program (static analysis).

Following are the simple rules that we can follow to draw a CFG

1. Any statement will be a node in graph
2. All nodes have a directed edge either coming to them or going out of them or both. Entry node (first statement) has only outgoing edges and Exit node has only incoming edges.
3. only conditional statements like if/else if, switch, loops would have more than one outgoing edges.
4. All paths coming out of a node will converge at some point, in worst case they converge on Exit.

Here's a cheat sheet which explains it better

Now lets map every statement in your program to an number that we'll use to denote CFG nodes

   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;
  }

Here's the output created by following the directions from cheat sheet diagram above. Notice that node 16 and 24 are acting as join node for many conditional nodes before.

Credit: I have used draw.io to create images posted above.

Note: Secret to drawing a CFG is to treat every statement independent to the program, draw it and then link it's entry and exit to the rest of the graph.

Following are a few initial steps that I followed

1. Statement 1, 2, and 3 are non conditional so I created three blocks linking them together.
2. 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.
3. 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.

And so on, we keep checking the cheat sheet for the applicable nodes and create them in isolation then link then with previous nodes.

这篇关于如何从此代码绘制控制流图?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！