Back to the 2023 paper

Module 2: Syntax Analysis (Parser)

20232m

Which of the following is the most powerful parser?
(i) SLR
(ii) LALR
(iii) Canonical LR
(iv) Operator precedence

Worked SolutionAI Assisted

Answer: (iii) Canonical LR

Explanation

Parsers can be ordered by the size of the grammar class they can handle (their power):

  • Operator-precedence parsing: only works on operator grammars (no ϵ\epsilon, no two adjacent nonterminals) — the least general.
  • SLR(1): uses the LR(0) items but decides reduce actions using the broad FOLLOW\mathrm{FOLLOW} set of the left-hand nonterminal, ignoring the specific context of each item → weaker.
  • LALR(1): merges LR(1) items that share the same core (same item, different lookahead). More powerful than SLR(1).
  • Canonical LR / LR(1): keeps every lookahead separate, producing the most states and therefore accepting the largest set of grammars among the given options.

Hence the most powerful parser is:

(iii) Canonical LR (LR(1))\boxed{\text{(iii) Canonical LR (LR(1))}}

Order of power (weakest → strongest):
Operator-precedence < SLR(1) < LALR(1) < Canonical LR(1)

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.