Pratt Parsers: Expression Parsing Made Easy (2011) | Hacker News Reader

Pratt Parsers: Expression Parsing Made Easy (2011)

journal.stuffwithstuff.com

24 pointsraydiatian7 comments

Prior discussions with comments:

https://news.ycombinator.com/item?id=16398830 - 88 points by signa11 on Feb 17, 2018 (12 comments)

https://news.ycombinator.com/item?id=2344837 - 89 points by jashkenas on March 19, 2011 (20 comments)

Oh, thanks. Didn’t realize this was a repost!

HN has been around for a while now, there are always reposts. When I notice one (like this) that also catches my attention I like to track down the prior discussions. And once I've done that, I may as well link to them here.

This just looks like a standard recursive descent parser with ladder climbing for precedence, am I missing something?

No. Precedence climbing is the same algorithm as Pratt parsing with basically just terminology and minor code structure differences: http://www.oilshell.org/blog/2016/11/01.html

The alternative is to lay out your BNF grammar fully, directly encoding precedence and associativity, and then map that to functions to implement. This can be done, but is more of a pain to maintain, and has no real benefit other than more closely matching automata theory.

Oh yeah I know the horror of the full BNF tree - they’re all yacc and bison support the last time I used them for anything

I don't think you are missing anything, but you probably isn't in the intended audience. IMhO, just doing it in plain C would have made the point stronger.

<anecdote alert> A thousand years ago I was reading the legendary SmallC (for Z80) sources and was surprised to find it didn't use this technique (which IIRC is described in the Dragon Book). I rewrote it and it worked (both less source and object code, and faster too).

My point: it might not be as well known as simple recursive descend. That said, it's essentially limited to expression parsing. </anecdote alert>

Reply on news.ycombinator.com