Allow precedences to be specified using strings and a partial ordering relation#939
Conversation
Right now, the strings are not used in comparisons, but they are passed through the grammar processing pipeline, and are available to the parse table construction algorithm. This also cleans up a confusing aspect of the parse table construction, in which precedences and associativities were temporarily stored in the parse table data structure itself.
|
That's great to hear! |
|
This seems to be missing from the dsl types? Causes this to error |
@razzeee could you tell where do you usually put such lines? Is it |
|
Top of your grammar file. I just have one which is grammar.js https://www.github.com/elm-tooling/tree-sitter-elm/tree/master/grammar.js |
|
Thanks for the heads up @razzeee. |
Fixed on master. |
|
It would be nice if commenting a partial ordering relation on I've been using the following strategy to workaround the "Undeclared precedence" error: Maybe the "Unresolved conflict" could be thrown after "Undeclared precedence" error? By the way, I appreciate the implementation of this elegant solution for the precedence problem. |
|
Ok, an update on this - In Tree-sitter v0.19.1, I've added a feature make the partial orderings easier to specify. You can control the precedence of an entire grammar rule by including a reference to the rule (using the For example, in JavaScript, to control the precedence of await expression and arrow functions relative to binary operators, you can simply do this: precedences: $ => [
[
'binary_times',
'binary_plus',
// ...
$.await_expression,
$.arrow_function
],
],I'll write up more documentation on this in the main docs site soon. |
|
This is a great change; looking forward to using it. I had already been trying to do something like this (very informally) myself 😄 : |
|
Also need to update the file ´cli/src/generate/grammar-schema.json´ to include the |

Background
For some grammars, it is very awkward to specify all of their rules' precedence as a total ordering, using integers. The problem is that we might need to statically (via precedence) resolve conflicts between rules
e,f, andg, and also between rulest,u, andv, but want to avoid resolving any conflicts between, say,eandu, organdt.This bug in the TypeScript grammar is an example of a case where it's really hard to do this using the integer precedence system.
What we need is a way of specifying precedences as a partial ordering. There's some discussion about this model in this blog post: Operator Precedence: We Can Do Better.
Solution
This PR makes two backward-compatible changes to the grammar DSL:
precedences, that specifies a set of precedence names, and a set of ordering relations between those names. Each ordering relation is structured as an array of names, in descending order of their strength.precfamily of functions can now take a precedence name instead of an integer. When constructing the parser, these names will be compared according to the grammar'sprecedenceslists. For some pairs of names, there will be no ordering relation that includes both names. These two names will be treated as equal in strength, for conflict-resolution purposes.Example
We might use these features in the TypeScript grammar, doing something like this:
Details
Grammars using integer precedence will not be affected. It's also valid to use a mixture of integer precedences and named precedences: those two groups will not be compared to each other.