---++ Summary Calculates conflicting patterns in an AST from an SDF syntax definition. ---++ Description sdf2ast-conflicts calculates a list of conflicting patterns in an AST by analyzing the priority and associativity declarations in an SDF syntax definition. These conflicting patterns can for example be used to insert parentheses in order to let a pretty-printed AST have the same meaning as the originating AST. Such a parentheses inserter can be generated with the [[SdfToParenthesize][sdf2parenthesize]] tool, which uses this sdf2-ast-conflicts tool. ---++ Example Consider the following SDF syntax definition for simple arithmetic expressions:
definition module Main exports context-free start-symbols Exp sorts Exp Id context-free syntax Id -> Exp {cons("Var")} "(" Exp ")" -> Exp {bracket} Exp "*" Exp -> Exp {left, cons("Mul")} Exp "/" Exp -> Exp {left, cons("Div")} Exp "+" Exp -> Exp {left, cons("Plus")} Exp "-" Exp -> Exp {non-assoc, cons("Minus")} context-free priorities {left: Exp "*" Exp -> Exp Exp "/" Exp -> Exp } > {left: Exp "+" Exp -> Exp Exp "-" Exp -> Exp } lexical syntax [a-zA-Z\_] [a-zA-Z0-9\_]* -> Id [\ \t\n] -> LAYOUT lexical restrictions Id -/- [a-zA-Z0-9\_] context-free restrictions LAYOUT? -/- [\ \t\n]
Applying the sdf2ast-conflicts tool:
$ sdf2ast-conflicts -i Exp.def | pp-aterm
Results in:
[ SubtermConflict(Symbol("Mul", 2), 0, Symbol("Plus", 2)) , SubtermConflict(Symbol("Mul", 2), 1, Symbol("Plus", 2)) , SubtermConflict(Symbol("Mul", 2), 0, Symbol("Minus", 2)) , SubtermConflict(Symbol("Mul", 2), 1, Symbol("Minus", 2)) , SubtermConflict(Symbol("Div", 2), 0, Symbol("Plus", 2)) , SubtermConflict(Symbol("Div", 2), 1, Symbol("Plus", 2)) , SubtermConflict(Symbol("Div", 2), 0, Symbol("Minus", 2)) , SubtermConflict(Symbol("Div", 2), 1, Symbol("Minus", 2)) , SubtermConflict(Symbol("Div", 2), 1, Symbol("Mul", 2)) , SubtermConflict(Symbol("Mul", 2), 1, Symbol("Div", 2)) , SubtermConflict(Symbol("Minus", 2), 1, Symbol("Plus", 2)) , SubtermConflict(Symbol("Plus", 2), 1, Symbol("Minus", 2)) , SubtermConflict(Symbol("Mul", 2), 1, Symbol("Mul", 2)) , SubtermConflict(Symbol("Div", 2), 1, Symbol("Div", 2)) , SubtermConflict(Symbol("Plus", 2), 1, Symbol("Plus", 2)) , SubtermConflict(Symbol("Minus", 2), 0, Symbol("Minus", 2)) , SubtermConflict(Symbol("Minus", 2), 1, Symbol("Minus", 2)) ]
The =SubtermConflict= indicates that a certain symbol is not allowed as the direct subterm of another symbol. Currently, the =SubtermConflict= is the only conflict pattern that is supported by sdf2ast-conflicts. To explain its meaning, let's have a look at the first conflict:
SubtermConflict(Symbol("Mul", 2), 0, Symbol("Plus", 2))
The =SubtermConflict= has three children: a =Symbol= (_A_), an integer (_x_), and another =Symbol= (_B_). A =Symbol= describes a constructor. The first subterm of a Symbol is the name of the constructor, in this case =Mul= and =Plus=. This constructor name corresponds to the =cons= attribute of the corresponding SDF production rule. The second argument of a =Symbol= is the arity of the symbol, which is 2 for both symbols. The meaning of a =SubtermConflict= is that the symbol =B= is not allowed as a subterm at position _x_ of the an aterm with symbol =A=. Thus, the example conflict defines that the term =Mul(Plus(e1, e2), e3)= has a conflict. Indeed, this expression is a problem. For instance, =6 + 5 * 3= will parse as =Plus(e1, Mul(e2, e3))=, not as =Mul(Plus(e1, e2), e3)=. Therefore, parentheses need to be inserted in this term.