The module DCST offers an abstract data type dcst of disjunctive concrete syntax trees. This definition is generic, that is, grammar-independent. This module offers an unsafe API: the smart constructors nonterminal and choice have preconditions whose validity is not tested at runtime. A safe, non-generic API can be constructed a posteriori on top of this unsafe, generic API.
A disjunctive concrete syntax tree (DCST) is a terminal node, a nonterminal node, or a disjunction node, also known as a choice node.
A disjunction node offers a choice between two subtrees. This is typically used to express a choice between two ways of displaying a piece of syntax: e.g., with or without enclosing parentheses. A DCST is typically a DAG: its subtrees can be shared.
Thanks to disjunction nodes, an (exponentially large) set of CSTs can be represented as a single DCST.
The type dcst is presented as an abstract type equipped with three constructors, namely terminal, nonterminal, and choice.
val nonterminal : A.production -> dcst array -> dcstnonterminal prod dcsts constructs a nonterminal node. It assumes (but does not check) that prod is not a start production, that the number of subtrees is the length of the right-hand side of production prod, and that the sequence of the head symbols of the subtrees forms the right-hand side of production prod.
choice dcst1 dcst2 constructs a choice node. It assumes (but does not check) that the subtrees dcst1 and dcst2 have the same head symbol.
The head symbol of a DCST is defined as follows. The head symbol of terminal tok is the terminal symbol associated with the token tok. The head symbol of nonterminal prod dcsts is the left-hand side of the production prod. The head symbol of choice dcst1 dcst2 is the common head symbol of dcst1 and dcst2.