NHacker Next
  • new
  • past
  • show
  • ask
  • show
  • jobs
  • submit
Intuiting Pratt Parsing (louis.co.nz)
priceishere 58 seconds 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.
logdahl 27 minutes 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 2 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.
Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact
Rendered at 11:25:36 GMT+0000 (Coordinated Universal Time) with Vercel.