6 ms·

>The prototypical compilers textbook is: Dragon Book?

deleted 4y ago
[deleted]
astrange 4y ago
Yes, which is why it's a bad book and you shouldn't tell people to read it. Actual compilers tend to handwrite their parsers rather than using theory; parser generators aren't good at recovery and error messages.
- zabzonk 4y ago
  I agree it is a bad book, but you don't seem to be explaining why.
  - astrange 4y ago
    The article says exactly what I'd say. It spends far too much time explaining the frontend (parsing theory) which isn't the difficult or important part of the compiler, and it somehow makes it sound scary and mathematical. The rest isn't covered enough and doesn't have enough practical real-world advice.
    - necheffa 4y ago
      As someone who has had to clean up (with backwards compatibility) after people who YOLO'd custom grammars rather than actually taking the time to respect the mathematics of parsing and design ambiguity out up front... I cannot disagree with you more.
      - astrange 4y ago
        I mean, I think you should read a book on parsing theory, just not that one. I like "Parsing Techniques: A Practical Guide" but there might be a newer better one. But clang and gcc both have handwritten recursive-descent parsers for C/C++. (C++ parsing of course is undecidable, or at least used to be.)
        samatman 4y ago
        C++ parsing being undecidable, and C having the Most Vexing Parse, are the classic arguments for developing a grammar using a parser generator, and only when the grammar is mature, write a handrolled implementation using the grammar as a reference. I happen to think generating useful software from declarative grammar specifications is, hmm. Not limited to what such frameworks have been capable of to date. Although if you've only worked with yacc/bison, and never ANTLR, you may be underestimating the quality of a generated parser with respect to error recovery and messages. The state of the art has advanced, I don't think anyone would claim parity with artisanal handcrafted softwares, but we can get a lot more than "barf: shift-reduce bunchanumbers" these days.
        zabzonk 4y ago
        > and C having the Most Vexing Parse C++ too. Just to be pedantic.
    - dgunay 4y ago
      I can echo this sentiment. Last year I took a course for my master's where we implemented a compiler end to end. The dragon book helped for most of it but when it came time to implement the assembler we were unable to get it completely correct and the book was very scant on any information about how to best manage going from virtual to physical registers, handle storing information on the stack, etc. Granted some of that is platform specific but the difference in material from frontend to backend was stark.
    - mhh__ 4y ago
      Parsing is also about 1% of the effort for a mature frontend. Books do not cover how to actually structure a compiler and write sensible passes etc.
    - oxff 4y ago
      Frontend is very important if you want your language to have good IDE tooling (which most languages do not have)
- zetalyrae 4y ago
  I think writing a parser by hand should be reserved for when 1. You have users. 2. You can demonstrate a marked improvement in performance and/or error reporting with the hand-written parser. Otherwise, deriving a parser from a grammar should absolutely be the default. Writing parsers by hand is error-prone, causes security vulnerabilities[0], and is very tedious work. [0]: http://langsec.org/ http://langsec.org/
  - t-3 4y ago
    3. Your language has very little/no syntax. A parser for a Forth is a one-liner or a short loop in most languages.
    - mhzsh 4y ago
      4. You want to learn how to implement a parser by hand.
  - pianoben 4y ago
    Having written production-level compilers, my advice: use ANTLR for as long as humanly possible. It can remain adequate far, far longer than you think, and will save you months/years of stress. When you outgrow it, you'll know - and by then, hopefully you'll have funding/users/contributors/etc to support the dev effort of rolling your own parser.
    - matijash 4y ago
      Our compiler stack is in Haskell so we initially started with Parsec (parser combinator library) and then eventually switched to Happy (parser generator that Haskell uses itself) since at first we didn't have a formal grammar defined so that made us write a lot of code for every little addition to the language (it's a simple declarative DSL, https://github.com/wasp-lang/wasp https://github.com/wasp-lang/wasp). The problem we're now facing with Happy is that it doesn't really have support for error recovery. We're trying to implement LSP so recovery is important in order to have proper syntax highlighting and error reporting in an IDE. Wondering how well ANTLR covers this, I was quite surprised to find out that Happy has so little support for it.
- defen 4y ago
  > Actual compilers tend to handwrite their parsers rather than using theory; parser generators aren't good at recovery and error messages. The linked article recommends using a parser generator. However in my experience I agree with you, parser generators aren't great in practice, which makes me hesitant to read the rest of the post.
  - zetalyrae 4y ago
    The time investment of writing a good hand-written parser is only worth it if you have users whose workflow would be improved by performance/error reporting gains once you have exhausted what a grammar-derived parser can provide. For Clang and GCC is it absolutely a no brainer to use a hand-written parser. If you're trying to get to an MVP compiler, or you're building a bootstrapping compiler, using a grammar-derived parser to get to the finish line faster is far more sensible.
    - eatonphil 4y ago
      Using parser generators doesn't make a lot of sense to me. It's far easier to handwrite parsers. Unless you're a midsized company with the resources and who doesn't mind bad error messages I would not recommend anyone use parser generators.
      - userbinator 4y ago
        It's also far easier to debug handwritten parsers.
      - zetalyrae 4y ago
        What could be easier than writing a grammar in EBNF-ish notation? This gives you the added benefit that the grammar is explicitly defined, and not implicit in the parser code.
        eatonphil 4y ago
        > What could be easier than writing a grammar in EBNF-ish notation? Not learning a new language/build system/coding paradigm. :)
- titzer 4y ago
  Just write recursive descent, except for the infix operator precedence, and then use a tiny stack that you either push to or pop from (shift/reduce, ala LR) based on the relative precedence. Pretty much all compilers that have fast parsers that also give good error messages are hand-written recursive descent.
- mrslave 4y ago
  It's a fine book and you should not tell people to read it. It belongs in a first compilers course where you learn about how scanners and parsers work, not just "configure this then call `yylex`". So yeah, it nerds out about finite state machines for a little too long for most audiences. And you know your audience. Your audience wants to write a compiler today, so you are correct not to recommend this book.
- dan-robertson 4y ago
  Regarding parsing techniques: https://notes.eatonphil.com/parser-generators-vs-handwritten-parsers-survey-2021.html https://notes.eatonphil.com/parser-generators-vs-handwritten...
deleted 4y ago
[deleted]
mhh__ 4y ago
I think engineering a compiler is a better book. The dragon book has a few places which are really good and then a few places which were an afterthought shoved in there later like SSA (which is really important). We are due a new batch of compiler books. As the utility of investment in compilers has decreased we are stuck with books mostly expecting x86 to die and be replaced with potentially statically schedulable machines so a lot of time is spent on algorithms that are really really fuzzy on a modern core. Muchnick is a still a Bible for optimizations but it's written in a bizarre pseudo-language which means many algorithms are rather inpenetrable. JITs are not very well covered in the literature. There's a lot of subtle variations in how they design their IRs these days.
sivakon 4y ago
so what’s the quintessential book for learning compilers (practical book)!

deleted 4y ago

[deleted]

Yes, which is why it's a bad book and you shouldn't tell people to read it. Actual compilers tend to handwrite their parsers rather than using theory; parser generators aren't good at recovery and error messages.

zabzonk 4y ago
I agree it is a bad book, but you don't seem to be explaining why.
- astrange 4y ago
  The article says exactly what I'd say. It spends far too much time explaining the frontend (parsing theory) which isn't the difficult or important part of the compiler, and it somehow makes it sound scary and mathematical. The rest isn't covered enough and doesn't have enough practical real-world advice.
  - necheffa 4y ago
    As someone who has had to clean up (with backwards compatibility) after people who YOLO'd custom grammars rather than actually taking the time to respect the mathematics of parsing and design ambiguity out up front... I cannot disagree with you more.
    - astrange 4y ago
      I mean, I think you should read a book on parsing theory, just not that one. I like "Parsing Techniques: A Practical Guide" but there might be a newer better one. But clang and gcc both have handwritten recursive-descent parsers for C/C++. (C++ parsing of course is undecidable, or at least used to be.)
      - samatman 4y ago
        C++ parsing being undecidable, and C having the Most Vexing Parse, are the classic arguments for developing a grammar using a parser generator, and only when the grammar is mature, write a handrolled implementation using the grammar as a reference. I happen to think generating useful software from declarative grammar specifications is, hmm. Not limited to what such frameworks have been capable of to date. Although if you've only worked with yacc/bison, and never ANTLR, you may be underestimating the quality of a generated parser with respect to error recovery and messages. The state of the art has advanced, I don't think anyone would claim parity with artisanal handcrafted softwares, but we can get a lot more than "barf: shift-reduce bunchanumbers" these days.
        zabzonk 4y ago
        > and C having the Most Vexing Parse C++ too. Just to be pedantic.
  - dgunay 4y ago
    I can echo this sentiment. Last year I took a course for my master's where we implemented a compiler end to end. The dragon book helped for most of it but when it came time to implement the assembler we were unable to get it completely correct and the book was very scant on any information about how to best manage going from virtual to physical registers, handle storing information on the stack, etc. Granted some of that is platform specific but the difference in material from frontend to backend was stark.
  - mhh__ 4y ago
    Parsing is also about 1% of the effort for a mature frontend. Books do not cover how to actually structure a compiler and write sensible passes etc.
  - oxff 4y ago
    Frontend is very important if you want your language to have good IDE tooling (which most languages do not have)
zetalyrae 4y ago
I think writing a parser by hand should be reserved for when 1. You have users. 2. You can demonstrate a marked improvement in performance and/or error reporting with the hand-written parser. Otherwise, deriving a parser from a grammar should absolutely be the default. Writing parsers by hand is error-prone, causes security vulnerabilities[0], and is very tedious work. [0]: http://langsec.org/ http://langsec.org/
- t-3 4y ago
  3. Your language has very little/no syntax. A parser for a Forth is a one-liner or a short loop in most languages.
  - mhzsh 4y ago
    4. You want to learn how to implement a parser by hand.
- pianoben 4y ago
  Having written production-level compilers, my advice: use ANTLR for as long as humanly possible. It can remain adequate far, far longer than you think, and will save you months/years of stress. When you outgrow it, you'll know - and by then, hopefully you'll have funding/users/contributors/etc to support the dev effort of rolling your own parser.
  - matijash 4y ago
    Our compiler stack is in Haskell so we initially started with Parsec (parser combinator library) and then eventually switched to Happy (parser generator that Haskell uses itself) since at first we didn't have a formal grammar defined so that made us write a lot of code for every little addition to the language (it's a simple declarative DSL, https://github.com/wasp-lang/wasp https://github.com/wasp-lang/wasp). The problem we're now facing with Happy is that it doesn't really have support for error recovery. We're trying to implement LSP so recovery is important in order to have proper syntax highlighting and error reporting in an IDE. Wondering how well ANTLR covers this, I was quite surprised to find out that Happy has so little support for it.
defen 4y ago
> Actual compilers tend to handwrite their parsers rather than using theory; parser generators aren't good at recovery and error messages. The linked article recommends using a parser generator. However in my experience I agree with you, parser generators aren't great in practice, which makes me hesitant to read the rest of the post.
- zetalyrae 4y ago
  The time investment of writing a good hand-written parser is only worth it if you have users whose workflow would be improved by performance/error reporting gains once you have exhausted what a grammar-derived parser can provide. For Clang and GCC is it absolutely a no brainer to use a hand-written parser. If you're trying to get to an MVP compiler, or you're building a bootstrapping compiler, using a grammar-derived parser to get to the finish line faster is far more sensible.
  - eatonphil 4y ago
    Using parser generators doesn't make a lot of sense to me. It's far easier to handwrite parsers. Unless you're a midsized company with the resources and who doesn't mind bad error messages I would not recommend anyone use parser generators.
    - userbinator 4y ago
      It's also far easier to debug handwritten parsers.
    - zetalyrae 4y ago
      What could be easier than writing a grammar in EBNF-ish notation? This gives you the added benefit that the grammar is explicitly defined, and not implicit in the parser code.
      - eatonphil 4y ago
        > What could be easier than writing a grammar in EBNF-ish notation? Not learning a new language/build system/coding paradigm. :)
titzer 4y ago
Just write recursive descent, except for the infix operator precedence, and then use a tiny stack that you either push to or pop from (shift/reduce, ala LR) based on the relative precedence. Pretty much all compilers that have fast parsers that also give good error messages are hand-written recursive descent.
mrslave 4y ago
It's a fine book and you should not tell people to read it. It belongs in a first compilers course where you learn about how scanners and parsers work, not just "configure this then call `yylex`". So yeah, it nerds out about finite state machines for a little too long for most audiences. And you know your audience. Your audience wants to write a compiler today, so you are correct not to recommend this book.
dan-robertson 4y ago
Regarding parsing techniques: https://notes.eatonphil.com/parser-generators-vs-handwritten-parsers-survey-2021.html https://notes.eatonphil.com/parser-generators-vs-handwritten...

deleted 4y ago

[deleted]

mhh__ 4y ago

I think engineering a compiler is a better book. The dragon book has a few places which are really good and then a few places which were an afterthought shoved in there later like SSA (which is really important). We are due a new batch of compiler books. As the utility of investment in compilers has decreased we are stuck with books mostly expecting x86 to die and be replaced with potentially statically schedulable machines so a lot of time is spent on algorithms that are really really fuzzy on a modern core. Muchnick is a still a Bible for optimizations but it's written in a bizarre pseudo-language which means many algorithms are rather inpenetrable. JITs are not very well covered in the literature. There's a lot of subtle variations in how they design their IRs these days.

sivakon 4y ago

so what’s the quintessential book for learning compilers (practical book)!