Skip to main content

Associativity Declaration

rascal-0.40.17

Synopsis​

Define associativity of operators

Syntax​

  • syntax Exp = Assoc Label Symbol₁ Symbol₂ ...
  • syntax Exp = Assoc ( Alt₁ | Alt₂ | ... )
  • syntax Exp = Assoc Symbol₁ Symbol₂ ...

Here Assoc is one of: left, right, assoc or non-assoc. See Syntax Definitions on how to define alternatives and Symbols.

Description​

Using Associativity declarations we may disambiguate binary recursive operators.

The semantics are that an associativity modifier will instruct the parser to disallow certain productions to nest at particular argument positions:

  • left and assoc will disallow productions to directly nest in their right-most position.
  • right will disallow productions to directly nest in their left-most position.
  • non-assoc will disallow productions to directly nest in either their left-most or their right-most position.

When associativity is declared for a group of productions, e.g. left ( Alt₁ | _Alt ₂_ | Alt₃), then each alternative will be mutually associative to each other alternative and itself. If an alternative of a group defines its own local associativity, as in left ( right Alt₁ | Alt₂ | Alt₃), then Alt₁ is right associative with respect to itself and left associative with respect to all others in the group.

A finer point is that associativity has no effect on any other position than the left-most and right-most position (see also Priority). This is to guarantee that associativity does not introduce parse errors. The following tables explain when an associativity declaration filters, given two productions father and child that share an associativity group.

If left (Parent \| Child)Parent None: E = "[" E "]"Parent Left-most: E = E "*"Parent Right-most: E = "*" EParent Both: E = E "*" E
Child None: E = "{" E "}"No filterNo filterNo filterNo filter
Child Left-most: E = E "+"No filterNo filterFilter under rightFilter under right
Child Right-most: E = "+" ENo filterNo filterNo filterNo filter
Child Both: E = E "+" ENo filterNo filterFilter under rightFilter under right
If right (Parent \| Child)Parent None: E = "[" E "]"Parent Left-most: E = E "*"Parent Right-most: E = "*" EParent Both: E = E "*" E
Child None: E = "{" E "}"No filterNo filterNo filterNo filter
Child Left-most: E = E "+"No filterNo filterNo filterNo filter
Child Right-most: E = "+" ENo filterFilter under leftNo filterFilter under left
Child Both: E = E "+" ENo filterFilter under leftNo filterFilter under left

Benefits​

  • Short notation for common constructs in programming languages.
  • Removes ambiguity but can not introduce parse errors.
  • Allows the use of fewer non-terminals for the same expression grammar (typically only one), which makes parse trees simpler as well as the mapping to an abstract syntax tree more direct.

Pitfalls​

  • Do not assume that Rascal's associativity declarations have the same semantics as SDF's associativity declarations.
  • Use of productions that are both left and right recursive in an associativity group, although safe, is not meaningful. We would advise to use the Priority relation such a case. For example:
Original associativityBetter written as priority
E = left ( "+" E \| E "+" E );E = E "+" E > "+" E;
E = right ( "+" E \| E "+" E );E = "+" E > E "+" E;
E = left ( E "+" \| E "+" E);E = E "+" > E "+" E;
E = right ( E "+" \| E "+" E);E = E "+" E > E "+" ;

//