5 ms·

Pratt Parsers: Expression Parsing Made Easy (2011)

24 points by raydiatian 4y ago

Jtsummers 4y ago
Prior discussions with comments: https://news.ycombinator.com/item?id=16398830 https://news.ycombinator.com/item?id=16398830 - 88 points by signa11 on Feb 17, 2018 (12 comments) https://news.ycombinator.com/item?id=2344837 https://news.ycombinator.com/item?id=2344837 - 89 points by jashkenas on March 19, 2011 (20 comments)
- raydiatian 4y ago
  Oh, thanks. Didn’t realize this was a repost!
  - Jtsummers 4y ago
    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.
olliej 4y ago
This just looks like a standard recursive descent parser with ladder climbing for precedence, am I missing something?
- jsmith45 4y ago
  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 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.
  - olliej 4y ago
    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
- FullyFunctional 4y ago
  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>

24 points by raydiatian 4y ago

Prior discussions with comments: https://news.ycombinator.com/item?id=16398830 https://news.ycombinator.com/item?id=16398830 - 88 points by signa11 on Feb 17, 2018 (12 comments) https://news.ycombinator.com/item?id=2344837 https://news.ycombinator.com/item?id=2344837 - 89 points by jashkenas on March 19, 2011 (20 comments)

raydiatian 4y ago
Oh, thanks. Didn’t realize this was a repost!
- Jtsummers 4y ago
  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.

olliej 4y ago

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

jsmith45 4y ago
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 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.
- olliej 4y ago
  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
FullyFunctional 4y ago
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>