Top-down vs bottom-up parsing overview in Compiler Design - Practice Questions

Challenge - 5 Problems

🧠 Conceptual

intermediate

Difference in parsing direction

Which statement correctly describes the main difference between top-down and bottom-up parsing?

A Bottom-up parsing begins with the start symbol and expands it, whereas top-down parsing begins with the input string and reduces it.

B Top-down parsing starts from the start symbol and tries to rewrite it to the input string, while bottom-up parsing starts from the input string and tries to reduce it to the start symbol.

C Top-down parsing always uses a stack, but bottom-up parsing does not use any stack.

D Top-down parsing is always faster than bottom-up parsing because it uses fewer rules.

💡 Hint

Think about which end each parsing method starts from: the grammar or the input.

Top-down parsing starts from the grammar's start symbol and tries to generate the input string by applying production rules. Bottom-up parsing starts from the input string and tries to reduce it back to the start symbol by reversing productions.

📋 Factual

intermediate

Common algorithms for parsing

Which of the following pairs correctly matches a parsing method with a common algorithm used for it?

A Top-down parsing - LR parser

B Bottom-up parsing - Predictive parser

C Top-down parsing - Recursive descent parser

D Bottom-up parsing - Recursive descent parser

💡 Hint

Recall which parsing method uses recursive calls and which uses state machines.

Recursive descent parsers are a common implementation of top-down parsing. LR parsers are typical bottom-up parsers. Predictive parsers are a type of top-down parser. Recursive descent is not used for bottom-up parsing.

🔍 Analysis

advanced

Handling left recursion

Why is left recursion a problem for top-down parsers but not for bottom-up parsers?

A Left recursion only affects lexical analysis, not parsing.

B Bottom-up parsers cannot parse left recursion at all, but top-down parsers can handle it easily.

C Both top-down and bottom-up parsers fail with left recursion, so grammar must be rewritten.

D Top-down parsers can get stuck in infinite recursion with left recursion, while bottom-up parsers handle it naturally through reductions.

💡 Hint

Consider how top-down parsers expand rules and how bottom-up parsers reduce input.

Top-down parsers expand rules starting from the start symbol, so left recursion causes infinite loops. Bottom-up parsers reduce input by matching patterns, so left recursion is handled naturally.

❓ Comparison

advanced

Error detection timing

When do top-down and bottom-up parsers typically detect syntax errors during parsing?

A Top-down parsers detect errors as soon as they encounter unexpected input, bottom-up parsers detect errors later after more input is processed.

B Neither parser detects syntax errors; this is done by semantic analysis.

C Both detect errors only after parsing the entire input string.

D Bottom-up parsers detect errors immediately, top-down parsers detect errors only at the end of parsing.

💡 Hint

Think about how each parser processes input and when it can tell something is wrong.

Top-down parsers try to match input from the start and can detect errors early when input doesn't match expected rules. Bottom-up parsers shift input and reduce later, so errors may be detected after more input is read.

❓ Reasoning

expert

Parsing method choice for ambiguous grammar

Given an ambiguous grammar that can be parsed by both top-down and bottom-up methods, which parsing approach is generally more suitable and why?

A Bottom-up parsing is more suitable because it can handle a wider range of grammars including ambiguous ones by using shift-reduce techniques.

B Top-down parsing is more suitable because it naturally resolves ambiguity by choosing the first matching rule.

C Top-down parsing is more suitable because it uses backtracking to try all possibilities efficiently.

D Neither parsing method can handle ambiguous grammars; ambiguity must be removed first.

💡 Hint

Consider which parsing method is more powerful in handling complex grammar structures.

Bottom-up parsers, such as LR parsers, can handle ambiguous grammars better by using shift-reduce parsing and conflict resolution strategies. Top-down parsers struggle with ambiguity and often require grammar rewriting.

Practice

1. Which of the following best describes top-down parsing?

easy

A. It starts from the input tokens and builds the parse tree upwards.

B. It ignores the grammar and parses randomly.

C. It uses machine learning to predict the next token.

D. It starts from the highest-level rule and breaks it down into smaller parts.

Solution

1. Step 1: Understand top-down parsing approach

   Top-down parsing begins with the start symbol of the grammar and tries to rewrite it to match the input string by breaking it down into smaller parts.

2. Step 2: Compare options with definition

   It starts from the highest-level rule and breaks it down into smaller parts. correctly states this approach. It starts from the input tokens and builds the parse tree upwards. describes bottom-up parsing. Options C and D are incorrect methods.

3. Final Answer:

   It starts from the highest-level rule and breaks it down into smaller parts. -> Option D

4. Quick Check:

   Top-down parsing = start big, break down [OK]

Hint: Top-down = start big, break down [OK]

Common Mistakes:

• Confusing top-down with bottom-up parsing
• Thinking parsing ignores grammar
• Believing parsing predicts tokens randomly

2. Which of the following is a correct statement about bottom-up parsing?

easy

A. It builds the parse tree by reducing input tokens to the start symbol.

B. It starts parsing from the start symbol and moves down.

C. It ignores input tokens and guesses the structure.

D. It only works for regular expressions.

Solution

1. Step 1: Understand bottom-up parsing approach

   Bottom-up parsing starts from the input tokens and tries to combine them step-by-step to form higher-level constructs until it reaches the start symbol.

2. Step 2: Match options with definition

   It builds the parse tree by reducing input tokens to the start symbol. correctly describes this process. It starts parsing from the start symbol and moves down. describes top-down parsing. Options C and D are incorrect statements.

3. Final Answer:

   It builds the parse tree by reducing input tokens to the start symbol. -> Option A

4. Quick Check:

   Bottom-up parsing = start small, build up [OK]

Hint: Bottom-up = start small, build up [OK]

Common Mistakes:

• Mixing up start symbol direction
• Assuming bottom-up ignores tokens
• Believing bottom-up only works for simple patterns

3. Given the input string id + id * id, which parsing method would typically handle operator precedence correctly without backtracking?

medium

A. Bottom-up parsing

B. Random parsing

C. Top-down parsing

D. No parsing needed

Solution

1. Step 1: Understand operator precedence handling

   Operator precedence means multiplication (*) has higher priority than addition (+). A parser must respect this to build the correct tree.

2. Step 2: Compare parsing methods for precedence

   Bottom-up parsers (like LR parsers) naturally handle precedence by reducing tokens in correct order without backtracking. Top-down parsers often need extra rules or backtracking.

3. Final Answer:

   Bottom-up parsing -> Option A

4. Quick Check:

   Operator precedence handled best by bottom-up [OK]

Hint: Bottom-up handles precedence naturally [OK]

Common Mistakes:

• Assuming top-down always handles precedence well
• Ignoring operator precedence importance
• Confusing parsing with tokenizing

4. Identify the error in this top-down parser snippet that tries to parse a + b but fails:

def parse_expr():
    if next_token == 'a':
        consume('a')
    elif next_token == '+':
        consume('+')
        parse_expr()
    else:
        error()

medium

A. It should ignore '+' tokens.

B. It does not handle the second operand after '+'.

C. It uses bottom-up parsing incorrectly.

D. It consumes tokens in the wrong order.

Solution

1. Step 1: Analyze the parser code flow

   The parser consumes 'a' if next token is 'a'. If next token is '+', it consumes '+' and calls parse_expr() again.

2. Step 2: Identify missing handling

   After consuming '+', the parser calls parse_expr() but does not ensure the next token is a valid operand like 'b'. This causes failure when parsing 'a + b'.

3. Final Answer:

   It does not handle the second operand after '+'. -> Option B

4. Quick Check:

   Missing operand after '+' causes failure [OK]

Hint: Check if all parts of expression are parsed [OK]

Common Mistakes:

• Ignoring missing operand after operator
• Confusing token consumption order
• Mixing parsing methods in code

5. You want to design a parser for a new programming language that has complex nested expressions and requires efficient error detection. Which parsing approach is generally more suitable and why?

hard

A. Random parsing, because it guesses the structure quickly.

B. Top-down parsing, because it is easier to implement and handles all grammars efficiently.

C. Bottom-up parsing, because it can handle a wider range of grammars and detects errors earlier.

D. No parsing needed, just interpret the code directly.

Solution

1. Step 1: Consider grammar complexity and error detection needs

   Complex nested expressions require a parser that can handle many grammar rules and detect errors precisely.

2. Step 2: Compare top-down and bottom-up parsing suitability

   Bottom-up parsing (like LR parsers) can handle more complex grammars and usually detect errors earlier during parsing. Top-down parsers are simpler but less powerful and may require backtracking.

3. Final Answer:

   Bottom-up parsing, because it can handle a wider range of grammars and detects errors earlier. -> Option C

4. Quick Check:

   Complex grammar + error detection = bottom-up [OK]

Hint: Bottom-up better for complex grammar and errors [OK]

Common Mistakes:

• Assuming top-down handles all grammars easily
• Ignoring error detection importance
• Thinking random parsing is valid