4 ms·

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

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.
    - kragen 3y ago
      thanks, this is very interesting

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.
  - kragen 3y ago
    thanks, this is very interesting