Sdf To Parenthesize

XT -- A Bundle of Program Transformation Tools


sdf2parenthesize generates a Stratego transformation tool that adds the necessary parentheses to an abstract syntax tree. The information is obtained from an SDF syntax definition.


For example, if Plus is declared to left associative, then the following rule will be generated:

  ExpParenthesize :
    Plus(q_15, Plus(o_15, p_15)) -> Plus(q_15, Parenthetical(Plus(o_15, p_15)))

A relative priority related example:

  ExpParenthesize :
    Mul(Plus(v_2, w_2), u_2) -> Mul(Parenthetical(Plus(v_2, w_2)), u_2)

  ExpParenthesize :
    Mul(t_2, Plus(v_2, w_2)) -> Mul(t_2, Parenthetical(Plus(v_2, w_2)))

The tool supports:

Relative priorities

    Exp "&&"  Exp -> Exp
  > Exp "||"  Exp -> Exp

Groups of associative productions

       Exp "*" Exp -> Exp
       Exp "/" Exp -> Exp
  > {left:
       Exp "+" Exp -> Exp
       Exp "-" Exp -> Exp

Associativity attributes: non-assoc, assoc, left, right.

  Exp "+"   Exp -> Exp  {left, cons("Plus")}

Kernel SDF associativities

  prod1 assoc prod2

Open Issues

Does this solve all the parentheses related problems? No, unfortunately not. The tool does not support {prefer} attributes, which are for example used in the dangling else problem.

So, if you want to make sure that

  IfThenElse(_, IfThen(_, _, _), _)
is pretty-printed correctly as:
  if a then (if b then c) else d
then you still need to implement this be hand. Notice that you can import the generated rules in this handwritten tool. I don't have a clue now I could automate these issues in the generator, since the {prefer} attributes are not really declarative.