The Gateway to Computer Science Excellence
+32 votes
6.2k views

Consider the following grammar:

  • stmt $\rightarrow$ if expr then expr else expr; stmt | $0$
  • expr $\rightarrow$ term relop term | term
  • term $\rightarrow$ id | number
  • id $\rightarrow$ a | b | c
  • number $\rightarrow [0-9]$ 

where relop is a relational operator (e.g.. $<$ . $>$ ...). $0$ refers to the empty statement, and if, then, else are terminals. 
Consider a program $P$ following the above grammar containing ten if terminals. The number of control flow paths in $P$ is________ . For example. the program 
if $e_1$ then $e_2$ else $e_3$ 
has $2$ control flow paths. $e_1 \rightarrow e_2$ and $e_1 \rightarrow e_3$. 

in Compiler Design by Veteran (422k points)
edited by | 6.2k views
+1
Why product rule is used not Sum rule ??
+3
It is not If e1 then e2 or e3 OR If e4 then e5 or e6. There are 10 if statements and we have conditions between them and not options. If you do OR then it will be single if statement and not 10.
+4
A larger event of 10 statements is broken down into 1 statement each. Now each statement has 2 options. statement 1 (2 options) AND statement 2(2 options)...... = 2^10.

6 Answers

+53 votes
Best answer

This question is picked from area of Counting in Combinatorics.

Given:
if $e_1$ then $e_2$ else $e_3$ has $2$ control flow paths $e_1 \rightarrow e_2$ and $e_1 \rightarrow e_3$.
(Meaning of "how many control flow" for if structure is clearly mentioned)

What is asked:
Number of control flow paths for $10$ if terminals?

Solution:
To get $10$ if's we need to use grammar to get,
         if <expr> then <expr> else <expr> ; stmt
         if <expr> then <expr> else <expr> ; if <expr> then <expr> else <expr> ; stmt
         ..............
         ..............
         ..............
         (keep doing it $10$ times to get $10$ if's)
Observe that there is a semi-colon after every if structure.

We know that every if structure has $2$ control flows as given in question. Hence,
        We have $2$ control flow choices for $1$st if terminal.
        We have $2$ control flow choices for $2$nd if terminal.
        ............
        ............
        ............
        We have $2$ control flow choices for $10$th if terminal.
        
By using multiplicative law of counting we get,
        Total choices as $2*2*2*2*2$......$10$ times $= 2^{10} = 1024$

Once again, one need not know "what control flow" is, but needs to know "how many control flows" are in if structure which is given in question.

by (271 points)
edited by
+10
Why are you not using Sum Rule in counting?
+2

The Number of Control Path in P ______

AND

The Number of Control Path Possible in P ______

Isn't it both represent different meaning?

0

@Mr_22B  Now as P is not given in questions so we can assume it is POSSIBLE paths only. Had P be given in questions then it would be the other way

+18 votes
I will take a small example to make it clear.

Taking 2 if terminals

If expr then e1 else e2;

If expr then e3 else e4;

So there can be 4 control flow paths.

e1 e3

e1  e4

e2  e3

e2  e4

Now u can consider  10 if terminals.

The total control flow paths=2^10=1024.
by Active (3.5k points)
0

Arjun  sir please tell me is my explanation of control flow path is correct or not?

+1
I think you are totally correct in explaining because  here no correlation is there between any if then else. So each "if else then" have 2 options to take independent to other thus 2(1st) * 2(2nd).....so on it will be 1024 ways to select if else path ways for program P
+17 votes

each if-else condition leads to two different paths, there are 10 if-else conditions one after the other, therefore totally 210  = 1024 paths possible

by Active (1.4k points)
0
yes i think correct..i also marked same
+3
i have one doubt..if is dreived only fro stmt..and it is not nested..how it can be one after other? how 1024..why not 20
+8

yes, it should be 20 ;as non-terminal stmnt is independent ...can't be nested ....

it occurs only like this (for 2 if terminals)

if e1 else e2 else e3

next as

if e4 else e5 else e6

So, control paths will be e1-> e2,e1-> e3,e4-> e5,e4-> e6 (only four control paths for 2 if statements)

Correct me if I am Wrong!

0
smriti i thinked the same
0
stmt  after ;
0

and in q it is not mentioned possible..it directly asks for the path...

but whenever we go for any permutation of 2that is like Possible path

0
I also got 20
0
Even I think it should be 20. Because nesting is not possible for the given grammar.
0
@Arjun Sir, @Uddipto pls correct me if I am wrong. 2^x is the total possible path. But for control path during the drerivation we have 2 choices for every if at that instant. Thus it should be 2*2*2* ... = 20
+15 votes

A control flow path/control flow graph is a graphical representation of all paths that might be traversed through a program during its execution.

Now each $if$ statement has 2 outcomes ~ either true or false.

As per the grammar each if statement is independent of the other.

Consider 3 if statements

if e1 then e2 $(T)$ else e3 $(F)$;

if e4 then e5 $(T)$ else e6 $(F)$;

if e7 then e8 $(T)$ else e9 $(F)$;

Now following are the paths the program goes through during its execution :

$1. \ TTT$

$2. \ TTF$

$3. \ TFT$

$4. \ TFF$

$5. \ FTT$

$6. \ FTF$

$7. \ FFT$

$8. \ FFF$

So for $n = 3$ we have $2^{3} = 8$ control flow paths, hence for $n = 10$ we will have total $2^{10} = 1024$ control flow paths.

by Boss (12.1k points)
0
Control depends only on If(condition) and doesn`t depend on statment or else condition.
So
$e_1\Rightarrow T \\ e_1\Rightarrow  F $

is what all we care about.
0
yes but you can see they are executed sequentially and not nested, so rest of the if's will execute independently of the other
0
ya.....this one is correct explanation ; Initially i also thought it was 20. But they asked what are the total possible control paths we can have.
+7 votes

people considering 2.2....=210  but tha happens when each 2 possiblity depends on the prevois possibility(counting rule---like topological sorting)

here for the Non-terminal expr no NESTING is done..

it will be like this..

for 3 if statement 

        every if statement is independent of previous one

so 20 should be the answer 

by Boss (17.9k points)
+2
but since 10 if else statements are written one after other than also for every statement you have 2 choices right?

say you choose path 1 from 1st if then path 1 from 2nd if(case 1)

                        path 1 from 1st if then path 2 from 2nd if(case 2)

                        path 2 from 1st if then path 1 from 2nd if(case 3)

                        path 2 from 1st if then path 2 from 2nd if(case 4)

similarly you have 2*2*2*2.......(10 times) no of choices...what nesting has to do here its like you have 10 boxes in sequence and each has 2 different ball you have to tell number of sequence of choosing them serially right?
0
no if i select path 1 from 1st thats it.based on that i can not selet any path from2..1 and 2 is completely different.. here we have

2 choice for 1 if

2 choice for 2 if

2 choice for 3rd if

---------------

2 choice for 10th if

so 10.2 hoice for  10 tota if
0
one after another does not always mean next one is dependent on the previous one
0
but it ask number of control flow paths...thats how we do it i think in Software Engineering subject for making control flow graph..nd obviously its a program of 10 statements dependent or not does not matter..what matters is from beginning to end how may paths you have
0
that means the grammar given has no role?
0
its more like reasoning and counting question rather than application of core compiler concept...
0
i am also saying the same ..here sum rule of counting applies ..as they are independent in the grammar
0
so you are saying if there are 10 statements one after other each having 2 paths if asked total possible ways to move from begining to end is 20?
+5
sum rule is applied if you have to choose either statement one or 2 or....10...even if program need to check 2 statements product rule comes into picture....and  if program checks one if statement and executes it then does the program stops or checks further?? here you have to go through every if till end
0
yes it may be the case.. if we selct path 2 suppose in my diagram..that is an end ..no way to go 3 or 4 from there
0
2 if-else statements will obviously be independent if 2nd is not using data of first...write a program in C and write 10 if else statement one after other...write printf("A"); in each....you will find 10 A's printed at end not 1
0
@Uddipto in your example you are doing nesting rt?

And a path differs even if one edge is different.
0
i am doing nesting of stmt ..not nesting of expr,on which solely if depends....so @Arjun sir you say it is 1024?
0
understand one thing.in ,my diagram..if i get into path 2... there is no way i can go to path 3..coz that is completely different if
0
although its independent but if you see path for each if we have two choices so for similarly 10 if 2 choices each...and bdw if 1st if takes path from e1-e2 second if now has 2 choices similary remaining 8 have 2 choices each...so what you can say is that..no. of possible control flow paths is product of all 10 people choices that is 2^10
0 votes

The first thing we need to know is given program(if statements) executes sequentially or in any order, so the answer is the program has been already written & given to us and now we can not decide which "if" statement will execute in which order, so it executes sequentially.
Now 1st  "if" statement has 2 control flow paths, either it can direct its path to "then" statement or "else" statement. Similarly 2nd "if" statement has to 2 control flow paths. Now if we look closely, using these 2 "if" statement we can have 4 control flow paths.
1) 1st "if" -> 1st "then" -> 2nd "if" -> 2nd "then"
2) 1st "if" -> 1st "then" -> 2nd "if" -> 2nd "else"
3) 1st "if" -> 1st "else" -> 2nd "if" -> 2nd "then"
4) 1st "if" -> 1st "else" -> 2nd "if" -> 2nd "else"

Similarly for 10 "if" statements we can have 2^10=1024 control flow paths.

by Active (3.2k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,157 answers
193,767 comments
93,741 users