C4 – C in 4 functions (github.com)
recommended by 1 user | 2014 | 517 points by petercooper | compilers | original thread |
One user recommended this thread. What they said:
userbinator Dec 4, 2015 | on: Self hosted C – breakdown | context

It's always great to see more people writing their own compilers - a "proof by example" that compilers do not have to be magical and mysterious special software that only few experts can write. The theory may be deep, but in practice getting a basic working compiler doesn't require all that much.

I notice you're using a recursive-descent parser, which I think is a good idea because it can actually reduce complexity over one made with parser-generators; in fact it's simple enough that even beginners who have just grasped recursion should be able to understand and write one. Once you have a basic parser that can evaluate arithmetic expressions, extending that to generating AST nodes and parse a (mostly) simple language like C is not so difficult. If I remember correctly, at least one college has an expression evaluator as a first-year CS assignment related to recursion. It's interesting that one of the sections of K&R, on reading and writing C declarations, even contains a simple parser for them --- I'm not aware of any introductory books for other languages which contain small pieces of their implementation.

That said, you can use the "precedence climbing" technique[1] to collapse many of the recursive functions for most of the expression operators into one function with a succinct loop and a table, making your parser even simpler and faster. C4[2] is an example of this technique but with a series of if-else in the body of the function instead of a table, and I think is worth some careful study just for its mindblowingly awesome ridiculous simplicity.

[1] https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing

[2] https://news.ycombinator.com/item?id=8558822