PEMDAS

rascal-0.40.17

Synopsis

How does one define the order of mathematical operations in an expression language in Rascal?

Description

lexical Id = [a-z]+;
lexical Num = [0-9]+;

syntax Exp
    = Id
    | Num
    | bracket "(" Exp ")"      ❶  
    > right Exp "^" Exp        ❷  
    > left ( Exp "*" Exp       ❸  
           | Exp "/" Exp       ❹  
           )
    > left ( Exp "+" Exp       ❺  
           | Exp "-" Exp       ❻  
           )
    ;

• The Id and Num rules are not ambiguous. They do not require an order.
• ❶ : The bracket rule is required to write expressions in a different order. The bracket syntax ryle attribute is used in Patterns to ignore superfluous brackets in either the pattern or the subject value.
• ❷ : At the first > starts the definition of order of operations. The highest precedences goes to the ^ operator (exponentiation). And here we chose for right associativity such that 1^2^3 parses as 1^(2^3).
• ❸ : We chain more > to expand the ordered list of operators to include multiplication * and division /. <4>: / is left associative like `and they are *also* towards one another, because they are grouped in an associativity groupleft ( ... )`.
• ❺ : The chain ends with addition and subtraction at the bottom of the hierarchy.
• ❻ : Again both operators are left associative within a group.

Examples

Let's add a small function that helps to visualize the order of the operators:

rascal>Exp brackets(Exp e) = visit(e) {
>>>>>>>case Exp f => (Exp) `(<Exp f>)` 
>>>>>>>  when (Exp) `(<Exp _>)` !:= f, (Exp) `<Id i>` !:= f, (Exp) `<Num n>` !:= f
>>>>>>>};
Exp (Exp): function(|prompt:///|(0,144,<1,0>,<4,2>))

No we can see what the parser does:

rascal>import IO;
ok
rascal>for (input <- ["a+b*c", "a^b*c+d", "(a^b+1)^d+1"]) {
>>>>>>>  t = parse(#Exp, input);
>>>>>>>  println("<t> - <brackets(t)>");
>>>>>>>}
a+b*c - (a+(b*c))
a^b*c+d - (((a^b)*c)+d)
(a^b+1)^d+1 - (((((a^b)+1))^d)+1)
list[void]: []

Or we can use some pretty printing:

rascal>import vis::Text;
ok
rascal>for (input <- ["a+b*c", "a^b*c+d", "(a^b+1)^d+1"]) {
>>>>>>>  t = parse(#Exp, input);
>>>>>>>  println(prettyTree(t));
>>>>>>>}
 Exp = Exp  "+"  Exp 
 ├─ Exp = Id 
 │  └─ Id = [a-z]+ 
 │     └─ [a-z]+
 │        └─ a
 └─ Exp = Exp  "*"  Exp 
    ├─ Exp = Id 
    │  └─ Id = [a-z]+ 
    │     └─ [a-z]+
    │        └─ b
    └─ Exp = Id 
       └─ Id = [a-z]+ 
          └─ [a-z]+
             └─ c

 Exp = Exp  "+"  Exp 
 ├─ Exp = Exp  "*"  Exp 
 │  ├─ Exp = Exp  "^"  Exp 
 │  │  ├─ Exp = Id 
 │  │  │  └─ Id = [a-z]+ 
 │  │  │     └─ [a-z]+
 │  │  │        └─ a
 │  │  └─ Exp = Id 
 │  │     └─ Id = [a-z]+ 
 │  │        └─ [a-z]+
 │  │           └─ b
 │  └─ Exp = Id 
 │     └─ Id = [a-z]+ 
 │        └─ [a-z]+
 │           └─ c
 └─ Exp = Id 
    └─ Id = [a-z]+ 
       └─ [a-z]+
          └─ d

 Exp = Exp  "+"  Exp 
 ├─ Exp = Exp  "^"  Exp 
 │  ├─ Exp = "("  Exp  ")" 
 │  │  └─ Exp = Exp  "+"  Exp 
 │  │     ├─ Exp = Exp  "^"  Exp 
 │  │     │  ├─ Exp = Id 
 │  │     │  │  └─ Id = [a-z]+ 
 │  │     │  │     └─ [a-z]+
 │  │     │  │        └─ a
 │  │     │  └─ Exp = Id 
 │  │     │     └─ Id = [a-z]+ 
 │  │     │        └─ [a-z]+
 │  │     │           └─ b
 │  │     └─ Exp = Num 
 │  │        └─ Num = [0-9]+ 
 │  │           └─ [0-9]+
 │  │              └─ 1
 │  └─ Exp = Id 
 │     └─ Id = [a-z]+ 
 │        └─ [a-z]+
 │           └─ d
 └─ Exp = Num 
    └─ Num = [0-9]+ 
       └─ [0-9]+
          └─ 1
list[void]: []

Benefits

• The standard operator order rules are easily expressed in Rascal
• We only need a single non-terminal Exp to define all operators and their relative precedence
• It is easy to add more operators