Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

sigbus.info

Post reply on HN
Print view View original

111–120 of 128 posts

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

#111

Post by alricb »

nly wrote: post #32
peter303 wrote: post #24

Long ago UNIX had compiler writing tools like yacc and lex. I wonder if they are useful for exercises like this.

They might, although no production quality C or C++ compiler uses anything other than a hand-rolled recursive descent parser, afaik. The lex, parse and AST directories in Clangs source tree are ~100,000 LOC combined, and all hand-written.

Not now, no, but back in the 4.0 days (2005) GCC still used a yacc/bison parser for C; it had switched to a hand written parser for C++. The C++ yacc parser was still in use as of GCC 3.3 (2003).

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

#112

Post by DougMerritt »

tomcam wrote: post #99
eliben wrote: post #45

Earlier quoted context omitted.

Out of curiosity - why do you consider cpp particularly hard? It's easier than the compiler, actually :)

Well... easier than the compiler but very hard to do the last 20% (I never had the time; hobby project) because docs are so hard to find. Or at least were--maybe that's changed.

There are lots of corner cases that people are unaware of, such that almost all reinventions of the C preprocessor are technically broken, but in ways that typically won't be noticed.

One of the primary authors of the standard posted a corner case where the standard was wrong, and one needed his posting to design one piece of the preprocessor correctly.

Generally when people say "why do you say XYZ is hard? I did it and it was easy!" -- they haven't put their creation into industrial use with millions of users, and hence are unaware of its flaws.

As you say, just doing the metaphorical 80% of most things is indeed easy, but not the remainder.

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

#113

Post by wtetzner »

sklogic wrote: post #107
wtetzner wrote: post #75

Earlier quoted context omitted.

Or even better, GLL. http://dotat.at/tmp/gll.pdf

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

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

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

#114

Post by PeCaN »

c4n4rd wrote: post #8
sdegutis wrote: post #3

Thought this was going to be an inspiration to me to continue with my pet project of writing my own little programming language. But it starts off on day 8 with him already having written a basic compiler, with no explanation of how he did any of the basics. Still interesting, just not what I thought it was.

Same here. I have been trying the same project as you... and get stuck on the grammar, every.single.time. Are you done with that part yet?

Let me guess, you're stuck fighting yacc and shift-reduce conflicts?

I find writing your own parser to be much more instructive and a better way to understand why parser generators work the way they do.

Alternatively you can use a PEG generator such as peg/leg[1] and your grammar will more or less work (until it resolves an ambiguity in some way you didn't expect, anyway).

1: http://piumarta.com/software/peg/

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

#115

Post by sklogic »

wtetzner wrote: post #113
sklogic wrote: post #107

Earlier quoted context omitted.

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

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

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.

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

#116

Post by eliben »

rui314 wrote: post #109
eliben wrote: post #102

Earlier quoted context omitted.

What docs? It's all in the standard

The standard says too little about the preprocessor. I don't think you can implement a preprocessor that can read system header files only with the standard.

System header files usually employ platform-specific extensions not only on the preprocessor side, but in preprocessed code as well AFAIK. That is, the compiler has to support them too.

My comment was not to say that coding cpp is easy - just that it's not a particularly hard task compared to the compiler itself.

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

#117

Post by wtetzner »

sklogic wrote: post #115
wtetzner wrote: post #113

Earlier quoted context omitted.

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

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.

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?

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

#118

Post by sklogic »

wtetzner wrote: post #117
sklogic wrote: post #115

Earlier quoted context omitted.

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.

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?

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.

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

#119

Post by astrange »

peterkelly wrote: post #28

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.

Strong disagreement. The Dragon Book is super expensive, spends all its time discussing the easy part (parsing) as if it was complicated, then spends no time discussing modern algorithms in code generation.

Working from an example like LLVM or reading Appel or Wirth's books are better.

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

#120

Post by isolate »

astrange wrote: post #119
peterkelly wrote: post #28

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.

Strong disagreement. The Dragon Book is super expensive, spends all its time discussing the easy part (parsing) as if it was complicated, then spends no time discussing modern algorithms in code generation. Working from an example like LLVM or reading Appel or Wirth's books are better.

Also Muchnick's book is good for the middle end.
Post reply on HN