Definition

Parsers build a parse tree either starting from the root (top-down) or from the leaves (bottom-up).

Key Points

• Top-Down Parsing: starts at the start symbol, tries to derive the input string by expanding non-terminals — builds the tree root-to-leaves.
  • Types: Recursive Descent (hand-written, one function per non-terminal), Predictive Parsing (table-driven, no backtracking, needs LL(1) grammar)
  • Cannot handle left-recursive grammars directly — must be eliminated first.
• Bottom-Up Parsing: starts from input tokens, repeatedly reduces substrings to non-terminals until reaching the start symbol — builds tree leaves-to-root.
  • Types: Shift-Reduce parsing, Operator-Precedence parsing, LR parsing (SLR, CLR, LALR)
  • Handles left recursion naturally; more powerful, but harder to hand-implement (usually auto-generated).

Example

For input id + id with E → E + T | T, T → id:

• Top-down: starts at E, expands → E+T → T+T → id+id
• Bottom-up: starts at id+id, reduces id→T, then T+T is reduced via E→E+T rule matching, up to E

📌 CSS Frequency: High — trace-based numeric questions ("parse this string using both approaches") are common.

Model Answer (short)

"Top-down parsers construct the parse tree from the start symbol downward by predicting productions, and require the grammar to be free of left recursion; examples include recursive-descent and predictive (LL) parsers. Bottom-up parsers construct the tree from the input tokens upward by repeatedly reducing substrings, naturally handle left recursion, and are more powerful — LR parsing is the standard bottom-up technique used by parser generators."