3 ms·

I get that this timeline is designed to promote the author's own parsing algorithm, and doesn't claim to be exhaustive, but I'd be curious to know how PEGs / pa

I get that this timeline is designed to promote the author's own parsing algorithm, and doesn't claim to be exhaustive, but I'd be curious to know how PEGs / packrat parsers and Hutton/Meijer's work on monadic parser combinators fit into this - both chronologically, and in terms of tradeoffs.

chubot 12y ago
Yeah I would also like to see how those topics fit in. To me, it is curious that people move from LALR to recursive descent -- i.e. generated bottom-up to manual top-down. It seems like moving to PEGs or ANTLR would be less drastic -- i.e. to generated top-down. That may be a historical thing though, because top-down parser generators seem to have come a lot later (was there anything before ANTLR's predecessors?) I find top down parsers a lot more intuitive and this article seems to say it's not just me (despite the fact that his project is bottom-up?). I think there is some confusion about top down parsers and arithmetic expressions, e.g. left recursion. But it seems much easier to mix top down parsers with other techniques like operator precedence parsing. You can always insert arbitrary code for one of the rule/production functions. I don't believe you can mix LALR with anything else. PEGs are really just a formalization of recursive descent, which I think makes them a very practical choice. I implemented a PEG parsing interpreter awhile ago. What I discovered though is that it's a lot more natural to have a separate traditional lex phase, and use the PEG abstraction (ordered choice with negations) for parsing only. It seems extremely natural because: - it uses the same top down algorithm as hand-written parsers - easy to reason about in terms of correctness - easy to reason about in terms of performance - easy to mix with other paradigms - I think it's easier to reason about how to insert good error messages too, though I have to investigate this more. So I think there is a missing design choice. PEGs are kind of coupling lexing and parsing, while you could use a PEG-like algorithm for a top down generated parser only. I believe that is a very practical choice for a lot of systems that use hand coded recursive descent. PEGs are relatively new (2004) so it's not that surprising that the entire design space hasn't been explored yet.
- loup-vaillant 12y ago
  > (despite the fact that his project is bottom-up?) Earley parsers, including Marpa, are at the same time top-down and bottom-up. And in the end it doesn't really matter. What does is the tree construction phase, and that generally ends up being defined in a top-down manner. As a result, Earley parsing feels like top-down parsing that doesn't fail on left-recursion.
igravious 12y ago
This is exactly the question I was going to ask. From playing around with PEG.js though let me tell you that while powerful it is mind-bending stuff. There's a reason why people keep returning to recursive descent, our brains have no problem debugging and grokking it. Still, if somebody out there with the knowledge wants to chime in I'd love to hear where PEG parsers fit into all this...
- loup-vaillant 12y ago
  First, some street cred: I have studied Ometa[1], and implemented a half-working clone[2] in Haskell. At their core, PEGs, or Parsing Expression Grammars, are recursive descent parsers with a nice syntax. A very nice syntax, which can divide your code size by up to 10. There is also a nearly 1:1 mapping between them and monadic parsing (my Haskell half-clone of OMeta is syntax sugar over Parsec). PEGs have two advantages: the ability to have nice error messages, as evidenced by Parsec; and the ability to add context sensitivity. On the other hand, they are general. We can hack them into supporting lookahead and a limited form of left recursion, but that doesn't solve everything. There are still nasty corner cases. This lack of generality didn't help LALR: right recursion is damn useful for describing right associativity, and LALR can't do it. This is why I'm so excited about Earley parsing. It's not too slow, it's fully general (no corner case whatsoever), it can support prioritised choice, context sensitivity, and stellar error messages thanks to the table of partial parses it maintains. We can now combine the power and convenience of PEGs with the generality of Earley parsing. Once that's done, nobody will ever look back to LALR, or even plain old recursive descent —except for really simple tasks. I think Marpa is only the beginning. [1]: https://en.wikipedia.org/wiki/OMeta https://en.wikipedia.org/wiki/OMeta [2]: http://loup-vaillant.fr/projects/metacompilers/ http://loup-vaillant.fr/projects/metacompilers/
  - aredridel 12y ago
    Another downside of PEGs: The language that a union of PEGs parses can reject constructs that the individual languages support.
  - sklogic 12y ago

chubot 12y ago

Yeah I would also like to see how those topics fit in. To me, it is curious that people move from LALR to recursive descent -- i.e. generated bottom-up to manual top-down. It seems like moving to PEGs or ANTLR would be less drastic -- i.e. to generated top-down. That may be a historical thing though, because top-down parser generators seem to have come a lot later (was there anything before ANTLR's predecessors?) I find top down parsers a lot more intuitive and this article seems to say it's not just me (despite the fact that his project is bottom-up?). I think there is some confusion about top down parsers and arithmetic expressions, e.g. left recursion. But it seems much easier to mix top down parsers with other techniques like operator precedence parsing. You can always insert arbitrary code for one of the rule/production functions. I don't believe you can mix LALR with anything else. PEGs are really just a formalization of recursive descent, which I think makes them a very practical choice. I implemented a PEG parsing interpreter awhile ago. What I discovered though is that it's a lot more natural to have a separate traditional lex phase, and use the PEG abstraction (ordered choice with negations) for parsing only. It seems extremely natural because: - it uses the same top down algorithm as hand-written parsers - easy to reason about in terms of correctness - easy to reason about in terms of performance - easy to mix with other paradigms - I think it's easier to reason about how to insert good error messages too, though I have to investigate this more. So I think there is a missing design choice. PEGs are kind of coupling lexing and parsing, while you could use a PEG-like algorithm for a top down generated parser only. I believe that is a very practical choice for a lot of systems that use hand coded recursive descent. PEGs are relatively new (2004) so it's not that surprising that the entire design space hasn't been explored yet.

loup-vaillant 12y ago
> (despite the fact that his project is bottom-up?) Earley parsers, including Marpa, are at the same time top-down and bottom-up. And in the end it doesn't really matter. What does is the tree construction phase, and that generally ends up being defined in a top-down manner. As a result, Earley parsing feels like top-down parsing that doesn't fail on left-recursion.

igravious 12y ago

This is exactly the question I was going to ask. From playing around with PEG.js though let me tell you that while powerful it is mind-bending stuff. There's a reason why people keep returning to recursive descent, our brains have no problem debugging and grokking it. Still, if somebody out there with the knowledge wants to chime in I'd love to hear where PEG parsers fit into all this...

loup-vaillant 12y ago
First, some street cred: I have studied Ometa[1], and implemented a half-working clone[2] in Haskell. At their core, PEGs, or Parsing Expression Grammars, are recursive descent parsers with a nice syntax. A very nice syntax, which can divide your code size by up to 10. There is also a nearly 1:1 mapping between them and monadic parsing (my Haskell half-clone of OMeta is syntax sugar over Parsec). PEGs have two advantages: the ability to have nice error messages, as evidenced by Parsec; and the ability to add context sensitivity. On the other hand, they are general. We can hack them into supporting lookahead and a limited form of left recursion, but that doesn't solve everything. There are still nasty corner cases. This lack of generality didn't help LALR: right recursion is damn useful for describing right associativity, and LALR can't do it. This is why I'm so excited about Earley parsing. It's not too slow, it's fully general (no corner case whatsoever), it can support prioritised choice, context sensitivity, and stellar error messages thanks to the table of partial parses it maintains. We can now combine the power and convenience of PEGs with the generality of Earley parsing. Once that's done, nobody will ever look back to LALR, or even plain old recursive descent —except for really simple tasks. I think Marpa is only the beginning. [1]: https://en.wikipedia.org/wiki/OMeta https://en.wikipedia.org/wiki/OMeta [2]: http://loup-vaillant.fr/projects/metacompilers/ http://loup-vaillant.fr/projects/metacompilers/
- aredridel 12y ago
  Another downside of PEGs: The language that a union of PEGs parses can reject constructs that the individual languages support.
- sklogic 12y ago