Hacker News Reader

Comment by stratos123 | Hacker News Reader

Operator precedence needs to get applied at parsing time, before you get a tree. 1 + 2 * 1 needs to get parsed to

     (+)
     / \
   (1) (*)
       / \
     (2) (1)

The tree representation is unambiguous and once you get that there's no need to think about precedence.

There's many ways to do this parsing, e.g. https://matklad.github.io/2020/04/13/simple-but-powerful-pra...

View on HN

Agree with 'solve it during parsing'.

I had a look at the link. The BNF looked good:

  Expr =
    Expr '+' Expr
    ...

Then the author fixed the left-recursion and precedence (which also looks good,) but then complains about the fixed version - "the “shape” of expressions feels completely lost in this new formulation." :

  Expr =
    Factor
  | Expr '+' Factor
  ...

Then the author takes us through Pratt parsing and ends up at:

  fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S { 
    let mut lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        t => panic!("bad token: {:?}", t),
    };

    loop {
        let op = match lexer.peek() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };
    ...

Yikes! I think he criticised the wrong code. I'll take the '{expression} is a {factor} or an {expression plus a factor}' formulation over the 'mut-loop-peek-panic-lexer-next' approach any day!

Reply on news.ycombinator.com