Intuiting Pratt Parsing

Post by norir » Wed, Apr 01, 2026, 2:53 PM UTC

gignico wrote: post #3

logdahl wrote: post #2

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 eve…

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.

Post by pklausler » Wed, Apr 01, 2026, 2:58 PM UTC

eru wrote: post #20

pklausler wrote: post #18

Earlier quoted context omitted.

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.

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 comb…

Post by dbcurtis » Wed, Apr 01, 2026, 3:26 PM UTC

pklausler wrote: post #18

eru wrote: post #13

Earlier quoted context omitted.

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.

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.

Post by wavemode » Wed, Apr 01, 2026, 3:39 PM UTC

kryptiskt wrote: post #5

priceishere wrote: post #4

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_ad…

You lose in versatility, then you can't add user-defined operators, which is pretty easy with a Pratt parser.

Post by glouwbug » Wed, Apr 01, 2026, 4:03 PM UTC

priceishere wrote: post #4

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_ad…

  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); };