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 🌲.
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>