Back to the 2023 paper

Module 2: Syntax Analysis (Parser)

20232m

A top down parser generates
(i) Rightmost derivation
(ii) Rightmost derivation in reverse
(iii) Leftmost derivation
(iv) Left most derivation in reverse

Worked SolutionAI Assisted

Answer: (iii) Leftmost derivation

Explanation

A top-down parser starts from the start symbol (root) and tries to derive the input string by expanding nonterminals in leftmost order — i.e. it always expands the leftmost nonterminal first.

  • Leftmost derivation: each step replaces the leftmost nonterminal — this is exactly what a top-down (recursive-descent / predictive / LL) parser constructs.
  • Rightmost derivation: each step replaces the rightmost nonterminal — not what a top-down parser does.
  • Rightmost derivation in reverse / handle pruning: that is the basis of bottom-up parsing (LR parsers), not top-down.

Therefore a top-down parser generates a

(iii) Leftmost derivation\boxed{\text{(iii) Leftmost derivation}}

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.