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

Re:How I wrote a self-hosting C compiler in 40 days by barrkel on Monday December 14, 2015 @12:15PM (#10732311)

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.

[ Parent | on HN ]

Re:How I wrote a self-hosting C compiler in 40 days by sklogic on Monday December 14, 2015 @01:40PM (#10732885)

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.

[ Parent | on HN ]

Re:How I wrote a self-hosting C compiler in 40 days by wtetzner on Monday December 14, 2015 @02:42PM (#10733267)

Or even better, GLL.

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

[ Parent | on HN ]

Re:How I wrote a self-hosting C compiler in 40 days by nickpsecurity on Monday December 14, 2015 @08:06PM (#10735271)

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.

[ Parent | on HN ]

Re:How I wrote a self-hosting C compiler in 40 days by sklogic on Monday December 14, 2015 @08:13PM (#10735314)

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

[ Parent | on HN ]

Re:How I wrote a self-hosting C compiler in 40 days by wtetzner on Monday December 14, 2015 @11:04PM (#10735857)

> 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...

[ Parent | on HN ]

Re:How I wrote a self-hosting C compiler in 40 days by sklogic on Tuesday December 15, 2015 @03:12AM (#10736567)

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.

[ Parent | on HN ]

Re:How I wrote a self-hosting C compiler in 40 days by wtetzner on Tuesday December 15, 2015 @10:30AM (#10738280)

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?

[ Parent | on HN ]

Re:How I wrote a self-hosting C compiler in 40 days by sklogic on Tuesday December 15, 2015 @11:31AM (#10738685)

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.

[ Parent | on HN ]

Re:How I wrote a self-hosting C compiler in 40 days by sparkie on Monday December 14, 2015 @02:38PM (#10733238)

Pfft. Who wants to parse in 2015? We all know that constructing your language as a JSON schema is the way forward. Your JSON parser is the only parser you'll ever need.

[ Parent | on HN ]

Re:How I wrote a self-hosting C compiler in 40 days by ORioN63 on Monday December 14, 2015 @02:54PM (#10733339)

Or a lisp.

[ Parent | on HN ]