In: Computer Science
Software Testing Question
Program P2 CFG.
a) Identify the basic blocks for the following program P2 written in pseudo-code.
b) Draw the control flow graph.
Program P2
1) integer A, B;
2) input (A);
3) B = 1;
4) while (int i=1; i<=A; i++)
5) {
6) B = B * i;
7) if (B>13)
8) B = B / 2;
9) else 1
0) B = B * 2;
11) }
12) output (A,B);
13) end;
First we have to write the 3 Address Code for given pseudo code.
3 Address Code :
1. B = 1;
2. i = 1;
3. if ( i > A) go to 10.
4. t1 = B * 1;
5. if (t1 <= 13) go to 7.
6. t2 = t1/2;
7. t3 = t1*2;
8. t4 = i+1;
9. i = t4;
10. calling program
Basic Block :
A basic block is a sequence of three address statements where control enters at the beginning and leaves only at the end without any jumps or halts.
To find basic blocks we have to find leaders in the 3AC
How to find leaders
1) First instructions in the 3AC are leaders i.e, 1 and 2
2) Any instructions that is the target of the conditioal or unconditional jump. Statement 3 is conditional jump and it goes to 10. So statement 10 is leader. Similarly 7 is the leader.
3) Any instruction that immediately follows a conditional or unconditional jump. Statements 4, 6 are leaders.
4) The statements between one leader to next leader forms the basic block.