6 ms·

I agree. I remember my compiler class where we went through the whole Dragon book and we had a lot of theoretical knowledge, but we were disappointed because we

by d0m 11y ago

I agree. I remember my compiler class where we went through the whole Dragon book and we had a lot of theoretical knowledge, but we were disappointed because we practically couldn't build a compiler. We went in too much detail too fast without having a good understanding and practical examples with compilers.

santaclaus 11y ago
> the whole Dragon book I learned compilers from Al Aho, and believe me, the class was no better in person. Mostly in-person waxing poetic about his time at Bell Labs...
- dgacmu 11y ago
  Dinner with Al Aho was one of the highlights of when I visited Columbia a while ago. He's simply an awesome person. And he's done some fantastic work - Aho-Corasick is a great algorithm. Alas, the Dragon Book was one of the low points of my undergraduate education, though I had a great teacher who pulled out a terrifically fun class despite the book. (Thanks, +Wilson Hsieh.) In fairness, though -- or more an admission of how wrong we can be about things like this -- I subscribed to the "parsing is boring and solved" belief until Bryan Ford's Packrat Parsing work made me realize that it had just gotten stuck at a traffic light for a few decades.
  - mdcox 11y ago
    Veering a bit offtopic, but does anyone have any pointers to important recent work on parsing? There are alot of papers out there and I guess I don't know how to sift through them. I've heard the "parsing is solved" line before, but so much of my time is spent doing some type of parsing that even incremental improvements are extremely interesting.
    - cwzwarich 11y ago
      I can probably help if you can narrow things down a bit. Are you parsing deterministic languages (e.g. for programming languages), general context-free languages, binary file formats, or something else? Because parsing is a field of little active research interest where most of the work happened more than 20 years ago, there are a lot of techniques from the 70s, 80s, and 90s that are relatively unknown.
      - mdcox 11y ago
        I'm most interested in deterministic languages. Non-deterministic context-free languages would be extremely interesting as well but more out of curiosity than an applicable need. Thanks!
        vidarh 11y ago
        For deterministic languages, hand written recursive descent is usually the choice even today because of simplicity and ease of error reporting. There are exceptions, but relatively few production compilers uses anything else, and most of the innovations in parsing provides relatively little value in this space because they tend to be focused on better expressing complex languages rather than provide improved ways of expressing / capturing errors, and it's the latter that would provide most benefit for deterministic languages.
    - sklogic 11y ago
      PEG (Packrat) is hot now.
      - nly 11y ago
        Interesting paper on left-recursion in recursive descent parsers like PEGs and Packrats http://web.cs.ucla.edu/~todd/research/pub.php?id=pepm08 http://web.cs.ucla.edu/~todd/research/pub.php?id=pepm08
        sklogic 11y ago
        Yes, I implemented exactly this approach. But for the binary expressions I am using Pratt, it is faster and easier to construct left-associative nodes.
        ltratt 11y ago
        If you're interested in left-recursion in PEGS then, at the risk of gross immodesty, you may be interested in http://tratt.net/laurie/research/pubs/html/tratt__direct_left_recursive_parsing_expression_grammars/ http://tratt.net/laurie/research/pubs/html/tratt__direct_lef... With less risk of immodesty you may also find http://arxiv.org/pdf/1207.0443.pdf?ref=driverlayer.com/web http://arxiv.org/pdf/1207.0443.pdf?ref=driverlayer.com/web interesting. There's probably more recent work than these two papers, but I'm a little out of date when it comes to the PEG world.
        nly 11y ago
        Thanks, looks like you've put a lot of work in to it and I'll enjoy reading it.
      - fanf2 11y ago
        It is important to distinguish between PEG and packrat. PEG is a model for recognizers, distinct from traditional grammers whose theoretical model is usually based on generating strings rather than recognising them. (Yes this is a bit backwards.) The most distinctive feature of PEGs is the ordered choice operator - traditional context-free grammars and regexes use unordered choice, but ordered choice is a closer model of how recursive descent parsers work in practice. Ordered choice naturally leads to implementations that have less backtracking than common regex matchers, e.g. Lpeg. Packrat parsers are based on a clever non-backtracking PEG matching algorithm. They spend O(n) memory to get O(n) parsing time, so they are reliably fast but not good for long inputs. They are also effective in a pure, lazy setting like Haskell. Lpeg is a PEG parser but not a packrat parser.
    - Apanatshka 11y ago
      It really depends on the kind of parsing that you're doing. Full context-free grammar are supported by "generalised parsing". The older stuff is GLR by Tomita, Early parsing, the CYK algorithm. The newer stuff based on Tomita is the particular rabbit hole I stuck with for a while. I read about SGLR which eliminates lexers, GLL which is GLR but based on the LL algorithm. The people who do GLL research also did improvements on SGLR with improved speed on right-nulled grammars. Then there is the SGLR improvements with disambiguation filters, automatic derivation of error recovery with island grammars, etc. The disambiguation filters include a kind of negation, making the current implementation of SGLR for SDF capable to parsing Boolean Grammars, which are a superset of context-free grammars. Anyway, there's more than context-free grammars. Definitely look into data-dependant grammars! It's able to define a lot of interesting things, like network protocol formats where you parse the length of the payload, then based on that length you know how much to interpret as the payload before you read the footer of the message. And you write all of that in a more declarative way and get a nice parser generated from it. There is so much more, but I think I should to stop now :)
    - exDM69 11y ago
      > Veering a bit offtopic, but does anyone have any pointers to important recent work on parsing? Parser combinators are a relatively modern topic in parsing. First research into the topic was made in the late 1980s, but parser combinators became popular after Parsec [0], a practical implementation of parser combinators in Haskell. These ideas have been borrowed to many different implementations in different languages since then. [0] Daan Leijen: "Parsec, a fast combinator parser", 2001 http://research.microsoft.com/en-us/um/people/daan/download/parsec/parsec.html http://research.microsoft.com/en-us/um/people/daan/download/...
    - fanf2 11y ago
      Check out ANTLR which is probably the best modern parser generator. ANTLR 4 uses "adaptive LL(*)" (aka "all star") for its underlying theory. http://www.antlr.org/papers/allstar-techreport.pdf http://www.antlr.org/papers/allstar-techreport.pdf
YZF 11y ago
In my compiler class we also used the Dragon book and we did write a compiler for a C like language... I don't think we covered the book in its entirety though but sounds like that was a better mix. I felt quite capable of writing simple compilers after I finished the course...
ChuckMcM 11y ago
Interesting, I took compilers where the Dragon book was the standard text book, we implemented a PASCAL like language (which compiled for the DEC10 as a target) and it was one of the really transformative classes I had taken. It brought together algorithms and data structures into a curriculum where they joined up to convert text into executable code. Really one of those moments of sudden clarity for me.
ww520 11y ago
I went through a undergrad compiler class with the Dragon book, not the whole thing though, just enough chapters to build a compiler. We did build a full fledged compiler for an OO language, with all the parts of a compiler all the way to code generating assembly. It's kind of fast pace with too many stuff crammed into a class. Some theoretical topics were kind of fuzzy at the time. Still it was one of the best classes I have ever attended. Later on when I re-read the book on my own pace, I thought the book was the best thing since slice bread. Got a much better understanding of the theories behind the compiler topics. A lot of the things I learned I can still apply to this day.
vidarh 11y ago
I loved the Dragon book, but I agree not a practical book. I probably loved it because at the time I'd already been experimenting with compiler writing for 5-6 years, and it gave me a theoretical grounding for a lot of stuff I'd been doing or doing subtly "wrong". I think it - and similar books - should be banished from first compiler classes, and instead be used later. Much more practical books like Wirth's that actually walk you through writing a compiler would be much better for most beginners.

by d0m 11y ago

santaclaus 11y ago

> the whole Dragon book I learned compilers from Al Aho, and believe me, the class was no better in person. Mostly in-person waxing poetic about his time at Bell Labs...

dgacmu 11y ago
Dinner with Al Aho was one of the highlights of when I visited Columbia a while ago. He's simply an awesome person. And he's done some fantastic work - Aho-Corasick is a great algorithm. Alas, the Dragon Book was one of the low points of my undergraduate education, though I had a great teacher who pulled out a terrifically fun class despite the book. (Thanks, +Wilson Hsieh.) In fairness, though -- or more an admission of how wrong we can be about things like this -- I subscribed to the "parsing is boring and solved" belief until Bryan Ford's Packrat Parsing work made me realize that it had just gotten stuck at a traffic light for a few decades.
- mdcox 11y ago
  Veering a bit offtopic, but does anyone have any pointers to important recent work on parsing? There are alot of papers out there and I guess I don't know how to sift through them. I've heard the "parsing is solved" line before, but so much of my time is spent doing some type of parsing that even incremental improvements are extremely interesting.
  - cwzwarich 11y ago
    I can probably help if you can narrow things down a bit. Are you parsing deterministic languages (e.g. for programming languages), general context-free languages, binary file formats, or something else? Because parsing is a field of little active research interest where most of the work happened more than 20 years ago, there are a lot of techniques from the 70s, 80s, and 90s that are relatively unknown.
    - mdcox 11y ago
      I'm most interested in deterministic languages. Non-deterministic context-free languages would be extremely interesting as well but more out of curiosity than an applicable need. Thanks!
      - vidarh 11y ago
        For deterministic languages, hand written recursive descent is usually the choice even today because of simplicity and ease of error reporting. There are exceptions, but relatively few production compilers uses anything else, and most of the innovations in parsing provides relatively little value in this space because they tend to be focused on better expressing complex languages rather than provide improved ways of expressing / capturing errors, and it's the latter that would provide most benefit for deterministic languages.
  - sklogic 11y ago
    PEG (Packrat) is hot now.
    - nly 11y ago
      Interesting paper on left-recursion in recursive descent parsers like PEGs and Packrats http://web.cs.ucla.edu/~todd/research/pub.php?id=pepm08 http://web.cs.ucla.edu/~todd/research/pub.php?id=pepm08
      - sklogic 11y ago
        Yes, I implemented exactly this approach. But for the binary expressions I am using Pratt, it is faster and easier to construct left-associative nodes.
      - ltratt 11y ago
        If you're interested in left-recursion in PEGS then, at the risk of gross immodesty, you may be interested in http://tratt.net/laurie/research/pubs/html/tratt__direct_left_recursive_parsing_expression_grammars/ http://tratt.net/laurie/research/pubs/html/tratt__direct_lef... With less risk of immodesty you may also find http://arxiv.org/pdf/1207.0443.pdf?ref=driverlayer.com/web http://arxiv.org/pdf/1207.0443.pdf?ref=driverlayer.com/web interesting. There's probably more recent work than these two papers, but I'm a little out of date when it comes to the PEG world.
        nly 11y ago
        Thanks, looks like you've put a lot of work in to it and I'll enjoy reading it.
    - fanf2 11y ago
      It is important to distinguish between PEG and packrat. PEG is a model for recognizers, distinct from traditional grammers whose theoretical model is usually based on generating strings rather than recognising them. (Yes this is a bit backwards.) The most distinctive feature of PEGs is the ordered choice operator - traditional context-free grammars and regexes use unordered choice, but ordered choice is a closer model of how recursive descent parsers work in practice. Ordered choice naturally leads to implementations that have less backtracking than common regex matchers, e.g. Lpeg. Packrat parsers are based on a clever non-backtracking PEG matching algorithm. They spend O(n) memory to get O(n) parsing time, so they are reliably fast but not good for long inputs. They are also effective in a pure, lazy setting like Haskell. Lpeg is a PEG parser but not a packrat parser.
  - Apanatshka 11y ago
    It really depends on the kind of parsing that you're doing. Full context-free grammar are supported by "generalised parsing". The older stuff is GLR by Tomita, Early parsing, the CYK algorithm. The newer stuff based on Tomita is the particular rabbit hole I stuck with for a while. I read about SGLR which eliminates lexers, GLL which is GLR but based on the LL algorithm. The people who do GLL research also did improvements on SGLR with improved speed on right-nulled grammars. Then there is the SGLR improvements with disambiguation filters, automatic derivation of error recovery with island grammars, etc. The disambiguation filters include a kind of negation, making the current implementation of SGLR for SDF capable to parsing Boolean Grammars, which are a superset of context-free grammars. Anyway, there's more than context-free grammars. Definitely look into data-dependant grammars! It's able to define a lot of interesting things, like network protocol formats where you parse the length of the payload, then based on that length you know how much to interpret as the payload before you read the footer of the message. And you write all of that in a more declarative way and get a nice parser generated from it. There is so much more, but I think I should to stop now :)
  - exDM69 11y ago
    > Veering a bit offtopic, but does anyone have any pointers to important recent work on parsing? Parser combinators are a relatively modern topic in parsing. First research into the topic was made in the late 1980s, but parser combinators became popular after Parsec [0], a practical implementation of parser combinators in Haskell. These ideas have been borrowed to many different implementations in different languages since then. [0] Daan Leijen: "Parsec, a fast combinator parser", 2001 http://research.microsoft.com/en-us/um/people/daan/download/parsec/parsec.html http://research.microsoft.com/en-us/um/people/daan/download/...
  - fanf2 11y ago
    Check out ANTLR which is probably the best modern parser generator. ANTLR 4 uses "adaptive LL(*)" (aka "all star") for its underlying theory. http://www.antlr.org/papers/allstar-techreport.pdf http://www.antlr.org/papers/allstar-techreport.pdf

YZF 11y ago

In my compiler class we also used the Dragon book and we did write a compiler for a C like language... I don't think we covered the book in its entirety though but sounds like that was a better mix. I felt quite capable of writing simple compilers after I finished the course...

ChuckMcM 11y ago

Interesting, I took compilers where the Dragon book was the standard text book, we implemented a PASCAL like language (which compiled for the DEC10 as a target) and it was one of the really transformative classes I had taken. It brought together algorithms and data structures into a curriculum where they joined up to convert text into executable code. Really one of those moments of sudden clarity for me.

ww520 11y ago

I went through a undergrad compiler class with the Dragon book, not the whole thing though, just enough chapters to build a compiler. We did build a full fledged compiler for an OO language, with all the parts of a compiler all the way to code generating assembly. It's kind of fast pace with too many stuff crammed into a class. Some theoretical topics were kind of fuzzy at the time. Still it was one of the best classes I have ever attended. Later on when I re-read the book on my own pace, I thought the book was the best thing since slice bread. Got a much better understanding of the theories behind the compiler topics. A lot of the things I learned I can still apply to this day.

vidarh 11y ago

I loved the Dragon book, but I agree not a practical book. I probably loved it because at the time I'd already been experimenting with compiler writing for 5-6 years, and it gave me a theoretical grounding for a lot of stuff I'd been doing or doing subtly "wrong". I think it - and similar books - should be banished from first compiler classes, and instead be used later. Much more practical books like Wirth's that actually walk you through writing a compiler would be much better for most beginners.