Tree-sitter: How to specify run-time non-associative rules

[Dekker1]

tree-sitter, like yacc, provides users with the option to give a rule left, right, or dynamic associativity. Unlike yacc, it doesn't seem to allow for non-associative rules, marked by %nonassoc in yacc grammars. These rules are particularly useful when certain rules in the grammar can be ambiguous, but all ambiguous cases would mark a programming mistake.

An example of how this occurs in my grammar, where boolean types are subtypes of numerical types, is the < operator.

$.expression => choice($.binary_operation, <and_others>),
$.binary_operation => seq($.expression, '<', $.exppression),

These rules are ambiguous because it is not defined if a < b < c should be read as (a < b) < c or a < (b < c). In my language the idea is that it is just not allowed to write the first form and has to manually add the parentheses instead. Currently this grammar does not compile unless you specify either prec.left, prec.right, or prec.dynamic for the binary_operation rule.

I currently do not see a straight-forward way to implement the behaviour where conflicts are error at runtime in the tree-sitter grammar DSL and would love to see this feature added to the language.

[issue-label-bot[bot]]

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

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

[stephe-ada-guru]

"Jip J. Dekker" [e-mail] writes:

tree-sitter, like yacc, provides users with the option to give a
rule left, right, or dynamic associativity. Unlike yacc, it doesn't
seem to allow for non-associative rules, marked by %nonassoc in
yacc grammars. These rules are particularly useful when certain
rules in the grammar can be ambiguous, but all ambiguous cases would
mark a programming mistake.

An example of how this occurs in my grammar, where boolean types are
subtypes of numerical types, is the < operator.

$.expression => choice($.binary_operation, <and_others>),
$.binary_operation => seq($.expression, '<', $.exppression),

These rules are ambiguous because it is not defined if a < b < c
should be read as (a < b) < c or a < (b < c). In my language the
idea is that it is just not allowed to write the first form and has to
manually add the parentheses instead. Currently this grammar does not
compile unless you specify either prec.left, prec.right, or
prec.dynamic for the binary_operation rule.

I currently do not see a straight-forward way to implement the
behaviour where conflicts are error at runtime in the tree-sitter
grammar DSL and would love to see this feature added to the language.

Ada has a similar rule; it splits 'expression' into 'relation' for
logical operators, and 'simple_expression' for everything else. See
http://www.ada-auth.org/standards/2xrm/html/RM-P.html; search for
'expression ::='.

--
-- Stephe

[Dekker1]

Hi Stephe,

Although this is certainly a valid workaround, it does seem like the workaround would needlessly complicate the grammar (compared to having a DSL construct). To me it feel similar to splitting operator rules into seperate levels to establish the precedence of operators.

If this workaround is currently the only way to implement this behaviour, then I wonder if the developers wouldn't consider adding something like prec.nonassoc to the grammar DSL. I think this behaviour is not uncommon.