Recursive descent parsing in Compiler Design - Mini Project: Build & Apply

Recursive Descent Parsing

📖 Scenario: You are building a simple parser for arithmetic expressions containing numbers and plus signs. This parser will help understand how recursive descent parsing works by breaking down the expression into parts.

🎯 Goal: Create a step-by-step recursive descent parser that can recognize and parse simple addition expressions like 1+2+3. You will build the parser functions and the supporting data structure to process the input expression.

📋 What You'll Learn

Create a string variable holding the arithmetic expression to parse.

Create an index variable to track the current position in the expression.

Write a function to parse numbers from the expression.

Write a recursive function to parse addition expressions using recursive descent.

💡 Why This Matters

🌍 Real World

Recursive descent parsing is used in compilers and interpreters to analyze and understand programming language code by breaking it down into parts according to grammar rules.

💼 Career

Understanding recursive descent parsing is essential for compiler developers, language designers, and software engineers working on tools that process or analyze code.

1

DATA SETUP: Create the expression string

Create a string variable called expression and set it to the exact value "1+2+3".

Compiler Design

# Create the expression string
# Your code here

Hint

Use quotes to create a string variable named expression with the value "1+2+3".

2

CONFIGURATION: Create the index variable

Create an integer variable called index and set it to 0 to track the current position in the expression string.

Compiler Design

expression = "1+2+3"
# Create the index variable
# Your code here

Hint

Initialize index to zero to start parsing from the beginning of the expression.

3

CORE LOGIC: Write the parse_number function

Write a function called parse_number() that reads a single digit number from expression at the current index, converts it to an integer, increments index by 1, and returns the integer value.

Compiler Design

expression = "1+2+3"
index = 0
# Define parse_number function
# Your code here

Hint

Use global index to modify the index variable inside the function. Convert the character at expression[index] to an integer.

4

COMPLETION: Write the parse_expression function using recursion

Write a recursive function called parse_expression() that calls parse_number() to get the first number, then checks if the current character at index is a plus sign '+'. If yes, increment index by 1 and recursively call parse_expression() to get the next number, then return the sum of the first number and the recursive call result. If no plus sign is found, return the first number.

Compiler Design

expression = "1+2+3"
index = 0

def parse_number():
    global index
    value = int(expression[index])
    index += 1
    return value

# Define parse_expression function
# Your code here

Hint

Use recursion to parse the right side of the plus sign. Check if index is within bounds before accessing expression[index].

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