9 ms·

Compiler Construction by Niklaus Wirth [pdf]

135 points by vector_spaces 7y ago

NonEUCitizen 7y ago
OP's link points to a .pdf covering Chapters 1-8. Web page below has a link to Chapters 9-16 as well: https://inf.ethz.ch/personal/wirth/CompilerConstruction/ https://inf.ethz.ch/personal/wirth/CompilerConstruction/
dang 7y ago
Previous versions were discussed: 2015: https://news.ycombinator.com/item?id=10764672 https://news.ycombinator.com/item?id=10764672 2010: https://news.ycombinator.com/item?id=1529288 https://news.ycombinator.com/item?id=1529288 2008: https://news.ycombinator.com/item?id=267916 https://news.ycombinator.com/item?id=267916 A related thread from 2018: https://news.ycombinator.com/item?id=16609360 https://news.ycombinator.com/item?id=16609360
chrisseaton 7y ago
People should note that this isn't usually how we construct compilers in industry today. (This comment is posted every time but it's true.)
- throwaway55554 7y ago
  But a lot can still be learned by a hobbyist by doing so.
  - chrisseaton 7y ago
    Hmmm... I'm not as sure. I wonder if we could do people a service by showing them how it's done today from the start, rather than showing them yesterday's stuffy, ponderous, inelegant approach (sorry for the opinion) and then having to roll that back when they start working on something in practice.
    - spekcular 7y ago
      How would you show a novice how it's done today? I've always wanted to learn about compilers, but something tells me the dragon book is no longer the go-to source.
      - chrisseaton 7y ago
        It's actually a real problem - the knowledge of how for example JavaScript VMs and JITs work isn't really written down very well. It's all in people's heads and you learn as an apprentice (PhD student). I don't have a better solution than to show you in person.
      - jcranmer 7y ago
        One of the issues, I think, is that compilers has really become a topic that is way too broad to fit into one book. You'd need at least: * Foundations: the frontend, codegen [to IR] (including vtables, lambdas, and coroutines, probably), the big scalar optimizations, register allocation, maybe instruction scheduling? * Loop optimizations: dependence analysis, all the loop opts, autovectorization, autoparallelization. Maybe cover some OpenMP or heterogeneous computing (e.g., SYCL, CUDA) here * "Fancy" optimizations: profiling (including what & how to profile), link-time (including thin-lto techniques), SLP vectorization, possibly superoptimization and dataflow analysis * Dynamic language VMs: JITs, garbage collection, shape optimization, and several of the various tricks (e.g., NaN-boxing, deoptimization guards) * You might be able to make an entire book out of fuzzing and symbolic/concolic execution, but I think it'd be thinner than the other ones here. And there are still things I don't know where to put. Alias analysis, exception handling, debugging…
- hasbot 7y ago
  It really wasn't how compilers were constructed in '96 either. I was very into compilers in the late 80's and even then we didn't handwrite lexers or parsers. I was using bison and flex around '89.
  - onceUponADime 7y ago
    Still usefull little tools to parse in configuration dsls etc.
    - chrisseaton 7y ago
      Yes that's true - configuration files, network protocols, etc.
  - patrec 7y ago
    Basically no serious programming language uses bison or flex, and everything that does (awk is YACC based) has terrible error messages. People totally do handwrite lexers and parsers, if you use some language in earnest the chances it has a handwritten parser or lexer or both are far greater than that it has been developed with bison/flex.
    - hasbot 7y ago
      Hmm, I wrote a VHDL (a superset of ADA used for hardware design) front end using bison and flex. That's a serious language. Regarding error messages, if one implements the grammar as specified by the language spec, yes, confusing and useless error messages will result. That's because the language spec grammar includes restrictions based on semantics. To get good error messages, one has to remove/relax the spec grammar and then use semantic checking. Parsing is an art; not a science.
      - chrisseaton 7y ago
        Right - no 'serious language' is hyperbole, and another counter example is Ruby. But... if I was asked to implement a language tomorrow I wouldn't even consider using Bison and Flex. Why? Because they're context-free tools, and almost every industrial language is context-sensitive. Square pegs and round holes. These tools are a great example of over-complicating and over-theorising programming languages. We invented a theory that doesn't even apply to the problem we have, and then created crazy tools to solve the wrong problem, and gloss over the fact that they don't apply with terrible hacks and side-effects. We made a mistake with that phase in programming language history...
- vector_spaces 7y ago
  How do we usually construct compilers in industry today? I saw others mentioning parser generators -- is that the main difference?
  - chrisseaton 7y ago
    This whole thread has been about parser generators, but that's not really what I meant! I think the biggest difference is the rich intermediate representations we use these days. These classic texts don't really address intermediate representations and are usually syntax-directed instead. These days a program will spent almost all of its time deconstructed into an IR.
    - vector_spaces 7y ago
      I actually started reading Wirth because I was frustrated at how little coverage there seems to be of syntax related matters (lexing and parsing) in modern introductory books (with a couple of exceptions, notably the Dragon Book, but I've been having a hard time wrapping my head around it). I emailed an author of a book that specifically calls parsing a "distraction" (Shriram Krishnamurthi, in PLAI) and he explained that he and other textbook authors of recent texts are reacting to a sort of over-emphasis on parsing in older books and tools (for example, YACC standing for Yet Another Compiler Constructor despite being simply a parser generator). So it's interesting what you're saying about IRs -- I've definitely noticed Shriram's book and a few other recent ones seem to focus really heavily on them. I wonder if there's also a relationship between a more IR-focused approach and the reduced emphasis on parsing?
      - chrisseaton 7y ago
        There might be a bit of a backlash yes. But I think for example the Dragon book is comically unbalanced towards parsing. It's just ludicrous how much it drones on about this tiny tiny part of writing a compiler. I've been working professionally on one compiler continuously since 2013. I've spent like two or three days working on the parser. That's it. I've probably spent longer tweaking the Markdown of the README. For me the issue is that parsing is basically a solved problem. I don't see how you can make it much better for compilers. If you give me a language I can write you a parser for it. It won't be interesting, fun, or be better or worse than any other parser. It's a purely mechanical job. (Of course it could be a nicer parser, or a faster parser, or give better error messages, or work better for IDEs or tooling, but stick with me.) But the transformations that happen after that point? Well there a whole world opens up to you! You can do so much, in so many different ways, and achieve incredibly different results for different requirements.
ainar-g 7y ago
Wirthian languages, and especially Oberon-07, are definitely a topic I want to familiarise myself with, but there is so little information about it on the Web, and even fewer codebases to learn from. And a lot of the compilers and tooling seems to be weirdly Windows-oriented. The questions I still have very little answers to are: * How is error handling done in Oberon-07? * How does one do generic programming in Oberon-07? * What is Oberon-07's async story? I will be thankful for any pointers (heh).
- pjmlp 7y ago
  Error handling is done the old style, you just test for error conditions and such. Generic programming and async are supported on the Active Oberon programming language in the Oberon family branch. Which also does support exception handling. Most recent version from Active Oberon http://cas.inf.ethz.ch/news/2 http://cas.inf.ethz.ch/news/2 The A2 OS written in Active Oberon and respective documentation https://github.com/btreut/a2 https://github.com/btreut/a2 Some A2 overview http://sage.com.ua/en.shtml?e1l0 http://sage.com.ua/en.shtml?e1l0 While Modula-2 had co-routines and exceptions, Wirth has chosen a minimalist path with Oberon. Oberon-07 design goal has been to remove as many features as possible from original Oberon, while keeping a GC enabled systems programming language. Then you have the other path, taken by others at ETHZ, which extended Oberon into a more expressive language, namely Oberon-2, Component Pascal and Active Oberon. With Active Oberon being what is actually still used at ETHZ for teaching some OS classes and OS research subject.
- Rochus 7y ago
  Here (https://github.com/rochus-keller/Oberon https://github.com/rochus-keller/Oberon) is a Qt/C++ based viewer/cross-referencer for Oberon-07 code bases as well as an Oberon to C++/Lua/LuaJIT bytecode transpiler/compiler; an IDE is work in progress. > How is error handling done in Oberon-07? There is an Oberon programming language with compiler written in Oberon, and there is an operating system called Oberon as well; you can have a look at the source code, but there are also a couple of free books about it, see http://www.projectoberon.com/ http://www.projectoberon.com/ > How does one do generic programming in Oberon-07? No support for generics yet; there was a proposal in the nineties, but Wirth didn't integrate it. Neither the Go language which is a brain child of Oberon-2 has generics (yet). > What is Oberon-07's async story Oberon is single threaded; there is a coroutine library part of the Oakwood standard. But nothing comparable e.g. to Go.
sbmthakur 7y ago
Just discovered Wirth's book The School of Niklaus Wirth: The Art of Simplicity. I would like to know if it's worth the time investment?
- freemint 7y ago
  I do think it was not worth my time. I found the ideas presented trivial or impractically simplified. It was basically a book containing some papers on compilers celebrating Wirth. I felt i learned nothing and also felt rage due to the amount of attention his project gets (people reimplementing his pc designs on FPGA, etc.) while more worthwhile historically and technically interesting projects were ignored. I am also on an Oberon mailing list as a teacher and do not see anything interesting there. However if a person is really interested in compilers and likes the wirthian language family this book might be for him. However it seems like a circlejerk to me.

135 points by vector_spaces 7y ago

OP's link points to a .pdf covering Chapters 1-8. Web page below has a link to Chapters 9-16 as well: https://inf.ethz.ch/personal/wirth/CompilerConstruction/ https://inf.ethz.ch/personal/wirth/CompilerConstruction/

dang 7y ago

Previous versions were discussed: 2015: https://news.ycombinator.com/item?id=10764672 https://news.ycombinator.com/item?id=10764672 2010: https://news.ycombinator.com/item?id=1529288 https://news.ycombinator.com/item?id=1529288 2008: https://news.ycombinator.com/item?id=267916 https://news.ycombinator.com/item?id=267916 A related thread from 2018: https://news.ycombinator.com/item?id=16609360 https://news.ycombinator.com/item?id=16609360

chrisseaton 7y ago

People should note that this isn't usually how we construct compilers in industry today. (This comment is posted every time but it's true.)

throwaway55554 7y ago
But a lot can still be learned by a hobbyist by doing so.
- chrisseaton 7y ago
  Hmmm... I'm not as sure. I wonder if we could do people a service by showing them how it's done today from the start, rather than showing them yesterday's stuffy, ponderous, inelegant approach (sorry for the opinion) and then having to roll that back when they start working on something in practice.
  - spekcular 7y ago
    How would you show a novice how it's done today? I've always wanted to learn about compilers, but something tells me the dragon book is no longer the go-to source.
    - chrisseaton 7y ago
      It's actually a real problem - the knowledge of how for example JavaScript VMs and JITs work isn't really written down very well. It's all in people's heads and you learn as an apprentice (PhD student). I don't have a better solution than to show you in person.
    - jcranmer 7y ago
      One of the issues, I think, is that compilers has really become a topic that is way too broad to fit into one book. You'd need at least: * Foundations: the frontend, codegen [to IR] (including vtables, lambdas, and coroutines, probably), the big scalar optimizations, register allocation, maybe instruction scheduling? * Loop optimizations: dependence analysis, all the loop opts, autovectorization, autoparallelization. Maybe cover some OpenMP or heterogeneous computing (e.g., SYCL, CUDA) here * "Fancy" optimizations: profiling (including what & how to profile), link-time (including thin-lto techniques), SLP vectorization, possibly superoptimization and dataflow analysis * Dynamic language VMs: JITs, garbage collection, shape optimization, and several of the various tricks (e.g., NaN-boxing, deoptimization guards) * You might be able to make an entire book out of fuzzing and symbolic/concolic execution, but I think it'd be thinner than the other ones here. And there are still things I don't know where to put. Alias analysis, exception handling, debugging…
hasbot 7y ago
It really wasn't how compilers were constructed in '96 either. I was very into compilers in the late 80's and even then we didn't handwrite lexers or parsers. I was using bison and flex around '89.
- onceUponADime 7y ago
  Still usefull little tools to parse in configuration dsls etc.
  - chrisseaton 7y ago
    Yes that's true - configuration files, network protocols, etc.
- patrec 7y ago
  Basically no serious programming language uses bison or flex, and everything that does (awk is YACC based) has terrible error messages. People totally do handwrite lexers and parsers, if you use some language in earnest the chances it has a handwritten parser or lexer or both are far greater than that it has been developed with bison/flex.
  - hasbot 7y ago
    Hmm, I wrote a VHDL (a superset of ADA used for hardware design) front end using bison and flex. That's a serious language. Regarding error messages, if one implements the grammar as specified by the language spec, yes, confusing and useless error messages will result. That's because the language spec grammar includes restrictions based on semantics. To get good error messages, one has to remove/relax the spec grammar and then use semantic checking. Parsing is an art; not a science.
    - chrisseaton 7y ago
      Right - no 'serious language' is hyperbole, and another counter example is Ruby. But... if I was asked to implement a language tomorrow I wouldn't even consider using Bison and Flex. Why? Because they're context-free tools, and almost every industrial language is context-sensitive. Square pegs and round holes. These tools are a great example of over-complicating and over-theorising programming languages. We invented a theory that doesn't even apply to the problem we have, and then created crazy tools to solve the wrong problem, and gloss over the fact that they don't apply with terrible hacks and side-effects. We made a mistake with that phase in programming language history...
vector_spaces 7y ago
How do we usually construct compilers in industry today? I saw others mentioning parser generators -- is that the main difference?
- chrisseaton 7y ago
  This whole thread has been about parser generators, but that's not really what I meant! I think the biggest difference is the rich intermediate representations we use these days. These classic texts don't really address intermediate representations and are usually syntax-directed instead. These days a program will spent almost all of its time deconstructed into an IR.
  - vector_spaces 7y ago
    I actually started reading Wirth because I was frustrated at how little coverage there seems to be of syntax related matters (lexing and parsing) in modern introductory books (with a couple of exceptions, notably the Dragon Book, but I've been having a hard time wrapping my head around it). I emailed an author of a book that specifically calls parsing a "distraction" (Shriram Krishnamurthi, in PLAI) and he explained that he and other textbook authors of recent texts are reacting to a sort of over-emphasis on parsing in older books and tools (for example, YACC standing for Yet Another Compiler Constructor despite being simply a parser generator). So it's interesting what you're saying about IRs -- I've definitely noticed Shriram's book and a few other recent ones seem to focus really heavily on them. I wonder if there's also a relationship between a more IR-focused approach and the reduced emphasis on parsing?
    - chrisseaton 7y ago
      There might be a bit of a backlash yes. But I think for example the Dragon book is comically unbalanced towards parsing. It's just ludicrous how much it drones on about this tiny tiny part of writing a compiler. I've been working professionally on one compiler continuously since 2013. I've spent like two or three days working on the parser. That's it. I've probably spent longer tweaking the Markdown of the README. For me the issue is that parsing is basically a solved problem. I don't see how you can make it much better for compilers. If you give me a language I can write you a parser for it. It won't be interesting, fun, or be better or worse than any other parser. It's a purely mechanical job. (Of course it could be a nicer parser, or a faster parser, or give better error messages, or work better for IDEs or tooling, but stick with me.) But the transformations that happen after that point? Well there a whole world opens up to you! You can do so much, in so many different ways, and achieve incredibly different results for different requirements.

ainar-g 7y ago

Wirthian languages, and especially Oberon-07, are definitely a topic I want to familiarise myself with, but there is so little information about it on the Web, and even fewer codebases to learn from. And a lot of the compilers and tooling seems to be weirdly Windows-oriented. The questions I still have very little answers to are: * How is error handling done in Oberon-07? * How does one do generic programming in Oberon-07? * What is Oberon-07's async story? I will be thankful for any pointers (heh).

pjmlp 7y ago
Error handling is done the old style, you just test for error conditions and such. Generic programming and async are supported on the Active Oberon programming language in the Oberon family branch. Which also does support exception handling. Most recent version from Active Oberon http://cas.inf.ethz.ch/news/2 http://cas.inf.ethz.ch/news/2 The A2 OS written in Active Oberon and respective documentation https://github.com/btreut/a2 https://github.com/btreut/a2 Some A2 overview http://sage.com.ua/en.shtml?e1l0 http://sage.com.ua/en.shtml?e1l0 While Modula-2 had co-routines and exceptions, Wirth has chosen a minimalist path with Oberon. Oberon-07 design goal has been to remove as many features as possible from original Oberon, while keeping a GC enabled systems programming language. Then you have the other path, taken by others at ETHZ, which extended Oberon into a more expressive language, namely Oberon-2, Component Pascal and Active Oberon. With Active Oberon being what is actually still used at ETHZ for teaching some OS classes and OS research subject.
Rochus 7y ago
Here (https://github.com/rochus-keller/Oberon https://github.com/rochus-keller/Oberon) is a Qt/C++ based viewer/cross-referencer for Oberon-07 code bases as well as an Oberon to C++/Lua/LuaJIT bytecode transpiler/compiler; an IDE is work in progress. > How is error handling done in Oberon-07? There is an Oberon programming language with compiler written in Oberon, and there is an operating system called Oberon as well; you can have a look at the source code, but there are also a couple of free books about it, see http://www.projectoberon.com/ http://www.projectoberon.com/ > How does one do generic programming in Oberon-07? No support for generics yet; there was a proposal in the nineties, but Wirth didn't integrate it. Neither the Go language which is a brain child of Oberon-2 has generics (yet). > What is Oberon-07's async story Oberon is single threaded; there is a coroutine library part of the Oakwood standard. But nothing comparable e.g. to Go.

sbmthakur 7y ago

Just discovered Wirth's book The School of Niklaus Wirth: The Art of Simplicity. I would like to know if it's worth the time investment?

freemint 7y ago
I do think it was not worth my time. I found the ideas presented trivial or impractically simplified. It was basically a book containing some papers on compilers celebrating Wirth. I felt i learned nothing and also felt rage due to the amount of attention his project gets (people reimplementing his pc designs on FPGA, etc.) while more worthwhile historically and technically interesting projects were ignored. I am also on an Oberon mailing list as a teacher and do not see anything interesting there. However if a person is really interested in compilers and likes the wirthian language family this book might be for him. However it seems like a circlejerk to me.