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

2 votes
2 votes

if e1then e2 else e3 
has 2 control flow paths. e1→e2 and e1→e3

One if-condition has two possibilities.

So, for 10 if-conditions

__, __, __, __, __, __, __, __, __, __

We have 2 possibilities for each slot.

 

=> $2*2*2*2*2*2*2*2*2*2=1024$

1 votes
1 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.

0 votes
0 votes
  • One if statement: 2 paths (true or false)
  • Two if statements: 2 * 2 = 4 paths (true-true, true-false, false-true, false-false)
  • Three if statements: 2 * 2 * 2 = 8 paths
  • Ten if statements: 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 1024 paths
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 \}$ ...