Recursive descent parsing in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the basic mechanism of recursive descent parsing

Which of the following best describes how recursive descent parsing works?

A It uses a stack to simulate the parsing process without recursion.

B It converts the grammar into a finite automaton and uses state transitions to parse the input.

C It uses a set of mutually recursive functions where each function implements one non-terminal of the grammar.

D It relies on regular expressions to match tokens in the input string.

💡 Hint

Think about how the parser handles each grammar rule in code.

Recursive descent parsing uses a set of recursive functions, each corresponding to a grammar rule (non-terminal). These functions call each other to process the input according to the grammar.

📋 Factual

intermediate

Identifying grammar limitations for recursive descent parsing

Which type of grammar is NOT suitable for direct recursive descent parsing without modification?

A Left-recursive grammars

B LL(1) grammars

C Right-recursive grammars

D Non-recursive grammars

💡 Hint

Consider what happens when a function calls itself immediately without consuming input.

Left-recursive grammars cause infinite recursion in recursive descent parsers because the parser keeps calling the same function without consuming input. Such grammars must be rewritten to remove left recursion.

🔍 Analysis

advanced

Analyzing parser behavior on ambiguous grammar

Given the grammar:
S -> 'a' S 'b' | 'a' 'b'
What will a recursive descent parser do when parsing the input string "aabb"?

A Parse only the first 'ab' and stop, leaving input unconsumed.

B Successfully parse the string by matching the first rule recursively.

C Enter infinite recursion because of left recursion.

D Fail to parse due to ambiguity and backtracking issues.

💡 Hint

Check if the grammar is left-recursive and how the parser tries rules in order.

The grammar is right-recursive, not left-recursive, so the recursive descent parser can parse "aabb" by applying the first rule recursively until the base case 'a' 'b' is matched.

❓ Comparison

advanced

Comparing recursive descent parsing with other parsing methods

Which of the following is a key advantage of recursive descent parsing compared to table-driven LR parsing?

A It uses a parsing table to avoid backtracking and ambiguity.

B It can handle all context-free grammars without modification.

C It always produces the most efficient parse tree in linear time.

D It is easier to implement and understand because it uses straightforward recursive functions.

💡 Hint

Think about implementation complexity and readability.

Recursive descent parsing is simpler to implement and understand because it directly reflects the grammar rules as recursive functions, unlike LR parsing which requires complex tables and automata.

❓ Reasoning

expert

Determining the output of a recursive descent parser function

Consider the following pseudo-code for a recursive descent parser function for the rule Expr -> 'num' '+' Expr | 'num' parsing the input tokens [num, '+', num, '+', num]:

function parseExpr(tokens):
  if tokens[0] == 'num':
    consume 'num'
    if tokens[0] == '+':
      consume '+'
      parseExpr(tokens)
    return true
  else:
    return false

What will be the result of calling parseExpr on the given tokens?

A The function returns true after successfully parsing the entire input.

B The function returns false because it cannot handle multiple '+' operators.

C The function causes infinite recursion due to missing base case.

D The function returns true but leaves some tokens unconsumed.

💡 Hint

Trace the function calls and token consumption step by step.

The function consumes 'num', then if '+' is next, consumes it and recursively calls itself. This continues until no '+' is found. All tokens are consumed and the function returns true.

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