Add non-associative infix operators #800
Conversation
src/pratt.rs
Outdated
| pub fn right(binding_power: u16) -> Associativity { | ||
| Associativity::Right(binding_power) | ||
| pub fn right(precedence: u16) -> Associativity { | ||
| assert!(precedence > 0); |
There was a problem hiding this comment.
Might be worth adding #[track_caller] to this function (and others), which should result in the assert location pointing to the caller location rather than inside the function.
|
Hmm, looks like there are CI failures too. |
Binding power is an implementation detail, what users specify is the precedence level.
The binding power zero is used as a special marker for the first invocation. User can specify a precedence of zero resulting in a binding power of zero, which would mimic this marker. Use an i32 and i32:MIN as a marker instead.
This designates an infox operator as non-associative. Chained operator result in a parse error because without an associativity they can't be unambigiously parsed. Also add some test cases that will fail for now.
All pratt operators can now return two types of errors, non-fatal (`NoMatch`), which allow the parse to continue and fatal (`Err`) errors, that abort the parse. If a non-associative infix operator encounters an operator with the same binding strength it returns a fatal error because of an ambigious input. For this to work, the infix operator mus first parse it's operator before checking the binding power.
I changed it, a precedence of zero is now ok.
The check failures are somwhere else in the code, not sure why they fail. I made the new result type more generic so every operator can use it. I don't know how to handle error reporting properly. The infix parse returns a fatal error if it finds an operator (non-associative) with the same precedence. This is an ambigious input and should ideally result an an error like "Ambigous operator order, use () to fix it" or something like that. The above test fails because the prefix operator "§" and the infix operator "+" have the same binding_power, but "+" is non-associative. I think this should not cause an error because associativity should onyl matter between infix operators. I have to think how to fix that. |
Got it, just need to check if the operator is actually non-associative. What do you thing about the error handling/message? |
Great!
I think this is fine for an initial implementation. That said, chumsky supports non-fatal errors. It should be possible for the pratt parser to successfully generate an output while also emitting an error about the use of non-associative operators. You can find an example of this being doing in the What do you think? |
38bb88c to
02a1373
Compare
|
I haven't wrapped my head around the error handling. If I need to use it in my code, I might come back to it. |
|
Thanks! I may make some minor modifications to this post-merge, but I really appreciate all of the work you've put into this! |
I tried to mess with the code and got a working solution. I'm new to rust, so this might not be the best code.
I had to disallow a precedence of zero, which might be a breaking change. Zero is used as a start marker
and all implementations I've seen use precedences > 0 when defining the operators.
I also switched the check for associtivity with the operator parsing, which might change the performance?
Now the test
pratt::tests::with_pre_and_postfix_opsfails because it contains an ambiguity between the§and+operator, both have a binding power of 4.The comment in that test case indicates that such ambiguity is not a good thing, so maybe this new behaviour is okay? Then the check could just be changed. The old behaviour bound infix operators tighter than prefix operators of the same precedence.
This is a new attempt, the other ones are #600 and #728.