GATE CS 2024 Set 1 Q16 — Parsing (LL, LR)

Parsers can be broadly classified into two categories based on how they construct the parse tree:

1. Top-Down Parsers: They build the parse tree from the top (start symbol) down to the bottom (leaves). Examples include:
   • LL(1) Parser (Left-to-right scan, Leftmost derivation)
   • Predictive Parser (a non-recursive top-down parser)
2. Bottom-Up Parsers: They build the parse tree from the bottom (leaves/input words) up to the top (start symbol) by finding the rightmost derivation in reverse. Examples include:
   • Shift-reduce Parser (uses shift and reduce operations on a stack)
   • LR Parser (Left-to-right scan, Rightmost derivation in reverse, which includes LR(0), SLR(1), LALR(1), and CLR(1))

Thus, the bottom-up parsers among the choices are Shift-reduce Parser (Option A) and LR Parser (Option D).