IAE Academy

GATE 2024 CS1 Q.26: solution and answer

GATE 2024 · CS1Q.26 · 1 mark · MSQ

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

  1. (A)

    Shift-reduce Parser

  2. (B)

    Predictive Parser

  3. (C)

    LL(1) Parser

  4. (D)

    LR Parser

See the question in the paper
GATE 2024 CS1 question 26Tap to open full size

Answer and solution

ANSWER

The bottom-up parsers are (A) Shift-reduce Parser and (D) LR Parser.

Official answer: A, DSource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

  1. Bottom-up parsing builds the parse tree from the leaves (the input tokens) up to the start symbol, tracing a rightmost derivation in reverse.

  2. (A) A shift-reduce parser shifts tokens onto a stack and reduces handles to non-terminals. This is the general bottom-up method, so it qualifies.

  3. (B) A predictive parser is a recursive-descent or table-driven parser that chooses a production from the lookahead. It expands from the start symbol, so it is top-down.

  4. (C) An LL(1) parser is the table-driven predictive parser: Left-to-right scan, Leftmost derivation, 1 lookahead. It is top-down.

  5. (D) An LR parser (LR(0), SLR, LALR, CLR) is a shift-reduce parser driven by an automaton of items . It is bottom-up.

  6. So the bottom-up parsers are (A) and (D).

KEY IDEA

Bottom-up parsers (shift-reduce, and the LR family built on it) reduce the input to the start symbol. Top-down parsers (predictive, recursive descent, LL(1)) expand from the start symbol.

WATCH OUT FOR

Choosing the predictive or LL(1) parser because it is table-driven and uses a stack. Both build the tree from the root downwards, so they are top-down.

From the GATE 2024 CS1 paper. Every question of this paper · Download the full paper · All 13 Parsing questions, with notes

More Parsing questions