edited by
20,176 views
57 votes
57 votes

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$. 

edited by

11 Answers

Best answer
93 votes
93 votes

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.

edited by
46 votes
46 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.
30 votes
30 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.

18 votes
18 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

Answer:

Related questions

20 votes
20 votes
7 answers
2
Arjun asked Feb 14, 2017
6,684 views
Consider the following grammar:$P\rightarrow xQRS$$Q\rightarrow yz\mid z$$R\rightarrow w\mid \varepsilon$$S\rightarrow y$What is FOLLOW($Q$)?$\left \{ R \right \}$ ...