What are common examiner traps in Parsing?

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. Failing to propagate FOLLOW sets through cyclic derivations (e.g., A → S implies FOLLOW(A) ⊆ FOLLOW(S)). Placing an -production in table cells corresponding to its FIRST set rather than the LHS non-terminal's FOLLOW set. Confusing the LHS non-terminal of an indirect derivation (e.g., writing S → into M[B, a] instead of B → S when B ⇒* ). Forgetting transitive/recursive closure expansion when added productions also have a dot before a non-terminal (e.g., expanding R introduces [R → .P], which must then trigger adding productions of P). Including items where the dot shift does not match the transition symbol. Off-by-one errors by counting the shifted kernel item only and omitting the newly generated closure items.

GATE CSE Parsing PYQs

Medium yield28.1% of 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… Read the guide

Take topic test

Questions: 23
Asked: since 2012
Total marks: 38
Marks / paper: 1.5

23 GATE CSE Parsing PYQs with solutions, from Compiler Design. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

GATE CSE 2026 Set 1 · Q28Which of the following statements is/are true?MSQ1 markEasySolve
GATE CSE 2026 Set 2 · Q41Consider the canonical $LR(0)$ parsing of the grammar below using terminals $\{a, b, c\}$ and non-terminals $\{A, B, C, S\}$ with $S$ as the start symbol. $S \rightarrow ACB$ $A \rightarrow aA \mid \epsilon$ $C \rightarrow cC \mid \epsilon$ $B \rightarrow bB \mid b$ Which one of the following options…MCQ2 marksMediumSolve
GATE CSE 2025 Set 2 · Q40Given a Context-Free Grammar $G$ as follows: $S \rightarrow Aa \mid bAc \mid dc \mid bda$ $A \rightarrow d$ Which ONE of the following statements is TRUE?MCQ2 marksMediumSolve
GATE CSE 2025 Set 2 · Q51Consider 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…MSQ2 marksMediumSolve
GATE CSE 2024 Set 1 · Q26Which of the following is/are Bottom-Up Parser(s)?MSQ1 markEasySolve
GATE CSE 2024 Set 1 · Q38Consider the following grammar $G$ , with $S$ as the start symbol. The grammar $G$ has three incomplete productions denoted by (1), (2), and (3). $S \rightarrow daT \mid \underline{\quad (1) \quad}$ $T \rightarrow aS \mid bT \mid \underline{\quad (2) \quad}$ $R \rightarrow \underline{\quad (3) \quad} \mid \epsilon$ …MCQ2 marksMediumSolve
GATE CSE 2024 Set 2 · Q40Consider the following context-free grammar where the start symbol is $S$ and the set of terminals is $\{a,b,c,d\}$ . $\begin{aligned} S &\to AaAb \mid BbBa A &\to cS \mid \epsilon B &\to dS \mid \epsilon \end{aligned}$ The following is a partially-filled LL(1) parsing table. Which one of the following options…MCQ2 marksMediumDiagramSolve
GATE CSE 2024 Set 2 · Q65Consider the following augmented grammar, which is to be parsed with a SLR parser. The set of terminals is $\{a,b,c,d,\#,@\}$ $\begin{aligned} S^{\prime} &\rightarrow S S &\rightarrow SS \mid Aa \mid bAc \mid Bc \mid bBa A &\rightarrow d\# B &\rightarrow @ \end{aligned}$ Let $I_0 = CLOSURE(\{S^{\prime} \rightarrow \bullet S\})$ …NAT2 marksMediumSolve
GATE CSE 2022 · Q13Which one of the following statements is TRUE?MCQ1 markMediumSolve
GATE CSE 2022 · Q29Consider the augmented grammar with $\{+, *, (, ), id\}$ as the set of terminals. $S^{\prime} \rightarrow S$ $S \rightarrow S + R \mid R$ $R \rightarrow R * P \mid P$ $P \rightarrow (S) \mid id$ If $I_0$ is the set of two $LR(0)$ items $\{[S^{\prime} \rightarrow S.], [S \rightarrow S. + R]\}$ , then $goto(closure(I_0), +)$ …NAT1 markEasySolve
GATE CSE 2021 Set 1 · Q5Consider the following statements. $S_1$ : Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1). $S_2$ : For any context-free grammar, there is a parser that takes at most $O(n^3)$ time to parse a string of length $n$ . Which one of the following options is…MCQ1 markMediumSolve
GATE CSE 2021 Set 2 · Q51Consider the following augmented grammar with $\{\#, @, \lt, \gt, a, b, c\}$ as the set of terminals. $S^{\prime} \to S$ $S \to S\#cS$ $S \to SS$ $S \to S@$ $S \to \lt S \gt$ $S \to a$ $S \to b$ $S \to c$ Let $I_0 = \text{CLOSURE}(\{S^{\prime} \to \bullet S\})$ . The number of items in the set $\text{GOTO}(\text{GOTO}(I_0, \lt), \lt)$ …NAT2 marksMediumSolve
GATE CSE 2017 Set 2 · Q32Consider the following expression grammar $G$ : $\begin{aligned} \text{E} &\rightarrow \text{E} - \text{T} \mid \text{T} \\ \text{T} &\rightarrow \text{T} + \text{F} \mid \text{F} \\ \text{F} &\rightarrow (\text{E}) \mid \text{id} \end{aligned}$ Which of the following grammars is not left recursive, but is…MCQ2 marksEasySolve
GATE CSE 2016 Set 1 · Q45The attributes of three arithmetic operators in some programming language are given below. The value of the expression $2 - 5 + 1 - 7 * 3$ in this language is _______.NAT2 marksEasyDiagramSolve
GATE CSE 2016 Set 2 · Q45Which one of the following grammars is free from *left recursion*?MCQ2 marksEasySolve
GATE CSE 2015 Set 3 · Q16Among simple LR (SLR) , canonical LR, and look-ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful , in that order?MCQ1 markEasySolve
GATE CSE 2015 Set 3 · Q31Consider the following grammar $G$ $\begin{aligned} S &\rightarrow F \mid H F &\rightarrow p \mid c H &\rightarrow d \mid c \end{aligned}$ where $S, F$ , and $H$ are non-terminal symbols, $p, d$ , and $c$ are terminal symbols. Which of the following statement(s) is/are correct? S1. LL(1) can parse all…MCQ2 marksMediumSolve
GATE CSE 2014 Set 1 · Q34A canonical set of items is given below $S \rightarrow L. > R$ $Q \rightarrow R.$ On input symbol < the set hasMCQ2 marksEasySolve
GATE CSE 2014 Set 2 · Q17Consider the grammar defined by the following production rules, with two operators $*$ and $+$ $S \rightarrow T * P$ $T \rightarrow U \mid T * U$ $P \rightarrow Q + P \mid Q$ $Q \rightarrow Id$ $U \rightarrow Id$ Which one of the following is TRUE?MCQ1 markEasySolve
GATE CSE 2013 · Q9What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type $\text{A} \rightarrow \epsilon$ and $\text{A} \rightarrow \text{a}$ ) to parse a string with $n$ tokens?MCQ1 markMediumSolve
GATE CSE 2013 · Q40Consider the following two sets of LR(1) items of an LR(1) grammar. $\begin{array}{ll} X \rightarrow c.X, \text{ } c/d & X \rightarrow c.X, \text{ } \$ \\ X \rightarrow .cX, \text{ } c/d & X \rightarrow .cX, \text{ } \$ \\ X \rightarrow .d, \text{ } c/d & X \rightarrow .d, \text{ } \$ \end{array}$ Which of the…MCQ2 marksMediumSolve
GATE CSE 2012 · Q52Statement 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…MCQ2 marksMediumDiagramSolve
GATE CSE 2012 · Q53Statement 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…MCQ2 marksMediumDiagramSolve

What GATE tests in Parsing

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. 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.

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
Computation of FIRST sets for non-terminals and production right-hand sides
Computation of FOLLOW sets with transitive/mutual dependencies
Handling of -productions during LL(1) parse table construction
Handling end-marker \$ in the start symbol's FOLLOW set
Detection of multiple entries/conflicts (FIRST/FOLLOW or FIRST/FIRST conflicts)
Augmented CFG construction
LR(0) items representation
Closure operation in LR parsing
Goto transition computation in LR parsing automata

Recurring question patterns

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.
FIRST and FOLLOW Set Computation
CommonMCQ2 marks2012
Given a context-free grammar with nullable productions and cyclic or mutual dependencies (e.g., non-terminals deriving the start symbol), compute the exact FIRST and FOLLOW sets for specified non-terminals.
LL(1) Parsing Table Population
CommonMCQ2 marks2012
Given a grammar and its FIRST/FOLLOW sets (or as a multi-part follow-up), identify specific entries $M[A, a]$ in the LL(1) parsing table, testing whether candidates apply the rule for epsilon-deriving productions mapping to FOLLOW sets.
Computation of LR(0) Goto and Closure Item Sets
RareNAT1 marks2022
Given an augmented Context-Free Grammar (CFG) and a base set of LR(0) items, compute the cardinality (total count of distinct items) of a resulting LR(0) state after applying closure and goto transitions on a specified terminal or non-terminal symbol.

Formulas GATE uses

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 Parsing

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.
Failing to propagate FOLLOW sets through cyclic derivations (e.g., A → S implies FOLLOW(A) ⊆ FOLLOW(S)).
Placing an -production in table cells corresponding to its FIRST set rather than the LHS non-terminal's FOLLOW set.
Confusing the LHS non-terminal of an indirect derivation (e.g., writing S → into M[B, a] instead of B → S when B ⇒* ).
Forgetting transitive/recursive closure expansion when added productions also have a dot before a non-terminal (e.g., expanding R introduces [R → .P], which must then trigger adding productions of P).
Including items where the dot shift does not match the transition symbol.
Off-by-one errors by counting the shifted kernel item only and omitting the newly generated closure items.

How questions are asked

Compute item count in a state after sequential GOTO operations
Identify grammar membership within LR(0)/SLR(1)/LALR(1)/CLR(1)/LL(1)
Fill missing entries in an LL(1) parsing table
Reconstruct missing grammar rules given FIRST and FOLLOW sets
Count total number of Shift-Reduce or Reduce-Reduce conflicts in an ACTION table
Evaluate operator precedence and associativity from grammar or tabular attributes
Identify direct/indirect left recursion elimination correctness
Compute FIRST and FOLLOW sets for non-terminals
Identify entries in specific LL(1) parsing table cells M[A, t]
Count the number of conflicts/multiple entries in an LL(1) parse table
Count items in goto(closure(I), X) for a given grammar snippet

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
Direct calculation of LR parsing sub-routines (e.g., goto/closure sizes) is tested as an exact-integer NAT question without requiring full DFA construction.
2022

Difficulty notes

Easy questions (1 mark) test parser definitions (Top-Down vs Bottom-Up), standard operator precedence/associativity evaluations, or immediate left recursion identification. Medium questions (2 marks) require multi-step procedural computations: building LR item graphs, computing CLOSURE and GOTO, tracking exact lookahead sets to differentiate SLR(1) from LALR(1), counting table conflicts, or completing partially filled LL(1) tables from FIRST/FOLLOW sets.