|
|
|---|
|
|
|
|---|
Trees of rule names and terminal values.
This is a tagged union type, introduced by fty::deftagsum.
This type captures the basic structure of ABNF trees, without reference to specific rules.
Since a single
To represent trees whose rule names are not all expanded, rule names may appear as leaves too.
A non-leaf node of a tree is optionally labeled by a rule name. When it is labeled by a rule name, the branches correspond to a concatenation chosen from the alternation associated to the rule name. But since a concatenation is a sequence of repetitions, and a repetition may expand to multiple instances of the element of the repetition, the branches are organized as a list of lists: the outer list corresponds to the list of repetitions that form the chosen concatenation, while each inner list corresponds to the element instances of the corresponding repetition. An empty inner list is used for a repetition of no elements. An empty outer list is used for an empty concatenation, which is disallowed by [RFC:4] but allowed by our abstract syntax; an empty outer list is also used for an option [RFC:3.8] that is absent.
Since, via groups [RFC:3.5] and options [RFC:3.8], an element may recursively be an alternation, if a branch in an inner list under a rule name is an alternation, that branch recursively has a list of lists of branches. In this case, there is no rule name labeling the root of this branch. A rule name provides a name for an alternation; the presence of a rule name in a non-leaf node of a tree indicates that a named alternation is expanded at that place in the tree.