20 ms·
How I wrote a self-hosting C compiler in 40 days
- deleted 11y ago[deleted]
- sdegutis 11y agoThought 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.
- tomcam 11y agoLuckily you can see the history on Git.
- tomcam 11y agoLuckily you can see the history on Git.
- c4n4rd 11y agoSame 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?
- jerf 11y agoWhat do you mean "stuck on the grammar"? Can't figure out how to write a grammar, can't get all the fiddly implications correct so OOO fails, can't figure out how to write the parser, can't muster up enough enthusiasm to finish the work...? One option is to punt for a bit and use what I sometimes call the "Lisp non-grammar", even if you don't intend to be writing a Lisp; use parentheses to directly encode a parse tree, and whatever other hacky symbols you need for now to set up atom types or whatever. You might still be able to explore enough what you're interested in to figure out what you want in the grammar. Whatever the core idea of your toy language is, you should try to get to that as quickly as possible, punting on everything else you possibly can, so if the point of your language isn't to have an innovative new grammar, you might want to try to defer that work.
- arcatek 11y agoOn which parts exactly are you stuck? I've rolled with Ragel as lexer, and Lemon as parser, and it was relatively simple. [1] https://github.com/castel/libcastel/blob/master/parse/sources/lex/Lexer.rl#L35-L193 https://github.com/castel/libcastel/blob/master/parse/source... [2] https://github.com/castel/libcastel/blob/master/parse/sources/parse/lemon-parser.lm https://github.com/castel/libcastel/blob/master/parse/source...
- pjc50 11y agoThe C grammar is printed in BNF in the back of K&R and available in machine-readable form in the standards.
- zerr 11y agoIt's fine. "Compilers" topic is too wide. There are lot of sub-topics. I personally find lexing/parsing rather boring. It's after I have AST is when the fun begins for me (and right before actual/real code gen, where you have to know intricacies of particular CPU) :)
- sdegutis 11y agoI 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.
- PeCaN 11y agoLet 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/ http://piumarta.com/software/peg/
- jwmerrill 11y agoI 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.
- btrask 11y agoAnd thus, the 10X programmer.
- evanmoran 11y agoThis 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.
- mpweiher 11y ago"If you want to be a Millionaire, start with a billion dollars and launch a new airline ." -- Richard Branson
- zellyn 11y agoI can't recommend the Coursera compilers course highly enough. It was enough to get me from zero to a fully working compiler. Albeit for a simplified language, and a really bad compiler :-) If you did it in one of the languages for which scaffolding already exists, it'll be even easier (I did it in a different language, so had to build everything from scratch).
- tomcam 11y agoI was a little surprised that the author was able to manage both C11 and the preprocessor in that time. The preprocessor is hard. But there was existing code from a previous version of it, which makes sense. Still, a fantastic achievement! Congrats to the author!
- eliben 11y agoOut of curiosity - why do you consider cpp particularly hard? It's easier than the compiler, actually :)
- tomcam 11y agoWell... 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.
- eliben 11y agoWhat docs? It's all in the standard
- rui314 11y agoThe 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.
- eliben 11y agoSystem 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.
- DougMerritt 11y ago
- jlappi 11y agoThis is really interesting, and I was glad to see the author go beyond just the stated 40 days and give insight into where they went after it was 'self-hosting.'
- draugadrotten 11y agoInteresting, and quite funny to read with a sense of humour that reminds me of the movie PI. The author of the compiler goes from rational to something more... spiritual. "Day 52 I was looking for a mysterious bug for three days: ..." http://www.imdb.com/title/tt0138704/ http://www.imdb.com/title/tt0138704/
- jaybosamiya 11y ago> I suspect that he [Dennis Ritchie] invented a syntax, wrote code for it, which turned out to be more complicated than he had expected. And that was eventually standardized by the ANSI committee. It's hard to implement a standardized language because you have to get everything right. It's rather easy to write your own toy language. Love those lines
- nickpsecurity 11y agoIt's actually a clone of BCPL, which invented keywords & "programmer in charge philosophy." They ported it to PDP's with a few changes for UNIX. Standards came later. Specific details every step of the way are here: http://pastebin.com/UAQaWuWG http://pastebin.com/UAQaWuWG
- agumonkey 11y agoThat vimeo talk was rich. ps: https://vimeo.com/132192250 https://vimeo.com/132192250
- nickpsecurity 11y agoIt's in my references.
- agumonkey 11y agoI just wanted to put it upfront rather than a link at the bottom.
- nickpsecurity 11y agoIt's all good. Makes sense. Just making sure one of us didn't overlook it in the references.
- deleted 11y ago[deleted]
- yeison 11y agoWhat does it mean to be 'self-hosting' here? Does it just mean that it's a compiler that can compile itself?
- nlh 11y agoI believe so. FTA: "Looking at my code, even though I wrote it, it feels magical to me that it can handle itself as an input and translate it to assembly."
- wibr 11y agoyes "Day 40 Hooray! My compiler is now able to self-compile everything!"
- quickpost 11y agoThanks for asking the question I was embarrassed to ask - now I'm even more impressed with his accomplishment!
- quickpost 11y agoThanks for asking the question I was embarrassed to ask - now I'm even more impressed with his accomplishment!
- pskocik 11y agoNow repeat for C++.
- rav 11y agoConsidering that a considerably large subset of C is valid C++, it should be easy to modify 8cc to be valid C++ (e.g. by replacing implicit void*-casts to explicit ones), and then you already have a "self-hosting C++ compiler", but that could be considered cheating by some...
- serge2k 11y agoExcept it won't compile anything but "C++" htat's really C code.
- copperx 11y agoI wouldn't wish that on my worst enemy.
- bad-joke 11y agoI really enjoyed reading this. It's informative, fun, and has a refreshingly honest tone. Too often, stories passed around by computer scientists entail clever solutions and elegant insight striking the protagonist like lightning in the hour of need. Rarely does the programmer express regret, make self-corrections, and confront fear and doubt along the way: >I should have written beautiful code from the beginning, but because I needed to learn by writing a working code, the rewriting was unavoidable. >I should probably change my mind to implement all the features from end to end. I may find it fun as I'm approaching the goal. Sometimes, I have to write more code than I want to write in order to achieve a goal. >In a tough situation like this, I probably should recall the fact that the compiler was just in one file, to see how much progress I've made in a month. It just reads an integer with scanf() and prints it out with printf(). Really, I made so much progress in one month. Yeah, I think I can do this.
- zatkin 11y agoThere's a lot of this going on over at /r/adventofcode, people are abusing the hell out of languages just to get their answers as quickly as possible to make the leaderboard. For those of you who don't know what Advent of Code is, think of it as the advent calendar you had as a child (you know that thing with the chocolate behind the paper doors?), except you get a new coding problem every day and you get stars instead. https://adventofcode.com https://adventofcode.com
- nickpsecurity 11y ago"Rarely does the programmer express regret, make self-corrections, and confront fear and doubt along the way:" I agree with that part. You know you're looking at genuine science or art in software development when you see those things. Because they're always there tackling new, hard problems.
- peter303 11y agoLong ago UNIX had compiler writing tools like yacc and lex. I wonder if they are useful for exercises like this.
- DSMan195276 11y agoFor writing a general compiler (or anything similar to that), they're extremely useful because they produce very good lexers and/or parsers. The GNU versions of those two are 'bison' and 'flex'. Really, just about anything that requires parsing text can gain from using both of them. Noting that though, for this specific exercise they're not as useful because the author intended for this compiler to be self-hosting. It would be hard to be self-hosting if the compiler have to be able to compile the C code from yacc or lex, which may do any number of strange things.
- vidarh 11y agoWith the huge caveat that "nobody" uses these tools for production compilers because decent error handling becomes a nightmare. There are exceptions, but if you dig into most larger compilers, they usually sooner or later end up adopting their own handwritten recursive descent parsers.
- DSMan195276 11y agoThat's a fair point. Those tools have their uses, definitely - for a 'toy' compiler like this one, a simple lex lexer or yacc parser would/could be sufficient. Once you get more complex they start to become a limiting factor.
- fahadkhan 11y ago"Particularly, I'd use yacc instead of writing a parser by hand and introduce an intermediate language early on." Near the end of the article.
- nly 11y agoThey 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.
- peterkelly 11y agoFor 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-2nd/dp/0321486811 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.
- Ocerge 11y agoIndeed it is the standard, but I'm pretty sure I have a permanent twitch in the corner of my eye from my university compilers course and that book. It's probably not something I could ever do for fun, but it's extremely important and useful stuff to know. I'm just too stupid to really grok a lot of the concepts required to write a compiler.
- sklogic 11y agoPlease stop recommending the Dragon Book already. It is not just heavy, it is mostly outdated and irrelevant.
- fahadkhan 11y agoPlease could you recommend an alternative?
- landmark2 11y agoModern Compiler Implementation in C
- fao_ 11y agoBy A. Appel? I heard that the ML version is better since much of the code apparently isn't very idiomatic (It was supposedly translated directly from the ML book). I would probably recommend both that and The Dragon Book, as they cover roughly the same material but in a slightly different manner.
- 11y ago
- allannienhuis 11y ago> I have a mixed feeling — I learned a new stuff, but I could have learned that without spending this much time. Story of my life!
- pagade 11y agoAnyone tried using it? How do I use it to generate executable (as per the code it should fork the 'as')? Getting following error: [ERROR] main.c:144: (null): One of -a, -c, -E or -S must be specified -c, -E and -S are working fine. Couldn't figure out from code what -a does.
- hundchenkatze 11y agoHave you tried -o to specify the output file? As for -a it doesn't look like -a is actually handled in parseopt, through process of elimination it looks like -E sets cpponly, -c sets dontlink, and -S sets dumpasm. So from main.c:143 if you don't set any of those, dumpast needs to be true, and the only way I see that getting set to true is by using this flag '-fdump-ast' From this commit[0] it looks like -a was removed, but usage docs and error messages weren't updated. [0]https://github.com/rui314/8cc/commit/614f6e7b643333b9baaf8fbd6f0a4a8adc935307 https://github.com/rui314/8cc/commit/614f6e7b643333b9baaf8fb... Edit: adding link to relevant commit.
- sabujp 11y ago1) write compiler 2) get a job at google . . 4) profit
- rui314 11y agoI was already working at Google full-time (for an unrelated project) when I was writing this in my spare time.
- deleted 11y ago[deleted]
- steve19 11y agoSo I am hearing ... 1) Get a job at Google 2) Write a Compiler in Spare Time 3) ... 4) PROFIT!!!!
- nickpsecurity 11y agoSo, I'm hearing (1) Has job at Google, (2) Makes profit, (3)..., (4) Publishes cool tech written in spare time. The kind of stuff we've come to expect from you Googlers. Haha.
- pinn4242 11y agoSelf-hosting is pointless. Go has it--who cares. I wrote a program 1000x faster than the ruby one (at work) with zero bugs in Go, but I still don't want to use it(Go). Java is fine. Do I care if Java is self-hosting? No. I'll do (another) language in Javacc (my first one is still awesome) or ANTLR.
- andrewchambers 11y agoIf you want to create a self sufficient system then it isn't pointless at all. That just happens to be something that isn't in your requirements.
- andrewvijay 11y agoUnbelievable Jeff!
- andrewchambers 11y agorui314, thanks for posting this, you really were such a big inspiration to me writing my own. You were really quick!
- xigency 11y agoHonestly, 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 post by one of the Rust developers interesting. Writing your own parser generator is actually much easier than writing a parser by-hand (depending on the complexity of the language, here not that complex and still difficult), and I think it's more instructive than using a free or open parser-generator or compiler compiler. The downside is that it is less practical, because almost none of the important aspects of language implementation involve the parser.
- chrisseaton 11y ago> 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.
- adrianN 11y agoI have written a parser generator to generate a parser for a compiler project for a class. It is indeed the easier route. Your parser specification language is usually a lot simpler than your target language. Your parser generator also just needs the features required for your particular grammar, which means that dirty hacks and regex parsing are a viable route.
- deleted 11y ago[deleted]
- marssaxman 11y agoThis is completely contrary to my experience, in which parser generators have not paid for themselves. Writing a parser by hand in C is generally easier and less time-consuming over the long run than struggling along with a parser generator, especially if you have any interest in producing useful syntax error messages or recovering from other kinds of errors in some useful way. I agree that almost none of the important aspects of language implementation involve the parser - and that's why I write 'em by hand! It doesn't take much time, and it's much easier to debug whatever problems you run into when you can use your ordinary debugging tools.
- kleiba 11y agoWhat do you mean, "as a child"?
- JTon 11y agoThe parent poster is suggesting advent calendars are used most often by children. This is true around my area
- technofiend 11y agoAnd I think the person you responded to is implying his exit from childhood did not in any way slow down his use of advent calendars for chocolate-eating purposes.
- munificent 11y agoWhy would I purchase a device specifically designed to rate limit my chocolate consumption? Advent calendars are the Internet data caps of dessert.
- technofiend 11y agoIt's probably good to learn a little calender-based self control when young, but I happen to agree Chocolate Is Life.
- theoh 11y agoThe presumption seems to be that the reader grew up as a Christian in a Western county. Because of HN's supposed demographic.
- dang 11y agoWe detached this subthread from https://news.ycombinator.com/item?id=10733172 https://news.ycombinator.com/item?id=10733172 and marked it off-topic.
- joe563323 11y agoThis is awesome. I wish more of top coders post their flow of thoughts so the betas can learn from it.