I had to write an expression parser recently and found the number of names for essentially the same algorithm very confusing. There's Pratt parsing, precedence climbing, and shunting yard. But really they're all the same algorithm.<p>Pratt parsing and precedence climbing are the same except one merges left/right associativity precedence into a single precedence table (which makes way more sense). Shunting yard is the same as the others except it's iterative instead of recursive, and it seems like common implementations omit some syntax checking (but there's no reason you have to omit it).<p>Here's what I ended up with:<p><a href="https://github.com/Timmmm/expr">https://github.com/Timmmm/expr</a><p>I had to write that because somewhat surprisingly I couldn't find an expression parser library that supports 64-bit integers and bools. Almost all of them only do floats. Also I needed it in C++ - that library was a prototype that I later translated into C++ (easier to write in Rust and then translate).
FWIW this survey links to ~10 articles on Pratt Parsing, including the featured article -<p><a href="https://www.oilshell.org/blog/2017/03/31.html" rel="nofollow">https://www.oilshell.org/blog/2017/03/31.html</a> - <i>Pratt Parsing Index and Updates</i><p>I wrote it several years ago and updated it recently (probably should give it a better title)<p>The later articles are in TypeScript, Rust, Elm
Ha, nice to see this on HN: this article was pretty helpful to me to understand the concept a few years back when extending my PEG parsing library [1] with a Pratt parser; this mitigates the problem of PEG parsers not allowing left recursion and allows for a much more concise notation of grammars with operator precedence. Thank you Bob:<p>1. <a href="https://github.com/zevv/npeg#precedence-operators">https://github.com/zevv/npeg#precedence-operators</a>
Pratt or TDOP parsers are my favorite design when coding the parser directly in a host language, with parser combinators a close second (but it edges ahead depending on the host language).<p>But when it comes to writing a larger parser with many production rules, I'd rather use a parser generator based around an Earley parser. You can split production rules and organize their post-processing into an AST a lot easier .. but providing good error statements is still a bit of a hassle.<p>I haven't found a parser generator that makes it painless to provide good error messages. Writing the parser directly in the host language has always been much easier in that regard.
A few years back I had to implement a new parser for a custom expression language to replace an old parser that didn’t give very good errors and was hard to extend. I never did the traditional CS track so parsers were kind of mysterious black magic so naturally first thing I did was search HN.<p>I stumbled on an older parsing thread [1] with a link to a toy Pratt implementation [2] made by an HNer… and shamelessly ripped it off to write my own production Pratt parser implementation.<p>Great success! Writing a Pratt parser by hand is a lot easier than I thought and like the comment says, adding type information was trivial.<p>[1] <a href="https://news.ycombinator.com/item?id=24480504">https://news.ycombinator.com/item?id=24480504</a><p>[2] <a href="https://github.com/mx-scissortail/WebBS">https://github.com/mx-scissortail/WebBS</a>
I met Vaughan Pratt at a math seminar a few years back, where he was talking about his current interest, Chu spaces. While we were waiting in line to get coffee, with the coffee stations labeled "regular" and "decaf", Pratt said, "But where's the context-free coffee?" and then laughed at his own joke. Later at lunch he was telling us about a physics experiment he set up in his pool shed; "My wife told me to do it in the pool shed so that if it explodes it won't destroy the house."
I recently have implemented a Pratt parser for a language prototype. I initially looked at several parser generators, but while they are easier for writing down the grammar of your language, you need to do a lot of work to make them actually spit out working code that integrates well with your project. A Pratt parser can be implemented with just a few tens of lines of code in whatever language of your choice. You just have to mentally switch from thinking of your grammar in terms of production rules to thinking in terms of operators. For example, "if" becomes a prefix (nud) operator, and for function calls, the opening parenthesis after a function name becomes a binary (led) operator.<p>One issue I have with the tutorials for writing Pratt parsers is that they usually only describe how to parse simple and very regular expressions. You can still use Pratt parsers to parse much more complicated programming languages, but this requires a bit more work and some modifications to the main parsing function.
I found this Rust tutorial[1] on Pratt parsers to be really easy to follow as well. I'm not a Rustacean but I didn't find not knowing Rust to be a barrier. I used that as a guide to write the parser for my experimental programming language Fur[2].<p>However, I'll caution anyone writing their own programming languages to read some wisdom from someone who has written a production-quality programming language[3]. <i>Most</i> programming language developers get bogged down in writing the parser and never even get into solving the real hard problems of language development, which are things like bytecode generation and garbage collection. The fact is, a naive recursive descent parser with some low lookahead number to handle left recursion will be performant and can be written in an afternoon for 99% of parsable languages. I'm not sure what it is about parsers that makes them susceptible to yak shaving, but it seems to be a trap a lot of people fall into (including myself!).<p>[1] <a href="https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html" rel="nofollow">https://matklad.github.io/2020/04/13/simple-but-powerful-pra...</a><p>[2] <a href="https://github.com/kerkeslager/fur/blob/main/parser.c">https://github.com/kerkeslager/fur/blob/main/parser.c</a><p>[3] <a href="https://craftinginterpreters.com/compiling-expressions.html#design-note" rel="nofollow">https://craftinginterpreters.com/compiling-expressions.html#...</a>
These are certainly useful, but there's the major caveat that the "easy" stops when you have anything but the simplest precedence rules. For example, if unary `NOT` has a weaker precedence than other unary operators, or if `a < b < c` is to be treated differently than `(a < b) < c`, or if you want to forbid bitwise operators mixing with relationals to avoid confusion from fact that they have a different precedence in C (for historical reasons) than in many other languages.<p>Note also that Bison with precedence tags is more efficient than writing out the same grammar without precedence. And `bison --xml` lets you run the (trivial) machine yourself so you can do it in any language.
An interesting variant of Pratt which I haven't seen elsewhere, and should have written up, is to allow application as juxtaposition, i.e. shell command-like syntax rather than FORTRAN-like. I don't remember the code, but it was a simple mod. Long ago, that plus (inefficient) combinators straight out of Burge gave me a quick prototype of an alternative Scheme reader intended for interactive use inspired by Haskell syntax. S-expressions could still be used as a natural part of the syntax. I guess there's something like that for Racket now.
This is always a nice read. I was going through Bob's interpreter book and I wanted a more complete or interesting parser. This is a very nice addition to that.
I wrote a parser library based on (slightly extended) Pratt parsing. It's a nice, different location in the design space of parsers. Very declarative, and it allows having great error messages out of the box.<p><a href="https://github.com/justinpombrio/panfix">https://github.com/justinpombrio/panfix</a>
Eli Bendersky also has a nice post on Pratt parsing from 2010. I used both of these when implementing it for the first time.<p><a href="https://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing" rel="nofollow">https://eli.thegreenplace.net/2010/01/02/top-down-operator-p...</a>
Jonathan Blow just did a stream on parsers and how to make them easier <a href="https://www.twitch.tv/videos/2024681994?t=00h11m50s" rel="nofollow">https://www.twitch.tv/videos/2024681994?t=00h11m50s</a>