GATE CSE 2017 Set 1 | Question: 43

Question

Consider the following grammar:

• stmt $\rightarrow$ if expr then expr else expr; stmt | $Ò$
• 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., $< , >,\ldots),$ $Ò$ 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$. 

Comments

it was 10 statements.

---

Why product rule is used not Sum rule ??

---

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.

---

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.

Answer 1

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.

Comments

So it means we can think like execution of each if block is independent of other block.It means all are independent events.

So as per product rule 2*2*2*-----------(10 times)=1024 flow paths possible.

---

Basically they are checking if we read every character of question with 100% attention because once we miss $;$ we will land to a wrong answer.

---

They are nested just because of the nonterminal present in the last of the first production? and that’s why here every possible control flow path is considered?

what changes in question can be made , so that the we can get all the if statements independently?

@Abhrajyoti00 @Kabir5454 @Aditya_

Answer 2

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.

Comments

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

---

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

Answer 3

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.

Comments

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.

---

yes but you can see they are executed sequentially and not nested, so rest of the if's will execute independently of the other

---

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.

Answer 4

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

Comments

I also got 20

---

Even I think it should be 20. Because nesting is not possible for the given grammar.

---

@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