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/dwaynecrooks]

I think you're on the right track. I would caution against focusing on syntactically interesting features over semantically interesting ones. For e.g. all the features you listed are syntactically interesting and give you practice with the front-end of an interpreter/compiler. However, the really interesting parts of programming languages, at least for me, come when you're implementing features that have interesting semantics.

One under appreciated resource that encourages the approach I'm suggesting is the book "Essentials of Programming Languages by Friedman and Wand". It teaches you how to build various language features by modelling them with interpreters. But then it guides you into performing various semantics preserving transformations on those same interpreters to turn them into compilers for an abstract machine. It doesn't take you all the way to machine code but nonetheless you learn so much that's applicable not just to interpreters/compilers but to DSLs and library design as well.

Some of the things you'd learn include: defunctionalization, abstract syntax trees, static scoping, dynamic scoping, closures, call-by-value, call-by-reference, call-by-name, call-by-need, continuation-passing style, continuations, trampolining, exception handling, multi-threading.

For e.g. here's an interpreter that uses continuation-passing style that has support for threads and mutexes.

Haskell: https://github.com/dwayne/eopl3/tree/cce965ec7876f0d5dc7c65e7973b78cc59edf8df/solutions/05-ch5/interpreters/haskell/MUTEX

Elm: https://github.com/dwayne/elm-eopl3/tree/a82001840612bc3c7dc9f4f13cbce3260e8769f0/src/Ch5/MUTEX

The book uses Scheme, I did it in Haskell and Elm, but you can try it in Python too.

I recently started a project to teach, from the ground up, how programming languages work by building tiny interpreters. If that sounds interesting to you then check out: https://blog.tinyinterpreters.dev/about/ to learn more. The plan is to cover everything from EOPL and much much more.

[u/Inconstant_Moo → u/[deleted]]

But many people, especially in the Compilers sub, are obsessed with table-driven expression parsing, especially with the version called 'Pratt'.

It's not an obsession, it's just the only one I understand. And even then only best-out-of-three.

[u/beephod_zabblebrox → u/Inconstant_Moo]

do you not understand the tower of functions thing? genuine question

[u/Inconstant_Moo → u/beephod_zabblebrox]

I don't mean that the others have actually defeated me, I mean that having mastered Pratt I feel I've learned enough parser theory for one lifetime.

[u/max123246]

Sick

[u/Much-Gap2454]

Crafting interpreters is a fine book for your ambitions. It covers both the Pratt parser and your approach.

[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!