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
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.