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

81–90 of 128 posts

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

#81

Post by adrianN »

chrisseaton wrote: post #80
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.

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

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

#82

Post by [deleted] »

chrisseaton wrote: post #80
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.

[deleted]

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

#83

Post by sgeisenh »

sklogic wrote: post #59
hitlin37 wrote: post #54

Earlier quoted context omitted.

Since technologies changes before the book is out, how does that hold in compiler domain? Are there any modern compiler book that explains around llvm/gcc as an example compiler?

Not sure if there are any books around LLVM or gcc, but there is a lot of up to date texts. Grune at al., "Modern Compiler Design", Appel, "Modern Compiler Implementation in ML", and many more. P.S. Because of a slow-ban, adding another one to this answer. This is the best source on SSA: http://www.cri.ensmp.fr/people/pop/papers/2006-12-thesis.pdf

I'll just add this on: https://www.cs.cmu.edu/~fp/courses/15411-f14/schedule.html

The lecture notes are simple and excellent, though at a very high level of abstraction. Though most of the notes are full of references to the original material, which is super nice.

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

#84

Post by marktangotango »

nickpsecurity wrote: post #46
nly wrote: post #32

Earlier quoted context omitted.

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.

Semantic Designs toolkit uses GLR to handle about everything one could think of: http://www.semanticdesigns.com/Products/DMS/DMSToolkit.html

Ambiguous use of 'handle' here. For an ambiguous parse, GLR gives a forest of possible alternatives that still has to be disambiguated. Interesting to see a reference to Semantic Designs here, Ira Baxter used to pimp DMS on stack overflow quite a lot, I have not seen anything from them in years, are they still in business?

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

#86

Post by hundchenkatze »

pagade wrote: post #41

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

Have 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/614f6e7b643333b9baaf8fb...

Edit: adding link to relevant commit.

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

#87

Post by DSMan195276 »

vidarh wrote: post #35
DSMan195276 wrote: post #26

Earlier quoted context omitted.

For 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. I…

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

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

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

#88

Post by nickpsecurity »

marktangotango wrote: post #84
nickpsecurity wrote: post #46

Earlier quoted context omitted.

Semantic Designs toolkit uses GLR to handle about everything one could think of: http://www.semanticdesigns.com/Products/DMS/DMSToolkit.html

Ambiguous use of 'handle' here. For an ambiguous parse, GLR gives a forest of possible alternatives that still has to be disambiguated. Interesting to see a reference to Semantic Designs here, Ira Baxter used to pimp DMS on stack overflow quite a lot, I have not seen anything from them in years, are they still in business?

Having tried to write similar stuff, I was quite impressed with the claimed capabilities of the tool and how they went about it. He summarizes some of the issues here:

http://www.semanticdesigns.com/Products/DMS/LifeAfterParsing...

The stuff they support was also significant. Personally, I always thought they should open-source that then make their money on good front-ends, transformation heuristics, and services. Like LLVM, academic community would make core tool much better over time.

Far as in business, site is still up with more content than before and a current copyright. Last news release was 2012. Not sure if that's a bad sign or just a business that focuses less on PR. There's a paper or two in ResearchGate in 2015 promoting it with him still on StackOverflow but with less DMS references because of moderator pressure (explained in his profile). So, probably still in business.

My quick, top-of-head assessment of their situation, at least. Might be way off. :)

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

#89

Post by marssaxman »

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…

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

Post reply on HN