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

Want to write a compiler? Just read these two papers (2008)

prog21.dadgum.com

Post reply on HN
Print view View original

151–160 of 173 posts

Re: Want to write a compiler? Just read these two papers (2008)

#151

Post by troad »

khat wrote: post #120

The biggest issue with technical books is they spend the first 1-2 chapters vaguely describing some area and then follow up with but that's for a later more advanced discussion or we'll cover that in that last 1-2 chapters. Don't vaguely tell me about something you're not gonna go into detail about, because now all I'm thinking about reading the subsequent chapters is all the questions I have about that topic.

That's how all education works. It's the spiral model of teaching. In one grade you learn a bit of this and a bit of that, then the next year you retread, and flesh all those things out by adding more depth and complexity. Rinse and repeat every grade.

What would the alternative look like? Should a foreign language course spend three years on Nouns, just to make sure they're comprehensively covered, before you ever see your first Verb?

Re: Want to write a compiler? Just read these two papers (2008)

#152

Post by kibwen »

jcranmer wrote: post #63
antiquark wrote: post #48

Earlier quoted context omitted.

There is still hope for a compiler book. From Knuth's website: > And after Volumes 1--5 are done, God willing, I plan to publish Volume 6 (the theory of context-free languages) and Volume 7 (Compiler techniques), but only if the things I want to say about those topics are still relevant and still haven't been said. https://www-cs-faculty.stanford.edu/~knuth/taocp.html

I don't think there is hope if you look at actuarial tables and Knuth's age. It's not clear to me if he'll be able to finish volume 4. The outline he has seems to have enough material to fill volumes 4C-4G to my eyes, and he isn't exactly cranking out the volumes. Admittedly, volumes 5-7 wouldn't be as massive as volume 4 (it sort of turns out that almost all interesting algorithms ends up being categorized as being…

Have no fear, we'll just train an LLM on TAOCP and have it automatically generate the remaining volumes‽

Re: Want to write a compiler? Just read these two papers (2008)

#153

Post by aag »

LiamPowell wrote: post #23

See also, Andy Keep's dissertation [1] and his talk at Clojure/Conj 2013 [2]. I think that the nanopass architecture is especially well suited for compilers implemented by LLMs as they're excellent at performing small and well defined pieces of work. I'd love to see Anthropic try their C compiler experiment again but with a Nanopass framework to build on. I've recently been looking in to adding Nanopass support to La…

Andy gave a nice talk on the implementation of Chez Scheme, an optimizing compiler, at the Scheme Workshop in Berlin in 2019:

https://www.youtube.com/watch?v=N_-enNCZxaU

Re: Want to write a compiler? Just read these two papers (2008)

#154

Post by h4ch1 »

aldousd666 wrote: post #79

I learned from the Dragon Book, decades ago. I already knew a lot of programming at that point, but I think most people writing compilers do. I'm curious if there really is an audience of people whose first introduction to programming is writing a compiler... I would think not, actually.

Wouldn't say a lot of people use it for an introduction to programming, but I've personally seen it appear quite early in the programmers journey.

I was first exposed to compilers as a learning subject as a mandatory 2nd year/1st semester course; with the Dragon Book as the main textbook...

Re: Want to write a compiler? Just read these two papers (2008)

#155

Post by deterministic »

Whatever you do don't waste your time on the "Dragon" book.

Google "recursive descent parsing" and it will tell you everything you need to know about the front-end of a compiler.

Google "My First Language Frontend with LLVM" and it will teach you the other half.

Re: Want to write a compiler? Just read these two papers (2008)

#156

Post by raxxorraxor »

armchairhacker wrote: post #11

Nowadays I’ve heard recommended Crafting Interpreters. ( https://craftinginterpreters.com ) The Nanopass paper link doesn’t work.

Many languages like Pancake Stack are looking for efficient interpreters:

https://esolangs.org/wiki/Pancake_Stack

:)

Re: Want to write a compiler? Just read these two papers (2008)

#157

Post by torginus »

randomNumber7 wrote: post #106
projektfu wrote: post #62

Earlier quoted context omitted.

The dragon book almost convinced me never to try to write a compiler. I don't know why people recommend it. I guess you're a lot smarter than I am. There are some excellent books out there. In its own way, the dragon book is excellent, but it is a terrible starting place. Here are a bunch of references from the same vintage as OP. I recommend starting with a book that actually walks through the process of building a…

Imho the problem is the fixation on parser generators and BNF. It's just a lot easier to write a recursive descent parser than to figure out the correct BNF for anything other than a toy language with horrible syntax.

Imo BNF (or some other formal notation) is quite useful for defining your syntax, my biggest gripe with BNF in particular is the way it handles operator precedence (through nested recursive expressions), which can get messy quite fast.

Pratt parsers dont even use this recursion, they only have a concept of 'binding strength', which means in laymans terms that if I'm parsing the left side of say a '' expression, and I managed to parse something a binary subexpression, and the next token I'm looking at is another binary op, do I continue parsing that subexpression, which will be the RHS of the '' expression, or do I finish my original expression which will then be the LHS of the new one?

It represents this through the concept of stickiness, with onesimple rule - the subexpression always sticks to the operator that's more sticky.

This is both quite easy to imagine, and easy to encode, as stickiness is just a number.

I think a simpler most straightforward notation that incorporates precedence would be better.

Re: Want to write a compiler? Just read these two papers (2008)

#159

Post by torginus »

hmry wrote: post #76
tovej wrote: post #66

Earlier quoted context omitted.

I started with the dragon book, and I found it to be a good introductory text. A lot of people say the dragon book is difficult, so I suppose there must be something there. But I don't see what it is, I thought it was quite accessible. I'm curious, what parts/aspects of the dragon book make it difficult to start with?

It's been a few years since I worked with the dragon book, but I think the most common complaint was that it starts with like 350 pages on parser theory: generating bottom-up and top-down parsers from context free grammars, optimizing lexers for systems that don't have enough RAM to store an entire source file, etc... before ever getting to what most people who want to write a compiler care about (implementing type i…

The thing about parsing (and algorithms in general) is that it can be hair raisingly complex for arbitrary grammars, but in practice, people have recently discovered, that making simple, unambiguous grammars, and avoiding problems, like context dependent parsing, make the parsing problem trival.

Accepting such constraints is quite practical, and lead to little to no loss of power.

In fact, most modern languages are designed with little to no necessary backtracking and simple parsing, Go and Rust being noteworthy examples.

Re: Want to write a compiler? Just read these two papers (2008)

#160

Post by aleph_minus_one »

torginus wrote: post #157
randomNumber7 wrote: post #106

Earlier quoted context omitted.

Imho the problem is the fixation on parser generators and BNF. It's just a lot easier to write a recursive descent parser than to figure out the correct BNF for anything other than a toy language with horrible syntax.

Imo BNF (or some other formal notation) is quite useful for defining your syntax, my biggest gripe with BNF in particular is the way it handles operator precedence (through nested recursive expressions), which can get messy quite fast. Pratt parsers dont even use this recursion, they only have a concept of 'binding strength', which means in laymans terms that if I'm parsing the left side of say a ' ' expression, and…

> I think a simpler most straightforward notation that incorporates precedence would be better.

For example YACC provides a way to specify how a shift/reduce conflict

> https://www.gnu.org/software/bison/manual/html_node/Shift_00...

and a reduce/reduce conflict

> https://www.gnu.org/software/bison/manual/html_node/Reduce_0...

should be resolved; see also

> https://www.gnu.org/software/bison/manual/html_node/Mysterio...

This is actually a way to specify operator precedence in a much simpler and more straightforward way than via nested recursive expressions.

Post reply on HN