Back
+20 XP
Concept

Recursive Descent Parsing from Scratch

Recursive descent is a top-down parsing method where each grammar rule maps to a dedicated function. Functions call each other recursively to parse hierarchical grammar trees, naturally resolving operator precedence 🌲.

python
class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def peek(self):
        return self.tokens[self.pos] if self.pos < len(self.tokens) else None

    def consume(self):
        t = self.peek()
        self.pos += 1
        return t

    def factor(self):
        t = self.consume()
        if t == '(':
            val = self.expr()
            self.consume()  # ')'
            return val
        return int(t)

    def term(self):
        val = self.factor()
        while self.peek() == '*':
            self.consume()
            val *= self.factor()
        return val

    def expr(self):
        val = self.term()
        while self.peek() == '+':
            self.consume()
            val += self.term()
        return val

tokens = ['(', '3', '+', '2', ')', '*', '4']
print(f"Evaluated: {Parser(tokens).expr()} 🌲")

# 73. Recursive Descent Parsing from Scratch Recursive descent is a top-down parsing method where each grammar rule maps to a dedicated function. Functions call each other recursively to parse hierarchical grammar trees, naturally resolving operator precedence 🌲. ```python class Parser: def __init__(self, tokens): self.tokens = tokens self.pos = 0 def peek(self): return self.tokens[self.pos] if self.pos < len(self.tokens) else None def consume(self): t = self.peek() self.pos += 1 return t def factor(self): t = self.consume() if t == '(': val = self.expr() self.consume() # ')' return val return int(t) def term(self): val = self.factor() while self.peek() == '*': self.consume() val *= self.factor() return val def expr(self): val = self.term() while self.peek() == '+': self.consume() val += self.term() return val tokens = ['(', '3', '+', '2', ')', '*', '4'] print(f"Evaluated: {Parser(tokens).expr()} 🌲") ``` Python 3.9 replaced CPython's original LL(1) parser with a modern PEG (Parsing Expression Grammar) parser, allowing infinite lookahead and eliminating historic grammar hacks 🚀! --- ### Question Why does the recursive descent rule hierarchy `expr -> term -> factor` enforce correct operator precedence? 🧠 - [ ] a. Higher-precedence operations (like multiplication) resolve deeper in the call stack before lower ones (like addition) 🌲 - [ ] b. The lexer automatically sorts tokens in descending order before parsing - [ ] c. Python's compiler runtime prioritizes methods with fewer lines of code - [ ] d. Parentheses are rewritten into temporary shell variables --- ### Challenge Implement a mini recursive descent parser handling `+` and `*` with correct precedence on `['2', '+', '3', '*', '4']`. Print the evaluated integer. 🎯 <details> <summary>Solution</summary> ```python class Parser: def __init__(self, tokens): self.tokens = tokens self.pos = 0 def peek(self): return self.tokens[self.pos] if self.pos < len(self.tokens) else None def consume(self): t = self.peek() self.pos += 1 return t def factor(self): return int(self.consume()) def term(self): val = self.factor() while self.peek() == '*': self.consume() val *= self.factor() return val def expr(self): val = self.term() while self.peek() == '+': self.consume() val += self.term() return val print(Parser(['2', '+', '3', '*', '4']).expr()) ``` </details>

Checkpoint

Why does the recursive descent rule hierarchy `expr -> term -> factor` enforce correct operator precedence? 🧠

Practice

Implement a mini recursive descent parser handling `+` and `*` with correct precedence on `['2', '+', '3', '*', '4']`. Print the evaluated integer. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks