3 ms·

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

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
  You can also mix PEG (Packrat) with Pratt in an interesting way. Nemerle does this, as well as https://github.com/combinatorylogic/mbase https://github.com/combinatorylogic/mbase And you can do a lot of nice stuff with PEGs, like generating error recovery and sane error messages (thins thought to only be available for handwritten recursive descent), you can auto-generate pretty-printers, formatters, syntax highlighters, etc.
- igravious 12y ago
  Thanks for taking the time to reply, only just checked backed now to see if anyone answered my question. Seems like I'm going to have to do a bit of digging and reading myself. I'm wondering now if any of these parsing strategies exist in some implementation form or another in Javascript-land...
  - loup-vaillant 12y ago
    Ometa is itself written in JavaScript (or rather it meta-compiles itself into JavaScript). Here: http://www.tinlizzie.org/ometa/ http://www.tinlizzie.org/ometa/

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
You can also mix PEG (Packrat) with Pratt in an interesting way. Nemerle does this, as well as https://github.com/combinatorylogic/mbase https://github.com/combinatorylogic/mbase And you can do a lot of nice stuff with PEGs, like generating error recovery and sane error messages (thins thought to only be available for handwritten recursive descent), you can auto-generate pretty-printers, formatters, syntax highlighters, etc.
igravious 12y ago
Thanks for taking the time to reply, only just checked backed now to see if anyone answered my question. Seems like I'm going to have to do a bit of digging and reading myself. I'm wondering now if any of these parsing strategies exist in some implementation form or another in Javascript-land...
- loup-vaillant 12y ago
  Ometa is itself written in JavaScript (or rather it meta-compiles itself into JavaScript). Here: http://www.tinlizzie.org/ometa/ http://www.tinlizzie.org/ometa/