GATE CS 2017 Set 1 Q43 — Parsing (LL, LR)

To find the number of control flow paths in a program $P$ containing ten if terminals, we analyze the structure of the program generated by the given grammar.

1. Program Structure

The grammar rule for statements is:

$$\text{stmt} \rightarrow \textbf{if } \text{expr} \textbf{ then } \text{expr} \textbf{ else } \text{expr}; \text{stmt} \mid \epsilon$$

Here, $Ò$ represents the empty statement $\epsilon$. Since the recursion occurs at the end of the rule, a program $P$ containing ten if terminals consists of a sequence of $10$ independent if-then-else statements executed one after another:

$$\text{stmt}_1; \text{stmt}_2; \dots; \text{stmt}_{10}$$

2. Paths per Statement

As given in the example, a single if-then-else statement:

$$\textbf{if } e_1 \textbf{ then } e_2 \textbf{ else } e_3$$

has exactly $2$ control flow paths:

• Path 1: $e_1 \rightarrow e_2$ (when the condition is true)
• Path 2: $e_1 \rightarrow e_3$ (when the condition is false)

3. Total Control Flow Paths

Since the $10$ statements are executed sequentially, the choices made in each statement are independent of the others. By the product rule of combinatorics, the total number of control flow paths through the program is:

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