Tree-sitter: Production vs Operator Precedence. How does it work in Treesitter?

[JoeBlanchard]

Hello,

I've been working on automatically generating Treesitter parsers from other parser specifications. I've been running into some issues translating how precedence works in Treesitter and some explanation on the inner workings of Treesitter would be helpful. Additionally this could maybe go somewhere in the documentation?

How I understand precedence written with other parser generator tools is that precedence and associativity is specified on terminals which is used to resolve shift-reduce conflicts in the parse table while production precedence is used to resolve reduce-reduce conflicts in the parse table. In Treesitter, all precedence is specified on productions and specifying a precedence on a single "terminal rule" such as with Plus: => prec.left(5, '+') does not resolve any ambiguities. After doing what the current documentation says, expr: => prec.left(5, seq($.expr, '+', $.expr)) resolves this ambiguity.

What does specifying precedence this way mean in terms of resolving shift-reduce and reduce-reduce conflicts while generating the LR parser?

Thanks!

[issue-label-bot[bot]]

Issue-Label Bot is automatically applying the label question to this issue, with a confidence of 0.84. Please mark this comment with :thumbsup: or :thumbsdown: to give our bot feedback!

Links: app homepage, dashboard and code for this bot.

[maxbrunsfeld]

A SHIFT action is associated with a set of precedence values: one for each item in the resulting item set. For an item like this:

plus  ->  expr  •  '+'  expr

the precedence is given by the precedence between the first expr and the '+'. So the corresponding prec call in the grammar needs to contain both the expr and the '+'.

A REDUCE action is associated with one precedence value: the precedence at the end of the reduce production. So the corresponding prec call just needs to contain the last item in the sequence.

---

I diverged from Yacc in this regard because I wanted all precedences to be specified within the grammar rules. I don't think associating precedences with individual operators makes as much sense: a binary + can have a different precedence than a unary +, etc.