What are common examiner traps in Compiler Design?

Assuming LALR(1) state merging can introduce Shift-Reduce conflicts (it can only introduce Reduce-Reduce conflicts). Placing LR(0) reduce actions only under FOLLOW sets instead of under all input terminals (SLR places in FOLLOW, LR(0) places in all columns). Forgetting to include transitions when computing CLOSURE for non-terminals that derive (resulting in undercounting items). Overlooking indirect left recursion (e.g., S → Aa with A → Sc). Assuming an ambiguous grammar can be parsed by an LR(1) or LL(1) parser; any ambiguous grammar fails all deterministic parser checks. Failing to carry forward lookahead symbols when expanding non-terminals in LR(1) closure calculations ([A → · B , a] gives lookahead FIRST( a)). Forgetting to include \ in FOLLOW(S) for the start symbol S$. Omitting FOLLOW(A) when propagating to FOLLOW(B) if A → B with nullable or B as the rightmost symbol.

GATE CSE Compiler Design (CD) PYQs

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… Read the guide

Start mock · 30 Qs

Topics: 10
Questions: 88
Marks / paper: 5.2
Asked: since 2011

These are the 88 GATE CSE Compiler Design PYQs (since 2011), grouped topic-wise with solutions. See all GATE CSE PYQs or GATE CSE question papers by year.

By year

Jump to the first question from each year’s paper.

What GATE tests in Compiler Design

Concepts, patterns, formulas and traps distilled from past papers.

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. In GATE CS, Intermediate Code Generation (ICG) is tested through both theoretical/architectural concepts and precise algorithmic computations. In GATE CS, this foundational topic tests grammar analysis, parsing techniques, and compiler phase interactions through both theoretical properties and computational mechanics.

Core concepts

FIRST and FOLLOW set calculation
LL(1) parsing table construction and conflict resolution
Elimination of direct and indirect left recursion
Left factoring and non-backtracking predictive parsing
LR(0) canonical items, CLOSURE, and GOTO function computation
SLR(1) parsing table construction using FOLLOW sets
LR(1) / CLR(1) items with propagated lookaheads
LALR(1) core-merging criteria and generation of Reduce-Reduce conflicts
Shift-Reduce (S-R) vs Reduce-Reduce (R-R) conflicts
Parsing power hierarchy: LL(1) ⊂ SLR(1) ⊂ LALR(1) ⊂ CLR(1)
Ambiguity in grammars (e.g., dangling-else) and its impact on determinism
Operator precedence and associativity derived from recursive productions

How questions show up

Canonical LR Item and GOTO Set State Construction
CommonNAT2 marks2024, 2021
Given an augmented grammar, compute the CLOSURE of an initial set and evaluate multi-step GOTO transitions to count the exact number of items in a resulting state.
Grammar Classification in the LR/LL Hierarchy
CommonMCQ2 marks2025, 2022, 2015
Determine whether a given context-free grammar is LL(1), SLR(1), LALR(1), or CLR(1) by identifying specific conflicts (FIRST/FIRST, FIRST/FOLLOW, Shift-Reduce, or Reduce-Reduce) across states.
FIRST/FOLLOW Computation and LL(1) Table Population
CommonMCQ2 marks2024
Compute FIRST and FOLLOW sets to fill in blank cells of an LL(1) parsing table or reconstruct missing grammar productions from given FIRST/FOLLOW constraints.
Conflict Detection in LR Item Sets
CommonMCQ2 marks2026, 2014, 2013
Analyze either a single canonical item set or all states of an LR(0)/SLR(1)/LALR(1) automaton to count or identify Shift-Reduce (S-R) or Reduce-Reduce (R-R) conflicts under specific lookaheads.
Grammar Transformations: Left Recursion and Associativity
CommonMCQ1 marks2017, 2016, 2014
Identify direct/indirect left recursion, convert left-recursive grammars to right-recursive forms, or derive operator precedence/associativity directly from grammar structure.
Theoretical Properties and Hierarchy of Parsers
OccasionalMSQ1 marks2026, 2024, 2022, 2021
Evaluate conceptual assertions concerning deterministic CFGs, parser power comparisons (LL vs SLR vs LALR vs CLR), parsing time complexity (e.g., CYK $O(n^3)$ ), and state merging rules.

High-yield formulas

Maximum Bottom-Up Reductions

\text{Max Reductions} = n - 1

Used when parsing a string of $n$ tokens with a bottom-up parser on a grammar containing no $\epsilon$ -productions and no unit-productions.

Immediate Left Recursion Elimination

A \rightarrow A\alpha \mid \beta \implies A \rightarrow \beta A^{\prime}, \quad A^{\prime} \rightarrow \alpha A^{\prime} \mid \epsilon

Used to transform directly left-recursive productions into equivalent right-recursive productions suitable for top-down LL(1) parsing.

General Context-Free Parsing Worst-Case Time

T(n) = O(n^3)

Used to denote the worst-case time complexity of universal CFG parsers (e.g., CYK or Earley's algorithm) for a string of length $n$ .

LALR State Merge Condition

\text{Core}(I_j) = \text{Core}(I_k) \iff \{A \rightarrow \alpha\cdot\beta \mid [A \rightarrow \alpha\cdot\beta, a] \in I_j\} = \{A \rightarrow \alpha\cdot\beta \mid [A \rightarrow \alpha\cdot\beta, b] \in I_k\}

Used to determine if two LR(1) item sets can be merged to form a single LALR(1) state.

FOLLOW Set Propagation Rule

\text{FOLLOW}(B) = \bigcup_{A \rightarrow \alpha B \beta} ((\text{FIRST}(\beta) \setminus \{\varepsilon\}) \cup (\text{if } \varepsilon \in \text{FIRST}(\beta) \text{ then } \text{FOLLOW}(A)))

Used when determining the terminal symbols that can appear immediately to the right of a non-terminal $B$ across all sentential forms.

LL(1) Parsing Table Construction Rule

\text{For } A \rightarrow \alpha:\; \forall a \in \text{FIRST}(\alpha) \setminus \{\varepsilon\},\; M[A, a] \leftarrow A \rightarrow \alpha;\quad \text{if } \varepsilon \in \text{FIRST}(\alpha),\; \forall b \in \text{FOLLOW}(A),\; M[A, b] \leftarrow A \rightarrow \alpha

Used to place production $A \rightarrow \alpha$ into table cells $M[A, t]$ for terminals and the end-marker $\$ .

LR(0) Closure Function

\text{closure}(I) = I \cup \{[B \rightarrow .\gamma] \mid [A \rightarrow \alpha . B \beta] \in \text{closure}(I), B \rightarrow \gamma \in G\}

Used recursively whenever the dot directly precedes a non-terminal symbol in any LR(0) item of the set.

LR(0) Goto Function

\text{goto}(I, X) = \text{closure}(\{[A \rightarrow \alpha X . \beta] \mid [A \rightarrow \alpha . X \beta] \in I\})

Used to compute the transition state on terminal or non-terminal $X$ from an item set $I$ .

Examiner traps in Compiler Design

Assuming LALR(1) state merging can introduce Shift-Reduce conflicts (it can only introduce Reduce-Reduce conflicts).
Placing LR(0) reduce actions only under FOLLOW sets instead of under all input terminals (SLR places in FOLLOW, LR(0) places in all columns).
Forgetting to include transitions when computing CLOSURE for non-terminals that derive (resulting in undercounting items).
Overlooking indirect left recursion (e.g., S → Aa with A → Sc).
Assuming an ambiguous grammar can be parsed by an LR(1) or LL(1) parser; any ambiguous grammar fails all deterministic parser checks.
Failing to carry forward lookahead symbols when expanding non-terminals in LR(1) closure calculations ([A → · B , a] gives lookahead FIRST( a)).
Forgetting to include \ in FOLLOW(S) for the start symbol S$.
Omitting FOLLOW(A) when propagating to FOLLOW(B) if A → B with nullable or B as the rightmost symbol.

Paper trends

Shift from basic declarative MCQs on parser power to procedural NAT questions requiring exact item counts after multiple GOTO and CLOSURE steps.
2024, 2021
Increased use of MSQ formats to simultaneously test parser definitions, non-backtracking nature of predictive parsers, left-factoring necessities, and grammar ambiguity.
2026, 2025, 2024
Introduction of inverse/constraint-satisfaction problems, such as reconstructing missing production rules from partial grammars and complete FIRST/FOLLOW sets.
2024
LL(1) parsing questions in 2012 were posed as linked 2-mark MCQs that chained FIRST/FOLLOW evaluation directly into parse table cell verification.
2012

Topics