Skip to main content

Priority Declaration

rascal-0.28.2

Synopsis

Declare the priority of operators.

Syntax

  • syntax Exp = alt₁ > alt₂ > alt₃ is the basic syntax for priorities.
  • syntax Exp = alt₁ | alt₂ > alt₃ | alt₄, where the | signifies groups of equal priority
  • syntax Exp = associativity ( _alt₁ | ... ) > _alt₂, where an associativity group denotes a group of equal priority

Description

Priority declarations define a partial ordering between the productions within a single non-terminal. The feature is specifically designed to fit with the semantics of expression sub-languages embedded in programming languages. There exist other mechanisms for Disambiguation, if Priority does not work for you.

The semantics of a priority relation A > B is that B will not be nested under A in the left-most or right-most position. Any other position of A will allow B fine. Note that the priority relation you define is transitively closed, so if A > B and B > C then A > C.

A finer point is that Rascal restricts the filtering of priority such that it is guaranteed that no parse errors occur at the cause of a priority. The following table defines when and where Rascal forbids a direct nesting between two productions parent > child, depending on at which left-most or right-most positions the parent and the child are recursive.

If Parent > ChildParent 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 filterFilter under leftNo filterFilter under left
Child Both: E = E "+" ENo filterFilter under leftFilter under rightFilter under left and right

Examples

The following snippet uses all Priority features:

syntax Exp 
= A: Id
| B: Number
> C: Exp "[" Exp "]"
| D: Exp "!"
> E: Exp "*" Exp
> F: Exp "+" Exp;
| bracket G: "(" Exp ")"
;

A short explanation:

  • C and D share a group of equal priority. They are incomparable in the partial ordering. That's fine because 1![2] is not ambiguous.
  • Similarly A and B share a group; yet they are not recursive and so do not play any role in the priority ordering.
  • C and D both have higher priority then E and F, which means that E and F may not be directly nested under C or D.
  • However: E and F will be allowed under the second argument of C because it is not an outermost position. That's fine because 1 [2 + 3] is not ambiguous.

Here a number of strings for this language, with brackets to show how they will be parsed:

  • "1 + 2 3" will be parsed as "1 + (2 3)" because E > F.
  • "1 + 2 [ 3 ]" will be parsed as "1 + (2[3])" because C > F.
  • "1 * 3!" will be parsed as "1 + (3!)" because D > E.
  • "1 + [2 * 3]" will be parsed as "1 + ([2 * 3])" because priority is only defined for outermost positions.

Benefits

  • Short notation for common expression grammars
  • Removes ambiguity but can not introduce parse errors
  • Allows the use of less 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

  • Please do not assume that Rascal's priorities have the same semantics as SDF's priorities.
  • When a priority does not have a filtering effect, such as in E = E "+" > E "*" it is usually better to use normal alternative composition: E = E "+" | E "*". There is no difference in the semantics of parsing, but the latter expression is more intentional.
  • You should not hide right or left recursion behind a nullable non-terminal, since the system will not filter the ambiguity then. Example: E = left "a"? E "" E > E "+" E will remain ambiguous. This should be written as: E = left ("a" E "" E | E "*" E ) > E "+" E; (unfolding the optional such that E becomes explicitly left-most).