The module CST offers an algebraic data type cst of concrete syntax trees. This definition is generic, that is, grammar-independent. This module is unsafe: the data constructor NonTerminal has an invariant that is not enforced. A safe, non-generic API can be constructed a posteriori on top of this unsafe, generic API.
The fringe of a CST is a sequence of tokens.
A CST is viable if the parser accepts its fringe and produces the exact same CST again. In general, not every CST is viable: as a typical example, in a grammar of arithmetic expressions where there is a single nonterminal symbol for expressions and where priority declarations are used to resolve shift/reduce conflicts, a CST where an addition node is a child of a multiplication node is not viable. If the grammar is LR(1) then every CST is viable.
A concrete syntax tree (CST) is either a terminal node Terminal tok or a nonterminal node NonTerminal (prod, csts).
A terminal node carries just a token.
A nonterminal node carries a production index prod and an immutable array of subtrees csts. The length of the array csts must be the length of the right-hand side of the production prod. The sequence of the head symbols of the subtrees csts must match the right-hand side of the production prod. The production prod must not be a start production.