Back to the 2023 paper

Module 2: Syntax Analysis (Parser)

20232m

For a grammar G, shift reduce (S-R) conflicts are present in LALR(1) parser, if and only if
(i) The LAR (1) parser for G has S.R conflicts
(ii) The LR(0) parser for G has S.R conflicts
(iii) The SLR(1) parser for G has S.R conflicts
(iv) The SLR(0) parser for G has S.R conflicts

Worked SolutionAI Assisted

Answer: (i) The LR(1) parser for G has S–R conflicts

Explanation — LALR vs LR relationship

  • LALR(1) parsers are built by merging the states of a canonical LR(1) parser that share the same core (same items, different lookaheads).
  • Merging states can create a reduce–reduce (R–R) conflict (two different reduce actions that were separated by lookahead now share a cell).
  • However, state-merging cannot create a new shift–reduce (S–R) conflict. Intuitively, a shift action exists on a terminal tt in a state only if tt is in that state's core in the LR(1) automaton too. So if the LALR(1) table has an S–R conflict, the same conflict must have already been present in the LR(1) table.

Therefore the correct statement is the one in option (i) — the LR(1) parser for GG has S–R conflicts (with LAR(1) in the paper being a typo for LR(1)).

(i) The LR(1) parser for G has S.R conflicts\boxed{\text{(i) The LR(1) parser for G has S.R conflicts}}

Similar questions

Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.