7 ms·
Pratt Parsers: Expression Parsing Made Easy (2011)
- DonHopkins 9y agoVaughan Pratt also designed the Sun logo (an ambigram). But his original design was square, then John Gage rotated it 45 degrees. https://en.wikipedia.org/wiki/Vaughan_Pratt https://en.wikipedia.org/wiki/Vaughan_Pratt https://en.wikipedia.org/wiki/John_Gage https://en.wikipedia.org/wiki/John_Gage https://orig00.deviantart.net/e290/f/2011/230/2/c/sun_microsystems_logo_icon_by_mahesh69a-d4731ca.png https://orig00.deviantart.net/e290/f/2011/230/2/c/sun_micros...
- jlesk 9y agoDouglas Crockford also has a good article on how to implement Pratt parsing in JavaScript: https://crockford.com/javascript/tdop/tdop.html https://crockford.com/javascript/tdop/tdop.html I referenced it often when I implemented THT. (https://tht.help https://tht.help)
- chubot 9y agoFWIW I review the original article and this one here: http://www.oilshell.org/blog/2016/11/02.html http://www.oilshell.org/blog/2016/11/02.html Index of posts about expression parsing: http://www.oilshell.org/blog/2017/03/31.html http://www.oilshell.org/blog/2017/03/31.html
- jules 9y agoA great article! Here's another one that's a bit shorter: https://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing https://eli.thegreenplace.net/2010/01/02/top-down-operator-p...
- chubot 9y agoFWIW I review the original article and this one here: http://www.oilshell.org/blog/2016/11/02.html http://www.oilshell.org/blog/2016/11/02.html Index of posts about expression parsing: http://www.oilshell.org/blog/2017/03/31.html http://www.oilshell.org/blog/2017/03/31.html
- gnufx 9y agoGood point about "if you can do it in Java"... There's a "reprint" of Pratt's paper (of unclear copyright status) at <https://tdop.github.io/> https://tdop.github.io/>. Classic examples are his CGOL syntax for Lisp <https://people.eecs.berkeley.edu/~fateman/cgol/cgol.1> https://people.eecs.berkeley.edu/~fateman/cgol/cgol.1> and Carrette's alternative reader for SIOD as a simpleer example <https://github.com/gjcarrette/siod/tree/master/winsiod> https://github.com/gjcarrette/siod/tree/master/winsiod>. I used a variant long ago to implement a command line syntax for Scheme as an extension language. You can modify the dispatch so that juxtaposition acts as application (a pseudo operator with very low precedence) rather than raising an error. That allows mixfix or fully parenthesized forms interchangeably -- possibly with caveats I don't remember -- e.g. foo 2*bar*i; baz probably used at the REPL, reading as the form (begin (foo (* 2 bar i)) (baz)) you'd probably use in scripts.
- Sharlin 9y agoI’m on the move so can’t take a closer look right now but I wonder how this relates to precedence-climbing parsers: https://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing https://eli.thegreenplace.net/2012/08/02/parsing-expressions...
- krishanath 9y agoHere's an expression parser, written in C#, that also has the ability to execute the parse tree: https://github.com/Rajeev-K/formula-parser https://github.com/Rajeev-K/formula-parser
- dukoid 9y agoHere is one written in Java: https://github.com/stefanhaustein/expressionparser https://github.com/stefanhaustein/expressionparser In addition to a simple math expression evaluator, examples include a BASIC interpreter and a simple computer algebra system O:)
- jopsen 9y agoI recently needed a custom expression language and using a Pratt-Parser to write the interpreter was a joy. https://github.com/taskcluster/json-e/blob/a0ab770157a5fdb5d2adfa5f211e57aefb7b800f/src/interpreter.js#L323-L357 https://github.com/taskcluster/json-e/blob/a0ab770157a5fdb5d... I wrote up abstractions so you just declare token patterns, precedence ordering of tokens, and infix/prefix rules as mapping from token to function(token, ctx). Where ctx.attempt(...token)), ctx.require(...token) and ctx.parse(precedence) is all you need to implement almost anything. I didn't get as far as to make it recursive and support multiple grammars. But I'm sure this concept can be made very elegant, without too many tricks.