Consider two grammars G1 and G2 with the production rules given below: G1: S if\ E\ then\ S if\ E\ then\ S\ else\ S a E b G2: S if\ E\ then\ S M M if\ E\ then\ M\ else\ S c E b where if, then, else, a, b, c are the terminals. Which of the following option(s) is/are CORRECT? A) G1 is not LL(1) and G2 is LL(1). B) G1 is LL(1) and G2 is not LL(1). C) G1 and G2 are not LL(1). D) G1 and G2 are ambiguous.

Official answer: C) G1 and G2 are not LL(1).; D) G1 and G2 are ambiguous.. Explanation: ### Analysis of Grammar G1: - G1 is the classic "dangling-else" grammar. - For the string `if b then if b then a else a`, there are two distinct leftmost derivations / parse trees: 1. The `else` associates with the inner `if`. 2. The `else` associates with the outer `if`. - Since G1 generates a string with more than one parse tree, G1 is ambiguous [46]. - Any ambiguous grammar cannot be LL(1), so G1 is not LL(1). ### Analysis of Grammar G2: - Consider the string `if b then if b then c else if b then c`: - Parse Tree 1: S if\ E\ then\ S if\ b\ then\ M if\ b\ then\ if\ E\ then\ M\ else\ S if\ b\ then\ if\ b\ then\ c\ else\ (if\ E\ then\ S) - Parse Tree 2: S if\ E\ then\ S if\ b\ then\ (if\ E\ then\ S) if\ b\ then\ if\ b\ then\ M if\ b\ then\ if\ b\ then\ if\ E\ then\ M\ else\ S - Alternatively, consider the non-terminal S if\ E\ then\ S M. The non-terminal M has production M if\ E\ then\ M\ else\ S c. Both productions from S can generate sentences starting with `if`, causing First/First and Follow conflicts. - More directly, G2 does not unambiguously restrict the dangling-else structure because the else-branch in M produces S, which allows un-matched `if` statements inside it to cause ambiguity in nested conditionals. - Hence, G2 is also ambiguous and consequently not LL(1) [46]. Thus: - Option (C) is CORRECT (G1 and G2 are not LL(1)) [46]. - Option (D) is CORRECT (G1 and G2 are ambiguous) [46].

A) G1 is not LL(1) and G2 is LL(1).

B) G1 is LL(1) and G2 is not LL(1).

Compiler Design · Parsing

Official IIT answer key · IIT Guwahati · Audited Aug 2026

Take topic test

GATE CSE 2025 Set 2 Q51 · MSQ · 2 marks

Consider two grammars $G_1$ and $G_2$ with the production rules given below: $G_1: S \to if\ E\ then\ S \mid if\ E\ then\ S\ else\ S \mid a$ $E \to b$ $G_2: S \to if\ E\ then\ S \mid M$ $M \to if\ E\ then\ M\ else\ S \mid c$ $E \to b$ where $if, then, else, a, b, c$ are the terminals. Which of the following option(s) is/are CORRECT?

Select one or more options

Key concept

Parsing

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Parsing

GATE heavily tests the Parsing stage of compiler design across both Top-Down (LL(1), recursive descent) and Bottom-Up (LR(0), SLR(1), LALR(1), CLR(1)) paradigms. Key evaluation areas include computing FIRST and FOLLOW sets to populate parsing tables, detecting conflicts (Shift-Reduce, Reduce-Reduce), classifying grammars within the parsing power hierarchy, and executing item-set closure/goto operations. In recent years, items have shifted toward exact item counting via GOTO/CLOSURE in NAT format, reverse engineering grammar rules from FIRST/FOLLOW sets, and multi-concept MSQ verification.

Full Parsing guide →

More on Parsing

All 23 questions on Parsing →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Compiler Design · Parsing

Official IIT answer key · IIT Guwahati · Audited Aug 2026

Take topic test

GATE CSE 2025 Set 2 Q51 · MSQ · 2 marks

Consider two grammars $G_1$ and $G_2$ with the production rules given below: $G_1: S \to if\ E\ then\ S \mid if\ E\ then\ S\ else\ S \mid a$ $E \to b$ $G_2: S \to if\ E\ then\ S \mid M$ $M \to if\ E\ then\ M\ else\ S \mid c$ $E \to b$ where $if, then, else, a, b, c$ are the terminals. Which of the following option(s) is/are CORRECT?

Select one or more options

Key concept

Parsing

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Parsing

Full Parsing guide →

More on Parsing

All 23 questions on Parsing →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Step-by-step verified solution

Check you can still solve Parsing under a clock

More from GATE CSE 2025 Set 2

More on Parsing

Step-by-step verified solution

Check you can still solve Parsing under a clock

More from GATE CSE 2025 Set 2

More on Parsing

Step-by-step verified solution

Check you can still solve Parsing under a clock

More from GATE CSE 2025 Set 2

More on Parsing

Share this solution

Step-by-step verified solution

Check you can still solve Parsing under a clock

More from GATE CSE 2025 Set 2

More on Parsing

Share this solution