3 ms·

Those interested may find Pratt parsing compelling, it is easy to implement and works well for hobby parsers (production quality error messaging tends to requir

by jakear 4y ago

Those interested may find Pratt parsing compelling, it is easy to implement and works well for hobby parsers (production quality error messaging tends to require custom code). As an example here’s a quick and dirty expression evaluator I made a whole back that supports D&D-style die roll codes as literals/first class variables: https://github.com/JacksonKearl/RollDice-Discord https://github.com/JacksonKearl/RollDice-Discord http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e... https://github.com/JacksonKearl/PrattParse https://github.com/JacksonKearl/PrattParse

lioeters 4y ago
I'm a fan of Pratt parsers too. In addition to the article by @munificent you linked above, I found the following helpful. - How Desmos Uses Pratt Parsers (2018) - TypeScript - https://engineering.desmos.com/articles/pratt-parser/ https://engineering.desmos.com/articles/pratt-parser/ - Source: https://github.com/desmosinc/pratt-parser-blog-code https://github.com/desmosinc/pratt-parser-blog-code - Simple But Powerful Pratt Parsing (2020) - Rust - https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html https://matklad.github.io/2020/04/13/simple-but-powerful-pra... - Source: https://github.com/matklad/minipratt https://github.com/matklad/minipratt
userbinator 4y ago
I believe Pratt, TDOP, and precedence climbing are all just different names for the same technique that involves comparing precedences in a loop. The fact that it's basic principle is so simple is probably what lead to multiple independent reinventions. If anything, after reading about the aforementioned algorithms, the technique in the article seems to show that using parser combinators is a lot of work for very little gain --- I've read much shorter articles on recursive descent, and those do handle precedence correctly.
- jakear 4y ago
  What is your complaint re precedence in Pratt parsing? The linked code properly implements precedence fairly trivially.
  - userbinator 4y ago
    I think you misunderstood. I'm referring to the original article of this item, not your linked code.
    - jakear 4y ago
      That’s more a critique of the author than the concept - I gave up midway through the article but order combinators remain a useful tool, particularly as a library. To my eyes, the logic here https://github.com/JacksonKearl/RollDice-Discord/blob/master/src/dice-bot.ts https://github.com/JacksonKearl/RollDice-Discord/blob/master... is much simpler than the equivalent recursive descent code would be. I’d be interested in an article comparing them in greater detail.

by jakear 4y ago

lioeters 4y ago

I'm a fan of Pratt parsers too. In addition to the article by @munificent you linked above, I found the following helpful. - How Desmos Uses Pratt Parsers (2018) - TypeScript - https://engineering.desmos.com/articles/pratt-parser/ https://engineering.desmos.com/articles/pratt-parser/ - Source: https://github.com/desmosinc/pratt-parser-blog-code https://github.com/desmosinc/pratt-parser-blog-code - Simple But Powerful Pratt Parsing (2020) - Rust - https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html https://matklad.github.io/2020/04/13/simple-but-powerful-pra... - Source: https://github.com/matklad/minipratt https://github.com/matklad/minipratt

userbinator 4y ago

I believe Pratt, TDOP, and precedence climbing are all just different names for the same technique that involves comparing precedences in a loop. The fact that it's basic principle is so simple is probably what lead to multiple independent reinventions. If anything, after reading about the aforementioned algorithms, the technique in the article seems to show that using parser combinators is a lot of work for very little gain --- I've read much shorter articles on recursive descent, and those do handle precedence correctly.

jakear 4y ago
What is your complaint re precedence in Pratt parsing? The linked code properly implements precedence fairly trivially.
- userbinator 4y ago
  I think you misunderstood. I'm referring to the original article of this item, not your linked code.
  - jakear 4y ago
    That’s more a critique of the author than the concept - I gave up midway through the article but order combinators remain a useful tool, particularly as a library. To my eyes, the logic here https://github.com/JacksonKearl/RollDice-Discord/blob/master/src/dice-bot.ts https://github.com/JacksonKearl/RollDice-Discord/blob/master... is much simpler than the equivalent recursive descent code would be. I’d be interested in an article comparing them in greater detail.