Statement for Linked Answer Questions 52 and 53: For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. is the empty string, \$ indicates end of input, and separates alternate right hand sides of productions. S aAbB bAaB A S B S The appropriate entries for E1, E2, and E3 are A) E1: S aAbB,\ A S E2: S bAaB,\ B S E3: B S B) E1: S aAbB,\ S E2: S bAaB,\ S E3: S C) E1: S aAbB,\ S E2: S bAaB,\ S E3: B S D) E1: A S,\ S E2: B S,\ S E3: B S

Official answer: C) E1: S aAbB,\ S E2: S bAaB,\ S E3: B S. Explanation: To find the entries of the LL(1) parsing table M[A, a]: 1. For non-terminal S: - Production S aAbB: FIRST(aAbB) = \a\, so add S aAbB to M[S, a]. - Production S bAaB: FIRST(bAaB) = \b\, so add S bAaB to M[S, b]. - Production S : since FIRST( ), add S to M[S, t] for all t FOLLOW(S) = \a, b, \\, i.e., M[S, a], M[S, b], and M[S, \]. Therefore: - E1 = M[S, a] = \S aAbB,\ S \ - E2 = M[S, b] = \S bAaB,\ S \ 2. For non-terminal B: - Production B S: FIRST(S) = \a, b, \. - Add B S to M[B, a] and M[B, b]. - Since S * , add B S to M[B, t] for all t FOLLOW(B) = \a, b, \\, which includes M[B, \]. Therefore: - E3 = M[B, \] = \B S\$ This matches option (C).

A) E1: S aAbB,\ A S E2: S bAaB,\ B S E3: B S

B) E1: S aAbB,\ S E2: S bAaB,\ S E3: S

C) E1: S aAbB,\ S E2: S bAaB,\ S E3: B S

D) E1: A S,\ S E2: B S,\ S E3: B S

Compiler Design · Parsing

Official IIT answer key · IIT Delhi · Audited Aug 2026

Take topic test

GATE CSE 2012 Q53 · MCQ · 2 marks

Statement for Linked Answer Questions 52 and 53: For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. $\varepsilon$ is the empty string, $\$$ indicates end of input, and $\mid$ separates alternate right hand sides of productions. $S \rightarrow aAbB \mid bAaB \mid \varepsilon$ $A \rightarrow S$ $B \rightarrow S$ The appropriate entries for E1, E2, and E3 are

Select an option to check

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 Delhi · Audited Aug 2026

Take topic test

GATE CSE 2012 Q53 · MCQ · 2 marks

Statement for Linked Answer Questions 52 and 53: For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. $\varepsilon$ is the empty string, $\$$ indicates end of input, and $\mid$ separates alternate right hand sides of productions. $S \rightarrow aAbB \mid bAaB \mid \varepsilon$ $A \rightarrow S$ $B \rightarrow S$ The appropriate entries for E1, E2, and E3 are

Select an option to check

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 2012

More on Parsing

Step-by-step verified solution

Check you can still solve Parsing under a clock

More from GATE CSE 2012

More on Parsing

Step-by-step verified solution

Check you can still solve Parsing under a clock

More from GATE CSE 2012

More on Parsing

Share this solution

Step-by-step verified solution

Check you can still solve Parsing under a clock

More from GATE CSE 2012

More on Parsing

Share this solution