python 69 lines · 9 steps

A recursive descent arithmetic parser

A hand-written parser tokenizes an arithmetic string and evaluates it with one function per precedence level.

Explained by highlit
Intermediate recursive-descent tokenizer operator-precedence grammar recursion
1class Parser:
2 def __init__(self, text):
3 self.tokens = self._tokenize(text)
4 self.pos = 0
5 
6 def _tokenize(self, text):
7 tokens = []
8 i = 0
9 while i < len(text):
10 c = text[i]
11 if c.isspace():
12 i += 1
13 elif c in "+-*/()":
14 tokens.append(c)
15 i += 1
16 elif c.isdigit() or c == ".":
17 j = i
18 while j < len(text) and (text[j].isdigit() or text[j] == "."):
19 j += 1
20 tokens.append(float(text[i:j]))
21 i = j
22 else:
23 raise ValueError(f"Unexpected character: {c!r}")
24 return tokens
25 
26 def _peek(self):
27 return self.tokens[self.pos] if self.pos < len(self.tokens) else None
28 
29 def _advance(self):
30 tok = self.tokens[self.pos]
31 self.pos += 1
32 return tok
33 
34 def parse(self):
35 value = self._expr()
36 if self.pos != len(self.tokens):
37 raise ValueError("Unexpected trailing input")
38 return value
39 
40 def _expr(self):
41 value = self._term()
42 while self._peek() in ("+", "-"):
43 op = self._advance()
44 rhs = self._term()
45 value = value + rhs if op == "+" else value - rhs
46 return value
47 
48 def _term(self):
49 value = self._factor()
50 while self._peek() in ("*", "/"):
51 op = self._advance()
52 rhs = self._factor()
53 value = value * rhs if op == "*" else value / rhs
54 return value
55 
56 def _factor(self):
57 tok = self._peek()
58 if tok == "(":
59 self._advance()
60 value = self._expr()
61 if self._advance() != ")":
62 raise ValueError("Expected closing parenthesis")
63 return value
64 if tok == "-":
65 self._advance()
66 return -self._factor()
67 if isinstance(tok, float):
68 return self._advance()
69 raise ValueError(f"Unexpected token: {tok!r}")
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Splitting tokenizing from parsing keeps each stage simple and independently testable.
  2. 2One parse function per precedence level makes operator precedence fall out of the call structure.
  3. 3A shared position cursor with peek and advance lets recursive functions cooperate over one token stream.

Related explainers

python 
import re
from dataclasses import dataclass, field
 
 

Building a table of contents from Markdown

regular-expressions parsing slugification
Intermediate 9 steps
rust 
use std::collections::HashMap;
 
#[derive(Clone, Copy, PartialEq)]
enum Color {

Detecting cycles with three-color DFS in Rust

graph-algorithms cycle-detection depth-first-search
Intermediate 9 steps
python 
from flask import Blueprint, render_template, redirect, url_for, session, request
from wtforms import Form, StringField, SelectField, IntegerField
from wtforms.validators import DataRequired, Email, NumberRange
 

A multi-step signup wizard in Flask

blueprints session-state form-validation
Intermediate 10 steps
python 
from itertools import cycle
from collections import defaultdict
 
 

Round-robin task distribution in Python

round-robin iterators load-balancing
Intermediate 6 steps
python 
import base64
import json
from typing import Annotated, Optional
 

Cursor pagination in a FastAPI endpoint

pagination cursor async
Intermediate 9 steps
typescript 
type TokenType = "keyword" | "string" | "comment" | "number" | "text";
 
interface Token {
  type: TokenType;

How a regex tokenizer highlights code

tokenizer regex lexing
Intermediate 10 steps

Share this explainer

Here's the card — post it anywhere.

A recursive descent arithmetic parser — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code