logoalt Hacker News

priceishere • today at 11:24 AM • 2 replies • view on HN

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.

Replies

glouwbug • today at 4:03 PM

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
kryptiskt • today at 11:37 AM

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