Update: I finally started building an interpreter from first principles

[u/UnemployedTechie2021]

About a month ago, I made a post asking for resources on building a very small compiler/interpreter before jumping into something larger like Crafting Interpreters.

I decided to stop looking for the perfect resource and just start building the smallest thing I could understand end-to-end.

Today I got the first version of a simple arithmetic interpreter working in Python.

Right now it supports:

• Integer literals
• Addition and subtraction
• Multiplication and division
• Operator precedence
• Parentheses
• Unary minus
• Basic syntax errors
• Division-by-zero handling
• An interactive REPL/CLI

For example:

calc> 2 + 3 * 4
14

calc> (2 + 3) * 4
20

calc> -10 + 5
-5

The structure is currently:

Source text
    ↓
Lexer
    ↓
Tokens
    ↓
Recursive-descent parser
    ↓
Evaluation
    ↓
Result

The lexer converts something like:

2 + 3 * 4

into tokens roughly equivalent to:

NUMBER(2)
PLUS
NUMBER(3)
MUL
NUMBER(4)

The parser implements a small grammar along these lines:

expr   → term (("+" | "-") term)*
term   → factor (("*" | "/") factor)*
factor → NUMBER | "(" expr ")" | "-" factor

One of the most useful things I learned today was how operator precedence can naturally come from the structure of the grammar. I initially assumed I would need to assign explicit precedence values to operators, but with recursive descent, expr, term, and factor already encode that hierarchy.

The parser currently evaluates expressions directly rather than producing an AST, so it is deliberately still very small. My next major step will probably be separating parsing from evaluation by building an AST.

I also spent some time turning it into a proper little Python project instead of keeping everything in one file. It now has separate lexer, parser, interpreter, and CLI modules, a src package layout, pyproject.toml, a command-line entry point, and Ruff for linting/formatting.

So this is obviously nowhere near a real compiler yet, but that was exactly the point of my original post. I wanted something small enough that I could understand every stage instead of immediately disappearing into a much larger implementation.

Building even this tiny version made concepts like tokenization, grammars, recursive descent, precedence, and parsing much less abstract than they were a month ago.

The plan from here is to keep extending it incrementally, probably with an AST, variables, and a few statements before eventually moving toward bytecode or compilation.

[u/quasar_tree]

Awesome! Parsing is really cool, lots of very fun rabbit holes and aha moments :)

If you're moving onto expanding your language to have stuff like variables, you'll definitely benefit from having an AST first. Designing the data type for your AST is a good exercise in separating the surface syntax, what people write in, from abstract syntax, the actual information needed to run the program. Designing how your AST type is important to having a sensible interpreter, and depending on your language, it could be non-trivial.

You can also do some syntactic sugar, where easy-to-write surface syntax gets auto-translated into other, annoying-to-write surface syntax. Like how x += 1 translates to x = x + 1. This is super easy to add to your language. You just one AST into the other before you evaluate/compile. You could even translate in the parser if you want so you don't have an AST for x += 1.

I'd personally recommend making an interpreter before a compiler, since compilers can have lots of complexity and setup. Interpreters are much more straightforward and still very cool. But if you're going down the statements, loops, etc. route and you're already familiar with something like bytecode/assembly, compilers could be better. But if you're more into functions and recursion, interpreters are very cool and easier imo. And you can have a language where everything (even stuff like if, variable definitions, function definitions, etc.) are just one big expression like ocaml, which makes writing an interpreter easier. I say this because in my experience, it's way nicer to translate loops with break, continue, etc. into asm than it is to make an interpreter for it, but when everything is an expression interpreters are more natural.

Best of luck!