⬆️ Bottom-up Parsing (LR family)
Why it matters: The heaviest topic in CD: items, conflicts and the SLR ⊂ LALR ⊂ CLR relationships.
Subtopics
Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 6 done.
1Shift-reduce parsing and handles
2LR(0) items, closure and goto
3SLR(1)
4CLR(1) = canonical LR
5LALR(1)
6Hierarchy and conflicts
Formulas
closure(I)
repeat: for A → α • B β in I and every B → γ, add B → • γ
goto(I, X)
closure of { A → α X • β : A → α • X β ∈ I }
SLR reduce
in state with A → α •, put reduce on every a ∈ FOLLOW(A)
CLR reduce
in state with [A → α •, a], put reduce only on a
State counts
#LR(0) = #SLR = #LALR ≤ #CLR(1)
Stack on reduce
pop 2 × |α| entries (symbol, state pairs), push A and goto[top, A]
Accepting
in the state with S′ → S •, on $ → accept
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Number of states / items in a parser
Build the LR(0) canonical collection (or SLR) for a small grammar and count states.
★★★
Which parser accepts the grammar
Decide whether a grammar is LR(0), SLR(1), LALR(1) or CLR(1) by looking for conflicts.
★★★
Shift/reduce or reduce/reduce conflicts
Count or locate conflicts in a given state, or compare SLR vs LALR vs CLR.
★★★
Trace a parse
Stack contents, handle, or the sequence of actions on an input.
★★★
Relation between parsers
True/false: LALR has the same states as SLR; CLR has more; power ordering.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
12 real questions from the official GATE CSE papers (2013 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
12 questions · 0 correct of 0 attempted · marks 0 / 17
Year:
GATE 2025 CS2 · Q40MCQ2 marks
Given a Context-Free Grammar G:
S → A a | b A c | d c | b d a A → dWhich ONE of the following statements is TRUE?
GATE 2024 CS1 · Q26MSQ1 mark
Which of the following is/are Bottom-Up Parser(s)?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS2 · Q65NAT2 marks
Consider the following augmented grammar, to be parsed with an SLR parser. Terminals: {a, b, c, d, #, @}
S′ → S S → S S | A a | b A c | B c | b B a A → d # B → @Let I0 = CLOSURE({S′ → • S}). The number of items in the set GOTO(I0, S) is ______.
GATE 2022 · Q13MCQ1 mark
Which one of the following statements is TRUE?
GATE 2022 · Q29NAT1 mark
Consider the augmented grammar with {+, *, (, ), id} as the set of terminals:
S′ → S S → S + R | R R → R * P | P P → ( S ) | idIf I0 is the set of two LR(0) items {[S′ → S•], [S → S• + R]}, then goto(closure(I0), +) contains exactly ______ items.
GATE 2021 Set 1 · Q5MCQ1 mark
Consider the following statements. S1: Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1). S2: For any context-free grammar, there is a parser that takes at most O(n³) time to parse a string of length n. Which one of the following options is correct?
GATE 2020 · Q24NAT1 mark
Consider the following grammar:
S → aSB | d B → bThe number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is ______.
GATE 2019 Set 2 · Q3MCQ1 mark
Which one of the following kinds of derivation is used by LR parsers?
GATE 2019 Set 2 · Q43NAT2 marks
Consider the augmented grammar:
S′ → S S → ⟨L⟩ | id L → L, S | SLet I0 = CLOSURE({[S′ → •S]}). The number of items in the set GOTO(I0, ⟨) is ______.
GATE 2014 Set 1 · Q34MCQ2 marks
A canonical set of items is given below: S → L . > R and Q → R . . On input symbol < the set has
GATE 2013 Code A · Q9MCQ1 mark
What 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 A → ε and A → a) to parse a string with n tokens?
GATE 2013 Code A · Q40MCQ2 marks
Consider the following two sets of LR(1) items of an LR(1) grammar. Set 1:
1. Cannot be merged since look aheads are different.
2. Can be merged but will result in S-R conflict.
3. Can be merged but will result in R-R conflict.
4. Cannot be merged since goto on c will lead to two different sets.
X → c.X, c/d X → .cX, c/d X → .d, c/dSet 2:
X → c.X, $ X → .cX, $ X → .d, $Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?
1. Cannot be merged since look aheads are different.
2. Can be merged but will result in S-R conflict.
3. Can be merged but will result in R-R conflict.
4. Cannot be merged since goto on c will lead to two different sets.
Common traps
SLR and LALR have the same number of states but different reduce entries.
LALR never adds shift/reduce conflicts relative to CLR, but can add reduce/reduce.
An ε-production reduces by popping nothing.