←back to thread

How I wrote a self-hosting C compiler in 40 days

(www.sigbus.info)
429 points rui314 | 7 comments | 14 Dec 15 14:07 UTC | HN request time: 0s | source | bottom
Show context
peterkelly ◴[14 Dec 15 16:45 UTC] No.10732090[source]▶
For anyone interested in compiler writing and looking for a good resource to start, probably one of the best is the "Dragon Book":

http://www.amazon.com/Compilers-Principles-Techniques-Tools-...

I highly recommend it, but it's heavy stuff. There are probably simpler guides out there that just cover the basics.

replies(6): >>10732136 #>>10732162 #>>10732256 #>>10732890 #>>10733017 #>>10742248 #
sklogic ◴[14 Dec 15 16:55 UTC] No.10732162[source]▶
Please stop recommending the Dragon Book already. It is not just heavy, it is mostly outdated and irrelevant.
replies(7): >>10732214 #>>10732311 #>>10732417 #>>10732559 #>>10732828 #>>10733072 #>>10733258 #
barrkel ◴[14 Dec 15 17:15 UTC] No.10732311[source]▶
It's fairly heavy in lexing and parsing theory, especially around finite automata, pushdown automata, etc. It's the kind of book you might want to read if you're reimplementing yacc.

Modern code generation has moved on a bit, so I wouldn't dig too deeply into the latter third or so of the book.

All in all, for a hobby compiler, it would be a poor choice; heavy on unnecessary theory in the front end and outdated on on back end stuff.

Let's Build a Compiler by Jack Crenshaw is one of my favourite guides for the hobbyist, although it's a bit dated now since it used Turbo Pascal and targeted 16-bit x86.

replies(1): >>10732885 #
sklogic ◴[14 Dec 15 18:40 UTC] No.10732885[source]▶
It does not make any sense to reimplement yacc in the 21st century. There are far more powerful and yet simple parsing techniques, rendering all that automata stuff useless and outdated. Take a look at PEG, Pratt parsing and GLR.
replies(2): >>10733238 #>>10733267 #
1. wtetzner ◴[14 Dec 15 19:42 UTC] No.10733267[source]▶
Or even better, GLL.

http://dotat.at/tmp/gll.pdf

replies(2): >>10735271 #>>10735314 #
2. nickpsecurity ◴[15 Dec 15 01:06 UTC] No.10735271[source]▶
Best features of both types of parsers? Hell yeah! Never even heard of this one despite all the research updates I did a few years ago. Thanks for the link.
3. sklogic ◴[15 Dec 15 01:13 UTC] No.10735314[source]▶
It's an interesting one, I'll add it to my collection.

Although, to be fair, PEG (Packrat) do support left recursion [1], and it can also be combined with Pratt for the binary expressions very efficiently, at O(n).

[1] http://www.vpri.org/pdf/tr2007002_packrat.pdf

replies(1): >>10735857 #
4. wtetzner ◴[15 Dec 15 04:04 UTC] No.10735857[source]▶
> Although, to be fair, PEG (Packrat) do support left recursion [1]

Unfortunately it sometimes generates the wrong parse: http://tratt.net/laurie/research/pubs/papers/tratt__direct_l...

replies(1): >>10736567 #
5. sklogic ◴[15 Dec 15 08:12 UTC] No.10736567{3}[source]▶
And all the edge cases are related to the binary expressions - and you should be using Pratt for them instead.

Left recursive PEG must be reserved for things like method, structure field and array access, which are ok with that algorithm.

replies(1): >>10738280 #
6. wtetzner ◴[15 Dec 15 15:30 UTC] No.10738280{4}[source]▶
Ah, gotcha. I struggled with PEG and left recursion for a while before finding GLL. Do you have any resources on how to combine PEG and Pratt?
replies(1): >>10738685 #
7. sklogic ◴[15 Dec 15 16:31 UTC] No.10738685{5}[source]▶
There must have been some papers on it, but I lost a track. Will try to dig out something.

Meanwhile, you can take a look a my implementation of such a mix: https://github.com/combinatorylogic/mbase/tree/master/src/l/...

An example of a grammar built on top of it: https://github.com/combinatorylogic/clike/blob/master/clike/... - see the `binary` nodes there, they're translated into Pratt while all the others are Packrat.