I'm not sure whether someone else has commented on this. I am yet to read the comments. Maybe I will read them soon enough.
Anyways and however, speaking in strict mathetical sense, the model of a tree actually breaks the classical mathematical model of operator precedence.
1 + 1 + 1 evaluates to:
(+)
/ \
(+) (1)
/ \
(1) (1)
The above will be correct, mathematically, but will break once you involve multiple mathematical operators in the statement. Because, mathematically, operators have precedence.
The operators are essentially ordered based on their depth into the right of the question / statement but unless I am terribly wrong, this is not the case in mathematics and some operators have higher precedence regardless of their position in the statement.
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. <a href="https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html" rel="nofollow">https://matklad.github.io/2020/04/13/simple-but-powerful-pra...
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!
ReDress · · focus · HN ↗
Anyways and however, speaking in strict mathetical sense, the model of a tree actually breaks the classical mathematical model of operator precedence.
1 + 1 + 1 evaluates to:
The above will be correct, mathematically, but will break once you involve multiple mathematical operators in the statement. Because, mathematically, operators have precedence.The operators are essentially ordered based on their depth into the right of the question / statement but unless I am terribly wrong, this is not the case in mathematics and some operators have higher precedence regardless of their position in the statement.
Any comments on this?
stratos123 · · focus · HN ↗
There's many ways to do this parsing, e.g. <a href="https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html" rel="nofollow">https://matklad.github.io/2020/04/13/simple-but-powerful-pra...
mrkeen · · focus · HN ↗
I had a look at the link. The BNF looked good:
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." : Then the author takes us through Pratt parsing and ends up at: 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!