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

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 ]