Hacker News Reader

I really like Ghuloum’s approach: you start by compiling a tiny, trivial subset of your source language all the way down to x86 assembly. Then you add new language features, one step at a time. In step one, you just return constants; in a later step you handle addition and subtraction; and so on. Every step is small enough to feel manageable, and at the end of the every step you have a working compiler.

That approach sounds like the same one in Jack Crenshaw's very lucid tutorial:

https://compilers.iecc.com/crenshaw/

He uses Pascal to write a Pascal compiler, but the basic steps seem to be the same --- start with a very simple lexer, add pieces to it incrementally, then write a recursive-descent parser on top of that and gradually extend it to handle more of the language.

Another simplification that really helps, once you're used to recursive descent and have noticed that the functions for each operator/precedence level are very similar, is to refactor them into a lookup table and an even simpler function that uses it, creating "precedence climbing":

https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

That makes it very easy to add/change/extend operators, or even have them be user-defined(!) and dynamically modifiable.

As a demonstration of how absolutely tiny a compiler can be, this one is worth inspecting carefully --- it also uses a handwritten lexer and recursive-descent parser, but doesn't make an AST and just emits code for a stack VM: https://news.ycombinator.com/item?id=8558822

...and someone modified that one to make an x86 JIT: https://news.ycombinator.com/item?id=8746054

View on HN