Generate grammar-specific operations on trees.
The ABNF semantics includes tree matching predicates
that take the grammar as a parameter.
Given a grammar,
one can define tree matching predicates
that are specialized to the grammar,
i.e. that implicitly depend on the grammar.
In addition, this
We plan to extend this
(deftreeops *grammar* :prefix ... )
Name of the constant that contains the grammar that the tree operations are specialized to.
The grammar must be closed.
Specifies the prefix for the specialized tree operations.
It must be a symbol in a package different from the Common Lisp package and the keyword package.
A good choice for this symbol could be
<p>::cst, where <p>is the package of the application at hand and where cststands for CST (Concrete Syntax Tree). If the application involves multiple grammars for different languages, a good choice for this symbol could be <p>::<lang>-cst, where <lang>indicates the language that the grammar refers to.
In the rest of this documentation page, let
<prefix>be this symbol.
The events are put in a defsection
whose name is
Tree matching predicates, specialized to
*grammar*. The predicates are put in the same package as <prefix>.
Each predicate takes two arguments:
- A tree (for the first one), or a list of trees (for the second and third one), or a list of lists of trees (for the fourth and fifth one).
- An ACL2 string, which must be an ABNF concrete syntax representation of an element (for the first and second one), or a repetition (for the third one), or a concatenation (for the fourth one), or an alternation (for the fifth one).
Each predicate holds iff the (list of (list(s) of)) tree(s) is terminated and matches the element or repetition or concatenation or alternation. While in the semantics it makes sense to include non-terminated trees as potentially matching, for a specific grammar it normally makes sense to consider only terminated trees: this motivates the extra condition.
These generated predicates are actually macros, which use (subroutines of) the verified grammar parser to parse the ACL2 strings passed as second arguments into their ABNF abstract syntactic representation, and then expand to calls of the appropriate generic tree matching predicates in the semantics, passing the grammar as argument to them; the dependency on the grammar is implicit in the generated predicates. Note that the parsing of the strings happens at macro expansion time (i.e. at compile time), not at predicate call time (i.e. at run time).
There are some generated internal intermediate predicates that these macros expand into calls of, and it is these intermediate predicates that call the generic tree matching predicates from the semantics. These intermediate predicates are actual ACL2 functions, whose names are identical to the macros but with
$at the end. Macro aliases are also generated that link the macro names to the function names: this way, the predicates can be opened (in proofs) via their macro names.
For each rule name defined in the grammar, a theorem saying that a tree that matches the rule name is a non-leaf tree.
For each rule name defined in the grammar, a theorem saying that a tree that matches the rule name has exactly that rule name.
For each rule name defined in the grammar, a theorem saying that if a tree matches the rule name then its branches match the alternation that defines the rule name.
For each rule name defined in the grammar, a theorem saying that if a list of lists of trees matches the alternation that defines the rule name then the list of lists of trees matches one of the alternatives (each of which is a concatenation).
For each rule name defined in the grammar by two or more alternatives, a theorem stating equivalences between (i) the branches (of a tree matching the rule name) matching each alternative that defines the rule name and (ii) some term over the branches that discriminates among the alternatives; there is an equivalence for each alternative, and the theorem consists of the conjunction of the equivalences. For now we only generate this theorem when each alternative is a singleton concatenation of a singleton repetition of a rulename element.
For each rule name defined in the garmmar by two or more alternatives, a function that, given a tree matching the rule name, returns a positive integer indicating the alternative matched by the tree, in the order in which the alternative appears in the grammar, starting from 1 for the first alternative. If a rule name is defined by multiple rules (the first one non-incremental, the other ones incremental), the order of the alternatives indicated by the integer returned by this function is lexicographic, based first on the order of the rules and then on the order of the alternatives within each rule. The generated function is accompanied by theorems about it.
For each rule name defined in the grammar, and for each alternative
<i>(starting from 1) that defines the rule name, a theorem saying that if a list of lists of trees matches that alternative (which is a concatenation) then the list of lists of trees has the same length as the concatenation and each list of trees matches the corresponding repetition of the concatenation. For now we only generate this theorem when the alternative is a singleton concatenation.
For each rule name defined in the grammar, for each alternative
<i>(starting from 1) that defines the rule name, and for each repetition <j>(starting from 1) of that alternative, a theorem saying that if a list of trees matches that repetition then the list of trees has a length within the range of the repetition and each tree matches the element of the repetition. For now we only generate this theorem when the repetition has a range of 1.