Intuiting Pratt Parsing

3 comments

• logdahl 1 hour 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. :^)

  [-]
  • signa11 2 minutes 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 !
  • randomNumber7 17 minutes ago
    It's not for toy languages. Most big compilers use recursive descent parsing.
  • gignico 36 minutes 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.
  • ogogmad 21 minutes 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 separately.

    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 resembling precedence climbing.
• randomNumber7 16 minutes 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
• priceishere 35 minutes 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 22 minutes ago
    You lose in versatility, then you can't add user-defined operators, which is pretty easy with a Pratt parser.