Top-down vs bottom-up parsing overview in Compiler Design - Visual Side-by-Side Comparison

Concept Flow - Top-down vs bottom-up parsing overview

Start: Input string

↓

Try to build parse tree

↓

Match input tokens

↓

Success or error

↓

Parse result

The flow shows how top-down parsers start from the grammar's start symbol and try to match input by expanding rules, while bottom-up parsers start from input tokens and try to reduce them to the start symbol.

Execution Sample

Compiler Design

Input: a + b * c
Top-down: Start -> Expr -> Term -> Factor
Bottom-up: Shift a, shift +, shift b, reduce b * c, reduce a + ...

Shows how top-down expands from start symbol, bottom-up shifts tokens and reduces to build parse tree.

Analysis Table

Step	Parser Type	Action	Stack Content	Input Remaining	Result
1	Top-down	Start with Expr	Expr	a + b * c	Begin parse
2	Top-down	Expand Expr -> Term + Expr'	Term + Expr'	a + b * c	Expanding rules
3	Top-down	Expand Term -> Factor	Factor + Expr'	a + b * c	Expanding rules
4	Top-down	Match Factor -> a	a + Expr'	+ b * c	Matched token 'a'
5	Top-down	Match '+'	+ Expr'	b * c	Matched token '+'
6	Top-down	Expand Expr' -> Term	Term	b * c	Expanding rules
7	Top-down	Expand Term -> Factor * Term	Factor * Term	b * c	Expanding rules
8	Top-down	Match Factor -> b	b * Term	* c	Matched token 'b'
9	Top-down	Match '*'	* Term	c	Matched token '*'
10	Top-down	Match Factor -> c	c		Matched token 'c'
11	Top-down	Input consumed			Parse success
1	Bottom-up	Shift 'a'	a	+ b * c	Shift token
2	Bottom-up	Reduce 'a' to Factor	Factor	+ b * c	Reduce by rule
3	Bottom-up	Reduce Factor to Term	Term	+ b * c	Reduce by rule
4	Bottom-up	Shift '+'	Term +	b * c	Shift token
5	Bottom-up	Shift 'b'	Term + b	* c	Shift token
6	Bottom-up	Reduce 'b' to Factor	Term + Factor	* c	Reduce by rule
7	Bottom-up	Shift '*'	Term + Factor *	c	Shift token
8	Bottom-up	Shift 'c'	Term + Factor * c		Shift token
9	Bottom-up	Reduce 'c' to Factor	Term + Factor * Factor		Reduce by rule
10	Bottom-up	Reduce Factor * Factor to Term	Term + Term		Reduce by rule
11	Bottom-up	Reduce Term + Term to Expr	Expr		Reduce by rule
12	Bottom-up	Input consumed	Expr		Parse success

💡 Parsing stops when input is fully matched and parse tree is built or an error occurs.

State Tracker

Stack Content	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	Final
Top-down Stack	Expr	Term + Expr'	Factor + Expr'	a + Expr'	+ Expr'	Term	Factor * Term	b * Term	* Term	c
Bottom-up Stack		a	Factor	Term	Term +	Term + b	Term + Factor	Term + Factor *	Term + Factor * c	Term + Factor * Factor	Term + Term	Expr

Key Insights - 3 Insights

Why does top-down parsing expand rules before matching tokens?

Top-down parsing starts from the start symbol and tries to predict which rules to apply to match the input. This is shown in execution_table rows 1-7 where rules are expanded before tokens are matched.

Why does bottom-up parsing shift tokens first before reducing?

Bottom-up parsing reads input tokens (shift) and tries to find patterns to reduce to grammar rules. This is clear in execution_table rows 1-9 where tokens are shifted onto the stack before reductions happen.

When does parsing stop successfully in both methods?

Parsing stops successfully when the entire input is consumed and the parse tree corresponds to the start symbol. In the table, this is at top-down step 11 and bottom-up step 12.

Visual Quiz - 3 Questions

Look at the execution_table, at which top-down step is the token '+' matched?

A Step 5

B Step 4

C Step 6

D Step 7

💡 Hint

Check the 'Action' column for top-down parser steps matching tokens.

According to variable_tracker, what is the bottom-up stack content after shifting 'c'?

A Expr

B Term + Factor * Factor

C Term + Factor * c

D Term + Term

💡 Hint

Look at the bottom-up stack row and find the value after step 8.

If the input had an unexpected token, at which step would parsing likely stop?

A When expanding rules in top-down parser

B When matching tokens in top-down parser

C When shifting tokens in bottom-up parser

D When reducing rules in bottom-up parser

💡 Hint

Errors usually occur when the parser tries to match tokens that don't fit the grammar, as seen in top-down steps matching tokens.

Concept Snapshot

Top-down parsing starts from the start symbol and expands grammar rules to match input tokens.
Bottom-up parsing starts from input tokens and reduces them to the start symbol.
Top-down uses prediction and recursion; bottom-up uses shift and reduce operations.
Parsing succeeds when input is fully matched and parse tree is built.
Errors occur when tokens don't fit expected grammar rules.

Full Transcript

This visual execution compares top-down and bottom-up parsing methods. Top-down parsing begins with the grammar's start symbol and expands rules to match the input tokens step-by-step. Bottom-up parsing reads input tokens (shifts) and tries to reduce sequences to grammar rules until the start symbol is reached. The execution table traces each step, showing actions like expanding rules, matching tokens, shifting tokens, and reducing rules. The variable tracker shows how the parser's stack changes over time. Key moments clarify why top-down expands before matching and bottom-up shifts before reducing. The quiz tests understanding of specific steps and stack states. Overall, parsing stops successfully when the entire input is matched and the parse tree is complete.