Back to the 2026 paper

Module 2: Syntax Analysis (Parser)

20262m

Which of the following is a problem for a top-down parser?
(i) Left recursion
(ii) Right recursion
(iii) Ambiguity only
(iv) Bottom-up derivation

Worked SolutionAI Assisted

Answer: (i) Left recursion

Explanation

A grammar is left recursive if it has a rule of the form A→Aα∣βA \to A\alpha \mid \beta.

A top-down (recursive-descent / LL) parser expands the leftmost non-terminal first. For A→AαA \to A\alpha it would call A() which immediately calls A() again without consuming any input, so it falls into an infinite loop.

Fix: eliminate left recursion

A→Aα∣β    ⟹    A→βA′,A′→αA′∣εA \to A\alpha \mid \beta \;\;\Longrightarrow\;\; A \to \beta A',\quad A' \to \alpha A' \mid \varepsilon

  • Right recursion (A→αAA \to \alpha A) is harmless for top-down parsers.
  • Ambiguity affects all parsers, but it is not the characteristic problem of top-down parsing, and option (iii) says "only".

(i) Left recursion\boxed{\text{(i) Left recursion}}

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.