Live data from Hacker News

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

prog21.dadgum.com

51–60 of 173 posts

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

#51
post #3

fanf2 on Dec 25, 2015 [dead] | parent | prev | next [–] I quite like "understanding and writing compilers" by Richard Bornat - written in the 1970s using BCPL as the implementation language, so rather old-fashioned, but it gives a friendly gentle overview of how to do it, without excessive quantities of parsing theory.

Sadly, Richard died in January this year. This book is available to download from one of his academic pages:

https://www.eis.mdx.ac.uk/staffpages/r_bornat/#compilerbook

https://www.eis.mdx.ac.uk/staffpages/r_bornat/books/compilin...

https://en.wikipedia.org/wiki/Richard_Bornat

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

#52
One nice piece of advice that I received is that books are like RAMs, you do not have to go through them sequentially, but can do random access to the parts of it you need. With this in mind I find it doable to get one the thick books and only read the part that I need for my task.

But, to also be fair, the above random access method does not work when you don't know what you don't know. So I understand why having a light, but good introduction to the topic is important, and I believe that's what the author is pointing out.

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

#53

Earlier quoted context omitted.

I highly recommend nand2tetris to everyone. For me, nothing ever explained the whole domain from logic gates and inner workings of a CPU to compilers better than this course.

On a side note, why is imrozim's comment dead? What in the world is wrong with it? It's perfectly fine IMO.

check comment history

https://news.ycombinator.com/item?id=47582720

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

#54
post #30

Been working on a toy compiler for fun recently. I have ignored all the stuff about parsing theory, parser generators, custom DSL's, formal grammers etc. and instead have just been using the wonderful Megaparsec parser combinator library. I can easily follow the parsing logic, it's unambiguous (only one successful parse is possible, even if it might not be what you intended), it's easy to compose and re-use parser fu…

It seems to me LL and LR parser generators are overrated, and hand-written recursive descent is best in practice. I understand why academics teach them, but not why some spend so long on different parsing techniques, nor why hobbyists who just want to compile their toy language are directed to them.

I work in PL, and from my first compiler to today, have always found recursive descent easiest, most effective (less bugs, better error diagnostics, fast enough), and intuitive. Many popular language compilers use recursive descent: I know at least C# (Roslyn) and Rust, but I believe most except Haskell (GHC) and ocaml.

The LR algorithm was simple once I learned it, and yacc-like LR (and antlr-like LL) parser generators were straightforward once I learned how to resolve conflicts. But recursive descent (at least to me) is simpler and more straightforward.

LR being more expressive than LL has never mattered. A hand-written recursive descent parser is most expressive: it has unlimited lookahead, and can modify parsed AST nodes (e.g. reordering for precedence, converting if into if-else).

The only solution that comes close is tree-sitter, because it implements GLR, provides helpful conflict messages, and provides basic IDE support (e.g. syntax highlighting) almost for free. But it’s a build dependency, while recursive descent parsers can be written in most languages with zero dependencies and minimal boilerplate.

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

#56

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

Crafting Interpreters is great, I wish it had a companion book that covered:

  - types and typing
  - optimization passes
  - object files, executables, libraries and linking
Then two of them would be sufficient for writing a compiler.

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

#57
post #30

Been working on a toy compiler for fun recently. I have ignored all the stuff about parsing theory, parser generators, custom DSL's, formal grammers etc. and instead have just been using the wonderful Megaparsec parser combinator library. I can easily follow the parsing logic, it's unambiguous (only one successful parse is possible, even if it might not be what you intended), it's easy to compose and re-use parser fu…

It seems to me LL and LR parser generators are overrated, and hand-written recursive descent is best in practice. I understand why academics teach them, but not why some spend so long on different parsing techniques, nor why hobbyists who just want to compile their toy language are directed to them. I work in PL, and from my first compiler to today, have always found recursive descent easiest, most effective (less bu…

Parser generators are great in Python (Lark for me) so you can iterate fast and get a runtime spec of your grammar.

A hand-written recursive descent parser is something you do later when you start to industrialize your code, to get better error messages, make the parser incremental, etc.

Bison/ANTLR are code generators, they do not fit well in that model.

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

#58
the article's framing around nanopass is undersold: the real insight isn't the number of passes but that each pass has an explicit input and output language, which forces you to think about what invariants hold at each stage. that discipline alone catches a suprising number of bugs before you even run the compiler. crenshaw is fantastic but this structural thinking is what separates toy compilers from ones you can actaully extend later.

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

#59
post #22

*Donald Knute -> Donald Ervin Knuth is the author of the book "The Art of Computer Programming" (in progress for a couple of decades, currently volume 4c is being written). It is quite advanced, and it will likely not cover compilers anymore (Addison-Wesley had commissioned a compiler book from Knuth when he was a doctoral candidate, now he is retired and has stated his goal for the series has changed). I disagree wi…

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 hope that God is indeed willing, but the man is 88 years old and he’s not done with the third tome of volume four. It would require a minor miracle for him to finish volume 7 within this lifetime.

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

#60
post #7

I wonder if it makes sense to do the nand2tetris course for an absolute beginner since it too has compiler creation in it.

I highly recommend nand2tetris to everyone. For me, nothing ever explained the whole domain from logic gates and inner workings of a CPU to compilers better than this course.

I think it's worth mentioning Gustavo Pezzi's lectures at pikuma.com. The one on "Digital Electronics" and the one on "Interpreters & Compilers" really helped me.
Post reply on HN