5 ms·

It doesn't matter, optimized or not, the amount of work this entails is ridiculous. Writing a C++11 compiler requires intimate knowledge of the standard (which

by yuushi 14y ago

It doesn't matter, optimized or not, the amount of work this entails is ridiculous. Writing a C++11 compiler requires intimate knowledge of the standard (which is a massive, hard to read tome), implementing pretty much all of the standard library from the ground up, and honestly, good luck writing all of that - that's all the containers (set, vector, list, map, unordered_map, multimap, unordered_multimap, forward_list, stack, deque, tuple), algorithms, time and regex libraries (chrono and regex), threading and thread models, type_traits and so on (actually, I just realized, they have it listed on the right hand side). Honestly, it's worded very poorly. "Compliant with the latest 2011 standard (C++11)" suggests all of this. I have a hard time believing this isn't some kind of joke - there's literally no-one alive that could write all of this in the timeframe of a course.

Locke1689 14y ago
Not only that, but the dragon book is terrible. To quote my adviser, "writing a parser from scratch has no value except as a character building exercise." Anyone who wanted to write their own parser should probably just use a packrat parser (I find it much simpler). Whoever is organizing this course, frankly, is either way out of their depth or holds their 1985 compilers course in far too high esteem.
- wglb 14y ago
  I disagree about the Dragon book. In particular, the code generation part was very valuable to me in the code generator. But I think I see where you are going with this. Using a parser generator for compiling, in the words of Dave Conroy (author of MicroEmacs and many other things), "A Parser Generator makes the hard part harder and the easy part easier." Edit: Wait--1985? Ah, that is the problem. I used the First dragon book, not the second. I only got the second after I did the compiler work. Was it much worse than the first?
  - Locke1689 14y ago
    No, even the second edition is hugely out of date. First, note that basically the first half of the book is about parser implementation. Then, it basically just teaches you that there's only one parser and it's called LALR. Of course, they didn't include anything like packrat, but even worse, they pretend like a LALR generator is still better than LR, even though LR was extended to be tractable for large grammars years ago. And even with all that, it's far too high level to be of use in actually engineering a compiler (which, by the way, is a good intro book).
    - niggler 14y ago
      packrat is not a panacea: once you try to add left-recursion into the mix, it becomes much slower than LALR parsers. LALR represents a nice tradeoff: both LR and packrat involve much much larger state tables than LALR parsers.
      - Locke1689 14y ago
        That's not the point. The point is to impart information and let the compiler designer choose which is appropriate. The ordering is also confusing because the grammar parsers go from less powerful to more powerful. However, LALR is after LR. Edit: Oh, and for C++ you need a GLR, which isn't even covered in dragon.
    - eru 14y ago
      > And even with all that, it's far too high level to be of use in actually engineering a compiler (which, by the way, is a good intro book). I actually found it way too low level. And not meaty enough.
    - wglb 14y ago
      I can't argue with your "hugely out of date" note. It is likely that I am also out of date, not having written compilers since the mid-80s. Do you have an opinion about the Holub book? Also I have a collection of Davidson papers about code generation that I haven't looked at since back then.
      - 14y ago
- timtadh 14y ago
  as @wglb said below I can't disagree with you more on the Dragon book. Yes, there are probably better resources out there for lexing and parsing but have your looked at the rest of the book? It actually covers most of the important static analysis techniques in sufficient detail to implement many of the important optimizations. In short: there is a reason people keep recommending it: it is a really great resource. Also, if you do want to implement a traditional Yacc like parser generator then it is a pretty good resource for that as well (having done it). Finally, while writing a parser might be a "character building exercise" sometimes there is also no getting around it.
  - Locke1689 14y ago
    Have you looked at it? How can you say there are better references for lexing and parsing and leave out that the entire first half of the book is lexing and parsing? There are a ton of books that are better at every single thing you would want. Engineering a Compiler. Modern Compiler Implementation in ML. The compiler Handbook.
    - timtadh 14y ago
      I usually reference a combination of: Dragon Book, Muchnicks: Advanced Compiler Design, and Semantics with Applications. I have been meaning to pick up a copy of Engineering a Compiler. (I should also note I am currently reading: Principles of Program Analysis, it is a good book focusing on just theory. Read Semantics with Applications first it is basically the follow up) A guess my point is this: I have learned a great deal from the Dragon book. I think it is a solid book that has taught me a lot. There may be better books out there but I haven't read one yet (Advanced Compiler Design is great but it really is only about optimization and analysis you need an undergrad book to supplement it). Finally, I have encountered worse books on the subject of compilers. So yes, this is a book that I would recommend and continue to recommend. ps. You mis-characterize the length of the lexing and parsing coverage. It starts on page 109 and ends on page 302, the content goes to 964. Chapter wise: 3-4 lexing->parsing, (chapter 1-2 are really an introduction and illustrative example so they don't count). Chapters 5-8 cover the rest of what you need to get a working compiler + some other stuff. Chapters 9-12 (page wise 583-964) cover optimization and analysis in depth. So really, nearly 40% is optimization while about 20% is syntax analysis. This book has a lot of good material most of it isn't to do with syntax analysis and the syntax analysis is for the most part high quality.
- wglb 14y ago
  And if I were to start writing a compiler today, I would certainly start with Holub's book Compiler Design in C.
  - deleted 14y ago
    [deleted]
- qznc 14y ago
  Pretty much all the good compilers (gcc,clang,...) have a hand-written parser. An exception is javac, but that one is a minimalistic parser. Handwritten parsers have better error reporting and might even be faster.
  - Locke1689 14y ago
    Yes, that's called a production compiler. If you glance in my profile you will see I'm well aware of the practices of production compilers and also how few people ever even look inside one.
- Patient0 14y ago
  I disagree that there's something wrong with writing your own parser. A simple recursive descent parser is very easy to write, and more importantly is very easy for someone else to understand. It does not require any esoteric knowledge of lookup tables and "advanced" parsing algorithms. I far prefer a stack trace from inside someone's hand-written recursive descent parser to the cryptic mess you get from Yacc or Antlr generated code. I also prefer not having to have a whole code generation stage in my build process just to support some small DSL I have embedded. This whole "you should never write your own parser" thing is so often parroted out as "wisdom"... But I honestly believe that most of the people that say this don't realise how easy it is to "roll your own".
  - Locke1689 14y ago
    The pedagogical value of writing a parser for your compiler for any language more complex than, say, Scheme, is basically zero. Skip the parser, learn the useful stuff.
    - eru 14y ago
      Oh, writing parsers is useful outside of writing compilers. But yes, you shouldn't be writing parsers in low level languages like C++. Write them in OCaml or Haskell. It's a joy there.
      - helmut_hed 14y ago
        This is my cue to mention Spirit http://boost-spirit.com/home/ http://boost-spirit.com/home/
    - bane 14y ago
      unless you ever need to process data in a format for which a decent library doesn't already exist
      - wglb 14y ago
        Do you have an example in mind of such data?
- laichzeit0 14y ago
  Except when you work on embedded systems (I'm talking about the type where you have a few hundred kilobytes of ram and flash, no OS under your ass and crap libraries). I've used a recursive descent parsing technique that's described in a paper of about 5 pages by David Hanson to great effect [1]. Depends on the situation you find yourself in, sometimes it's unavoidable to re-invent the wheel. [1] http://drhanson.s3.amazonaws.com/storage/documents/compact.pdf http://drhanson.s3.amazonaws.com/storage/documents/compact.p...
- eru 14y ago
  > Not only that, but the dragon book is terrible. Agreed. I can never believe the people who still praise it.
  - mossplix 14y ago
    Which is the best book for compiler design then?
    - eru 14y ago
      I haven't read all of them. But I liked "Modern Compiler Design" (http://www.amazon.com/Modern-Compiler-Design-D-Grune/dp/0471976970 http://www.amazon.com/Modern-Compiler-Design-D-Grune/dp/0471...). If you have a functional bend, Simon Peyton Jones' book (https://research.microsoft.com/en-us/um/people/simonpj/Papers/pj-lester-book/ https://research.microsoft.com/en-us/um/people/simonpj/Paper...) is worth reading, too. His book, however, is not a complete treatment. It assumes you know e.g. how to write a parser, and concentrates on the challenges unique to lazy functional languages.
- yan 14y ago
  > To quote my adviser, "writing a parser from scratch has no value except as a character building exercise." I think I just read the best potentially unintentional compiler pun I have ever seen.
- dspeyer 14y ago
  Is there any parser autogeneration tool that can cope with c++11's grammer? Including weird edge cases like template vs. comparison depending on previously declared types?
  - Locke1689 14y ago
    C++ is messed up that you're gonna need to do some weird stuff. First, the grammar is ambiguous. Second, the template language is undecidable. Nothing you can do about the second. The first, you'll at least need something capable of parsing context-free languages. My recommendation is to start here[1]. [1] http://arxiv.org/abs/1010.5023 http://arxiv.org/abs/1010.5023
niggler 14y ago
I was just replying to the comment regarding GCC and MSVC -- the argument seemed to be that most of the development manhours were devoted to C++11 when in fact most of it was devoted to optimization strategies and cross-architectural compatibility.

by yuushi 14y ago

Locke1689 14y ago

Not only that, but the dragon book is terrible. To quote my adviser, "writing a parser from scratch has no value except as a character building exercise." Anyone who wanted to write their own parser should probably just use a packrat parser (I find it much simpler). Whoever is organizing this course, frankly, is either way out of their depth or holds their 1985 compilers course in far too high esteem.

wglb 14y ago
I disagree about the Dragon book. In particular, the code generation part was very valuable to me in the code generator. But I think I see where you are going with this. Using a parser generator for compiling, in the words of Dave Conroy (author of MicroEmacs and many other things), "A Parser Generator makes the hard part harder and the easy part easier." Edit: Wait--1985? Ah, that is the problem. I used the First dragon book, not the second. I only got the second after I did the compiler work. Was it much worse than the first?
- Locke1689 14y ago
  No, even the second edition is hugely out of date. First, note that basically the first half of the book is about parser implementation. Then, it basically just teaches you that there's only one parser and it's called LALR. Of course, they didn't include anything like packrat, but even worse, they pretend like a LALR generator is still better than LR, even though LR was extended to be tractable for large grammars years ago. And even with all that, it's far too high level to be of use in actually engineering a compiler (which, by the way, is a good intro book).
  - niggler 14y ago
    packrat is not a panacea: once you try to add left-recursion into the mix, it becomes much slower than LALR parsers. LALR represents a nice tradeoff: both LR and packrat involve much much larger state tables than LALR parsers.
    - Locke1689 14y ago
      That's not the point. The point is to impart information and let the compiler designer choose which is appropriate. The ordering is also confusing because the grammar parsers go from less powerful to more powerful. However, LALR is after LR. Edit: Oh, and for C++ you need a GLR, which isn't even covered in dragon.
  - eru 14y ago
    > And even with all that, it's far too high level to be of use in actually engineering a compiler (which, by the way, is a good intro book). I actually found it way too low level. And not meaty enough.
  - wglb 14y ago
    I can't argue with your "hugely out of date" note. It is likely that I am also out of date, not having written compilers since the mid-80s. Do you have an opinion about the Holub book? Also I have a collection of Davidson papers about code generation that I haven't looked at since back then.
    - 14y ago
timtadh 14y ago
as @wglb said below I can't disagree with you more on the Dragon book. Yes, there are probably better resources out there for lexing and parsing but have your looked at the rest of the book? It actually covers most of the important static analysis techniques in sufficient detail to implement many of the important optimizations. In short: there is a reason people keep recommending it: it is a really great resource. Also, if you do want to implement a traditional Yacc like parser generator then it is a pretty good resource for that as well (having done it). Finally, while writing a parser might be a "character building exercise" sometimes there is also no getting around it.
- Locke1689 14y ago
  Have you looked at it? How can you say there are better references for lexing and parsing and leave out that the entire first half of the book is lexing and parsing? There are a ton of books that are better at every single thing you would want. Engineering a Compiler. Modern Compiler Implementation in ML. The compiler Handbook.
  - timtadh 14y ago
    I usually reference a combination of: Dragon Book, Muchnicks: Advanced Compiler Design, and Semantics with Applications. I have been meaning to pick up a copy of Engineering a Compiler. (I should also note I am currently reading: Principles of Program Analysis, it is a good book focusing on just theory. Read Semantics with Applications first it is basically the follow up) A guess my point is this: I have learned a great deal from the Dragon book. I think it is a solid book that has taught me a lot. There may be better books out there but I haven't read one yet (Advanced Compiler Design is great but it really is only about optimization and analysis you need an undergrad book to supplement it). Finally, I have encountered worse books on the subject of compilers. So yes, this is a book that I would recommend and continue to recommend. ps. You mis-characterize the length of the lexing and parsing coverage. It starts on page 109 and ends on page 302, the content goes to 964. Chapter wise: 3-4 lexing->parsing, (chapter 1-2 are really an introduction and illustrative example so they don't count). Chapters 5-8 cover the rest of what you need to get a working compiler + some other stuff. Chapters 9-12 (page wise 583-964) cover optimization and analysis in depth. So really, nearly 40% is optimization while about 20% is syntax analysis. This book has a lot of good material most of it isn't to do with syntax analysis and the syntax analysis is for the most part high quality.
wglb 14y ago
And if I were to start writing a compiler today, I would certainly start with Holub's book Compiler Design in C.
- deleted 14y ago
  [deleted]
qznc 14y ago
Pretty much all the good compilers (gcc,clang,...) have a hand-written parser. An exception is javac, but that one is a minimalistic parser. Handwritten parsers have better error reporting and might even be faster.
- Locke1689 14y ago
  Yes, that's called a production compiler. If you glance in my profile you will see I'm well aware of the practices of production compilers and also how few people ever even look inside one.
Patient0 14y ago
I disagree that there's something wrong with writing your own parser. A simple recursive descent parser is very easy to write, and more importantly is very easy for someone else to understand. It does not require any esoteric knowledge of lookup tables and "advanced" parsing algorithms. I far prefer a stack trace from inside someone's hand-written recursive descent parser to the cryptic mess you get from Yacc or Antlr generated code. I also prefer not having to have a whole code generation stage in my build process just to support some small DSL I have embedded. This whole "you should never write your own parser" thing is so often parroted out as "wisdom"... But I honestly believe that most of the people that say this don't realise how easy it is to "roll your own".
- Locke1689 14y ago
  The pedagogical value of writing a parser for your compiler for any language more complex than, say, Scheme, is basically zero. Skip the parser, learn the useful stuff.
  - eru 14y ago
    Oh, writing parsers is useful outside of writing compilers. But yes, you shouldn't be writing parsers in low level languages like C++. Write them in OCaml or Haskell. It's a joy there.
    - helmut_hed 14y ago
      This is my cue to mention Spirit http://boost-spirit.com/home/ http://boost-spirit.com/home/
  - bane 14y ago
    unless you ever need to process data in a format for which a decent library doesn't already exist
    - wglb 14y ago
      Do you have an example in mind of such data?
laichzeit0 14y ago
Except when you work on embedded systems (I'm talking about the type where you have a few hundred kilobytes of ram and flash, no OS under your ass and crap libraries). I've used a recursive descent parsing technique that's described in a paper of about 5 pages by David Hanson to great effect [1]. Depends on the situation you find yourself in, sometimes it's unavoidable to re-invent the wheel. [1] http://drhanson.s3.amazonaws.com/storage/documents/compact.pdf http://drhanson.s3.amazonaws.com/storage/documents/compact.p...
eru 14y ago
> Not only that, but the dragon book is terrible. Agreed. I can never believe the people who still praise it.
- mossplix 14y ago
  Which is the best book for compiler design then?
  - eru 14y ago
    I haven't read all of them. But I liked "Modern Compiler Design" (http://www.amazon.com/Modern-Compiler-Design-D-Grune/dp/0471976970 http://www.amazon.com/Modern-Compiler-Design-D-Grune/dp/0471...). If you have a functional bend, Simon Peyton Jones' book (https://research.microsoft.com/en-us/um/people/simonpj/Papers/pj-lester-book/ https://research.microsoft.com/en-us/um/people/simonpj/Paper...) is worth reading, too. His book, however, is not a complete treatment. It assumes you know e.g. how to write a parser, and concentrates on the challenges unique to lazy functional languages.
yan 14y ago
> To quote my adviser, "writing a parser from scratch has no value except as a character building exercise." I think I just read the best potentially unintentional compiler pun I have ever seen.
dspeyer 14y ago
Is there any parser autogeneration tool that can cope with c++11's grammer? Including weird edge cases like template vs. comparison depending on previously declared types?
- Locke1689 14y ago
  C++ is messed up that you're gonna need to do some weird stuff. First, the grammar is ambiguous. Second, the template language is undecidable. Nothing you can do about the second. The first, you'll at least need something capable of parsing context-free languages. My recommendation is to start here[1]. [1] http://arxiv.org/abs/1010.5023 http://arxiv.org/abs/1010.5023

niggler 14y ago

I was just replying to the comment regarding GCC and MSVC -- the argument seemed to be that most of the development manhours were devoted to C++11 when in fact most of it was devoted to optimization strategies and cross-architectural compatibility.