11 ms·

Intuiting Pratt Parsing

169 points by signa11 7mo ago

logdahl 7mo ago
Love Pratt parsing! Not a compiler guy, but I've spent way too many hours reflecting on parsing. I remember trying to get though the dragon book so many times and reading all about formal grammar etc. Until I landed on; recursive descent parsing + Pratt for expressions. Super simple technique, and for me is sufficient. I'm sure it doesn't cover all cases, but just for toy languages it feels like we can usually do everything with 2-token lookahead. Not to step on anyone's toes, I just don't feel that formal grammar theory is that important in practice. :^)
- gignico 7mo ago
  Until you need to do more than all-or-nothing parsing :) see tree-sitter for example, or any other efficient LSP implementation of incremental parsing.
  - norir 7mo ago
    It is easily possible to parse at > 1MM lines per second with a well designed grammar and handwritten parser. If I'm editing a file with 100k+ lines, I likely have much bigger problems than the need for incremental parsing.
    - fwip 7mo ago
      It's not just speed - incremental parsing allows for better error recovery. In practice, this means that your editor can highlight the code as-you-type, even though what you're typing has broken the parse tree (especially the code after your edit point).
- ogogmad 7mo ago
  Quick other one: To parse infix expressions, every time you see "x·y | (z | w)", find the operator of least binding power: In my example, I've given "|" less binding power than "·". Anyway, this visually breaks the expression into two halves: "x·y" and "(z | w)". Recursively parse those two subexpressions. Essentially, that's it. The symbols "·" and "|" don't mean anything - I've chosen them to be visually intuitive: The "|" is supposed to look like a physical divider. Also, bracketed expressions "(...)" or "{...}" should be parsed first. Wikipedia mentions that a variant of this got used in FORTRAN I. You could also speed up my naive O(n^2) approach by using Cartesian trees, which you can build using something suspiciously resembling precedence climbing.
  - duped 7mo ago
    An even easier approach is to give all infix operators the same precedence and force the programmer to group subexpressions.
    - randomNumber7 7mo ago
      You can always write lisp but most people can read code better that doesnt have that many (((()))))))
      - ogogmad 7mo ago
        I'm sure there's a middle ground which still gives you some of the metaprogramming power of Lisp. OTOH this: https://www.gingerbill.org/article/2026/02/21/does-syntax-matter/ https://www.gingerbill.org/article/2026/02/21/does-syntax-ma...
- randomNumber7 7mo ago
  It's not for toy languages. Most big compilers use recursive descent parsing.
  - ebiederm 7mo ago
    Language design benefits from parser generators that can point out ambiguities and verify a language is easy to parse.
    - marssaxman 7mo ago
      It does not follow that a generated parser would make sense in production code.
- signa11 7mo ago
  > Not to step on anyone's toes, I just don't feel that formal grammar theory is that important in practice. :^) exactly this ! a thousand times this !
  - ogogmad 7mo ago
    I think even the theory of Regular Languages is somewhat overdone: You can get the essence of what NFAs are without really needing NFAs. You can get O(n) string matching without formally implementing NFAs, or using any other formal model like regex-derivatives. In fact, thinking in terms of NFAs makes it harder to see how to implement negation (or "complement" if you prefer to call it that) efficiently. It's still only linear time! The need for NFA/DFA/derivative models is mostly unnecessary because ultimately, REG is just DSPACE(O(1)). That's it. Thinking in any other way is confusing the map with the territory. Furthermore, REG is extremely robust, because we also have REG = DSPACE(o(log log n)) = NSPACE(o(log log n)) = 1-DSPACE(o(log n)). For help with the notation, see here: https://en.wikipedia.org/wiki/DSPACE https://en.wikipedia.org/wiki/DSPACE
- eru 7mo ago
  The Dragon book is not very good, to be honest. It was probably decent when all you had was something like Pascal and you wanted to write a C compiler. Parsing and compiling and interpreting etc are all much more at home in functional languages. Much easier to understand there. And once you do, then you can translate back into imperative. For parsing: by default you should be using parser combinators.
  - pklausler 7mo ago
    Is there a production compiler out there that doesn't use recursive descent, preferably constructed from combinators? Table-driven parsers seem now to be a "tell" of an old compiler or a hobby project.
    - ogogmad 7mo ago
      Some people appreciate that an LR/LALR parser generator can prove non-ambiguity and linear time parse-ability of a grammar. A couple of examples are the creator of the Oil shell, and one of the guys responsible for Rust. It does make me wonder though about why grammars have to be so complicated that such high-powered tools are needed. Isn't the gist of LR/LALR that the states of an automaton that can parse CFGs can be serialised to strings, and the set of those strings forms a regular language? Once you have that, many desirable "infinitary" properties of a parsing automaton can be automatically checked in finite time. LR and LALR fall out of this, in some way.
      - pklausler 7mo ago
        Production compilers must have robust error recovery and great error messages, and those are pretty straightforward in recursive descent, even if ad hoc.
        deleted 7mo ago
        [deleted]
    - eru 7mo ago
      Oh, I was talking much more about how you can first learn how to write a compiler. I wasn't talking about how you write a production industry-strength compiler. Btw, I mentioned parser combinators: those are basically just a front-end. Similar to regular expressions. The implementation can be all kinds of things, eg could be recursive descent or a table or backtracking or whatever. (Even finite automata, if your combinators are suitably restricted.)
- marssaxman 7mo ago
  I am a compiler guy, and I completely agree. Parsing is not that hard and not that important. Recursive descent + pratt expressions is almost always the practical choice.
- joe_the_user 7mo ago
  Not to step on anyone's toes, I just don't feel that formal grammar theory is that important in practice. :^) Well, it depends how formal you're talking about. I have to say that the standard you mention, recursive descent parsing + Pratt for expressions. actually requires you to understand what a formal language is - that it's a "thing" that can't (or shouldn't) be an object or a data structure but exists abstractly before any objects created by the program. Moreover, the standard way of producing a recursive descend parser is to begin with your language in Chomsky normal form or some human understandable format and then convert to Greibach Normal form and that specification converts readily to your series of recursive functions. So all language transforms are useful to know (though you can skip steps if you have a good intuition of your language).
- deterministic 7mo ago
  Professional compiler writer here. All you really need to use is a recursive descent parser. Very easy to understand. Very easy to implement. While also being very powerful.
priceishere 7mo ago
An even simpler way imo, is explicit functions instead of a precedence table, then the code pretty much has the same structure as EBNF. Need to parse * before +? Begin at add, have it call parse_mul for its left and right sides, and so on. parse_mul() { left = parse_literal() while(is_mul_token()) { // left associative right = parse_literal() make_mul_node(left, right) } } parse_add() { left = parse_mul() while(is_add_token()) { // left associative right = parse_mul() make_add_node(left, right) } } Then just add more functions as you climb up the precedence levels.
- kryptiskt 7mo ago
  You lose in versatility, then you can't add user-defined operators, which is pretty easy with a Pratt parser.
  - wavemode 7mo ago
    You can have user-defined operators with plain old recursive descent. Consider if you had functions called parse_user_ops_precedence_1, parse_user_ops_precedence_2, etc. These would simply take a table of user-defined operators as an argument (or reference some shared/global state), and participate in the same recursive callstack as all your other parsing functions.
- glouwbug 7mo ago
  With a couple of function pointers you can climb precedence with just functions: parse_left_to_right(with(), is_token()) { left = with() while(is_token()) { right = with() left = operate(left, right, operator) } ret left; } p0() { ret lex digit or ident; }; p1() { ret parse_left_right(p0, is_mul); }; p2() { ret parse_left_right(p1, is_add); }; ... and so on for all operators
- tasty_freeze 7mo ago
  Systemverilog has an operator precedence table with 16 levels. https://www.academia.edu/figures/3550818/table-2-operator-precedence-and-associativity-in https://www.academia.edu/figures/3550818/table-2-operator-pr... Writing a recursive descent for this would require writing 16 functions, and you'd end up spending most of your time cycling through the functions to finally come across the one which applies for the given situation. I've written straight-forward expressions parsers as you suggest, but when I had to do it for systemverilog, I used a classic shunting yard parser. You see the operator, compare its precedence against the stack and you know immediately what to do, vs possibly drilling down 16 levels of function calls to figure out what to do. Another advantage of table-driven expression parsers is you can bail in error cases without needing to unwind countless levels of stack.
randomNumber7 7mo ago
I can recommend anyone reading pratts original paper. Its written in a very cool and badass style. https://dl.acm.org/doi/epdf/10.1145/512927.512931 https://dl.acm.org/doi/epdf/10.1145/512927.512931
- tonyedgecombe 7mo ago
  For some reason I struggled to get my head around Pratt parsing. Then I read an offhand comment on Reddit that said to start with a recursive descent parser and add table parsing to that. Once I did that it all clicked.
  - deleted 7mo ago
    [deleted]
- DonaldPShimoda 7mo ago
  > Its written in a very cool and badass style. Out of curiosity, what do you mean by this? Do you mean you like the prose, or the typesetting, or...?
  - fmbb 7mo ago
    I cannot say what this person means, and I have never read this paper before, but just the fourth paragraph of the paper has piqued my interest and I will read it all.
  - randomNumber7 7mo ago
    He is a bit offensive towards traditional academia that favors BNF and parser generators. It's been a while since a read it but I remember e.g. a rhetoric question (not exactly cited but by meaning): "Has anyone learned a programming language by reading the BNF?" The style is very good and fun to read for someone who also reads other more boring papers.
hyperhello 7mo ago
You can either use the stack in an intuitive way, or you can change the tree directly in a somewhat less intuitive way without recursion. Essentially either DF or BF. I don’t see how it matters much anymore with stacks that grow automatically, but it’s good to understand.
svat 7mo ago
> I’ve read many articles on the same topic but never found it presented this way - hopefully N + 1 is of help to someone. Can confirm; yes it was helpful! I've never thought seriously about parsing and I've read occasionally (casually) about Pratt parsing, but this is the first time it seemed like an intuitive idea I'll remember. (Then I confused myself by following some references and remembering the term "precedence climbing" and reading e.g. https://www.engr.mun.ca/~theo/Misc/pratt_parsing.htm https://www.engr.mun.ca/~theo/Misc/pratt_parsing.htm by the person who coined that term, but nevermind — the original post here has still given me an idea I think I'll remember.)
IshKebab 7mo ago
Also if you're looking into this area you'll find there is another algorithm called "Precedence climbing", which is really the same thing with some insignificant differences in how precedence is encoded. There's also the "shunting yard" algorithm, which is basically the iterative version of these algorithms (instead of recursive). It is usually presented with insufficient error checking, so it allows invalid input, but there's actually no reason you have to do it like that.
antirez 7mo ago
The latest implementation of Picol has a Tcl-alike [expr] implemented in 40 lines of code that uses Pratt-style parsing: https://github.com/antirez/picol/blob/main/picol.c#L490 https://github.com/antirez/picol/blob/main/picol.c#L490
- incanus77 7mo ago
  Love Picol, and love this! When I first revisited Tcl, I was a bit miffed about needing [expr] but now really appreciate both it and the normal Tcl syntax.
- cmacleod4 7mo ago
  I have a Tcl Improvement Proposal (TIP 676) currently being voted on which introduces an alternative compact form of calculation. The implementation uses a Pratt parser: https://core.tcl-lang.org/tcl/file?ci=cgm-equals-command&name=generic%2FtclCompExpr.c&ln=3036-3310 https://core.tcl-lang.org/tcl/file?ci=cgm-equals-command&nam... which directly generates bytecode rather than creating a parse tree.
dpratt 7mo ago
I will never forget the amusing attention I got from the professor when this topic was covered during my undergrad. It's only happened once, sadly, but this is only seconded by the time I was assisting a junior engineer with a related problem and was able to say "Oh, that's just a Pratt Parser. Let me show you."
caspianm 7mo ago
"I’ve read many articles on the same topic but never found it presented this way" it reminds me a lot of a description I saw in a video with Jonathan Blow talking about precedence and parsing with Casey Muratori. The video is 3 hours long though, and I'm not sure the text he shows is available. At this point he's talking about left leaning vs right leaning trees, after having already talked about one of them: https://youtu.be/fIPO4G42wYE?t=2256&si=aanthLGe-q8ntZez https://youtu.be/fIPO4G42wYE?t=2256&si=aanthLGe-q8ntZez
erichocean 7mo ago
Also discussed in detail in Crafting Interpreters.[0] [0] https://craftinginterpreters.com/ https://craftinginterpreters.com/
Abbit 7mo ago
> But of course, people (for the most part) don’t write programs as trees. Such a beautiful reference to Lisp.

169 points by signa11 7mo ago

Love Pratt parsing! Not a compiler guy, but I've spent way too many hours reflecting on parsing. I remember trying to get though the dragon book so many times and reading all about formal grammar etc. Until I landed on; recursive descent parsing + Pratt for expressions. Super simple technique, and for me is sufficient. I'm sure it doesn't cover all cases, but just for toy languages it feels like we can usually do everything with 2-token lookahead. Not to step on anyone's toes, I just don't feel that formal grammar theory is that important in practice. :^)

gignico 7mo ago
Until you need to do more than all-or-nothing parsing :) see tree-sitter for example, or any other efficient LSP implementation of incremental parsing.
- norir 7mo ago
  It is easily possible to parse at > 1MM lines per second with a well designed grammar and handwritten parser. If I'm editing a file with 100k+ lines, I likely have much bigger problems than the need for incremental parsing.
  - fwip 7mo ago
    It's not just speed - incremental parsing allows for better error recovery. In practice, this means that your editor can highlight the code as-you-type, even though what you're typing has broken the parse tree (especially the code after your edit point).
ogogmad 7mo ago
Quick other one: To parse infix expressions, every time you see "x·y | (z | w)", find the operator of least binding power: In my example, I've given "|" less binding power than "·". Anyway, this visually breaks the expression into two halves: "x·y" and "(z | w)". Recursively parse those two subexpressions. Essentially, that's it. The symbols "·" and "|" don't mean anything - I've chosen them to be visually intuitive: The "|" is supposed to look like a physical divider. Also, bracketed expressions "(...)" or "{...}" should be parsed first. Wikipedia mentions that a variant of this got used in FORTRAN I. You could also speed up my naive O(n^2) approach by using Cartesian trees, which you can build using something suspiciously resembling precedence climbing.
- duped 7mo ago
  An even easier approach is to give all infix operators the same precedence and force the programmer to group subexpressions.
  - randomNumber7 7mo ago
    You can always write lisp but most people can read code better that doesnt have that many (((()))))))
    - ogogmad 7mo ago
      I'm sure there's a middle ground which still gives you some of the metaprogramming power of Lisp. OTOH this: https://www.gingerbill.org/article/2026/02/21/does-syntax-matter/ https://www.gingerbill.org/article/2026/02/21/does-syntax-ma...
randomNumber7 7mo ago
It's not for toy languages. Most big compilers use recursive descent parsing.
- ebiederm 7mo ago
  Language design benefits from parser generators that can point out ambiguities and verify a language is easy to parse.
  - marssaxman 7mo ago
    It does not follow that a generated parser would make sense in production code.
signa11 7mo ago
> Not to step on anyone's toes, I just don't feel that formal grammar theory is that important in practice. :^) exactly this ! a thousand times this !
- ogogmad 7mo ago
  I think even the theory of Regular Languages is somewhat overdone: You can get the essence of what NFAs are without really needing NFAs. You can get O(n) string matching without formally implementing NFAs, or using any other formal model like regex-derivatives. In fact, thinking in terms of NFAs makes it harder to see how to implement negation (or "complement" if you prefer to call it that) efficiently. It's still only linear time! The need for NFA/DFA/derivative models is mostly unnecessary because ultimately, REG is just DSPACE(O(1)). That's it. Thinking in any other way is confusing the map with the territory. Furthermore, REG is extremely robust, because we also have REG = DSPACE(o(log log n)) = NSPACE(o(log log n)) = 1-DSPACE(o(log n)). For help with the notation, see here: https://en.wikipedia.org/wiki/DSPACE https://en.wikipedia.org/wiki/DSPACE
eru 7mo ago
The Dragon book is not very good, to be honest. It was probably decent when all you had was something like Pascal and you wanted to write a C compiler. Parsing and compiling and interpreting etc are all much more at home in functional languages. Much easier to understand there. And once you do, then you can translate back into imperative. For parsing: by default you should be using parser combinators.
- pklausler 7mo ago
  Is there a production compiler out there that doesn't use recursive descent, preferably constructed from combinators? Table-driven parsers seem now to be a "tell" of an old compiler or a hobby project.
  - ogogmad 7mo ago
    Some people appreciate that an LR/LALR parser generator can prove non-ambiguity and linear time parse-ability of a grammar. A couple of examples are the creator of the Oil shell, and one of the guys responsible for Rust. It does make me wonder though about why grammars have to be so complicated that such high-powered tools are needed. Isn't the gist of LR/LALR that the states of an automaton that can parse CFGs can be serialised to strings, and the set of those strings forms a regular language? Once you have that, many desirable "infinitary" properties of a parsing automaton can be automatically checked in finite time. LR and LALR fall out of this, in some way.
    - pklausler 7mo ago
      Production compilers must have robust error recovery and great error messages, and those are pretty straightforward in recursive descent, even if ad hoc.
      - deleted 7mo ago
        [deleted]
  - eru 7mo ago
    Oh, I was talking much more about how you can first learn how to write a compiler. I wasn't talking about how you write a production industry-strength compiler. Btw, I mentioned parser combinators: those are basically just a front-end. Similar to regular expressions. The implementation can be all kinds of things, eg could be recursive descent or a table or backtracking or whatever. (Even finite automata, if your combinators are suitably restricted.)
marssaxman 7mo ago
I am a compiler guy, and I completely agree. Parsing is not that hard and not that important. Recursive descent + pratt expressions is almost always the practical choice.
joe_the_user 7mo ago
Not to step on anyone's toes, I just don't feel that formal grammar theory is that important in practice. :^) Well, it depends how formal you're talking about. I have to say that the standard you mention, recursive descent parsing + Pratt for expressions. actually requires you to understand what a formal language is - that it's a "thing" that can't (or shouldn't) be an object or a data structure but exists abstractly before any objects created by the program. Moreover, the standard way of producing a recursive descend parser is to begin with your language in Chomsky normal form or some human understandable format and then convert to Greibach Normal form and that specification converts readily to your series of recursive functions. So all language transforms are useful to know (though you can skip steps if you have a good intuition of your language).
deterministic 7mo ago
Professional compiler writer here. All you really need to use is a recursive descent parser. Very easy to understand. Very easy to implement. While also being very powerful.

priceishere 7mo ago

An even simpler way imo, is explicit functions instead of a precedence table, then the code pretty much has the same structure as EBNF. Need to parse * before +? Begin at add, have it call parse_mul for its left and right sides, and so on. parse_mul() { left = parse_literal() while(is_mul_token()) { // left associative right = parse_literal() make_mul_node(left, right) } } parse_add() { left = parse_mul() while(is_add_token()) { // left associative right = parse_mul() make_add_node(left, right) } } Then just add more functions as you climb up the precedence levels.

kryptiskt 7mo ago
You lose in versatility, then you can't add user-defined operators, which is pretty easy with a Pratt parser.
- wavemode 7mo ago
  You can have user-defined operators with plain old recursive descent. Consider if you had functions called parse_user_ops_precedence_1, parse_user_ops_precedence_2, etc. These would simply take a table of user-defined operators as an argument (or reference some shared/global state), and participate in the same recursive callstack as all your other parsing functions.
glouwbug 7mo ago
With a couple of function pointers you can climb precedence with just functions: parse_left_to_right(with(), is_token()) { left = with() while(is_token()) { right = with() left = operate(left, right, operator) } ret left; } p0() { ret lex digit or ident; }; p1() { ret parse_left_right(p0, is_mul); }; p2() { ret parse_left_right(p1, is_add); }; ... and so on for all operators
tasty_freeze 7mo ago
Systemverilog has an operator precedence table with 16 levels. https://www.academia.edu/figures/3550818/table-2-operator-precedence-and-associativity-in https://www.academia.edu/figures/3550818/table-2-operator-pr... Writing a recursive descent for this would require writing 16 functions, and you'd end up spending most of your time cycling through the functions to finally come across the one which applies for the given situation. I've written straight-forward expressions parsers as you suggest, but when I had to do it for systemverilog, I used a classic shunting yard parser. You see the operator, compare its precedence against the stack and you know immediately what to do, vs possibly drilling down 16 levels of function calls to figure out what to do. Another advantage of table-driven expression parsers is you can bail in error cases without needing to unwind countless levels of stack.

randomNumber7 7mo ago

I can recommend anyone reading pratts original paper. Its written in a very cool and badass style. https://dl.acm.org/doi/epdf/10.1145/512927.512931 https://dl.acm.org/doi/epdf/10.1145/512927.512931

tonyedgecombe 7mo ago
For some reason I struggled to get my head around Pratt parsing. Then I read an offhand comment on Reddit that said to start with a recursive descent parser and add table parsing to that. Once I did that it all clicked.
- deleted 7mo ago
  [deleted]
DonaldPShimoda 7mo ago
> Its written in a very cool and badass style. Out of curiosity, what do you mean by this? Do you mean you like the prose, or the typesetting, or...?
- fmbb 7mo ago
  I cannot say what this person means, and I have never read this paper before, but just the fourth paragraph of the paper has piqued my interest and I will read it all.
- randomNumber7 7mo ago
  He is a bit offensive towards traditional academia that favors BNF and parser generators. It's been a while since a read it but I remember e.g. a rhetoric question (not exactly cited but by meaning): "Has anyone learned a programming language by reading the BNF?" The style is very good and fun to read for someone who also reads other more boring papers.

hyperhello 7mo ago

You can either use the stack in an intuitive way, or you can change the tree directly in a somewhat less intuitive way without recursion. Essentially either DF or BF. I don’t see how it matters much anymore with stacks that grow automatically, but it’s good to understand.

svat 7mo ago

> I’ve read many articles on the same topic but never found it presented this way - hopefully N + 1 is of help to someone. Can confirm; yes it was helpful! I've never thought seriously about parsing and I've read occasionally (casually) about Pratt parsing, but this is the first time it seemed like an intuitive idea I'll remember. (Then I confused myself by following some references and remembering the term "precedence climbing" and reading e.g. https://www.engr.mun.ca/~theo/Misc/pratt_parsing.htm https://www.engr.mun.ca/~theo/Misc/pratt_parsing.htm by the person who coined that term, but nevermind — the original post here has still given me an idea I think I'll remember.)

IshKebab 7mo ago

Also if you're looking into this area you'll find there is another algorithm called "Precedence climbing", which is really the same thing with some insignificant differences in how precedence is encoded. There's also the "shunting yard" algorithm, which is basically the iterative version of these algorithms (instead of recursive). It is usually presented with insufficient error checking, so it allows invalid input, but there's actually no reason you have to do it like that.

antirez 7mo ago

The latest implementation of Picol has a Tcl-alike [expr] implemented in 40 lines of code that uses Pratt-style parsing: https://github.com/antirez/picol/blob/main/picol.c#L490 https://github.com/antirez/picol/blob/main/picol.c#L490

incanus77 7mo ago
Love Picol, and love this! When I first revisited Tcl, I was a bit miffed about needing [expr] but now really appreciate both it and the normal Tcl syntax.
cmacleod4 7mo ago
I have a Tcl Improvement Proposal (TIP 676) currently being voted on which introduces an alternative compact form of calculation. The implementation uses a Pratt parser: https://core.tcl-lang.org/tcl/file?ci=cgm-equals-command&name=generic%2FtclCompExpr.c&ln=3036-3310 https://core.tcl-lang.org/tcl/file?ci=cgm-equals-command&nam... which directly generates bytecode rather than creating a parse tree.

dpratt 7mo ago

I will never forget the amusing attention I got from the professor when this topic was covered during my undergrad. It's only happened once, sadly, but this is only seconded by the time I was assisting a junior engineer with a related problem and was able to say "Oh, that's just a Pratt Parser. Let me show you."

caspianm 7mo ago

"I’ve read many articles on the same topic but never found it presented this way" it reminds me a lot of a description I saw in a video with Jonathan Blow talking about precedence and parsing with Casey Muratori. The video is 3 hours long though, and I'm not sure the text he shows is available. At this point he's talking about left leaning vs right leaning trees, after having already talked about one of them: https://youtu.be/fIPO4G42wYE?t=2256&si=aanthLGe-q8ntZez https://youtu.be/fIPO4G42wYE?t=2256&si=aanthLGe-q8ntZez

erichocean 7mo ago

Also discussed in detail in Crafting Interpreters.[0] [0] https://craftinginterpreters.com/ https://craftinginterpreters.com/

Abbit 7mo ago

> But of course, people (for the most part) don’t write programs as trees. Such a beautiful reference to Lisp.