Recursive descent parsing in Compiler Design - Step-by-Step Execution

Concept Flow - Recursive descent parsing

Start parsing input

↓

Call parse function for start symbol

↓

Match current token with expected token?

Yes No↓

Consume token

↓

Call parse functions for subrules

↓

Repeat until input fully parsed

↓

Parsing success or failure

The parser starts by calling a function for the start symbol, matches tokens step-by-step, calls subrule functions recursively, and either succeeds or reports an error.

Execution Sample

Compiler Design

def parse_expr():
    parse_term()
    while current_token == '+':
        consume('+')
        parse_term()

This code parses an expression with terms separated by '+' recursively.

Analysis Table

Step	Function Called	Current Token	Action	Next Token	Output/Result
1	parse_expr	3	Call parse_term	3	Parsing term
2	parse_term	3	Match number token '3'	+	Term parsed
3	parse_expr	+	Check for '+' token	+	Found '+'
4	parse_expr	+	Consume '+' token	5	Token consumed
5	parse_expr	5	Call parse_term	5	Parsing term
6	parse_term	5	Match number token '5'	EOF	Term parsed
7	parse_expr	EOF	No more '+' tokens	EOF	Expression parsed successfully

💡 Reached end of input with successful parse

State Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	Final
current_token	3	+	5	EOF	EOF
parse_expr_state	start	after first term	after consuming '+'	after second term	done

Key Insights - 3 Insights

Why does parse_expr call parse_term first before checking for '+'?

Because parse_expr expects an expression to start with a term. The execution_table row 1 shows parse_expr calling parse_term to parse the first part before looking for '+' operators.

What happens if the current token does not match the expected token?

The parser reports an error and stops. In the flow diagram, the 'No' branch after matching token leads to an error, which is not shown in this successful example.

How does recursion help in parsing nested expressions?

Each parse function can call others to handle subparts. For example, parse_expr calls parse_term, and parse_term could call parse_factor, allowing nested structures. This is shown in the concept flow where parse functions call subrule functions recursively.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current_token at Step 4?

A '+'

B '3'

C '5'

D 'EOF'

💡 Hint

Check the 'Current Token' column for Step 4 in the execution_table.

At which step does parse_expr consume the '+' token?

A Step 3

B Step 5

C Step 4

D Step 6

💡 Hint

Look at the 'Action' column for the step where '+' is consumed.

If the input had no '+' token, how would the execution_table change?

A parse_term would fail to parse the first number

B parse_expr would not enter the while loop and finish after first term

C The parser would consume a '+' token anyway

D The parser would call parse_term twice regardless

💡 Hint

Refer to the 'Action' column and the loop condition in the execution_sample code.

Concept Snapshot

Recursive descent parsing uses a set of functions, each for a grammar rule.
Each function matches tokens and calls other functions for subrules.
Parsing proceeds by consuming tokens step-by-step recursively.
If tokens don't match expected patterns, parsing fails.
This method is simple and intuitive for many grammars.

Full Transcript

Recursive descent parsing works by starting at the top grammar rule and calling a function for it. This function tries to match the current input token with what it expects. If it matches, it consumes the token and calls other functions for subrules. This process repeats recursively until the entire input is parsed or an error occurs. The execution table shows step-by-step how tokens are matched and consumed, and how functions call each other. Variables like current_token change as tokens are consumed. Beginners often wonder why functions call subrules first or what happens on mismatch; these are clarified by following the execution steps. Quizzes help check understanding of token states and function calls during parsing.

Practice

1. What is the main idea behind recursive descent parsing?

easy

A. Using a single loop to scan the input once

B. Converting input into machine code directly

C. Using functions that call themselves to analyze input step-by-step

D. Using tables to decide parsing actions

Solution

1. Step 1: Understand recursive descent parsing concept

   Recursive descent parsing uses functions that call themselves to process parts of the input one by one.

2. Step 2: Compare options with concept

   Only Using functions that call themselves to analyze input step-by-step describes this method correctly; others describe different parsing or compilation techniques.

3. Final Answer:

   Using functions that call themselves to analyze input step-by-step -> Option C

4. Quick Check:

   Recursive descent = functions calling themselves [OK]

Hint: Look for self-calling functions in parsing [OK]

Common Mistakes:

• Confusing recursive descent with table-driven parsing
• Thinking parsing is done in one pass without recursion
• Mixing parsing with code generation

2. Which of the following is a correct syntax feature of a recursive descent parser function?

easy

A. It calls itself to process nested grammar rules

B. It uses a while loop to parse all tokens at once

C. It directly generates machine code

D. It uses a global variable to store the entire parse tree

Solution

1. Step 1: Identify function behavior in recursive descent parsing

   Functions in recursive descent parsers call themselves to handle nested or repeated grammar parts.

2. Step 2: Evaluate options

   It calls itself to process nested grammar rules correctly states this behavior. Options B, C, and D describe unrelated or incorrect features.

3. Final Answer:

   It calls itself to process nested grammar rules -> Option A

4. Quick Check:

   Recursive descent functions call themselves [OK]

Hint: Look for self-calling function behavior [OK]

Common Mistakes:

• Assuming loops replace recursion in these functions
• Confusing parsing with code generation
• Thinking parse tree is stored globally by default

3. Given this simple grammar rule:
Expr -> 'a' Expr | 'b'
What will a recursive descent parser output when parsing the input aaab?

medium

A. Successfully parses the input

B. Syntax error at first character

C. Infinite recursion without stopping

D. Parses only the first character

Solution

1. Step 1: Understand the grammar and input

   The rule says Expr can be 'a' followed by Expr again, or just 'b'. Input 'aaab' fits this pattern: 'a' + 'a' + 'a' + 'b'.

2. Step 2: Trace parsing steps

   The parser calls Expr recursively for each 'a', finally matching 'b' and stopping successfully.

3. Final Answer:

   Successfully parses the input -> Option A

4. Quick Check:

   Input matches recursive pattern = success [OK]

Hint: Match input step-by-step with grammar rules [OK]

Common Mistakes:

• Thinking recursion never ends here
• Assuming syntax error on repeated 'a's
• Believing parser stops after first character

4. What is the main problem if a recursive descent parser function calls itself without consuming any input tokens?

medium

A. It generates an incorrect parse tree but finishes

B. It correctly parses empty input

C. It skips tokens and misses errors

D. It causes infinite recursion leading to a crash

Solution

1. Step 1: Analyze recursion without input consumption

   If a parser function calls itself but does not move forward in the input, it repeats the same call endlessly.

2. Step 2: Understand consequences

   This causes infinite recursion, which usually crashes the program or stack overflow.

3. Final Answer:

   It causes infinite recursion leading to a crash -> Option D

4. Quick Check:

   No input consumed + recursion = infinite loop [OK]

Hint: Check if input advances before recursive call [OK]

Common Mistakes:

• Assuming parser can handle infinite recursion gracefully
• Thinking empty input is always valid
• Believing parse tree is built despite infinite recursion

5. How can left recursion in grammar rules cause problems in recursive descent parsing, and what is a common solution?

hard

A. Left recursion causes syntax errors; add more tokens to grammar

B. Left recursion causes infinite recursion; rewrite grammar to remove left recursion

C. Left recursion causes slow parsing; use iterative loops instead

D. Left recursion causes missing parse trees; use global variables

Solution

1. Step 1: Understand left recursion problem

   Left recursion means a rule calls itself first without consuming input, causing infinite recursion in recursive descent parsers.

2. Step 2: Identify common solution

   To fix this, grammars are rewritten to remove left recursion, often by using right recursion or iteration.

3. Final Answer:

   Left recursion causes infinite recursion; rewrite grammar to remove left recursion -> Option B

4. Quick Check:

   Left recursion = infinite recursion; fix by rewriting [OK]

Hint: Rewrite grammar to eliminate left recursion [OK]

Common Mistakes:

• Thinking adding tokens fixes left recursion
• Assuming loops replace recursion without grammar change
• Believing global variables solve recursion issues