xbgf.xsd

<xsd:schema
  xmlns:xsd="http://www.w3.org/2001/XMLSchema"
  xmlns:bgf="http://planet-sl.org/bgf"
  xmlns:xbgf="http://planet-sl.org/xbgf"
  targetNamespace="http://planet-sl.org/xbgf">

  <xsd:annotation>
  <xsd:documentation>
    BGF transformation operator suite
  </xsd:documentation>
  <xsd:documentation>
    This chapter describes the transformational suite for BGF and all the details about it.
  </xsd:documentation>
  </xsd:annotation>

  <xsd:import namespace="http://planet-sl.org/bgf" schemaLocation="bgf.xsd"/>

  <xsd:element name="sequence">
    <xsd:annotation>
      <xsd:documentation>
        Sequential composition of multiple transformations.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:group ref="xbgf:transformation" minOccurs="0" maxOccurs="unbounded"/>
    </xsd:complexType>
  </xsd:element>

  <xsd:group name="transformation">
    <xsd:annotation>
      <xsd:documentation>
        Here is a grouped list of all the XBGF transformations.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:choice>
      <xsd:group ref="xbgf:foldingtransformation"/>
      <xsd:group ref="xbgf:refactoringtransformation"/>
      <xsd:group ref="xbgf:increasingtransformation"/>
      <xsd:group ref="xbgf:decreasingtransformation"/>
      <xsd:group ref="xbgf:concreterevisingtransformation"/>
      <xsd:group ref="xbgf:abstractrevisingtransformation"/>
      <xsd:group ref="xbgf:decorativetransformation"/>
      <!-- status unclear -->
      <xsd:element ref="xbgf:reroot"/>
      <!-- debug -->
      <xsd:element ref="xbgf:dump"/>
      <!-- semantics unclear -->
      <xsd:element ref="xbgf:rename"/>
      <!-- deprecated -->
      <xsd:element ref="xbgf:strip"/>
    </xsd:choice>
  </xsd:group>

  <xsd:group name="foldingtransformation">
    <xsd:annotation>
      <xsd:documentation>
        Folding and unfolding activities are the most basic ones in grammar
        transformation and the most used ones in grammar convergence. Since
        grammar comparison is done in such a way that only applies very basic
        algebraic laws in its endeavours to match the two grammars, many
        more sophisticated manipulations need to be executed semi-automatically
        in a programmable fashion. These manual steps help to establish a
        stronger link between the convergence point and the original grammar
        artifact since they aid to reveal some unapparent properties of those
        grammars.
      </xsd:documentation>
      <xsd:documentation>
        All these transformations are provably correct in the sense that
        it is possible to prove that the languages generated by the grammars
        before the transformation and after it are indeed the same. All
        refactorings are easily reversible and usually introduced below in
        pairs.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:choice>
      <xsd:element ref="xbgf:unfold"/>
      <xsd:element ref="xbgf:fold"/>
      <xsd:element ref="xbgf:inline"/>
      <xsd:element ref="xbgf:extract"/>
      <xsd:element ref="xbgf:abridge"/>
      <xsd:element ref="xbgf:detour"/>
      <xsd:element ref="xbgf:unchain"/>
      <xsd:element ref="xbgf:chain"/>
    </xsd:choice>
  </xsd:group>
  <xsd:group name="refactoringtransformation">
    <xsd:annotation>
      <xsd:documentation>
        Here is a list of the XBGF transformations that perform
        other provably semantic-preserving refactorings
      </xsd:documentation>
    </xsd:annotation>
    <xsd:choice>
      <xsd:element ref="xbgf:massage"/>
      <xsd:element ref="xbgf:factor"/>
      <xsd:element ref="xbgf:distribute"/>
      <xsd:element ref="xbgf:deyaccify"/>
      <xsd:element ref="xbgf:yaccify"/>
      <xsd:element ref="xbgf:eliminate"/>
      <xsd:element ref="xbgf:introduce"/>
      <xsd:element ref="xbgf:import"/>
      <xsd:element ref="xbgf:vertical"/>
      <xsd:element ref="xbgf:horizontal"/>
      <xsd:element ref="xbgf:rassoc"/>
      <xsd:element ref="xbgf:lassoc"/>
    </xsd:choice>
  </xsd:group>
  <xsd:group name="increasingtransformation">
    <xsd:annotation>
      <xsd:documentation>
        Here is a list of the XBGF transformations that
        lenghten the grammar (increase semantics).
      </xsd:documentation>
    </xsd:annotation>
    <xsd:choice>
      <xsd:element ref="xbgf:add"/>
      <xsd:element ref="xbgf:appear"/>
      <xsd:element ref="xbgf:widen"/>
      <xsd:element ref="xbgf:upgrade"/>
      <xsd:element ref="xbgf:unite"/>
    </xsd:choice>
  </xsd:group>
  <xsd:group name="decreasingtransformation">
    <xsd:annotation>
      <xsd:documentation>
        Here is a list of the XBGF transformations that
        shorten the grammar (decrease semantics).
      </xsd:documentation>
    </xsd:annotation>
    <xsd:choice>
      <xsd:element ref="xbgf:remove"/>
      <xsd:element ref="xbgf:disappear"/>
      <xsd:element ref="xbgf:narrow"/>
      <xsd:element ref="xbgf:downgrade"/>
    </xsd:choice>
  </xsd:group>
  <xsd:group name="concreterevisingtransformation">
    <xsd:annotation>
      <xsd:documentation>
        We may refer to the semantics of a grammar as the language (set of strings)
        generated by the grammar, as it is common for formal languages --- for
        context-free grammars, in particular. With the string-oriented semantics
        in mind, all transformations mentioned above in folding and refactoring
        sections are semantics-preserving. To give an example where different
        semantics are needed consider the scenario of aligning a concrete and
        an abstract syntax.
      </xsd:documentation>
      <xsd:documentation>
        When necessary, we may apply the algebraic interpretation of a grammar, where
        grammar productions constitute an algebraic signature subject to a term-algebraic model.
        In this case, the terminal occurrences in any given production do no longer carry
        semantic meaning; they are part of the function symbol. (Hence, abstract and concrete
        syntaxes can be aligned now.)
      </xsd:documentation>
      <xsd:documentation>
        Some transformations that were effortlessly semantics-preserving w.r.t.
        the string-oriented semantics, require designated bijective mappings
        w.r.t. the term-oriented semantics, e.g., fold/unfold manipulations,
        but generally, the term-oriented semantics admits a larger class of
        semantics-preserving transformations than the string-oriented one.
      </xsd:documentation>
      <xsd:documentation>
        The following section gathers those transformations that would have been
        considered refactorings if we only used term-oriented semantics. From
        the string-oriented point of view they revise semantics and can be deemed
        as neither grammar lenghtening nor grammar shortening transformations.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:choice>
      <xsd:element ref="xbgf:abstractize"/>
      <xsd:element ref="xbgf:concretize"/>
      <xsd:element ref="xbgf:permute"/>
    </xsd:choice>
  </xsd:group>
  <xsd:group name="abstractrevisingtransformation">
    <xsd:annotation>
      <xsd:documentation>
        Some grammar differences may require more arbitrary replacements,
        that cannot be expressed as semantics-preserving even in abstract
        syntax. These include projections or injections of non-optional
        nonterminals, adding definitions for bottom nonterminals,
        performing volatile replacements.
      </xsd:documentation>
      <xsd:documentation>
        Whenever a transformation from this group is used in a conergence
        path, it signals either about a construction point where the grammar
        engineer is having a temporary shortcut to be substituted later
        with a longer sequence of more accurate manipulations, or an inevitable
        error in the BGF that needs fixing (preferably in the original
        artifact---specification, compiler sources, etc).
      </xsd:documentation>
    </xsd:annotation>
    <xsd:choice>
      <xsd:element ref="xbgf:define"/>
      <xsd:element ref="xbgf:undefine"/>
      <xsd:element ref="xbgf:redefine"/>
      <xsd:element ref="xbgf:inject"/>
      <xsd:element ref="xbgf:project"/>
      <xsd:element ref="xbgf:replace"/>
    </xsd:choice>
  </xsd:group>
  <xsd:group name="decorativetransformation">
    <xsd:annotation>
      <xsd:documentation>
        Last but not least, there are two pairs of refactorings that are
        very specific to the BGF itself. Not all grammar definition formalisms
        have labelled productions, but since we do, we also need two transformation
        steps made possible: to designate an already available production with a
        label, and to unlabel an existing labelled production. By anonymising
        we refer to stripping selectors from subexpressions, and by deanonymising,
        naturally, adding selectors.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:choice>
      <xsd:element ref="xbgf:designate"/>
      <xsd:element ref="xbgf:unlabel"/>
      <xsd:element ref="xbgf:anonymize"/>
      <xsd:element ref="xbgf:deanonymize"/>
    </xsd:choice>
  </xsd:group>

  <xsd:element name="add">
    <xsd:annotation>
      <xsd:documentation>
        Nonterminal definitions can be extended ("added to") vertically
        and horizontally. In the former case, a given production is added
        to an existing definition. In the latter case, a given branch is
        added to a given expression. The
        horizontal mode is there for convenience only because it could be
        simulated by a sequence of extraction, vertical addition, and
        inlining. There are two operators that are very similar to the
        (vertical) add operator: define and introduce. The define operator
        should be used when an the definition of an undefined nonterminal
        is added. The introduce operator should be used when a fresh
        nonterminal is to be defined.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:choice>
        <xsd:element name="vertical">
          <xsd:complexType>
            <xsd:sequence>
             <xsd:element ref="bgf:production"/>
            </xsd:sequence>
          </xsd:complexType>
        </xsd:element>
        <xsd:element name="horizontal">
          <xsd:complexType>
            <xsd:sequence>
             <xsd:element ref="bgf:production"/>
            </xsd:sequence>
          </xsd:complexType>
        </xsd:element>
      </xsd:choice>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="appear">
    <xsd:annotation>
      <xsd:documentation>
        An appear transformation takes a production as an input. Inside that production,
        one subexpression should be marked. The marked expression must be nillable, i.e.,
        reducible to an empty sequence.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="chain">
    <xsd:annotation>
      <xsd:documentation>
        Just like unchain is a specific form of inline,
        chaining is a disciplined form of extraction. The argument
        production will be part of the resulting grammar; it is a chain
        production, i.e., a production with a nonterminal as its defining
        expression. That nonterminal is the one whose definition is to be
        extracted. That definition is the defining expression of the
        production (from the input grammar) whose defined nonterminal and
        label (if any) matches with the argument production.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="deanonymize">
    <xsd:annotation>
      <xsd:documentation>
        Adding a selector to the existing production.
        Selectors must be introduced one at a time, and the one being introduced needs to be marked.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="define">
    <xsd:annotation>
      <xsd:documentation>
        An undefined nonterminal is resolved. The nonterminal must be in
        use. The introduce operator should be used when a fresh nonterminal
        is to be defined. The add operator should be used when an existing
        definition is to be extended.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production" maxOccurs="unbounded"/>
      </xsd:sequence>
      <xsd:attribute name="tag" type="xsd:string"/>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="disappear">
    <xsd:annotation>
      <xsd:documentation>
        As project, but only allows for nillable elements (optional, star) to disappear.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="downgrade">
    <xsd:annotation>
      <xsd:documentation>
        Replaces a nonterminal with one of its definitions.
        The first parameter is the scope production with one of the nonterminals marked.
        The second parameter is one of that nonterminal's definitions,
        which right hand side will be used for replacement.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production"/>
        <xsd:element ref="bgf:production"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="designate">
    <xsd:annotation>
      <xsd:documentation>
        An unlabeled production is labeled. The argument production is
        the intended result, i.e., the labeled production.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="unlabel">
    <xsd:annotation>
      <xsd:documentation>
        Strips an existing production from a label.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element name="label" type="bgf:label"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="deyaccify" type="bgf:nonterminal">
    <xsd:annotation>
      <xsd:documentation>
        The definition of the given nonterminal is deyaccified.
        That is, its definition is replaced by one that uses
        regular expression operators instead of epsilon, choice,
        and recursion. Both left- and right-recursive forms
        can be factored with this transformation.
      </xsd:documentation>
    </xsd:annotation>
  </xsd:element>

  <xsd:element name="distribute">
    <xsd:annotation>
      <xsd:documentation>
        Distribute sequential composition over choices so that choices
        are pulled out of sequences. The transformation
        is either attempted for all productions of a nonterminal or for a
        specific one appointed by its label.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:choice>
        <xsd:group ref="xbgf:scope"/>
        <xsd:element ref="bgf:production"/>
      </xsd:choice>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="dump">
    <xsd:annotation>
      <xsd:documentation>
        A debugging tool.
        Upon arrival at current transformation, the input grammar is dumped.
        See the file xbgf.log.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType/>
  </xsd:element>

  <xsd:element name="eliminate" type="bgf:nonterminal">
    <xsd:annotation>
      <xsd:documentation>
        An unused definition (at most used within the definition itself)
        is removed. The undefine operator should be used instead when
        the definition must be remove despite remaining uses. The
        remove operator should be used instead when only part of the
        definition (i.e., a production of a vertical definition) is
        to be removed.
      </xsd:documentation>
    </xsd:annotation>
  </xsd:element>

  <xsd:element name="extract">
    <xsd:annotation>
      <xsd:documentation>
        A new definition is introduced by extraction. The argument provided for this transformation
        is a production that identifies both the fresh nonterminal to be introduced and the
        expression that is used both as a pattern for folding and as a right hand side of
        the added definition.
        An optional scope can limit the application
        of the folding part of the extraction transformation to a
        specific production or a specific nonterminal.
      </xsd:documentation>
      <xsd:documentation>
        If the nonterminal defined by the argument production is
        already mentioned (i.e., defined or referenced) in the current
        grammar, the transformation refuses to work and reports an
        error. This usually signals an error in the language engineer's
        logic because the existing traces of a possibly similar nonterminal
        conflict with the definition that is being introduced.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production"/>
        <xsd:element name="in" minOccurs="0">
          <xsd:complexType>
            <xsd:group ref="xbgf:scope"/>
          </xsd:complexType>
        </xsd:element>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="factor">
    <xsd:annotation>
      <xsd:documentation>
        Massage modulo factorization over choices. The transformation
        is either attempted for all productions of a nonterminal or for a
        specific one appointed by its label.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:expression"/>
        <xsd:element ref="bgf:expression"/>
        <xsd:element name="in" minOccurs="0">
          <xsd:complexType>
            <xsd:group ref="xbgf:scope"/>
          </xsd:complexType>
        </xsd:element>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="fold">
    <xsd:annotation>
      <xsd:documentation>
        Folding replaces every expression that matches with the right hand
        side of the given nonterminal's definition with the nonterminal
        itself. As with unfold, fold works on the scope of the grammar,
        but its impact can be limited to one labelled production or to
        all the productions belonging to one nonterminal. Regardless
        of the specified scope, folding is not applied to the definition
        of the argument nonterminal.
      </xsd:documentation>
      <xsd:documentation>
        Since this transformation strives to preserve the language, it needs
        a horisontal definition to work. When only one of several existing
        definitions is used for folding, it actually increases the semantics
        of the language after transformation---the corresponding XBGF command
        is called upgrade.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element name="nonterminal" type="bgf:nonterminal"/>
        <xsd:element name="in" minOccurs="0">
          <xsd:complexType>
            <xsd:group ref="xbgf:scope"/>
          </xsd:complexType>
        </xsd:element>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="horizontal" type="bgf:nonterminal">
    <xsd:annotation>
      <xsd:documentation>
        Turn a definition based on multiple productions into a choice-based one.
      </xsd:documentation>
    </xsd:annotation>
  </xsd:element>

  <xsd:element name="inject">
    <xsd:annotation>
      <xsd:documentation>
        The argument production defines the intended result of the
        transformation -- a production that has additional components
        in the sequential composition, when compared to the correpsonding
        production in the input grammar with the same defined nonterminal
        and the same label, if any.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:choice>
        <xsd:element ref="bgf:production"/>
      </xsd:choice>
      <xsd:attribute name="tag" type="xsd:string"/>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="inline" type="bgf:nonterminal">
    <xsd:annotation>
      <xsd:documentation>
        When this transformation is performed, an existing definition is eliminated by inlining.
        This means that the argument nonterminal identifies the (horisontal) definition
        that is to be unfolded and stripped away from the grammar.
      </xsd:documentation>
      <xsd:documentation>
        The impact of inline is that of a pair of unfold and eliminate.
      </xsd:documentation>
    </xsd:annotation>
  </xsd:element>

  <xsd:element name="introduce">
    <xsd:annotation>
      <xsd:documentation>
        A definition of a fresh nonterminal is added. The add operator
        should be used instead, if the nonterminal is already defined,
        is to be merely extended. The define operator should be used
        instead, if the nonterminal is readily in use, but merely lacks
        a definition.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production" maxOccurs="unbounded"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="import">
    <xsd:annotation>
      <xsd:documentation>
        Allows to import another grammar: the nonterminals within it can
        refer to one another, but none of the existing productions are allowed
        to refer to them before this transformation takes place.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production" maxOccurs="unbounded"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="lassoc">
    <xsd:annotation>
      <xsd:documentation>
        The argument production is expected result of the transformation.
        Its defining expression involves a pattern of binary recursion
        with regard to the defined nonterminal. The argument production
        replace a production with the same defined nonterminal and label,
        if any, assuming that the defining expression uses an equivlent,
        repeating expression form. The "l" in "lassoc" refers to the
        intended effect at the level of derivation trees: the list of
        subtrees is to be converted into a nested binary tree in a
        left-associative manner.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:choice>
        <xsd:element ref="bgf:production"/>
      </xsd:choice>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="massage">
    <xsd:annotation>
      <xsd:documentation>
        The grammar is rewritten by local transformations such that
        the language generated by the grammar (or the denotation according
        to any other semantics for that matter) is preserved. The known
        rewriting rules affect the use of selectors and regular expression
        operators: e.g., any symbol will always generate the same set of strings
        that the same symbol wrapped in a selector.
      </xsd:documentation>
      <xsd:documentation>
        There are two expression arguments: one to be matched,
        and another one that replaces the matched expression.
        One of them must be in a `massage relation' to the other.
      </xsd:documentation>
      <xsd:documentation>
        The scope of
        the transformation can be limited.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:expression"/>
        <xsd:element ref="bgf:expression"/>
        <xsd:element name="in" minOccurs="0">
          <xsd:complexType>
            <xsd:group ref="xbgf:scope"/>
          </xsd:complexType>
        </xsd:element>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="narrow">
    <xsd:annotation>
      <xsd:documentation>
        The grammar is rewritten by local transformations such that
        the language generated by the grammar (or the denotation according
        to any other semantics for that matter) is decreased. The known
        rewriting rules affect the use of epsilon and regular expression
        operators. There are two expression arguments: one to be matched,
        and another one that replaces the matched expression. The scope of
        the transformation can be limited.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:expression"/>
        <xsd:element ref="bgf:expression"/>
        <xsd:element name="in" minOccurs="0">
          <xsd:complexType>
            <xsd:group ref="xbgf:scope"/>
          </xsd:complexType>
        </xsd:element>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="permute">
    <xsd:annotation>
      <xsd:documentation>
        The argument production defines the intended result of the
        transformation -- a production that has the same components
        in the sequential composition, but in a different order, when
        compared to the correpsonding production in the input grammar
        with the same defined nonterminal and the same label, if any.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:choice>
        <xsd:element ref="bgf:production"/>
      </xsd:choice>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="project">
    <xsd:annotation>
      <xsd:documentation>
        The argument production defines the intended result of the
        transformation -- a production that has fewer components
        in the sequential composition, when compared to the correpsonding
        production in the input grammar with the same defined nonterminal
        and the same label, if any.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:choice>
        <xsd:element ref="bgf:production"/>
      </xsd:choice>
      <xsd:attribute name="tag" type="xsd:string"/>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="rassoc">
    <xsd:annotation>
      <xsd:documentation>
        The argument production is expected result of the transformation.
        Its defining expression involves a pattern of binary recursion
        with regard to the defined nonterminal. The argument production
        replace a production with the same defined nonterminal and label,
        if any, assuming that the defining expression uses an equivlent,
        repeating expression form. The "r" in "rassoc" refers to the
        intended effect at the level of derivation trees: the list of
        subtrees is to be converted into a nested binary tree in a
        right-associative manner.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:choice>
        <xsd:element ref="bgf:production"/>
      </xsd:choice>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="redefine">
    <xsd:annotation>
      <xsd:documentation>
        A replace variant that works on production level. When this
        transformation is executed, all current productions for the
        nonterminal are dropped, and all the given ones are added
        to the grammar.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production" maxOccurs="unbounded"/>
      </xsd:sequence>
      <xsd:attribute name="tag" type="xsd:string"/>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="remove">
    <xsd:annotation>
      <xsd:documentation>
        Productions can be removed from existing, vertical definitions.
        The remaining definition must not become empty, i.e., undefined.
        There is the undefine operator that can be applied in that case.
        There is also a horizontal mode of removing branches from choices.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:choice>
        <xsd:element name="vertical">
          <xsd:complexType>
            <xsd:sequence>
             <xsd:element ref="bgf:production"/>
            </xsd:sequence>
          </xsd:complexType>
        </xsd:element>
        <xsd:element name="horizontal">
          <xsd:complexType>
            <xsd:sequence>
             <xsd:element ref="bgf:production"/>
            </xsd:sequence>
          </xsd:complexType>
        </xsd:element>
      </xsd:choice>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="rename">
    <xsd:annotation>
      <xsd:documentation>
        Labels, nonterminals, selectors and terminals can be renamed.
        Being in line with the fundamental notion of renaming, such
        renaming must be done consistently throughout the entire grammar,
        without introducing any clashes. There is one justifiable
        exception. That is, arguably, the scope of selectors is the
        level of production as opposed to necessarily the entire grammar.
        Hence, selectors can be renamed in such a scope, optionally.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:choice>
        <xsd:element name="label">
          <xsd:complexType>
            <xsd:sequence>
              <xsd:element name="from" type="bgf:label"/>
              <xsd:element name="to" type="bgf:label"/>
            </xsd:sequence>
          </xsd:complexType>
        </xsd:element>
        <xsd:element name="nonterminal">
          <xsd:complexType>
            <xsd:sequence>
              <xsd:element name="from" type="bgf:nonterminal"/>
              <xsd:element name="to" type="bgf:nonterminal"/>
            </xsd:sequence>
          </xsd:complexType>
        </xsd:element>
        <xsd:element name="selector">
          <xsd:complexType>
            <xsd:sequence>
              <xsd:element name="in" minOccurs="0" type="bgf:label"/>
              <xsd:element name="from" type="bgf:selector"/>
              <xsd:element name="to" type="bgf:selector"/>
            </xsd:sequence>
          </xsd:complexType>
        </xsd:element>
        <xsd:element name="terminal">
          <xsd:complexType>
            <xsd:sequence>
              <xsd:element name="from" type="bgf:terminal"/>
              <xsd:element name="to" type="bgf:terminal"/>
            </xsd:sequence>
          </xsd:complexType>
        </xsd:element>
      </xsd:choice>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="replace">
    <xsd:annotation>
      <xsd:documentation>
        This operator provides a last resort to grammar editing. It
        basically provides access to free editing without any semantically
        meaningful preconditions. There are two expression arguments:
        one to be matched, and another one that replaces the matched
        expression. The scope of the transformation can be limited.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:expression"/>
        <xsd:element ref="bgf:expression"/>
        <xsd:element name="in" minOccurs="0">
          <xsd:complexType>
            <xsd:group ref="xbgf:scope"/>
          </xsd:complexType>
        </xsd:element>
      </xsd:sequence>
      <xsd:attribute name="tag" type="xsd:string"/>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="reroot">
    <xsd:annotation>
      <xsd:documentation>
        Redefine the roots (start symbols) of the grammar.
        The empty set of roots is interpreted to abbreviate the
        complete set of nonterminals used or defined by a grammar.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element name="root" type="bgf:nonterminal" minOccurs="0" maxOccurs="unbounded"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="abridge">
    <xsd:annotation>
      <xsd:documentation>
        Given a reflexive chain production, i.e., a production whose
        defined nonterminal equals its body, this production is simply
        removed from the grammar, even if it contains some potentially
        valuable information (like labels and selectors).
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="detour">
    <xsd:annotation>
      <xsd:documentation>
        A reverse of abridge that can introduce a reflexive chain production.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="strip">
    <xsd:annotation>
      <xsd:documentation>
        Various details of productions can be stripped with this transformation.
        In detail, one can strip labels, terminals, and selectors.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:choice>
        <xsd:element name="label" type="bgf:label">
          <xsd:annotation>
            <xsd:documentation>
              Stripping a label means that a production that uses the
              label becomes unlabeled.
            </xsd:documentation>
          </xsd:annotation>
        </xsd:element>
        <xsd:element name="allLabels">
          <xsd:annotation>
            <xsd:documentation>
              Stripping all labels means that all productions become unlabeled.
            </xsd:documentation>
          </xsd:annotation>
          <xsd:complexType/>
        </xsd:element>
        <xsd:element name="selector" type="bgf:selector">
          <xsd:annotation>
            <xsd:documentation>
              Stripping a selector s means that any occurrence of the
              selector disappears.
            </xsd:documentation>
          </xsd:annotation>
        </xsd:element>
        <xsd:element name="allSelectors">
          <xsd:annotation>
            <xsd:documentation>
              Stripping all selectors.
            </xsd:documentation>
          </xsd:annotation>
          <xsd:complexType/>
        </xsd:element>
        <xsd:element name="terminal" type="bgf:terminal">
          <xsd:annotation>
            <xsd:documentation>
              Stripping a terminal means that any occurrence of the
              terminal disappears as if the terminal denoted epsilon.
            </xsd:documentation>
          </xsd:annotation>
        </xsd:element>
        <xsd:element name="allTerminals">
          <xsd:annotation>
            <xsd:documentation>
              Stripping all terminals.
            </xsd:documentation>
          </xsd:annotation>
          <xsd:complexType/>
        </xsd:element>
      </xsd:choice>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="concretize">
    <xsd:annotation>
      <xsd:documentation>
        As inject, but works only with terminals.
      </xsd:documentation>
      <xsd:documentation>
        Terminalize breaks concrete, but not abstract, semantics.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:choice>
        <xsd:element ref="bgf:production"/>
      </xsd:choice>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="unchain">
    <xsd:annotation>
      <xsd:documentation>
        Unchaining is a disciplined form of inlining. The argument
        production must occur in the input grammar, and it must be a chain
        production, i.e., a production with a nonterminal as its
        defining expression. The latter nonterminal is the one whose
        definition is to be inlined; it must not have any occurrences
        except in the chain production at hand.
      </xsd:documentation>
      <xsd:documentation>
        The unchain transformation does not increase the expressivity nor
        the power of the transformational language: technically, it is
        nothing more than an inline with a precondition. However, this
        particular precondition seems useful and not uncommon when dealing
        with layered grammars.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:choice>
        <xsd:element ref="bgf:production"/>
      </xsd:choice>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="undefine">
    <xsd:annotation>
      <xsd:documentation>
        Undefine a nonterminal, i.e., remove all productions. The
        nonterminal must have using occurrences elsewhere than just in
        its own definition. If there are no such using occurrences, then
        the less disruptive eliminate operator is to be used.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:simpleContent>
        <xsd:extension base="bgf:nonterminal">
          <xsd:attribute name="tag" type="xsd:string"/>
        </xsd:extension>
      </xsd:simpleContent>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="unfold">
    <xsd:annotation>
      <xsd:documentation>
        The most basic unfolding transformation searches for all the instances
        of the given nonterminal usage and replaces such occurrences with the
        defining expression of that nonterminal. By default the scope of the
        transformation is the full grammar, but it can be limited to all the
        definitions of one nonterminal or to one labelled definition. Regardless
        of the specified scope, unfolding is not applied to the definition
        of the argument nonterminal.
      </xsd:documentation>
      <xsd:documentation>
        The definition that is being unfolded is assumed to be horisontal
        (see the section on refactorings for more information about horisontal
        and vertical definitions).
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element name="nonterminal" type="bgf:nonterminal"/>
        <xsd:element name="in" minOccurs="0">
          <xsd:complexType>
            <xsd:group ref="xbgf:scope"/>
          </xsd:complexType>
        </xsd:element>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="unite">
    <xsd:annotation>
      <xsd:documentation>
        Two nonterminals, say x and y, are merged (possibly recursively).
        That is, the definitions of x and y (i.e., their productions)
        are merged in one definition while preserving the nonterminal y
        and replacing all occurrences of x (in the definition of x and
        anywhere else) by y.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element name="add" type="bgf:nonterminal"/>
        <xsd:element name="to" type="bgf:nonterminal"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="abstractize">
    <xsd:annotation>
      <xsd:documentation>
        As project, but works only with terminals.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="anonymize">
    <xsd:annotation>
      <xsd:documentation>
        Removes one (marked) selector from an existing definition.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="vertical">
    <xsd:annotation>
      <xsd:documentation>
        Turn top-level choices into multiple productions. The transformation
        is either attempted for all productions of a nonterminal or for a
        specific one appointed by its label.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:group ref="xbgf:scope"/>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="widen">
    <xsd:annotation>
      <xsd:documentation>
        The grammar is rewritten by local transformations such that
        the language generated by the grammar (or the denotation according
        to any other semantics for that matter) is increased. The known
        rewriting rules affect the use of epsilon and regular expression
        operators. There are two expression arguments: one to be matched,
        and another one that replaces the matched expression. The scope of
        the transformation can be limited.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:expression"/>
        <xsd:element ref="bgf:expression"/>
        <xsd:element name="in" minOccurs="0">
          <xsd:complexType>
            <xsd:group ref="xbgf:scope"/>
          </xsd:complexType>
        </xsd:element>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="yaccify">
    <xsd:annotation>
      <xsd:documentation>
        The given production is a horizontal definition of an optional
        or repeating nonterminal, given in BNF-only expressiveness. The
        defined nonterminal must be equivalently defined in EBNF-like
        expressiveness in the input grammar. One may often wish to use
        extract to first introduce a nonterminal for the optional or
        repeating phrase.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production" maxOccurs="unbounded"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:element name="upgrade">
    <xsd:annotation>
      <xsd:documentation>
        Replaces an expression by a nonterminal that can be evaluated to it.
        The first parameter is the scope production with an expression marked.
        The second parameter is one of that nonterminal's definitions,
        which right hand side equals that expression.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element ref="bgf:production"/>
        <xsd:element ref="bgf:production"/>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

  <xsd:group name="scope">
    <xsd:annotation>
      <xsd:documentation>
        Several transformation operators are possibly restricted to
        a specific scope as opposed to their application to the full
        input grammar. Two major forms of scope can be identified.
        First, a production can be appointed by its label. Second, a
        definition (nonterminal) can be appointed by its defined
        nonterminal. Arguably, one may want to be able to appoint a
        production even when it is not labeled, but a prior designate
        transformation can then be used in order to attach a label
        to the production in question.
      </xsd:documentation>
    </xsd:annotation>
    <xsd:choice>
      <xsd:element name="label" type="bgf:label"/>
      <xsd:element name="nonterminal" type="bgf:nonterminal"/>
    </xsd:choice>
  </xsd:group>

</xsd:schema>