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.