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.

Compiler Design

10 topics · 88 Qs · 5.2 marks/paper · since 2011

Start mock (30 Qs)

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, Interm… Guide

Topics

Open a topic to browse, or practice it timed.

By year

Jump to the first question from that paper.

Subject guide

What does GATE test in Compiler Design?

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

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.

How questions show up

Canonical LR Item and GOTO Set State Construction
common · NAT · 2 marks · 2024, 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
common · MCQ · 2 marks · 2025, 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
common · MCQ · 2 marks · 2024
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
common · MCQ · 2 marks · 2026, 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
common · MCQ · 1 marks · 2017, 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
occasional · MSQ · 1 marks · 2026, 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.