GATE CS 2017 Set 1 — Question 43
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.NAT+2 / -0MediumBasic Blocks & Flow GraphsCode OptimizationCompiler DesignControl FlowC ProgrammingProgramming & Data Structures
Compiler Design → Code Optimization → Basic Blocks & Flow Graphs
Last updated
Question
Consider the following grammar:where relop is a relational operator (e.g., <, >, ...),
stmt -> if expr then expr else expr; stmt | ò
expr -> term relop term | term
term -> id | number
id -> a | b | c
number -> [0-9]
ò refers to the empty statement, and if, then, else are terminals.Consider a program following the above grammar containing ten if terminals. The number of control flow paths in is _______. For example, the programif e1 then e2 else e3has 2 control flow paths, and .Correct answer
1024 to 1024
Solution
The grammar for
For ten
stmt is defined recursively as:This structure represents a sequence of if-then-else blocks. Each if construct introduces a branching point where the control flow splits into two paths (one for the then clause and one for the else clause) and then merges back to execute the subsequent stmt.Since the program contains ten if terminals, it consists of a sequence of 10 such if-then-else blocks. The total number of control flow paths in a sequence of independent branching blocks is the product of the number of paths in each block.For one if block, there are 2 paths.For ten
if blocks in sequence, the total number of paths is:Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Code Optimization
2026 Set 2 Q12The set T represents various traversals over binary tree. The set S represents the order of…2026 Set 2 Q17In C runtime environment, which one of the following is stored in heap?2026 Set 2 Q19Consider the following three ANSI-C programs, P1, P2, and P3. P1 [code] P2 [code] **P3**…2026 Set 1 Q23Let be an odd number greater than 100. Consider a binary minheap with elements stored in an…2026 Set 1 Q24Consider a hash table that is initially empty. The hash table is maintained…