Hacker News new | past | comments | ask | show | jobs | submit login

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!




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.


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

[2] https://eli.thegreenplace.net/2010/01/02/top-down-operator-p...

[3] https://norvig.com/lispy.html

[4] https://nim-lang.org/


I found it : 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

...so basically everything can be derived from simple, straightforward predictive recursive descent.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: