Top-Down vs Bottom-Up Parsers

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."

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2017 · Paper-I · Q7(b) · 6 marks

Q. Using a suitable example, compare the operation of a top-down and a bottom-up parser based compiler.

Ans. Grammar: E → E + T | T, T → id. Input: id + id.

• Top-down: E ⇒ E + T ⇒ T + T ⇒ id + T ⇒ id + id (expands from E).
• Bottom-up: id + id → T + id → E + id → E + T → E (reduces back to E).

2025 · Paper-I · Q8(c) · 8 marks

Q. What is a parse tree? How is it used to check whether a specific string belongs to a language? Give an example.

Ans.

• A parse tree is a tree showing how a string is derived from the grammar's start symbol. The root is the start symbol, internal nodes are non-terminals, and the leaves (read left to right) are the terminals of the string.
• Membership check: parse the string. If a parse tree can be built whose leaves spell exactly the string, the string belongs to the language. If no tree exists, it does not.
• Example: grammar S → aSb | ab and string aabb.

   S
 / | \
a  S  b
  / \
 a   b

• The leaves read aabb, so the string is in the language. The string aab cannot be derived, so it is rejected.

MCQs

2026 P-I · Q16. What is the advantage of using LL(1) grammars in syntax analysis?

• (A) More complex parsing
• (B) Predictive parsing with less complexity ✅
• (C) No need for grammar rules
• (D) None of these
• Answer: (B).
• Why: with an LL(1) grammar the parser decides every step by looking at just one next token, so it can parse without backtracking. This is simple and fast. Grammar rules are still needed, and complex parsing is not an advantage.

2026 P-I · Q17. What is the difference between top-down and bottom-up parsers?

• (A) Top-down is always faster
• (B) Bottom-up handles more grammars
• (C) Top-down starts from the start symbol ✅
• (D) None of these
• Answer: (C) Top-down starts from the start symbol.
• Why: a top-down parser begins at the start symbol and expands it to match the input. A bottom-up parser begins at the input and reduces it back to the start symbol. (Option (B) is also a true fact, since LR parsers cover more grammars than LL, but (C) is the defining difference, and (A) is false.)