SPPF (shared packed parse forest) is the best known graph representation of a parse forest (family of related parse trees) used in parsing with ambiguous/conjunctive grammars. Systematic general purpose transformations of SPPFs have never been investigated and are considered to be an open problem in software language engineering. In this paper, we motivate the necessity of having a transformation operator suite for SPPFs and extend the state of the art grammar transformation operator suite to metamodel/model (grammar/graph) cotransformations.
Classically, parsing consumes a string of characters or tokens, recognises its
grammatical structure and produces a corresponding parse tree [
There have been various attempts in the past to represent parse forests.
The earliest ones required a grammar to be in a Chomsky Normal Form [
The next attempt in representing parse forests revolved around tree
merging [
The best representation of a conceptual parse forest (a set of trees with equal lists of leaves) so far is a so-called shared packed parse forest [43, §2.4], SPPF from now on: its components are merged from the top until the divergent nodes, and due to maximal sharing the leaves and perhaps even entire subtrees grouping leaves together, are also merged. An example of such a graph is given on Figure 2. Formally, an SPPF is an acyclic ordered directed graph where each edge is a tuple from a vertex to a linearly ordered list of successors and each vertex may have more than one successor list. If V is a set of vertices, then edges are:
E = fhvi; (vi1; vi2; :::; viki )i j vi 2 V; vij 2 V g V
V
SPPF-like structures are used nowadays both in software language toolkits
that allow explicit ambiguities (such as Rascal [
For many years trees have been the dominant data structure for representing
hierarchical data in software language processing. They are remarkably easy
to define, formalise, implement, validate, visualise and transform. There are
many ways to circumvent data representation as graphs by considering a tree
together with a complementary component such as a relation between its vertices
that would have turned a tree into a cyclic graph, as well as many
optimisations of graph algorithms that work on skeleton trees of a graph. Take, for
instance, traversing a tree — it can be done hierarchically from the root
towards the leaves or incrementally from the leaves towards the root, each case
guaranteed termination even if the traversal is not supposed to stop when a
match is made. This naturally provides us with four traversal strategies found
in metaprogramming: bottom-up-continue, bottom-up-break, top-down-continue
and top-down-break [
+ E + E + (f)
E + 2 (d) E + 2
2 (g)
E + E + 2 2 2+2+2 (b)
E + 2
2 (e) 2
E +
E
+
2
2
2
One of the relatively well-researched kind of SPPF transformations is
disambiguation — it is commonly practised with ambiguous generalised parsing
because static detection of ambiguity is undecidable for context-free grammars [
Ordered choice, dynamic lookahead and other conventions aimed to prevent
ambiguities altogether or avoid them. These are fairly static, relatively
wellunderstood and widely used in TXL [
E E
Disambiguation filters that are run after the parsing process has yielded a
fully formed SPPF: their main objective is to reduce the number of
ambiguities and ultimately to shave all of them off, leaving one parse tree. An
example of this would be how processing production rules marked for
rejection is done for SGLR [
Formally speaking, the first class never produces parse forests; the second
class works with disambiguators (higher order functions that take a parser and
return a parser that produces less ambiguous SPPFs) [
Grammar programming is like normal programming, but with grammars: there is a concrete problem at hand which can be solved with a grammar, which is then being adjusted until an acceptable solution emerges. A representative pattern here is working with a high level software artefact describing a language (we assume it to be a grammar for the sake of simplicity, but in a broad sense it can be a schema, a metamodel, an ontology, etc), from which a tool solving the problem at hand is inferred automatically.
There are at least three common approaches to grammar programming:
manual, semi-automated and operator-based. Manual grammar programming
involves textual/visual editing of the grammar file by a grammarware engineer.
It is the easiest method in practice and is used quite often, especially for minor
tweaks during grammar debugging. However, it leads to hidden inconsistencies
within grammars (which require advanced methods like grammar convergence
to uncover [
We speak of coupled transformations when two or more kinds of mutually
dependent software artefacts are transformed together to preserve consistency among
them: usually one changes, and others co-evolve with it [
Assuming that we have a sequence of grammar transformation steps, we may
want to execute them on the language instances (programs) as well, to make
them compatible with the updated grammar. Such a need arises in the case of
grammar convergence [
Consider another scenario where we have the change on language instances
and want to lift it to the level of language definitions. An example could be
found in program transformation, a common software engineering practice of
metaprogramming. If we want a refactoring like extracting a method, renaming
a variable or removing a go-to statement, it is easy and practical to express it in
terms of matching/rewriting paradigm: in Spoofax [
This was already mentioned before, but becomes a crucial point from now on: parse forests can arise from two different sources — conjunctive clauses in the grammar used for parsing and generalised parsing with ambiguous grammars. The latter case can be considered implicit conjunction, since it is present on the level of language instances but not on the grammar level. In that case, instead of a more cumbersome construction specifying a precise parse, we use a simpler grammatical definition which yields a forest. If a grammar is both conjunctive and ambiguous, this can lead to its both implicit and explicit conjunctive clauses to be found in SPPFs — with no observable difference on an instance level.
Similarly, some of the transformations will “collapse” conjunctions, making one branch of a clause equal to another. Formally, for an SPPF node to have several branches means existence of several edges in the form hvi; (vi1; :::; viki )i, hvi; (vi01; :::; vi0k0i )i, etc. When a transformation results in all vij becoming equal to the corresponding vi0j , such edges merge in the set. If such conjunctions represent ambiguities, this is disambiguation; if they represent parse views, it merges the views and makes them undistinguishable.
Language preserved
Language extended
Language reduced
Language
revised
XBGF (standing for “transformations of BNF-like grammar formalism”) was
an operator suite for grammar programming originally developed for grammar
recovery and convergence experiments [
The last two operators seen in this cell on Figure 3 are vertical(n) and horizontal(n) — they facilitate switching between a horizontal style of grammatical definitions (i.e., “ A ::= B | C;”) and a vertical one (i.e., “ A ::= B; A ::= C;”) — some grammatical frameworks distinguish between them, but never on an instance level, since a realisation of a disjunction commits to one particular branch. Hence, these operators also have no impact on SPPFs. 3.1.2
In the same way rearranging alternatives in production rules discussed in the previous section, has no impact on SPPFs, strict language extension operators like addV(p) and addH(p) have no impact on the forests. Since disjunctive clauses are not explicitly visible in SPPFs, any tree or forest derived with the original grammar, also conforms to the transformed one — the coupled instance transformation is trivial.
There is even one operator which is very invasive on a grammar level while
being entirely harmless on the instance level — define(p) is a variant of
introduce(p) that adds a definition of a nonterminal that is used in some parts in
the grammar reachable from the top symbol. Having such nonterminals (called
“bottom nonterminals”) in a grammar is not a healthy practice and is in general
considered a sign of bad quality since it signals incompleteness [
ABP AP
AB b+
BC c+
AB b+
BC c+ a+
AB b+
BC c+ AB?
BC?
AB?
BC?
AB?
BC? There are several cases when we do not know in advance whether the cotransformation of SPPFs will be possible: when it is, it is trivial. 3.2.1
The operators removeV(p) and removeH(p) are the counterparts of addV and addH operators we have considered above, which remove alternatives instead of adding them. The effect of such a transformation on a given SPPF is easy to determine: if the alternative which is being removed, is exercised anywhere in the graph, the (co)transformation fails; if it is not, then no update of the forest is required.
Note that since all branches of the conjunctive clause are present in a given SPPF, their removal requires a (possibly failing) refactoring: hence, removeC(p) is considered later in §3.3.2.
The undefine(n) operator takes a valid nonterminal (defined and used within the grammar) and turns it into a bottom nonterminal (used yet not defined). It is a language reducing operator since its effect is a strict decrease in the number of possible correct programs: any parse graph containing a note related to the nonterminal n, becomes invalid. Hence, the coupled transformation for it checks whether such a node is indeed found in the given SPPF: if yes, the transformation fails; if not, it immediately succeeds without updating the SPPF. ABC b+ a+
AB
BC c+ a+
AB b+
BC c+ AB?
BC?
AB?
BC? a ε b ε S ::= ABC & AB c+ & a+ BC; AB ::= a AB? b; BC ::= b BC? c; ABC ::= a+ b+ c+; (a) c In the next subsections we consider cases of less trivial coupled transformations, when language instances have to change to preserve conformance. 3.3.1
Many transformation operators that preserve the language associated with a grammar, still have some impact on the parse graphs. When the impact is easy to calculate in advance and thus encode the coupled transformations as SPPF refactorings that are parametrised in the same way the grammar transformations are, we can run commands like extract(p) on both grammars and SPPFs.
Consider Figure 4(a). It shows a simple grammar of a non-context-free
language fanbncn j n > 0g with three conjunctive views: the first one (a+ b+ c+)
being the most intuitive and hence the most suitable for expressing patterns to
be matched on programs; the remaining two being used to parse the language
(which is well-known to be context-sensitive, so we need the power of two
conjuncts to recognise it precisely). In a sense, the last two conjuncts represent a
recogniser and the first one specifies a parser [
Many other operators of this category from Figure 3 work similarly: chain replaces a node with a chain of two nodes; fold does the same folding we have seen above with extract, but without introducing a new nonterminal and possibly in a limited scope; rassoc and lassoc replace an iterative production rule with a recursive right/left associative one and thus stretches a node with multiple children into an unbalanced binary subtree; concatT and splitT merge or unmerge leaves, etc. 3.3.2
Above we have considered grammar transformation operators that add disjunctive clauses to the grammar, obviously extending the associated language. In the case of extended context-free grammars (regular right hand side grammars) that allow metasyntactic sugar like optionals (x? effectively meaning xj") and regular closures (x+ for transitive and x for reflexive transitive), the widen(e; e0) operator is used to transform x? to x or x to x+, together with the appear(p) operator that transforms " to x? (effectively injecting an optional symbol). The coupled graph transformations for these cases usually boil down to inserting new vertices in the right places in order to keep the structural commitments up to date with the changed grammar.
An even less trivial case of language extension is called “upgrading” and involves replacing a nonterminal by an expression that can be reduced to it. For instance, in A ::= B C; D ::= B|E; we can upgrade B in A (underlined) to D. Such a transformation increases the string language associated with a grammar, as well as rearranges the relations between nonterminals. The coupled transformation for SPPF is still simple and inserts an extra vertex for D between A and B (E is still not present in the SPPF).
The removeC(p) operator that eliminates a conjunct, formally also increases the underlying language since any extra conjunct is possibly an extra condition to be met, and dropping it makes the combination weaker. Technically the coupled SPPF transform that removes a conjunct is a disambiguation filter, but it is not useful to count it as such since the ambiguity being removed is explicit (recall §2.4). 3.3.3
The disappear(p) operator is used to transform x? or x to ". The coupled transformation on SPPFs for it exists, but is completely different from the ones being considered so far: it is inherently irreversible since if the SPPF in question actually contains the x? with x as a child node, then that x is removed and lost. This is contrasting to folding/unfolding vertices and rearranging the edges around them. 3.3.4
The operators abstractize(p) and concretize(p) eliminate and introduce terminals from production rules (a common practice when mapping abstract syntax to concrete syntax, hence the names). Since the terminals are present explicitly in the arguments, we can easily implement our coupled SPPF transformations by inserting leaves and connecting them to the appropriate places to the graph, or removing them. These transformations can have a big effect on the SPPF and are therefore more similar to the coupled transform from the previous paragraph. The project operator is a stronger version of abstractize or disappear that works on any symbol, but the transformation coupled with it, is the same: locate all the parts being removed from the grammar, remove them from the graph.
The rest of language revising operators are coupled with less invasive rearrangements of the parse graph: reordering edges (permute), updating the contents of the leaves (renameT) and splitting one nonterminal into several (splitN). 3.4
Cotransformations from the previous section were necessary but could never fail: they were applicable to all possible graphs. Let us now move on to cotransformations that could seem successful on the grammar level but fail on the instance level (causing the combination to fail). 3.4.1
The narrow operator (the reverse of widen discussed above) and the downgrade operator (the reverse of upgrade) become simple parse graph rearrangements, if the constructs in the SPPF happen to correspond to the new grammar, and fail otherwise. For instance, if a “wider” option is found in the SPPF, we have no automated way to update it.
The addC operator, on the other hand, shows us yet another class of coupled
transforms: namely, the one requiring reparsing. Indeed, if the first branch of the
conjunctive clause of S from Figure 4 were to be introduced as a
transformation step, we would need to reconnect the left subnode of S to the appropriate
children, which formally corresponds to parsing. In the current prototype
implementation we reuse the existing parser — to the best of our knowledge, other
frameworks like TXL [
Interestingly, there is one particular operator that is always doomed: inject(p) that works like appear but can insert any symbol anywhere in the grammar. In order to construct a coupled SPPF transformation for inject, we need to know how to connect the new node to its children, but this information is ultimately lacking from the operator parameters. The only cases where it could have worked, are already covered by other operators (e.g., injecting terminals is concretize, injecting possibly empty symbols is appear). 4
As said before, we are not the only ones trying to use computation models based
on graphs instead of trees in software language engineering. It remains to be seen
whether systematically using abstract syntax graphs [
Our approach to couple instance transformations to grammar
transformations and not vice versa has its counterparts in other technological spaces such
as modelware [
Grammar mutations [
The classification of coupled SPPF transformations from Figure 3
corresponds to the two kinds of negotiated evolution: “adaptation through
tolerance” when SPPFs are preserved and “through adjustment” when they are
refactored [
There is a lot of work on disambiguation, parse forest pruning and
shaving, and it remains to be seen whether our approach can usefully complement
similarly-minded techniques from that area such as van den Brand et al [
SPPF transformations could possibly be represented formally as classical
graph replacement systems that rewrite nodes [
In this paper, we have considered coupled transformations of grammars together with shared packed parse forests defined by these grammars. An implementation of a transformation operator suite was proposed. Each grammar change was coupled to one of the following: (1) no change in the parse graphs; (2) rearranging the graphs; (3) introducing new elements to graphs based on operator arguments; (4) reparsing; (5) imminent failure. This classification is complementary to the previously existing ones based on preserving, increasing, reducing or revising the semantics chosen for the grammar.
The examples given in the paper mostly refer to concrete grammars in the context of parsing, but the research was done with software language engineering principles, which means that the contribution is applicable to coupled evolution of grammars as well as ontologies, API, DSLs, XML schemata, libraries, etc. We have used Boolean grammars as the underlying formalism due to their power to represent non-context-free languages, ambiguous generalised parses and parse views in a uniform way. This is the first project involving coupled transformations of Boolean grammars.
The computation model proposed in this paper, can be used for formalisations and proofs of certain properties of transformation chains; for grammar-based convergence; for manipulating parse views and in general for tasks involving synchronous consistent changes to Boolean grammars and shared packed parse forests. This is an area of rapidly growing interest in the software language engineering community, and its limits, as well as the extent of its usefulness, remains to be examined.