Anikki
3 posts
|
#14558
"Cheating" on Day 2 with a Pratt parser 1 month, 1 week ago Edited by on March 17, 2018, 3:38 a.m. Reason: Initial post
I think this is a very simple way of parsing expressions. It's called a Pratt parser. Changing the associativity of the binary operators is as simple as subtracting 1.
|
pervognsen
Per Vognsen 37 posts
1 project
|
#14560
"Cheating" on Day 2 with a Pratt parser 1 month, 1 week ago Edited by Per Vognsen on March 17, 2018, 5:41 a.m.
Yeah, Pratt parsing is neat and easy to code, but most people couldn't have invented it from scratch. The nice thing about precedence climbing is that it's intuitive enough that many people can invent (and have invented) it on their own, and it doesn't require a different mental model from the rest of your recursive-descent parser. If you do the "make it table driven" exercise from day 2, you'll also see the code compresses down heavily and becomes generic by a straightforward parameterization and refactoring of your existing code. The sequence leading up to the table-driven refactoring is intended as a guided exercise culminating in inventing a "name brand" computer science algorithm on your own that would have been non-obvious or opaque if it had just been sprung on you fully formed. I encourage you to try it out and see for yourself even if you know other techniques like Pratt parsing or Dijkstra's shunting yard algorithm.
|