GATE CS 2017 Set 1 Q.43 (CS Q.43): Intermediate Code Generation, Data Flow Analysis and Code Optimization

Consider the following grammar:

stmt -> if expr then expr else expr; stmt | 0
expr -> term relop term | term
term -> id | number
id -> a | b | c
number -> [0-9]

where relop is a relational operator (e.g., $<, >, \dots$ ), 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 e1 then e2 else e3

has 2 control flow paths, $e_1 \to e_2$ and $e_1 \to e_3$ .

Your answer

Official answer and solution

Official answer: 1024
From: Official GATE 2017 answer key

Solution

Determine the control flow branching factor of each if statement generated by the grammar and compute the total number of paths for ten sequential if statements.

Consider the production for statements:

stmt -> if expr then expr else expr; stmt | 0

Each individual if expr then expr else expr; construct represents a conditional statement that branches into two mutually exclusive control flow execution paths:

Path 1: through the then branch.
Path 2: through the else branch.

The grammar rule stmt -> if expr ...; stmt chains these statements sequentially. A program $P$ containing ten if terminals consists of a sequence of 10 sequential conditional statements.

Because each of the 10 if statements branches independently into 2 paths, the total number of distinct control flow paths from the start of the program to the end is given by the product rule:

\text{Total Paths} = 2 \times 2 \times 2 \times \dots \times 2 = 2^{10} = 1024

Final answer

1024.0

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 1
Question: 43 of 65, printed as CS Q.43
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source