GATE CS 2007 Q18 — Parsing (LL, LR)

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

1. Top-Down Parsers: These parsers construct the parse tree starting from the root (the start symbol) and proceed downwards to the leaves (the input terminals). Examples include:
   • Recursive Descent Parser (which uses recursive procedures to parse the input, with or without backtracking)
   • LL(k) parsers
2. Bottom-Up Parsers: These parsers construct the parse tree starting from the leaves (the input terminals) and proceed upwards to the root (the start symbol) using shift-reduce operations. Examples include:
   • Operator Precedence Parser
   • LR(k) parsers (including SLR, LALR, and CLR)

Among the given options, only the Recursive descent parser is a top-down parser. The others (Operator precedence, LR(k), and LALR(k)) are bottom-up parsers.