Calculates conflicting patterns in an AST from an SDF syntax definition.
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 sdf2parenthesize tool, which uses this sdf2-ast-conflicts tool.
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.