I didn't find the Shunting Yard Algorithm all that difficult to use when parsing expressions. I handle unary operators and parenthesis at a lower level than binary operators, and the Shunting Yard Algorithm can easily handle right-associative binary operators.
My current favorite version of this family of parsing algorithms is the one where you parse infix expressions into a scratch array by pretending they all have the same precedence, like x + y * -z / q becomes a 7-element array, where every other item is an infix operation, and then you run the pure precedence climbing algorithm on that array.
Having the array as a scratch state instead of as an emergent behavior of the algorithm saves you from the headache of having to think about how non-infix operators interact with precedence or making sure that you're tying them into the pratt parser correctly, but the end result and behavior of the algorithm is the same. In fact IMO it's secretly the same algorithm as pratt's, just organized differently. As a bonus, you have the option of implementing it as a CST->AST conversion step after a parser generator, instead of being forced to handwrite almost all of the expression-related stuff in your parser (this bonus is also a reminder of where to put the equal-precedence scratch array parse when you're handwriting it).
The whole point of Pratt parsing is eliminating the complexity of parsing by reducing it to a single question: does the token expect something to the left?
You no longer see binary, prefix, postfix, ternary, function call, and whatnot operators in the stream. You only see nuds & leds.
I not only dislike Matklad's approach to teaching Pratt parsing, but I also strongly believe that it's harmful as it completely ignores Pratt parsing mindset itself from growing roots. The whole article is not about breaking tokens into nuds & leds, but extending a broken parsing loop to actually handle binary, prefix, postfix ... operators. He extends the parsing loop every time he stumbles on some "new" category of tokens. That's not Pratt at all. The point in Pratt is: you don' need to change Pratt's algorithm. Pratt's algorithm already works with all these operators. What you need is a framework to describe the nuds & leds of your grammar.
Here's the diff when he adds support for postfix operators:
loop {
let op = match lexer.peek() {
Token::Eof => break,
Token::Op(op) => op,
t => panic!("bad token: {:?}", t),
};
+ if let Some((l_bp, ())) = postfix_binding_power(op) {
+ if l_bp < min_bp {
+ break;
+ }
+ lexer.next();
+
+ lhs = S::Cons(op, vec![lhs]);
+ continue;
+ }
Why is Matklad introducing the unnecessary concept of postfix binding powers? Why is Matklad changing the parsing algorithm when the parsing algorithm should already be able to handle postfix operators (leds)? If you don't understand nuds & leds, you haven't learnt anything about Pratt parsing.
spc476 | 7 hours ago
I didn't find the Shunting Yard Algorithm all that difficult to use when parsing expressions. I handle unary operators and parenthesis at a lower level than binary operators, and the Shunting Yard Algorithm can easily handle right-associative binary operators.
wareya | 5 hours ago
My current favorite version of this family of parsing algorithms is the one where you parse infix expressions into a scratch array by pretending they all have the same precedence, like
x + y * -z / qbecomes a 7-element array, where every other item is an infix operation, and then you run the pure precedence climbing algorithm on that array.Having the array as a scratch state instead of as an emergent behavior of the algorithm saves you from the headache of having to think about how non-infix operators interact with precedence or making sure that you're tying them into the pratt parser correctly, but the end result and behavior of the algorithm is the same. In fact IMO it's secretly the same algorithm as pratt's, just organized differently. As a bonus, you have the option of implementing it as a CST->AST conversion step after a parser generator, instead of being forced to handwrite almost all of the expression-related stuff in your parser (this bonus is also a reminder of where to put the equal-precedence scratch array parse when you're handwriting it).
T6 | 9 hours ago
Related: https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html
vinipsmaker | 26 minutes ago
The whole point of Pratt parsing is eliminating the complexity of parsing by reducing it to a single question: does the token expect something to the left?
You no longer see binary, prefix, postfix, ternary, function call, and whatnot operators in the stream. You only see nuds & leds.
I not only dislike Matklad's approach to teaching Pratt parsing, but I also strongly believe that it's harmful as it completely ignores Pratt parsing mindset itself from growing roots. The whole article is not about breaking tokens into nuds & leds, but extending a broken parsing loop to actually handle binary, prefix, postfix ... operators. He extends the parsing loop every time he stumbles on some "new" category of tokens. That's not Pratt at all. The point in Pratt is: you don' need to change Pratt's algorithm. Pratt's algorithm already works with all these operators. What you need is a framework to describe the nuds & leds of your grammar.
Here's the diff when he adds support for postfix operators:
Why is Matklad introducing the unnecessary concept of postfix binding powers? Why is Matklad changing the parsing algorithm when the parsing algorithm should already be able to handle postfix operators (leds)? If you don't understand nuds & leds, you haven't learnt anything about Pratt parsing.
vinipsmaker | 26 minutes ago