How I wrote a self-hosting C compiler in 40 days • Hacker News Board

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

#71

Post by sparkie » Mon, Dec 14, 2015, 7:38 PM UTC

sklogic wrote: post #57

barrkel wrote: post #37

Earlier quoted context omitted.

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…

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.

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.

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

#72

Post by nickpsecurity » Mon, Dec 14, 2015, 7:38 PM UTC

agumonkey wrote: post #62

nickpsecurity wrote: post #50

Earlier quoted context omitted.

It's in my references.

I just wanted to put it upfront rather than a link at the bottom.

It's all good. Makes sense. Just making sure one of us didn't overlook it in the references.

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

#73

Post by troydj » Mon, Dec 14, 2015, 7:41 PM UTC

sklogic wrote: post #30

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.

Please stop recommending the Dragon Book already. It is not just heavy, it is mostly outdated and irrelevant.

I wouldn't go so far to say that the Dragon Book is outdated and irrelevant. (I'm assuming you're referring to the 2nd edition from 2006.) Unless you're focusing on back-end optimization and code generation techniques (something a new compiler writer typically does NOT do), the bulk of the theory and material you'd cover in a first semester compiler course is fairly static.

But if a person is merely looking to bang out a compiler without getting overwhelmed with how to convert NFAs to DFAs for lexing, etc., some good alternative books are:

A Retargetable C Compiler: Design and Implementation, by Hanson and Fraser (http://www.amazon.com/Retargetable-Compiler-Design-Implement...). This book constructs and documents the explains the code for a full C compiler with a recursive descent approach (no flex/lex or bison/yacc). I have some experience augmenting this compiler, so I can vouch for the book's ability to clearly convey their design.

Compiler Design in C, by Allen Holub (http://www.holub.com/software/compiler.design.in.c.html). Downloadable PDF at that link as well. A book from 1990 in which Holub constructs his own version of lex and yacc, and then builds a subset-C compiler which generates intermediate code.

Practical Compiler Construction, by Nils Holm (http://www.lulu.com/shop/nils-m-holm/practical-compiler-cons...). A recent book which documents the construction of a SubC (subset of C) compiler and generates x86 code on the back end.

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

#74

Post by nickpsecurity » Mon, Dec 14, 2015, 7:42 PM UTC

sklogic wrote: post #63

nickpsecurity wrote: post #44

Earlier quoted context omitted.

There's quite a few decent alternatives. I often suggest Wirth's Compiler Construction and Oberon sources because they're straightforward lessons plus give experience with Wirth style of simple, safe, efficient languages. Then, they can improve the Oberon System or compilers for personal projects and improvement. That said, I typically recommend compilers get written in an ML or LISP given it's so much easier to do i…

Yes, functional side of things is interesting and rarely covered in the standard compilers courses. There is an old but good book, often overlooked: "Functional Programming" by Anthony J. Field and Peter G. Harrison (1988). Despite the title, it's more about various compilation techniques. Also an old but still relevant (it is missing the STG, but otherwise full of interesting stuff): http://research.microsoft.com/en…

I got the 2nd link here before, maybe from you. Might be old but very thorough treatment of about every aspect of functional compilation. I have it saved in djvu and pdf in case I neet someone starting in that area. :)

The other two are new to me. Thanks for those.

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

#75

Post by wtetzner » Mon, Dec 14, 2015, 7:42 PM UTC

sklogic wrote: post #57

barrkel wrote: post #37

Earlier quoted context omitted.

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…

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.

Or even better, GLL.

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

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

#76

Post by evanmoran » Mon, Dec 14, 2015, 7:51 PM UTC

btrask wrote: post #16

jwmerrill wrote: post #9

Earlier quoted context omitted.

I think the best inspiration to take here is that the best way to write a compiler in 40 days is to first write one in 400 days. From the first entry: > Implementing these features is easy because this is the second time for me.

And thus, the 10X programmer.

This is quite well said. It never occurred to me that 10x programmer is just the programmer who has already written code that grappled with the ideas that matter most. By your fifth compiler, all the basics seem easy.

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

#77

Post by ORioN63 » Mon, Dec 14, 2015, 7:54 PM UTC

sparkie wrote: post #71

sklogic wrote: post #57

Earlier quoted context omitted.

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.

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.

Or a lisp.

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

#78

Post by [deleted] » Mon, Dec 14, 2015, 8:00 PM UTC

rui314 wrote: post #60

sabujp wrote: post #42

1) write compiler 2) get a job at google . . 4) profit

I was already working at Google full-time (for an unrelated project) when I was writing this in my spare time.

[deleted]

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

#79

Post by sdegutis » Mon, Dec 14, 2015, 8:05 PM UTC

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?

I haven't finished any part of it yet. My goal is to write a small language entirely in C. It would have a lexer, parser, bytecode compiler, stack based bytecode VM, and GC. It would only have numbers, strings, and functions to start with. That would be my "hello world" that I can build on to add new features. And since it would all be written in C, it could be easily embeddable. So my goal is to make it similar to Lua, except with a nicer API for embedding. I've got some vacation days coming up and hope to make some progress on this during that time.

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

#80

Post by chrisseaton » Mon, Dec 14, 2015, 8:06 PM UTC

xigency wrote: post #68

Honestly, the most difficult, time consuming, and mundane aspect to this project would have to be the parser, which was apparently written in C by hand. So bravo. Getting to some of the final notes: > ... I'd choose a different design than that if I were to write it again. Particularly, I'd use yacc instead of writing a parser by hand and introduce an intermediate language early on. That's why I found the LALRPOP pos…

> Writing your own parser generator is actually much easier than writing a parser by-hand

Surely to write your own parser generator you will need to write a parser for your grammar language? So you are now writing that parser, and then your actual parser using your new grammar language? That can't be easier than writing one by hand.