15 ms·

Pratt Parsers: Expression Parsing Made Easy (2011)

152 points by memalign 3y ago

zevv 3y ago
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: 1. https://github.com/zevv/npeg#precedence-operators https://github.com/zevv/npeg#precedence-operators
- vidarh 3y ago
  I love that way of embedding precedence tables without the "classic" repetitive EBNF pattern. I will shamelessly steal this for my next parser library. Also, your documentation is outstanding. (tiny typo - "Pratt" is spelled "Prett" in one sentence on your page)
- kragen 3y ago
  did you try warth's left-recursion hack for packrat parsers? i'm curious what your experience was with it if so
throwup238 3y ago
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. 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. 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. [1] https://news.ycombinator.com/item?id=24480504 https://news.ycombinator.com/item?id=24480504 [2] https://github.com/mx-scissortail/WebBS https://github.com/mx-scissortail/WebBS
PartiallyTyped 3y ago
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.
deleted 3y ago
[deleted]
kevindamm 3y ago
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). 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. 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.
- nickpsecurity 3y ago
  sklogic told us here that his strategy was to use two parsers: a fast, generated one by default; a separate one for good, error handling. If using that strategy, then we might be able to build some error handling in as part of the grammar. The generator ignores it for one engine and uses it for another.
  - kevindamm 3y ago
    That's good advice.. it's especially useful in an Earley design because it is much faster when it doesn't have to keep explicit back references for derivation, but those references are needed for explaining the current context. Adding a switch for keeping/discarding history (and a compiler pass for whether or not to fold the epsilon-DFA into collapsed states, "NNF" style) would automate the fast-vs-slow|informative variants. Add in some debug-only output in postprocessors and it wouldn't really need any syntactical changes to the parser generator. I may try this soon..
- danybittel 3y ago
  I've been working on a parser that parses while typing and gives type and syntax errors as soon as possible but never any false positives. I didn't expect it to be that difficult. I still haven't really grokked it and any bugfix usually ends in a game of whack a mole over integration tests. Any hints?
timhh 3y ago
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. 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). Here's what I ended up with: https://github.com/Timmmm/expr https://github.com/Timmmm/expr 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).
- secondcoming 3y ago
  There is Boost.Spirit. We use it but I find its cleverness just results in incomprehensible code. https://www.boost.org/doc/libs/1_84_0/libs/spirit/classic/doc/introduction.html https://www.boost.org/doc/libs/1_84_0/libs/spirit/classic/do...
  - timhh 3y ago
    Ah yeah I should have said "a library for which the integration is easier than writing my own library from scratch"!
  - amag 3y ago
    Last I used it, even pretty small grammars took forever to build. I had to be very diligent not to let the grammar cpp-file depend on anything else in my codebase.
  - nly 3y ago
    It wouldn't be efficient for expression parsing. Spirit is a recursive descent parser.
- mgaunard 3y ago
azhenley 3y ago
Eli Bendersky also has a nice post on Pratt parsing from 2010. I used both of these when implementing it for the first time. https://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing https://eli.thegreenplace.net/2010/01/02/top-down-operator-p...
- lioeters 3y ago
  Some time ago I went down a fascinating rabbit hole on Pratt parsers while writing a math expression evaluator. In addition to the OP and above-linked article, I found the following helpful. - How Desmos Uses Pratt Parsers (2018) - TypeScript - https://engineering.desmos.com/articles/pratt-parser/ https://engineering.desmos.com/articles/pratt-parser/ - Source: https://github.com/desmosinc/pratt-parser-blog-code https://github.com/desmosinc/pratt-parser-blog-code - Simple But Powerful Pratt Parsing (2020) - Rust - https://matklad.github.io/2020/04/13/simple-but-powerful-pra https://matklad.github.io/2020/04/13/simple-but-powerful-pra... - Source: https://github.com/matklad/minipratt https://github.com/matklad/minipratt
mgaunard 3y ago
Isn't this just the traditional way to parse infix operators with LL parsers, which are commonplace?
- vidarh 3y ago
  It's commonplace, and one of a few very closely related algorithms (Pratt/TDOP, precedence climbing, shunting yard, etc.) that I guess you can call "traditional", but outside of people who regularly write parsers people are still often unaware of it. Not least, I suspect, because while the pattern is obvious once you know it, a lot of people will implement their parser from looking at a (E)BNF representation that doesn't make it explicit. E.g. this is a small subset of Oberon 07's grammar: expression = SimpleExpression [relation SimpleExpression]. relation = "=" | "#" | "<" | "<=" | ">" | ">=" | IN | IS. SimpleExpression = ["+"|"−"] term {AddOperator term}. AddOperator = "+" | "−" | OR. term = factor {MulOperator factor}. MulOperator = "*" | "/" | DIV | MOD | "&" . When you know any of the precedence parser techniques and how to map a grammar to it, it's instantly obvious that this is modeling precedence rules, and it's trivial to turn it straight into a table, but if you've never written a parser before, isn't familiar with the theory, and just about figured out how to read EBNF, it's a lot easier to stumble your way to a working recursive descent parser than figuring out to generalize the grammar fragment above into reusable functions and a precedence table.
chubot 3y ago
FWIW this survey links to ~10 articles on Pratt Parsing, including the featured article - https://www.oilshell.org/blog/2017/03/31.html https://www.oilshell.org/blog/2017/03/31.html - Pratt Parsing Index and Updates I wrote it several years ago and updated it recently (probably should give it a better title) The later articles are in TypeScript, Rust, Elm
gsliepen 3y ago
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. 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.
- vidarh 3y ago
  I have parsed a whole language using a precedence-based approach before - the first time I wrote a precedence-based parser. It very easily slips away from you and ends up a maddening mess of extra rules and flags (and I keep making that mistake, to be honest, because the conceptual simplicity of a precedence-based parser - be it Pratt or shunting-yard or variations - is seductive), unless you remember that you can easily "mode-shift" between different methods. E.g. "escaping" out from a Pratt parser to recursive descent (or anything else) for a sub-expression that is sufficiently messy to make it painful to model with precedence tables is fairly simple. It's worth keeping in mind (for myself too...) if your main parsing function and/or precedence table starts becoming too complex.
  - kragen 3y ago
    i feel like maybe this is messier if the parser you're trying to escape from is lalr or something else bottom-up?
    - vidarh 3y ago
      It really depends on how easy it is to determine the handover points. If the grammar gives you clear, unambiguous boundaries that don't require much context to determine when to switch, you should be able to switch reasonably easily almost no matter the grammar type. I agree it's easier to apply this top-down, though - you just call into the other parser and get whatever subexpression back, and you "just" need to have it treat tokens that can't continue an expression as the end of the stream. E.g. a trivial top down example would be any language where IF/ELSE is not an expression - you might parser IF (condition), then call into a Pratt parser, treat "ELSE" or "END" as terminating the expression, and just continue. Bottom-up you can still handle grammars that unambiguous fairly easily if the delimiting tokens aren't valid in other contexts, but I suspect you're right you'll get into trouble more easily if the grammars are more complex.
kerkeslager 3y ago
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]. 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]. Most 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!). [1] https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html https://matklad.github.io/2020/04/13/simple-but-powerful-pra... [2] https://github.com/kerkeslager/fur/blob/main/parser.c https://github.com/kerkeslager/fur/blob/main/parser.c [3] https://craftinginterpreters.com/compiling-expressions.html#design-note https://craftinginterpreters.com/compiling-expressions.html#...
- GloomyBoots 3y ago
  Maybe in this case it should be spelled yacc shaving.
  - kerkeslager 3y ago
    As a pun enthusiast I'd like to express my appreciation for this. :D
- norir 3y ago
  I don't know. This is becoming conventional wisdom but I think a reverse argument is equally true: aspiring language designers get too bogged down in bytecode generation or gc that they are unable to make a compelling language that adequately differentiates itself from existing languages that already do those things well. Are you actually claiming that handwriting a recursive descent parser for most popular languages can be done in afternoon? Unless the language is a lisp, I find that unlikely in most cases. You can write a parser generator that generates a recursive descent parser. Writing the grammar will almost surely be significantly faster in the parser generator dsl than a handrolled recursive descent parser. To improve your language design skills, you need to design multiple languages. Parser generators will get you a prototype faster and allow you to explore the language design space. You can target a high level language to do the hard parts. Once you are satisfied with a language, then maybe it makes sense to design your own custom bytecode or gc to solve its unique problems. I do agree though that optimizing parsing at an early stage makes no sense and many do get bogged down there.
lichtenberger 3y ago
The technique is also described in the awesome book "Crafting Interpreters" by Robert Nystrom.
- reichstein 3y ago
  Which is probably not a coincidence, since the article was written by the same Robert Nystrom.
  - pdpi 3y ago
    I saw the title and it reminded me that I wanted to work through that book. Was thoroughly unsurprised when I clicked through and saw his face.
o11c 3y ago
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. 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.
- ReleaseCandidat 3y ago
  > anything but the simplest precedence rules. For example, if unary `NOT` has a weaker precedence than other unary operators Unary operátors use precedence levels (binding powers) too, they are no different (regarding the existence of precedence levels) from infix functions. This is just a simplification of the precedence table in the linked article (which I haven't read). > or if `a < b < c` is to be treated differently than `(a < b) < c` If you want "<" to be right associative, that's exactly one of the things that's easy to do with a Pratt parser, change the binding power on one side for the "<". > if you want to forbid bitwise operators mixing with relationals I don't know how using a Pratt parser would interfere with throwing an error?
  - orthoxerox 3y ago
    > If you want "<" to be right associative, that's exactly one of the things that's easy to do with a Pratt parser, change the binding power on one side for the "<". It's not about associativity at all. "a < b < c" is a ternary operator that compares three operands.
    - ReleaseCandidat 3y ago
      That's what I would think too (as it doesn't make much sense to compare a boolean to c), but what OP wrote doesn't make much sense else: or if `a < b < c` is to be treated differently than `(a < b) < c`
professoretc 3y ago
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."
dang 3y ago
Related: Pratt Parsers: Expression Parsing Made Easy (2011) - https://news.ycombinator.com/item?id=32125386 https://news.ycombinator.com/item?id=32125386 - July 2022 (7 comments) Pratt Parsers: Expression Parsing Made Easy (2011) - https://news.ycombinator.com/item?id=16398830 https://news.ycombinator.com/item?id=16398830 - Feb 2018 (12 comments) Pratt Parsers: Expression Parsing Made Easy - https://news.ycombinator.com/item?id=2344837 https://news.ycombinator.com/item?id=2344837 - March 2011 (20 comments)
justinpombrio 3y ago
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. https://github.com/justinpombrio/panfix https://github.com/justinpombrio/panfix
gnufx 3y ago
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.
- vidarh 3y ago
  You mean "f x y" instead of e.g. "f(x,y)"? You can generalize that into handling operators of various arity both before and after the operator. E.g. I once had a parser that would handle "x op y z". I don't recall why - it was 30+ years ago, but I can back up that it's a fairly simple modification to expand precedence based parsers this way.
andreif 3y ago
Jonathan Blow just did a stream on parsers and how to make them easier https://www.twitch.tv/videos/2024681994?t=00h11m50s https://www.twitch.tv/videos/2024681994?t=00h11m50s

152 points by memalign 3y ago

zevv 3y ago

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: 1. https://github.com/zevv/npeg#precedence-operators https://github.com/zevv/npeg#precedence-operators

vidarh 3y ago
I love that way of embedding precedence tables without the "classic" repetitive EBNF pattern. I will shamelessly steal this for my next parser library. Also, your documentation is outstanding. (tiny typo - "Pratt" is spelled "Prett" in one sentence on your page)
kragen 3y ago
did you try warth's left-recursion hack for packrat parsers? i'm curious what your experience was with it if so

throwup238 3y ago

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. 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. 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. [1] https://news.ycombinator.com/item?id=24480504 https://news.ycombinator.com/item?id=24480504 [2] https://github.com/mx-scissortail/WebBS https://github.com/mx-scissortail/WebBS

PartiallyTyped 3y ago

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.

deleted 3y ago

[deleted]

kevindamm 3y ago

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). 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. 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.

nickpsecurity 3y ago
sklogic told us here that his strategy was to use two parsers: a fast, generated one by default; a separate one for good, error handling. If using that strategy, then we might be able to build some error handling in as part of the grammar. The generator ignores it for one engine and uses it for another.
- kevindamm 3y ago
  That's good advice.. it's especially useful in an Earley design because it is much faster when it doesn't have to keep explicit back references for derivation, but those references are needed for explaining the current context. Adding a switch for keeping/discarding history (and a compiler pass for whether or not to fold the epsilon-DFA into collapsed states, "NNF" style) would automate the fast-vs-slow|informative variants. Add in some debug-only output in postprocessors and it wouldn't really need any syntactical changes to the parser generator. I may try this soon..
danybittel 3y ago
I've been working on a parser that parses while typing and gives type and syntax errors as soon as possible but never any false positives. I didn't expect it to be that difficult. I still haven't really grokked it and any bugfix usually ends in a game of whack a mole over integration tests. Any hints?

timhh 3y ago

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. 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). Here's what I ended up with: https://github.com/Timmmm/expr https://github.com/Timmmm/expr 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).

secondcoming 3y ago
There is Boost.Spirit. We use it but I find its cleverness just results in incomprehensible code. https://www.boost.org/doc/libs/1_84_0/libs/spirit/classic/doc/introduction.html https://www.boost.org/doc/libs/1_84_0/libs/spirit/classic/do...
- timhh 3y ago
  Ah yeah I should have said "a library for which the integration is easier than writing my own library from scratch"!
- amag 3y ago
  Last I used it, even pretty small grammars took forever to build. I had to be very diligent not to let the grammar cpp-file depend on anything else in my codebase.
- nly 3y ago
  It wouldn't be efficient for expression parsing. Spirit is a recursive descent parser.
mgaunard 3y ago

azhenley 3y ago

Eli Bendersky also has a nice post on Pratt parsing from 2010. I used both of these when implementing it for the first time. https://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing https://eli.thegreenplace.net/2010/01/02/top-down-operator-p...

lioeters 3y ago
Some time ago I went down a fascinating rabbit hole on Pratt parsers while writing a math expression evaluator. In addition to the OP and above-linked article, I found the following helpful. - How Desmos Uses Pratt Parsers (2018) - TypeScript - https://engineering.desmos.com/articles/pratt-parser/ https://engineering.desmos.com/articles/pratt-parser/ - Source: https://github.com/desmosinc/pratt-parser-blog-code https://github.com/desmosinc/pratt-parser-blog-code - Simple But Powerful Pratt Parsing (2020) - Rust - https://matklad.github.io/2020/04/13/simple-but-powerful-pra https://matklad.github.io/2020/04/13/simple-but-powerful-pra... - Source: https://github.com/matklad/minipratt https://github.com/matklad/minipratt

mgaunard 3y ago

Isn't this just the traditional way to parse infix operators with LL parsers, which are commonplace?

vidarh 3y ago
It's commonplace, and one of a few very closely related algorithms (Pratt/TDOP, precedence climbing, shunting yard, etc.) that I guess you can call "traditional", but outside of people who regularly write parsers people are still often unaware of it. Not least, I suspect, because while the pattern is obvious once you know it, a lot of people will implement their parser from looking at a (E)BNF representation that doesn't make it explicit. E.g. this is a small subset of Oberon 07's grammar: expression = SimpleExpression [relation SimpleExpression]. relation = "=" | "#" | "<" | "<=" | ">" | ">=" | IN | IS. SimpleExpression = ["+"|"−"] term {AddOperator term}. AddOperator = "+" | "−" | OR. term = factor {MulOperator factor}. MulOperator = "*" | "/" | DIV | MOD | "&" . When you know any of the precedence parser techniques and how to map a grammar to it, it's instantly obvious that this is modeling precedence rules, and it's trivial to turn it straight into a table, but if you've never written a parser before, isn't familiar with the theory, and just about figured out how to read EBNF, it's a lot easier to stumble your way to a working recursive descent parser than figuring out to generalize the grammar fragment above into reusable functions and a precedence table.

chubot 3y ago

FWIW this survey links to ~10 articles on Pratt Parsing, including the featured article - https://www.oilshell.org/blog/2017/03/31.html https://www.oilshell.org/blog/2017/03/31.html - Pratt Parsing Index and Updates I wrote it several years ago and updated it recently (probably should give it a better title) The later articles are in TypeScript, Rust, Elm

gsliepen 3y ago

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. 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.

vidarh 3y ago
I have parsed a whole language using a precedence-based approach before - the first time I wrote a precedence-based parser. It very easily slips away from you and ends up a maddening mess of extra rules and flags (and I keep making that mistake, to be honest, because the conceptual simplicity of a precedence-based parser - be it Pratt or shunting-yard or variations - is seductive), unless you remember that you can easily "mode-shift" between different methods. E.g. "escaping" out from a Pratt parser to recursive descent (or anything else) for a sub-expression that is sufficiently messy to make it painful to model with precedence tables is fairly simple. It's worth keeping in mind (for myself too...) if your main parsing function and/or precedence table starts becoming too complex.
- kragen 3y ago
  i feel like maybe this is messier if the parser you're trying to escape from is lalr or something else bottom-up?
  - vidarh 3y ago
    It really depends on how easy it is to determine the handover points. If the grammar gives you clear, unambiguous boundaries that don't require much context to determine when to switch, you should be able to switch reasonably easily almost no matter the grammar type. I agree it's easier to apply this top-down, though - you just call into the other parser and get whatever subexpression back, and you "just" need to have it treat tokens that can't continue an expression as the end of the stream. E.g. a trivial top down example would be any language where IF/ELSE is not an expression - you might parser IF (condition), then call into a Pratt parser, treat "ELSE" or "END" as terminating the expression, and just continue. Bottom-up you can still handle grammars that unambiguous fairly easily if the delimiting tokens aren't valid in other contexts, but I suspect you're right you'll get into trouble more easily if the grammars are more complex.

kerkeslager 3y ago

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]. 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]. Most 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!). [1] https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html https://matklad.github.io/2020/04/13/simple-but-powerful-pra... [2] https://github.com/kerkeslager/fur/blob/main/parser.c https://github.com/kerkeslager/fur/blob/main/parser.c [3] https://craftinginterpreters.com/compiling-expressions.html#design-note https://craftinginterpreters.com/compiling-expressions.html#...

GloomyBoots 3y ago
Maybe in this case it should be spelled yacc shaving.
- kerkeslager 3y ago
  As a pun enthusiast I'd like to express my appreciation for this. :D
norir 3y ago
I don't know. This is becoming conventional wisdom but I think a reverse argument is equally true: aspiring language designers get too bogged down in bytecode generation or gc that they are unable to make a compelling language that adequately differentiates itself from existing languages that already do those things well. Are you actually claiming that handwriting a recursive descent parser for most popular languages can be done in afternoon? Unless the language is a lisp, I find that unlikely in most cases. You can write a parser generator that generates a recursive descent parser. Writing the grammar will almost surely be significantly faster in the parser generator dsl than a handrolled recursive descent parser. To improve your language design skills, you need to design multiple languages. Parser generators will get you a prototype faster and allow you to explore the language design space. You can target a high level language to do the hard parts. Once you are satisfied with a language, then maybe it makes sense to design your own custom bytecode or gc to solve its unique problems. I do agree though that optimizing parsing at an early stage makes no sense and many do get bogged down there.

lichtenberger 3y ago

The technique is also described in the awesome book "Crafting Interpreters" by Robert Nystrom.

reichstein 3y ago
Which is probably not a coincidence, since the article was written by the same Robert Nystrom.
- pdpi 3y ago
  I saw the title and it reminded me that I wanted to work through that book. Was thoroughly unsurprised when I clicked through and saw his face.

o11c 3y ago

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. 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.

ReleaseCandidat 3y ago
> anything but the simplest precedence rules. For example, if unary `NOT` has a weaker precedence than other unary operators Unary operátors use precedence levels (binding powers) too, they are no different (regarding the existence of precedence levels) from infix functions. This is just a simplification of the precedence table in the linked article (which I haven't read). > or if `a < b < c` is to be treated differently than `(a < b) < c` If you want "<" to be right associative, that's exactly one of the things that's easy to do with a Pratt parser, change the binding power on one side for the "<". > if you want to forbid bitwise operators mixing with relationals I don't know how using a Pratt parser would interfere with throwing an error?
- orthoxerox 3y ago
  > If you want "<" to be right associative, that's exactly one of the things that's easy to do with a Pratt parser, change the binding power on one side for the "<". It's not about associativity at all. "a < b < c" is a ternary operator that compares three operands.
  - ReleaseCandidat 3y ago
    That's what I would think too (as it doesn't make much sense to compare a boolean to c), but what OP wrote doesn't make much sense else: or if `a < b < c` is to be treated differently than `(a < b) < c`

professoretc 3y ago

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."

dang 3y ago

Related: Pratt Parsers: Expression Parsing Made Easy (2011) - https://news.ycombinator.com/item?id=32125386 https://news.ycombinator.com/item?id=32125386 - July 2022 (7 comments) Pratt Parsers: Expression Parsing Made Easy (2011) - https://news.ycombinator.com/item?id=16398830 https://news.ycombinator.com/item?id=16398830 - Feb 2018 (12 comments) Pratt Parsers: Expression Parsing Made Easy - https://news.ycombinator.com/item?id=2344837 https://news.ycombinator.com/item?id=2344837 - March 2011 (20 comments)

justinpombrio 3y ago

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. https://github.com/justinpombrio/panfix https://github.com/justinpombrio/panfix

gnufx 3y ago

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.

vidarh 3y ago
You mean "f x y" instead of e.g. "f(x,y)"? You can generalize that into handling operators of various arity both before and after the operator. E.g. I once had a parser that would handle "x op y z". I don't recall why - it was 30+ years ago, but I can back up that it's a fairly simple modification to expand precedence based parsers this way.

andreif 3y ago

Jonathan Blow just did a stream on parsers and how to make them easier https://www.twitch.tv/videos/2024681994?t=00h11m50s https://www.twitch.tv/videos/2024681994?t=00h11m50s