Specification of associativity on the grammar rule

templates
Exp.Addition =	<<Exp> + <Exp>> {left}

and in priorities

...
{ left:
	Exp.Addition
	Exp.Subtraction
} >
...

is redundant.

The priorities are already specifying that addition is left associative.

However compiling without {left} on the Addition rule results in ambiguities in the grammar.

What is actually going on with priorities?
How come ambiguities arise without {left}?

Submitted by Daco Harkes on 12 June 2014 at 16:52

Priorities in groups only apply when you mix constructors from the group, e.g. Addition(Subtraction(…, …), …) should not be ambiguous. You need to add a left annotation to the Addition rule as well, to specify associativity for nested additions.

Why is mixing the same constructor different from mixing different constructors? That seems illogical.

If there is no example where same constructor associativity differs from different constructor associativity the modifiers on templates should be dropped.

If there is a example, then the modifiers on templates should only overwrite the priorities (no modifier specified on template means derive from priorities).

So far nobody has come up with an example.

@Eelco, you mentioned looking at the original SDF introduction. Where might we find this?

But nobody coming up with an example, does not mean there are no such examples.

I like to keep the local disambiguations and report a warning if they are missing in rules of the form S = <<S> ... <S>>. Local disambiguation solves the issue at the point where it arises. It supports composition, since every rule is disambiguated, independent of potential combinations with other modules, which might have priority rules or not.

@Daco:

• http://researchr.org/publication/HeeringHKR89
• http://researchr.org/publication/Visser-1997-SDF
• http://researchr.org/publication/Vis97.thesis

@Eelco: the only snippet I could find using both group associativity and single rule associativity seems kind of arbitrary.

syntax
  "(" E ")" -> E {bracket}
priorities
   "-" E -> E
>  E "^" E -> E {right}
>  E "*" E -> E {left}
> {left:
   E "+" E -> E {assoc}
   E "-" E -> E {left}}

I agree with Guido that not having an example doesn’t mean there are no such examples.
I do agree that local associativity disambiguation solves the point where it arises, for rules not in a group.
Within a group the problem arises with all combinations of single rules, and it seems logical to address that at the group instead of at the group and in single rules.

By any means I would argue that a non-ambiguous, non-redundant notation is preferred. And for cases like the one in the first post having the single rules default to the associativity specified in the priorities section would be shorter and non-ambiguous.

But if you don’t want it to change that is fine by me. It would just be a minor improvement. (If we are not going to change it then the issue can be closed.)

Using the attribute of a rule override the attribute of a group may be a good solution. I suspect that the expansion of priority and associativity declarations into a relation on pairs of productions is currently still done by the SDF2 normalizer. Once we port / redefine the normalizer for SDF3, we can consider such a policy. Another consideration is that in a priorities section there is no way to define the associativity of a single production. In the new interpretation one could write a group associativity for a single production:

context-free syntax
Exp.Addition = <<Exp> + >
priorities
{ left: Exp.Addition }

But that is definitely less concise.

The problem with an overriding interpretation is that it will be a non-local property of a production to figure out what its associativity is. One needs to look at the rule and at the priorities section.

Let’s keep the issue open.