CD Notes

Recursive Descent Parsers: Procedural Approach to Top-Down Parsing

Master recursive descent parsing: grammar transformation, procedure generation, backtracking mechanisms, error recovery, implementation patterns, and practical compiler design with ASCII automata diagrams.

Introduction

A recursive descent parser is a top-down parser implemented as a collection of recursive procedures. Each non-terminal in the grammar corresponds to a procedure that recognizes that non-terminal's syntax.

Why Recursive Descent?

Example

Advantages: 1. Natural correspondence: Grammar ↔ Code structure 2. Easy to understand and debug 3. Can integrate error recovery easily 4. Direct implementation without table generation 5. Flexible action placement (semantic actions)

Grammar Requirements

LL(1) Grammar Prerequisite

Recursive descent works naturally with LL(1) grammars (no left recursion, no ambiguity):

1. No left recursion: A	A α \| β
2. No common prefixes: A	a α \| a β
3. FIRST-FOLLOW disjoint: For A	α \| β:

Grammar Transformations

Eliminate Left Recursion:

Original

E → E + T | T

Transformed

E → T E'

E' → + T E' | ε

Factor out Common Prefixes:

Original

Statement → if expr then stmt else stmt

| if expr then stmt

Transformed

Statement → if expr then stmt Else_part

Else_part → else stmt | ε

Parsing Procedures

Basic Structure

python example

def parse_nonterminal():
    # For production A → X₁ X₂ ... Xₖ:
    
    for each symbol Xi in production:
        if Xi is terminal:
            if current_token != Xi:
                error(f"Expected {Xi}")
            advance()
        else:  # Xi is non-terminal
            parse_Xi()
    
    # Optional: semantic action
    return result

Handling Alternatives

python example

def parse_Statement():
    if lookahead == 'if':
        # Statement → if Condition then Statement else Statement
        advance()  # consume 'if'
        parse_Condition()
        expect('then')
        parse_Statement()
        expect('else')
        parse_Statement()
    elif lookahead == 'while':
        # Statement → while Condition do Statement
        parse_While_Statement()
    elif lookahead == '{':
        # Statement → Block
        parse_Block()
    else:
        error(f"Unexpected token: {lookahead}")

Concrete Example: Expression Parser

Grammar

E	T E'
E'	+ T E' \| ε
T	F T'
T'	* F T' \| ε
F	( E ) \| id \| num

Implementation

Example

class Parser: def __init__(self, tokens): self.tokens = tokens self.pos = 0 def current_token(self): if self.pos < len(self.tokens): return self.tokens[self.pos] return None def advance(self): self.pos += 1 def expect(self, expected): if self.current_token() != expected: raise SyntaxError(f"Expected {expected}, got {self.current_token()}") self.advance() def parse_E(self): result = self.parse_T() result = self.parse_E_prime(result) return result def parse_E_prime(self, left): if self.current_token() == '+': self.advance() right = self.parse_T() left = BinOp('+', left, right) left = self.parse_E_prime(left) # else ε (do nothing) return left def parse_T(self): result = self.parse_F() result = self.parse_T_prime(result) return result def parse_T_prime(self, left): if self.current_token() == '*': self.advance() right = self.parse_F() left = BinOp('*', left, right) left = self.parse_T_prime(left) return left def parse_F(self): token = self.current_token() if token == '(': self.advance() result = self.parse_E() self.expect(')') return result elif token.type == 'ID': self.advance() return Var(token.value) elif token.type == 'NUM': self.advance() return Num(token.value) else: raise SyntaxError(f"Unexpected token: {token}")

Backtracking Implementation

Some recursive descent parsers use backtracking for disambiguation:

python example

def parse_Statement_with_backtracking():
    saved_pos = pos
    
    try:
        # Try first alternative
        parse_Assignment()
        return "assignment"
    except:
        # Backtrack
        pos = saved_pos
    
    try:
        # Try second alternative
        parse_Expression_Statement()
        return "expression"
    except:
        # All alternatives failed
        pos = saved_pos
        raise SyntaxError()

Error Recovery

Error Recovery Strategy

python example

def expect(self, token_type):
    if self.current_token().type != token_type:
        self.error(f"Expected {token_type}")
        # Synchronize to known state
        self.synchronize()
        return False
    self.advance()
    return True

def synchronize(self):
    # Skip tokens until reaching synchronized position
    sync_tokens = {';', '}', 'if', 'while', 'for'}
    
    while self.current_token() not in sync_tokens:
        self.advance()
    
    if self.current_token() == ';':
        self.advance()

Parse Tree Construction

Building AST Nodes During Parsing

python example

class Node:
    pass

class BinOp(Node):
    def __init__(self, op, left, right):
        self.op = op
        self.left = left
        self.right = right

class Num(Node):
    def __init__(self, value):
        self.value = value

# During parsing:
def parse_E_prime(self, left):
    if self.current_token() == '+':
        self.advance()
        right = self.parse_T()
        # Construct AST node
        left = BinOp('+', left, right)
        left = self.parse_E_prime(left)
    return left

Recursive Descent vs Table-Driven LR

Aspect	Recursive Descent	Table-Driven LR
Implementation	Procedures	Tables + algorithm
Grammar class	LL(1)	LR(1)
Table generation	None	Automatic
Code size	Larger (procedures)	Smaller (tables)
Debugging	Easier (trace calls)	Harder (stack machine)
Error handling	Natural	Requires code
Flexibility	High	Lower
Performance	Comparable	Comparable

Advantages and Limitations

Advantages ✓

Intuitive: Direct grammar-to-code mapping
Debuggable: Procedure call stack visible
Flexible error handling: Insert recovery anywhere
Hand-implementable: No tool needed
Clear semantics: Actions in procedures

Limitations ✗

Grammar restrictions: Must be LL(1)
Backtracking: Inefficient for large inputs
Indirect left recursion: Infinite loops possible
Scaling: Many procedures for complex grammars
Maintenance: Changes require procedure updates

Quick Revision Notes

Recursive descent: Each procedure recognizes one non-terminal
LL(1) required: Deterministic lookahead drives choices
Left recursion elimination: Convert A → Aα | β before implementation
Procedure structure: For each alternative, check lookahead, parse symbols
Error recovery: Sync on punctuation, restart parsing
Backtracking: Save position, restore on failure (expensive)
AST construction: Build nodes during parse, return from procedures

Interview Q&A

Q1: Why do recursive descent parsers require LL(1) grammars?

A: Recursive descent uses one lookahead token to decide which production to apply. If multiple productions start the same way, you cannot decide which to use. LL(1) ensures each lookahead uniquely determines the production.

Q2: How do you implement error recovery in recursive descent parsers?

A: Catch exceptions from parsing failures, synchronize (skip tokens to known points like ; or }), then resume parsing. Many error recovery points can be placed naturally in procedures since they mirror grammar structure.

Q3: What's the advantage of recursive descent over automatic parser generation?

A: Manual code is easier to debug (procedure call stack visible), more flexible for error recovery, and sometimes more efficient for small grammars. No tool needed. Disadvantage: manual work, easier to introduce bugs.

Q4: Can recursive descent parsers handle right recursion?

A: Yes, right recursion works naturally: A → X A | ε becomes parse_A() { parse_X(); parse_A(); }. Left recursion causes infinite recursion and must be eliminated first. This is why LL(1) transformation to eliminate left recursion is necessary.

Q5: How do you handle semantic actions in recursive descent parsers?

A: Add code directly in the procedure after parsing symbols. Collect attribute values from recursive calls, compute new values, return results. Attribute flow is explicit (parameters and return values) rather than implicit via stacks.

Q6: Why is backtracking inefficient in recursive descent parsers?

A: Backtracking requires re-scanning input and re-executing procedures, wasting work. For large inputs, multiple failed attempts mean O(n²) or worse complexity. LL(1) grammars avoid this by deterministic lookahead.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Recursive Descent Parsers: Procedural Approach to Top-Down Parsing.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, syntax, analysis, recursive, descent

Continue learning this concept

Syntax AnalysisCLR Parser: Canonical LR(1) Parsing with Complete Lookahead InformationComprehensive exploration of CLR parser construction: complete item sets, lookahead propagation algorithms, full DFA generation, parsing tables, comparison with SLR/LALR, practical compiler implementation.Syntax AnalysisLALR Parser: Practical LR(1) With State Merging for EfficiencyMaster LALR parsing: state merging techniques, lookahead merge rules, DFA construction, parsing table generation, conflict detection, comparison with SLR/CLR, industry standard compiler implementation.Syntax AnalysisLL(1) Parser: Single Lookahead Predictive Parsing from First PrinciplesMaster LL(1) parsing: grammar conversion to LL(1) form, FIRST/FOLLOW computation, parsing table construction, parse decisions, error recovery, practical recursive descent implementation with examples.Syntax AnalysisLR Parsers: Canonical LR Parsing for Complex Language SyntaxComplete guide to LR(1) parsers: item sets, lookahead computation, DFA construction, parsing table generation, shift-reduce decisions, conflict resolution, and modern compiler toolchain applications.Syntax AnalysisPredictive Parsers: Lookahead-Guided Top-Down ParsingComprehensive guide to predictive parsing techniques using lookahead tokens, FIRST and FOLLOW sets, parsing tables, and practical implementations with detailed examples and parse tree diagrams.Syntax AnalysisShift-Reduce Parsing: Fundamental Mechanism of Bottom-Up Syntax AnalysisDeep exploration of shift-reduce parsing: stack operations, reduction strategies, action tables, conflict types and resolution, relationship to LR parsing, practical implementations with complete examples.

PreviousPredictive Parsers: Lookahead-Guided Top-Down Parsing NextShift-Reduce Parsing: Fundamental Mechanism of Bottom-Up Syntax Analysis

CD Notes

Recursive Descent Parsers: Procedural Approach to Top-Down Parsing

Introduction

Why Recursive Descent?

Example

Grammar Requirements

LL(1) Grammar Prerequisite

Recursive descent works naturally with LL(1) grammars (no left recursion, no ambiguity):

1. No left recursion: A	A α \| β
2. No common prefixes: A	a α \| a β
3. FIRST-FOLLOW disjoint: For A	α \| β:

Grammar Transformations

Eliminate Left Recursion:

Original

E → E + T | T

Transformed

E → T E'

E' → + T E' | ε

Factor out Common Prefixes:

Original

Statement → if expr then stmt else stmt

| if expr then stmt

Transformed

Statement → if expr then stmt Else_part

Else_part → else stmt | ε

Parsing Procedures

Basic Structure

python example

def parse_nonterminal():
    # For production A → X₁ X₂ ... Xₖ:
    
    for each symbol Xi in production:
        if Xi is terminal:
            if current_token != Xi:
                error(f"Expected {Xi}")
            advance()
        else:  # Xi is non-terminal
            parse_Xi()
    
    # Optional: semantic action
    return result

Handling Alternatives

python example

def parse_Statement():
    if lookahead == 'if':
        # Statement → if Condition then Statement else Statement
        advance()  # consume 'if'
        parse_Condition()
        expect('then')
        parse_Statement()
        expect('else')
        parse_Statement()
    elif lookahead == 'while':
        # Statement → while Condition do Statement
        parse_While_Statement()
    elif lookahead == '{':
        # Statement → Block
        parse_Block()
    else:
        error(f"Unexpected token: {lookahead}")

Concrete Example: Expression Parser

Grammar

E	T E'
E'	+ T E' \| ε
T	F T'
T'	* F T' \| ε
F	( E ) \| id \| num

Implementation

Example

Backtracking Implementation

Some recursive descent parsers use backtracking for disambiguation:

python example

def parse_Statement_with_backtracking():
    saved_pos = pos
    
    try:
        # Try first alternative
        parse_Assignment()
        return "assignment"
    except:
        # Backtrack
        pos = saved_pos
    
    try:
        # Try second alternative
        parse_Expression_Statement()
        return "expression"
    except:
        # All alternatives failed
        pos = saved_pos
        raise SyntaxError()

Error Recovery

Error Recovery Strategy

python example

def expect(self, token_type):
    if self.current_token().type != token_type:
        self.error(f"Expected {token_type}")
        # Synchronize to known state
        self.synchronize()
        return False
    self.advance()
    return True

def synchronize(self):
    # Skip tokens until reaching synchronized position
    sync_tokens = {';', '}', 'if', 'while', 'for'}
    
    while self.current_token() not in sync_tokens:
        self.advance()
    
    if self.current_token() == ';':
        self.advance()

Parse Tree Construction

Building AST Nodes During Parsing

python example

class Node:
    pass

class BinOp(Node):
    def __init__(self, op, left, right):
        self.op = op
        self.left = left
        self.right = right

class Num(Node):
    def __init__(self, value):
        self.value = value

# During parsing:
def parse_E_prime(self, left):
    if self.current_token() == '+':
        self.advance()
        right = self.parse_T()
        # Construct AST node
        left = BinOp('+', left, right)
        left = self.parse_E_prime(left)
    return left

Recursive Descent vs Table-Driven LR

Aspect	Recursive Descent	Table-Driven LR
Implementation	Procedures	Tables + algorithm
Grammar class	LL(1)	LR(1)
Table generation	None	Automatic
Code size	Larger (procedures)	Smaller (tables)
Debugging	Easier (trace calls)	Harder (stack machine)
Error handling	Natural	Requires code
Flexibility	High	Lower
Performance	Comparable	Comparable

Advantages and Limitations

Advantages ✓

Intuitive: Direct grammar-to-code mapping
Debuggable: Procedure call stack visible
Flexible error handling: Insert recovery anywhere
Hand-implementable: No tool needed
Clear semantics: Actions in procedures

Limitations ✗

Grammar restrictions: Must be LL(1)
Backtracking: Inefficient for large inputs
Indirect left recursion: Infinite loops possible
Scaling: Many procedures for complex grammars
Maintenance: Changes require procedure updates

Quick Revision Notes

Recursive descent: Each procedure recognizes one non-terminal
LL(1) required: Deterministic lookahead drives choices
Left recursion elimination: Convert A → Aα | β before implementation
Procedure structure: For each alternative, check lookahead, parse symbols
Error recovery: Sync on punctuation, restart parsing
Backtracking: Save position, restore on failure (expensive)
AST construction: Build nodes during parse, return from procedures

Interview Q&A

Q1: Why do recursive descent parsers require LL(1) grammars?

Q2: How do you implement error recovery in recursive descent parsers?

Q3: What's the advantage of recursive descent over automatic parser generation?

Q4: Can recursive descent parsers handle right recursion?

Q5: How do you handle semantic actions in recursive descent parsers?

Q6: Why is backtracking inefficient in recursive descent parsers?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Recursive Descent Parsers: Procedural Approach to Top-Down Parsing.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, syntax, analysis, recursive, descent

Continue learning this concept

PreviousPredictive Parsers: Lookahead-Guided Top-Down Parsing NextShift-Reduce Parsing: Fundamental Mechanism of Bottom-Up Syntax Analysis