edited by
25,472 views
41 votes
41 votes

Consider the intermediate code given below.

(1) i=1    
(2) j=1    
(3) t1 = 5 * i    
(4) t2 = t1 + j    
(5) t3 = 4 * t2    
(6) t4 = t3    
(7) a[t4] = -1    
(8) j = j + 1    
(9) if j <= 5 goto (3)    
(10) i = i +1    
(11) if i < 5 goto (2)

The number of nodes and edges in control-flow-graph constructed for the above code, respectively, are

  1. $5$ and $7$
  2. $6$ and $7$
  3. $5$ and $5$
  4. $7$ and $8$
edited by

7 Answers

Best answer
66 votes
66 votes

Answer is $6,7$ if we add an explicit start and end nodes. This follows from the definition of CFG in the below IITM link

http://www.cse.iitm.ac.in/~krishna/cs3300/pm-lecture1.pdf

But many of the standard books/universities don't follow this definition. 

edited by
7 votes
7 votes

Following are the Candidates for leader :

1.. First statement is a leader 

2. the target of unconditional and conditional instruction is a leader 

3. Statement following  unconditional and conditional instruction is a leader .

So let us count number of nodes :

Node1 :statement 1 

node 2 : Statement 2 

Node 3 : Statement 3 

node 4 : statement 4--9 

node 5 : Statement 10-11

Plus if i add one start and end nodes 

So in all there will be 7 nodes 

And the number of edges : 

We know that in a simple  connected graph with n nodes we have n-1 edges,

So here with 7 nodes we would have 6 edges + 2 edges ( GOTO 3 and GOTO 2--->backedges  ) = 8 edges .

1 flag:
✌ Edit necessary (Ray Tomlinson “incorrect solution please edit it”)
5 votes
5 votes

 4 NODES 5-edges

and if we add start and end nodes then

6-nodes and 7-edges

edited by
Answer:

Related questions

34 votes
34 votes
3 answers
1
go_editor asked Feb 12, 2015
6,896 views
Match the following:$$\begin{array}{ll|ll}\hline \text{P.} & \text{Lexical analysis} & \text{1.} & \text{Graph coloring} \\\hline \text{Q.} & \text{Parsing} & \text{2.}&...
80 votes
80 votes
7 answers
2
makhdoom ghaya asked Feb 13, 2015
28,737 views
The least number of temporary variables required to create a three-address code in static single assignment form for the expression $q + r / 3 + s - t * 5 + u * v/w$ is_...