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.

Parsing

23 Qs · since 2012 · 38 marks · 1.5 marks/paperMedium yield

Take topic test

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 are… Guide

Type

GATE CSE 2026 Set 1Q28MSQ1 markEasyWhich of the following statements is/are true?
GATE CSE 2026 Set 2Q41MCQ2 marksMediumConsider 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…
GATE CSE 2025 Set 2Q40MCQ2 marksMediumGiven 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?
GATE CSE 2025 Set 2Q51MSQ2 marksMediumConsider 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…
GATE CSE 2024 Set 1Q26MSQ1 markEasyWhich of the following is/are Bottom-Up Parser(s)?
GATE CSE 2024 Set 1Q38MCQ2 marksMediumConsider 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$ …
GATE CSE 2024 Set 2Q40MCQ2 marksMediumDiagramConsider 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…
GATE CSE 2024 Set 2Q65NAT2 marksMediumConsider 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\})$ …
GATE CSE 2022Q13MCQ1 markMediumWhich one of the following statements is TRUE?
GATE CSE 2022Q29NAT1 markEasyConsider 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), +)$ …
GATE CSE 2021 Set 1Q5MCQ1 markMediumConsider 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…
GATE CSE 2021 Set 2Q51NAT2 marksMediumConsider 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)$ …
GATE CSE 2017 Set 2Q32MCQ2 marksEasyConsider 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…
GATE CSE 2016 Set 1Q45NAT2 marksEasyDiagramThe 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 _______.
GATE CSE 2016 Set 2Q45MCQ2 marksEasyWhich one of the following grammars is free from *left recursion*?
GATE CSE 2015 Set 3Q16MCQ1 markEasyAmong 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?
GATE CSE 2015 Set 3Q31MCQ2 marksMediumConsider 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…
GATE CSE 2014 Set 1Q34MCQ2 marksEasyA canonical set of items is given below $S \rightarrow L. > R$ $Q \rightarrow R.$ On input symbol < the set has
GATE CSE 2014 Set 2Q17MCQ1 markEasyConsider 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?
GATE CSE 2013Q9MCQ1 markMediumWhat 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?
GATE CSE 2013Q40MCQ2 marksMediumConsider 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…
GATE CSE 2012Q52MCQ2 marksMediumDiagramStatement 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…
GATE CSE 2012Q53MCQ2 marksMediumDiagramStatement 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…

Topic guide

What does GATE test in 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.

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
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.
FIRST and FOLLOW Set Computation
common · MCQ · 2 marks · 2012
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
common · MCQ · 2 marks · 2012
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
rare · NAT · 1 marks · 2022
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.

Parsing

23 Qs · since 2012 · 38 marks · 1.5 marks/paperMedium yield

Take topic test

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 are… Guide

Type

Topic guide

What does GATE test in Parsing?

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
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.
FIRST and FOLLOW Set Computation
common · MCQ · 2 marks · 2012
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
common · MCQ · 2 marks · 2012
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
rare · NAT · 1 marks · 2022
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