LALR questions look like definition recall, but the mark usually turns on three precise distinctions: parser power, an LR(0) core versus an LR(1) lookahead, and conflicts caused by state merging. Choose A, B, C, or D before reading each solution. If the surrounding compiler-design sequence needs revision, use the GATE CS Exam page alongside this set.
LALR(1) state merging in one worked example
Use this power order: LR(0) < SLR(1) < LALR(1) < canonical LR(1). SLR and LALR have the same state count because both end with one state per distinct LR(0) core. Canonical LR(1) can retain the same core in different lookahead contexts.
For S -> Aa | bAc | Bc | bBa, A -> d, B -> d, state I_A has [A -> d., a] and [B -> d., c]; I_B has [A -> d., c] and [B -> d., a]. Separately, each has one reduction on a and one on c. Their common LR(0) core is {A -> d., B -> d.}, so LALR merges them into [A -> d., {a,c}] and [B -> d., {a,c}]. Two reductions now compete on both symbols.
This creates a new reduce-reduce conflict. Such merging cannot create a new shift-reduce conflict when the canonical states were shift-reduce-conflict-free. A shift item belongs to the core, so each canonical source state already carries that shift before any reduction lookaheads are unioned. For more detail, revise SLR vs CLR vs LALR Parsers for GATE: States & Conflicts.
LALR MCQs 1-2: yacc, scan direction and derivation
Question 1
yacc is which of the following parsers?
A. Predictive Parser
B. SLR Parser
C. CLR Parser
D. LALR Parser
Correct answer: D.
yacc generates a bottom-up LALR(1) parser. Predictive parsing is top-down, SLR uses FOLLOW sets, and canonical LR retains unmerged LR(1) contexts.
Question 2
Which one of the following statements is false?
A. LALR parser is Bottom-Up parser
B. A parsing algorithm that scans left to right and constructs a rightmost derivation in reverse is RL(1)
C. LR parser is Bottom-Up parser
D. In LL(1), the 1 indicates that there is a one symbol look-ahead
Correct answer: B.
The intended notation is LR: scan left to right and construct a rightmost derivation in reverse. LALR and LR are bottom-up, and the 1 in LL(1) means one lookahead symbol. Only B is false.
LALR MCQs 3-4: parser power and implementation trade-offs
Question 3
Arrange the following parsers from the least powerful to the most powerful.
A. LR(0); B. LR(1); C. LALR(1); D. LL(0); E. SLR.
Choose the correct answer from the options below.
A. LL(0) → LR(0) → SLR → LR(1) → LALR(1)
B. SLR → LR(0) → LL(0) → LR(1) → LALR(1)
C. LL(0) → LR(0) → SLR → LALR(1) → LR(1)
D. LR(0) → LL(0) → SLR → LR(1) → LALR(1)
Correct answer: C.
The chain adds LR(0) items, FOLLOW-guided reductions, merged LR(1) lookaheads, then full canonical context. Table compactness and grammar-handling power are different axes.
Question 4
Among simple LR (SLR), canonical LR and look-ahead LR (LALR), which pair identifies the easiest method to implement and the most powerful method, in that order?
A. SLR, LALR
B. Canonical LR, LALR
C. SLR, canonical LR
D. LALR, canonical LR
Correct answer: C.
SLR is easiest because it uses an LR(0) automaton plus global FOLLOW sets. Canonical LR(1) is most powerful because reductions have item-specific lookaheads. LALR sits between them.
LALR MCQs 5-6: how many states survive merging
Question 5
Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is:
A. n1 is necessarily less than n2
B. n1 is necessarily equal to n2
C. n1 is necessarily greater than n2
D. none of these
Correct answer: B.
SLR has one state per LR(0) item set. LALR merges canonical states to one per distinct LR(0) core. Thus n1 = n2, although their reduce actions differ.
Question 6
Consider the grammar S → (S) | a.
Let the numbers of states in its SLR(1), LR(1) and LALR(1) parsers be n1, n2 and n3, respectively. Which relationship holds?
A. n1 < n2 < n3
B. n1 = n3 < n2
C. n1 = n2 = n3
D. n1 ≥ n3 ≥ n2
Correct answer: B.
The LR(0) automaton has 6 cores, so n1 = 6. Canonical LR(1) separates $ and ) contexts, giving n2 = 10. LALR merges equal cores, so n3 = 6. Hence 6 = 6 < 10.
LALR MCQs 7-8: when merging does and does not create a conflict
Question 7
Consider these two sets of LR(1) items for an LR(1) grammar.
Set 1: X → c·X, c/d; X → ·cX, c/d; X → ·d, c/d.
Set 2: X → c·X, $; X → ·cX, $; X → ·d, $.
Which statements about merging the two sets in the corresponding LALR parser are false?
1. They cannot be merged because their lookaheads differ.
2. They can be merged but will produce a shift-reduce conflict.
3. They can be merged but will produce a reduce-reduce conflict.
4. They cannot be merged because goto(c) leads to two different sets.
A. 1 only
B. 2 only
C. 1 and 4 only
D. 1, 2, 3 and 4
Correct answer: D.
Identical cores {X -> c.X, X -> .cX, X -> .d} allow merging. Unioning gives lookaheads {c,d,$}. Every dot precedes a symbol, so there is no reduction or conflict. goto(c) keeps the common core. All four statements are false.
Question 8
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if
A. the SLR(1) parser for G has S-R conflicts
B. the LR(1) parser for G has S-R conflicts
C. the LR(0) parser for G has S-R conflicts
D. the LALR(1) parser for G has reduce-reduce conflicts
Correct answer: B.
Shifts come from the LR(0) core, while merging unions reduction lookaheads. A source state supplying a reduction already contains the core's shift item, so any S-R conflict already existed in canonical LR(1). Only a new R-R conflict can appear.
LALR MCQs 9-10: FOLLOW sets, item lookaheads and deterministic languages
Question 9
Given the following statements:
S1: SLR uses FOLLOW information to guide reductions. In LR and LALR parsers, lookaheads are associated with items and use the left context available to the parser.
S2: LR grammars form a larger subclass of context-free grammars than SLR and LALR grammars.
Which option is true?
A. S1 is not correct and S2 is not correct.
B. S1 is not correct and S2 is correct.
C. S1 is correct and S2 is not correct.
D. S1 is correct and S2 is correct.
Correct answer: D.
For A -> alpha., SLR reduces across FOLLOW(A); LR(1) and LALR use item lookaheads. Also, SLR(1) subset LALR(1) subset LR(1), so canonical LR(1) handles the largest class. Both statements are correct.
Question 10
Which one of the following statements is TRUE?
A. The LALR(1) parser for a grammar G cannot have reduce-reduce conflict if the LR(1) parser for G does not have reduce-reduce conflict.
B. Symbol table is accessed only during the lexical analysis phase.
C. Data flow analysis is necessary for run-time memory management.
D. LR(1) parsing is sufficient for deterministic context-free languages.
Correct answer: D.
A fails by the opening counterexample. B fails because later phases use symbol tables. C confuses compile-time data-flow analysis with runtime memory management. Canonical LR(1) is sufficient for deterministic context-free languages, so D is true.
LALR MCQs 11-12: classify the grammar instead of guessing the parser
Question 11
Given the context-free grammar G:
S → Aa | bAc | dc | bda
A → d
Which one of the following statements is true?
A. 𝐺 is neither LALR(1) nor SLR(1)
B. 𝐺 is CLR(1), not LALR(1)
C. 𝐺 is LALR(1), not SLR(1)
D. 𝐺 is LALR(1), also SLR(1)
Correct answer: C.
FOLLOW(A) = {a,c}. After d, the LR(0) state has S -> d.c and A -> d.. SLR's reduction on c clashes with the shift. LR(1) separates the contexts, and LALR remains conflict-free. Therefore C.
Question 12
Consider the grammar:
S → CC
C → cC | d
The grammar is:
A. LL(1)
B. SLR(1) but not LL(1)
C. LALR(1) but not SLR(1)
D. LR(1) but not LALR(1)
Correct answer: A.
FIRST(cC) = {c} and FIRST(d) = {d} are disjoint. With no epsilon production, no FIRST/FOLLOW collision arises. One lookahead selects C's production, so the grammar is LL(1); the later-class options are wrong.
The four-line check for your next LALR question
Erase lookaheads and compare the LR(0) cores.
Merge only states with identical cores.
Union the lookaheads of corresponding items.
Inspect the merged ACTION entries. A new R-R conflict is possible, but a new S-R conflict is not.
Remember states(SLR) = states(LALR) <= states(CLR) and the power order SLR < LALR < CLR.
At 10-12, move to mixed parser MCQs. At 7-9, revisit merging and FOLLOW versus item lookahead. At 0-6, rebuild the broader top-down and bottom-up comparison with Parsing MCQs: 12 solved questions on top-down and bottom-up parsing.
For lessons, use GATE Guidance by Sanchit Sir. For testing, use the GATE Test Series. Apply the check until merges and ACTION entries become routine.
