GATE CS 2024 Set 1 | Question 26

MSQ · 1 mark

Which of the following is/are Bottom-Up Parser(s)?

  1. Option A: Shift-reduce Parser (correct)
  2. Option B: Predictive Parser
  3. Option C: LL(1) Parser
  4. Option D: LR Parser (correct)

Answer

(A), (D)

Explanation

A bottom-up parser starts from the input tokens and repeatedly replaces a substring that matches the right side of a production by its left side, until only the start symbol remains. It traces a rightmost derivation in reverse.

  • A shift-reduce parser is exactly this method: it shifts tokens onto a stack and reduces the handle on top of it.
  • LR parsers (SLR, LALR and canonical LR) are table-driven shift-reduce parsers, so they are bottom-up as well.
  • Predictive and LL(1) parsers start from the start symbol and expand nonterminals to match the input, following a leftmost derivation. They are top-down, so B and C are wrong.

Answer: A, D