4 ms·

Funny, I used to dig into everything about parsing that I could get my grubby fingers on, and now I don't even care anymore. Use recursive descent + TDOP for e

by _0ffh 6y ago

Funny, I used to dig into everything about parsing that I could get my grubby fingers on, and now I don't even care anymore. Use recursive descent + TDOP for expressions!

nly 6y ago
TDOP / Pratt parsing is basically the same as recursive descent, it's just an optimization where rules with the same or lower precedence are matched iteratively rather than recursively. I can't find the link now but I found a great page once where this was shown, and it made all the complexity vanish for me.
- _0ffh 6y ago
  Yeah, the advantage here is that once you wrote your Pratt parser it's a nice, quite generic piece of code that you can just drop into any new project, reconfigure a bit and it does it's job. Don't know what page you mean, but personally I first stumbled upon it on Douglas Crockford's page [1]. A couple of years later Eli Bendersky did a nice writeup for Python [2]. I wrote my first Pratt parser in D, based on Crockford's. It was a learning project that ended up as a Javascript interpreter. I parsed JS into a Lispy syntax tree and added a simple Lisp interpreter based on Norvig's [3]. In the meantime I've switched my default language (to Nim [4]), but I've since never used anything but RD and/or Pratt for any parsing job. [1] https://crockford.com/javascript/tdop/tdop.html https://crockford.com/javascript/tdop/tdop.html [2] https://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing/ https://eli.thegreenplace.net/2010/01/02/top-down-operator-p... [3] https://norvig.com/lispy.html https://norvig.com/lispy.html [4] https://nim-lang.org/ https://nim-lang.org/
  - nly 6y ago
    I found it : https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#more_climbing https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#more_clim... It shows the transformations that get you from recursive descent to table driven precedence climbing Pratt/TDOP and precedence climbing are actually the same algorithm: https://www.oilshell.org/blog/2016/11/01.html https://www.oilshell.org/blog/2016/11/01.html ...so basically everything can be derived from simple, straightforward predictive recursive descent.

by _0ffh 6y ago

Funny, I used to dig into everything about parsing that I could get my grubby fingers on, and now I don't even care anymore. Use recursive descent + TDOP for expressions!

nly 6y ago

TDOP / Pratt parsing is basically the same as recursive descent, it's just an optimization where rules with the same or lower precedence are matched iteratively rather than recursively. I can't find the link now but I found a great page once where this was shown, and it made all the complexity vanish for me.

_0ffh 6y ago
Yeah, the advantage here is that once you wrote your Pratt parser it's a nice, quite generic piece of code that you can just drop into any new project, reconfigure a bit and it does it's job. Don't know what page you mean, but personally I first stumbled upon it on Douglas Crockford's page [1]. A couple of years later Eli Bendersky did a nice writeup for Python [2]. I wrote my first Pratt parser in D, based on Crockford's. It was a learning project that ended up as a Javascript interpreter. I parsed JS into a Lispy syntax tree and added a simple Lisp interpreter based on Norvig's [3]. In the meantime I've switched my default language (to Nim [4]), but I've since never used anything but RD and/or Pratt for any parsing job. [1] https://crockford.com/javascript/tdop/tdop.html https://crockford.com/javascript/tdop/tdop.html [2] https://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing/ https://eli.thegreenplace.net/2010/01/02/top-down-operator-p... [3] https://norvig.com/lispy.html https://norvig.com/lispy.html [4] https://nim-lang.org/ https://nim-lang.org/
- nly 6y ago
  I found it : https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#more_climbing https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#more_clim... It shows the transformations that get you from recursive descent to table driven precedence climbing Pratt/TDOP and precedence climbing are actually the same algorithm: https://www.oilshell.org/blog/2016/11/01.html https://www.oilshell.org/blog/2016/11/01.html ...so basically everything can be derived from simple, straightforward predictive recursive descent.