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

Revisiting "Let's Build a Compiler"

eli.thegreenplace.net

Post reply on HN
Print view View original

41–50 of 53 posts

Re: Revisiting "Let's Build a Compiler"

#41

Post by mafuy »

emeraldd wrote: post #27
ernst_klim wrote: post #19

> Rather than getting stuck in front-end minutiae, the tutorial goes straight to generating working assembly code, from very early on. I think this is important and for a more sophisticated compiler design I find Ghuloum approach very appealing [1]. I.e. build a very simple subset of the language from top to bottom and then grow the meat gradually. The really great book following this approach I've discovered recentl…

This is something I've noticed on academic vs "practicing" coders. Academics tend to build in layers, though not always, and "practicing" coders tend to build in pipes give or take. The layers approach might give you buildable code, but is hard to exercise and run. Both approaches can work though, especially if you build in executable chunks, but you have to focus on the smallest chunk you can actually run.

I'd argue the opposite. Nora's approach demonstrates that simple ideas work great for getting half of the problem done, but can make it impossible to finish the second half.

Re: Revisiting "Let's Build a Compiler"

#42

Post by userbinator »

Crenshaw's tutorial doesn't quite reach the point where it becomes useful, but precedence-climbing is a rather straightforward refactoring of recursive descent that becomes extremely useful when there are many precedence levels.

Naturally, the author has also written an article about it, albeit without the explanation of the refactoring that links it to RD:

https://eli.thegreenplace.net/2012/08/02/parsing-expressions...

Re: Revisiting "Let's Build a Compiler"

#43

Post by userbinator »

HarHarVeryFunny wrote: post #26
statictype wrote: post #2

This article sums it up perfectly. I was interested in building a compiler long before going to college and this was the most accessible body of work. Building a recursive descent parser from scratch was an eye opener to 17yo me on how a seemingly very complex problem that I had no idea how to approach can be made simple by breaking it down into the right primitives.

That's a good point - recursive descent as a general lesson in program design, in addition to being a good way to write a parser. Table driven parsers (using yacc/etc) used to be emphasized in old compiler writing books such as Aho & Ullman's famous "dragon (front cover) book". I'm not sure why - maybe part efficiency for the slower computers of the day, and part because in the infancy of computing a more theoretical…

Rather than having the recursive descent parser generate code, I just had it generate executable data structures - subclasses of Statement and Expression base classes, with virtual Execute() and Value() methods respectively, so that the parsed program could be run by calling program->Execute() on the top level object.

That is basically an AST interpreter.

Re: Revisiting "Let's Build a Compiler"

#44

Post by userbinator »

scotty79 wrote: post #9
statictype wrote: post #2

This article sums it up perfectly. I was interested in building a compiler long before going to college and this was the most accessible body of work. Building a recursive descent parser from scratch was an eye opener to 17yo me on how a seemingly very complex problem that I had no idea how to approach can be made simple by breaking it down into the right primitives.

When I need to parse something nowadays I always end up with parser combinators. They just make so much sense.

That's just a generalisation of recursive descent.

Re: Revisiting "Let's Build a Compiler"

#45

Post by userbinator »

dang wrote: post #33

Revisiting "Let's Build a Compiler" threads: Let's Build a Compiler (1988) - https://news.ycombinator.com/item?id=38773049 - Dec 2023 (15 comments) Let's Build a Compiler (1988) - https://news.ycombinator.com/item?id=36054416 - May 2023 (19 comments) Let’s Build a Compiler (1995) - https://news.ycombinator.com/item?id=22346532 - Feb 2020 (41 comments) Let's Build a Compiler (1995) - https://news.ycombinator.com/item?…

The 4th one is not about Crenshaw's, but another article of the same name with very different contents.

Re: Revisiting "Let's Build a Compiler"

#46

Post by scotty79 »

userbinator wrote: post #44
scotty79 wrote: post #9

Earlier quoted context omitted.

When I need to parse something nowadays I always end up with parser combinators. They just make so much sense.

That's just a generalisation of recursive descent.

The right primitives and composability bring in immense value.

Re: Revisiting "Let's Build a Compiler"

#47

Post by HarHarVeryFunny »

userbinator wrote: post #43
HarHarVeryFunny wrote: post #26

Earlier quoted context omitted.

That's a good point - recursive descent as a general lesson in program design, in addition to being a good way to write a parser. Table driven parsers (using yacc/etc) used to be emphasized in old compiler writing books such as Aho & Ullman's famous "dragon (front cover) book". I'm not sure why - maybe part efficiency for the slower computers of the day, and part because in the infancy of computing a more theoretical…

Rather than having the recursive descent parser generate code, I just had it generate executable data structures - subclasses of Statement and Expression base classes, with virtual Execute() and Value() methods respectively, so that the parsed program could be run by calling program->Execute() on the top level object. That is basically an AST interpreter.

No - there was no separation of AST and interpreter. You could consider it just as a directly executable AST.

Re: Revisiting "Let's Build a Compiler"

#48

Post by microtherion »

fuzztester wrote: post #40
microtherion wrote: post #38

Earlier quoted context omitted.

Wirth also wrote an extremely accessible book on Compiler Construction, using exactly the hand written recursive descent parsing approach discussed by OP. The initial edition was published in 1976, in German, but the latest version is available online: https://people.inf.ethz.ch/wirth/CompilerConstruction/Compil... There are also parser generators like ANTLR ( https://en.wikipedia.org/wiki/ANTLR ) which take an input…

Thank you. Just to confirm, by "accessible", do you mean easy to understand? Anyway, I think I had come across that book on the net, but did not check it out at the time. I don't remember the exact reason, maybe it was because I didn't want to go into the subject of compilers at the time, and was only interested in interpreters, because I prefer to take things one step at a time. Now I will check it out.

Yes, accessible in the sense of being readable without extensive prior knowledge. If I recall correctly, I read the initial edition while still in high school.

Re: Revisiting "Let's Build a Compiler"

#49

Post by dang »

userbinator wrote: post #45
dang wrote: post #33

Revisiting "Let's Build a Compiler" threads: Let's Build a Compiler (1988) - https://news.ycombinator.com/item?id=38773049 - Dec 2023 (15 comments) Let's Build a Compiler (1988) - https://news.ycombinator.com/item?id=36054416 - May 2023 (19 comments) Let’s Build a Compiler (1995) - https://news.ycombinator.com/item?id=22346532 - Feb 2020 (41 comments) Let's Build a Compiler (1995) - https://news.ycombinator.com/item?…

The 4th one is not about Crenshaw's, but another article of the same name with very different contents.

Ah whoops - I've removed it from the above list. Thanks!

(It was this one btw: Let's Build a Compiler - https://news.ycombinator.com/item?id=20444474 - July 2019 (47 comments) )

Re: Revisiting "Let's Build a Compiler"

#50

Post by cxr »

hashtag-til wrote: post #5

For modern compiler and a more direct approach I recommend https://www.cs.cornell.edu/~asampson/blog/llvm.html

Adrian Sampson (the author of that now 10-year old blog post) has a online course for actually teaching compilers:

https://web.archive.org/web/20210208162458/https://www.cs.co...>

Discussed several times on HN: https://hn.algolia.com/?query=cs6120%20advanced%20compilers>

(And discussion about the blog post from last year about the IL used in the course: https://news.ycombinator.com/item?id=41084318>.)

Post reply on HN