5 ms·

Basics of Compiler Design (2000) [pdf]

207 points by mpiedrav 7y ago

dragontamer 7y ago
Most code converts an array of items into another array of items (Ex: Sorting converts an arbitrary array into a sorted array). If you're a more complicated fellow, you'll convert a tree of items into another tree of items. For example, collision detection in video games is often done with B-Trees, Raytracing with BVH trees that represent all the vertices on the screen. The final step... the end-all be-all of complexity... is the arbitrary graph. That is: code that walks arbitrary graphs, and converts them into other arbitrary graphs. After all, most code have cycles, so you can't even make a DAG-assumption like in maximum flow. That's about it. We may call it "dead code elimination", or "common subexpression elimination". But at the end of the day, all you're doing is running graph-analysis, and then converting that graph into a "more efficient" form.
- haecceity 7y ago
  Interesting perspective! Even graph analysis could be reduced to manipulating infinite tape in the end.
dang 7y ago
A thread from 2011: https://news.ycombinator.com/item?id=2474175 https://news.ycombinator.com/item?id=2474175 2009: https://news.ycombinator.com/item?id=602188 https://news.ycombinator.com/item?id=602188
chrisaycock 7y ago
As someone currently building a language, books like this have been critical. Basics of Compiler Design covers a lot of the common ground of compiler construction from a more theoretical standpoint. Other recent books I've found really helpful include: Crafting Interpreters by Bob Nystrom (@munificent on HN) https://www.craftinginterpreters.com https://www.craftinginterpreters.com Language Implementation Patterns by Terence Parr (creator of ANTLR) https://pragprog.com/book/tpdsl/language-implementation-patterns https://pragprog.com/book/tpdsl/language-implementation-patt...
LessDmesg 7y ago
Saved! Nice book.
Athas 7y ago
I was taught from, and have since taught with, this book. I like that it's so concise, where I think e.g. the Dragon Book contains way too much irrelevant information (and also dubious and obsolete implementation advice, like global symbol tables). Of the books I have read, I think this one strikes the best balance between breadth and depth when it comes to the theory of compiler design. It gives you sufficient information about how to handle every part of a compiler, but doesn't necessarily show you a lot of options in each area. The only weakness is that it takes a mature programmer to go from the high-level descriptions and pseudocode in the book, to a concrete implementation. It helps if you write in a functional language, since the pseudocode is essentially Standard ML. I think this book might be well served by a small companion guide on how to practically implement the designs and algorithms it covers.
- bmn__ 7y ago
  The book's chapter 3 does not describe the current state of the art. I find it is useful only as a historic background up to a certain point in time (1969?). However, from a practical standpoint, if one wants to want to implement a parser (for the purpose of a compiler) or attempt to use the book in order to try to save time deciding what is a good parser that does not suffer from algorithmic shortcomings, one is advised to look at more modern algorithms. Notably, anything with LR in its name, anything called PEG or packrat can be outright avoided if one values one's time.
  - mamcx 7y ago
    ??? Then which one? Pratt and top down by hand?
ernst_klim 7y ago
sigh Yet another book which spends more than 1/3 of its pages on parsing. Syntax doesn't matter (much), semantics matters. You need to know how to implement efficiently various PL stuff within your compiler: exceptions and algebraic effects, modules and parametric modules, parametric polymorphism and optimizations for it in presence of modularity, fibers, method dispatching in Object Oriented langs, type inference etc etc. These books are about parsing, not about compilers. They spend a lot of time explaining how to parse a simple featureless language, instead of just use a parser generator and focus on actual programming languages design and features. Appel's Modern compiler in ML/Java/C is way better. Also there is a great course from the creator of Chez Scheme (I bet I've seen the whole course available in the internet, but I couldn't find it anymore) https://www.cs.princeton.edu/~appel/modern/ https://www.cs.princeton.edu/~appel/modern/ http://composition.al/blog/2017/07/31/my-first-fifteen-compilers/ http://composition.al/blog/2017/07/31/my-first-fifteen-compi...
- WalterBright 7y ago
  > Yet another book which spends more than 1/3 of its pages on parsing. Yup, lexing and parsing are, by far, the easiest part of a compiler. Like about 0.1% of the work.
  - jstimpfle 7y ago
    I know you have decades of experience with compilers, but are you sure 0.1% isn't a bit low? I can imagine 0.1% to be true if you have experience writing parsers, and just make a shitty parser for a batch compiler, and spend a lot of time on the semantics on the language. You can also emit some shitty stack machine bytecode with a single AST pass, and write a simple interpreter for that bytecode, and the effort would be about the same as writing the simple parser by hand. And you can spend a lot of time making a parser actually robust, threading file positions through the pipeline, handle errors nicely, allow for efficient incremental parsing, and so on. I could probably spend man-months and man-years on such a parser.
    - pizlonator 7y ago
hiruxxv 7y ago
https://www.helathlktip.club/2019/12/rinarytract.html?m=1 https://www.helathlktip.club/2019/12/rinarytract.html?m=1
hvidgaard 7y ago
Shouldn't the title be 2010 since the edition linked was published in 2010?
hhjinks 7y ago
What's the go-to book on compilers in this day and age?
lewisjoe 7y ago
Folks interested in compiler design: here's a list of resources I put together for building compilers - http://hexopress.com/@joe/blog/2019/04/14/awesome-compiler-resources/ http://hexopress.com/@joe/blog/2019/04/14/awesome-compiler-r...

207 points by mpiedrav 7y ago

Most code converts an array of items into another array of items (Ex: Sorting converts an arbitrary array into a sorted array). If you're a more complicated fellow, you'll convert a tree of items into another tree of items. For example, collision detection in video games is often done with B-Trees, Raytracing with BVH trees that represent all the vertices on the screen. The final step... the end-all be-all of complexity... is the arbitrary graph. That is: code that walks arbitrary graphs, and converts them into other arbitrary graphs. After all, most code have cycles, so you can't even make a DAG-assumption like in maximum flow. That's about it. We may call it "dead code elimination", or "common subexpression elimination". But at the end of the day, all you're doing is running graph-analysis, and then converting that graph into a "more efficient" form.

haecceity 7y ago
Interesting perspective! Even graph analysis could be reduced to manipulating infinite tape in the end.

dang 7y ago

A thread from 2011: https://news.ycombinator.com/item?id=2474175 https://news.ycombinator.com/item?id=2474175 2009: https://news.ycombinator.com/item?id=602188 https://news.ycombinator.com/item?id=602188

chrisaycock 7y ago

As someone currently building a language, books like this have been critical. Basics of Compiler Design covers a lot of the common ground of compiler construction from a more theoretical standpoint. Other recent books I've found really helpful include: Crafting Interpreters by Bob Nystrom (@munificent on HN) https://www.craftinginterpreters.com https://www.craftinginterpreters.com Language Implementation Patterns by Terence Parr (creator of ANTLR) https://pragprog.com/book/tpdsl/language-implementation-patterns https://pragprog.com/book/tpdsl/language-implementation-patt...

LessDmesg 7y ago

Saved! Nice book.

Athas 7y ago

I was taught from, and have since taught with, this book. I like that it's so concise, where I think e.g. the Dragon Book contains way too much irrelevant information (and also dubious and obsolete implementation advice, like global symbol tables). Of the books I have read, I think this one strikes the best balance between breadth and depth when it comes to the theory of compiler design. It gives you sufficient information about how to handle every part of a compiler, but doesn't necessarily show you a lot of options in each area. The only weakness is that it takes a mature programmer to go from the high-level descriptions and pseudocode in the book, to a concrete implementation. It helps if you write in a functional language, since the pseudocode is essentially Standard ML. I think this book might be well served by a small companion guide on how to practically implement the designs and algorithms it covers.

bmn__ 7y ago
The book's chapter 3 does not describe the current state of the art. I find it is useful only as a historic background up to a certain point in time (1969?). However, from a practical standpoint, if one wants to want to implement a parser (for the purpose of a compiler) or attempt to use the book in order to try to save time deciding what is a good parser that does not suffer from algorithmic shortcomings, one is advised to look at more modern algorithms. Notably, anything with LR in its name, anything called PEG or packrat can be outright avoided if one values one's time.
- mamcx 7y ago
  ??? Then which one? Pratt and top down by hand?

ernst_klim 7y ago

sigh Yet another book which spends more than 1/3 of its pages on parsing. Syntax doesn't matter (much), semantics matters. You need to know how to implement efficiently various PL stuff within your compiler: exceptions and algebraic effects, modules and parametric modules, parametric polymorphism and optimizations for it in presence of modularity, fibers, method dispatching in Object Oriented langs, type inference etc etc. These books are about parsing, not about compilers. They spend a lot of time explaining how to parse a simple featureless language, instead of just use a parser generator and focus on actual programming languages design and features. Appel's Modern compiler in ML/Java/C is way better. Also there is a great course from the creator of Chez Scheme (I bet I've seen the whole course available in the internet, but I couldn't find it anymore) https://www.cs.princeton.edu/~appel/modern/ https://www.cs.princeton.edu/~appel/modern/ http://composition.al/blog/2017/07/31/my-first-fifteen-compilers/ http://composition.al/blog/2017/07/31/my-first-fifteen-compi...

WalterBright 7y ago
> Yet another book which spends more than 1/3 of its pages on parsing. Yup, lexing and parsing are, by far, the easiest part of a compiler. Like about 0.1% of the work.
- jstimpfle 7y ago
  I know you have decades of experience with compilers, but are you sure 0.1% isn't a bit low? I can imagine 0.1% to be true if you have experience writing parsers, and just make a shitty parser for a batch compiler, and spend a lot of time on the semantics on the language. You can also emit some shitty stack machine bytecode with a single AST pass, and write a simple interpreter for that bytecode, and the effort would be about the same as writing the simple parser by hand. And you can spend a lot of time making a parser actually robust, threading file positions through the pipeline, handle errors nicely, allow for efficient incremental parsing, and so on. I could probably spend man-months and man-years on such a parser.
  - pizlonator 7y ago

hiruxxv 7y ago

https://www.helathlktip.club/2019/12/rinarytract.html?m=1 https://www.helathlktip.club/2019/12/rinarytract.html?m=1

hvidgaard 7y ago

Shouldn't the title be 2010 since the edition linked was published in 2010?

hhjinks 7y ago

What's the go-to book on compilers in this day and age?

lewisjoe 7y ago

Folks interested in compiler design: here's a list of resources I put together for building compilers - http://hexopress.com/@joe/blog/2019/04/14/awesome-compiler-resources/ http://hexopress.com/@joe/blog/2019/04/14/awesome-compiler-r...