We need a means to annotate a Jacc grammar so as to ease and automate the process of specifying an XML serialization for the language defined by the grammar. The way we proceed is by annotating some rules and terminals to produce an XML form built out of those XML forms built for the constituents of the CST (i.e., from a terminal's contents or a rule's RHS).

This specifies a grammar for a simple annotation language meant to enable passing XML formatting information from a Jacc grammar to a Jacc parser. This defines the form of what goes between square bracketed arguments of the xmlinfo command annotating a terminal, or appearing in a rule being annotated for XML conversion (i.e., for serialization purposes). Doing this gives us great flexibility for extending or modifying the annotation meta-syntax simply by:

1. modifying the Jacc grammar source file,
2. running the jacc command on it to regenerate the XmlAnnotationParser java source, and
3. recompiling.

Specification

Basic annotation notation

In order for the parser of the annotation notation to stay small and light-weight, as well as avoiding ambiguity and stay strictly within LALR(1) recognition power, we will adopt the following very simple keyword-driven syntax. For example:

  A0 : A1 A2 A3 A4 
     [
       nsprefix   : "foo"
       localname  : "Azero"
       attributes : {a = "bar blah", b="blech"}
       children   : (2, 3)
     ] 
     ;
  

  <foo:Azero a="bar blah" b="blech">
    xmlification of A2
    xmlification of A3
  </foo:Azero>
  

        nsprefix
        localname
        attributes
        children
  

N.B.: The annotation is meant to be light-weight - all these keywords may be abbreviated to any non-empty case-insensitive prefix of their full form, and some punctuation may be used interchangeably or simply omitted: e.g., the ":" separating keywords and values, the "," separating list elements, as well as unnecessary quotes, are all in fact optional. The following key/value separator symbols may be used: ":", "=", "->", "=>", or they may be simply omitted. Similarly, the following list separator symbols may be used: "," (comma), ";" (semicolon), or they may be simply omitted. See the associate tokenizer class: XmlAnnotationTokenizer.java for details.

For example, the above same annotation could equally be written as follows:

  A0 : A1 A2 A3 A4 
     [
       NS foo
       LO Azero
       AT {a -> 'bar blah';  b -> blech}
       CH (2 3)
     ]
     ;
  

More complex annotation notation

A more elaborate XML annotation notation extends the above basic notation by allowing the values of attributes and children in the annotation to take on more complex forms denoting a reference to the desired XML constructs within the XML trees already built for the CST children of this node. Following are some simple color-coded examples illustrating the meaning of these annotations, showing how the basic notation for homomorphic tree-transduction annotations for attribute and children is extended to express heteromorphic tree-transduction as well.

Children annotation:

• Basic children annotation notation:

    CH:(2, 4)
    

  specifies that the XML children are, in this order:
  1. XML form of 2^nd child CST,
  2. XML form of 4^th child CST.

• Extended children annotation notation:

  • Granchildren notation:

      CH:(2[1], 4[2])
      

    specifies that the XML children are, in this order:
    1. 1^st XML component of the XML form of 2^nd child CST,
    2. 2^nd XML component of the XML form of 4^th child CST.

  • Descendants notation:

      CH:(2[1.4], 1[2.1.3])

    specifies that the XML children are, in this order:
    1. 4^th XML component of 1^st XML component of the XML form of 2^nd child CST,
    2. 3^rd XML component of 1^st XML component of 2^nd XML component of the XML form of 1^st child CST.

  • Attribute reference notation:

      CH:(2[1.4]/foo)

    specifies that the only XML child is:
    1. the string value of the attribute named foo of the 4^th XML component of 1^st XML component of the XML form of 2^nd child CST.

  • Wrapper notation:

      CH:(foo.2, bar.fuz.4)
      

    specifies that the XML children are, in this order:
    1. <foo> XML form of 2^nd child CST </foo>
    2. <bar> <fuz> XML form of 4^th child CST </fuz> </bar>

    N.B.: By default, wrappers do not distribute over their contents. In other words, the resulting form will be one with all the contents wrapped in a single nesting of wrappers. If it is desired to override this default behavior and actually distribute a wrapper tag path over the sequence making up the contents being wrapped, then one uses an asterisk ('*') instead of a dot ('.'), as in, e.g.:

    CH:(foo*2, bar*fuz.4)

    Thus, using an asterisk rather than a dot in specifying a wrapper path triggers one of three things depending on whether the contents being wrapped is:

    1.	nothing:	nothing;
    2.	a single XML element:	the wrapped single element;
    3.	a sequence of XML elements:	the sequence of wrapped elements.

• Summary of children notation

  The full form of the annotation expression for specifying children is:

  CH:(... w1 ... wnc[x1. ... .xm]/a ...)

  of which only c is mandatory. The four parts of a child specification expression are:

  1. The wrapper path: w₁ ... w_n is optional: each wrapper w_i is a pair made of a (unquoted, single-quoted, or double-quoted) string (an XML tag), followed by a distribution marker : either a dot ('.'), or an asterisk ('*'). Using a dot triggers single wrapping, while using an asterisk triggers distributive wrapping (at the nesting level specified).

  2. The child: there are two cases:

     1. in a rule's annotation, c is a positive integer and denotes a position in the rule's RHS (i.e., a position in the CST) and refers to the XML tree corresponding to the child CST at this position;

     2. c may not be a number but a special form. In this case, there may be nothing trailing after c; i.e., [x₁. ... .x_m]/a is empty.

  3. The XML tree path:[x₁. ... .x_m] is optional; if not empty, it denotes a path in the XML tree corresponding to referring CST child, each x_j being a positive integer denoting a child position in the XML tree rooted in this referring CST child.

  4. The attribute reference: /a is optional; when present, a is a (possibly unquoted, single-quoted, or double-quoted) string; it must be the name of an XML attribute in the ultimate XML tree referred to by c[x₁. ... .x_m], and denotes the string content making up the value of that XML attribute.

Attributes annotation:

• Basic attribute annotation notation:

    AT:{foo="bar"}

  sets the attribute named foo to the literal string value "bar".

• Extended attribute notation:

  • Child's text value:

      AT:{foo=3}

    sets the attribute named foo to the text value of the XML form of 3^rd child CST.

  • Child's attribute value:

      AT:{foo=3/bar}

    sets the attribute named foo to the value of the attribute named bar in the XML form of 3^rd child CST.

  • Descendant's text value:

      AT:{foo=3[1.2]}

    sets the attribute named foo to the text value of the 2^nd XML component of the 1^st XML component of the XML form of the 3^rd child CST.

  • Descendant's attribute value:

      AT:{foo=3[1.2]/bar}

    sets the attribute named foo to the value of the attribute named bar located in the 2^nd XML component of the 1^st XML component of the XML form of the 3^rd child CST.

  • Terminal value:

    In a terminal's annotation only:

      AT:{foo=$VALUE}

    sets the attribute named foo to the value of the terminal node actually parsed.

• Summary of attribute notation

  The full form of the annotation expression for specifying an attribute is:

  AT:{... foo=c[x1. ... .xm]/a ...}

  of which only c is mandatory.

  • If [x₁. ... .x_m]/a is missing, then c may be only one of:

    1. a literal string "bar"; or,

    2. a special form.

  • If [x₁. ... .x_m]/a is present, then the annotation is that of a rule and c must be a positive integer denoting the position a child CST for the current rule (a position in the rule's RHS). It refers to the XML tree of child CST at that position. If [x₁. ... .x_m] is present, the x_i is a sequence of dot-separated positive integers, an XML tree path referencing an XML subtree; /a is required whenever c is a child position and must be the name of an attribute in the XML tree so-referenced. This annotation denotes the string value of this attribute in that XML tree.

Interpreted special forms:

• Extracting the value of a terminal: $VALUE

  The notation $VALUE may appear in an XML annotation expression for either a rule or a terminal whenever the CST construct it refers to is that of a terminal. For example:
  • an attribute value string; e.g.:

         %xmlinfo TERMINAL   [ L:"BAR" N:"Foo" A:{ fuz = $VALUE } ]

    specifies that the terminal symbol TERMINAL whose print value is "Gloop" will be serialized thus:

        <Foo:BAR fuz="Gloop"/>

  • a single XML content string; e.g.:

         %xmlinfo TERMINAL   [ L:"BAR" N:"Foo" C:( $VALUE ) ]

    specifies that the terminal symbol TERMINAL whose print value is "Gloop" will be serialized thus:

    
         <Foo:BAR>Gloop</Foo:BAR>

• Concatenating pieces of text: $TEXT

  Wherever text is expected, we may use the notation $TEXT(...) to denote the text string resulting from the concatenation of the text strings denoted by its arguments, each of which may be either a literal (possibly single- or double-quoted) string, or a reference to a text value deeper in a descendant CST's XML structure using the XML tree reference notation c[x₁ ... x_n]/a, where the [x₁ ... x_n] and /a parts are optional.

  This construct comes handy for composing a text string on the fly to make up the text value of a child or an attribute. For example, given the following annotations:

    %xmlinfo ID    [ L:"Identifier"  A:{ name  = $VALUE } ]
   
    %xmlinfo STR   [ L:"String"      A:{ value = $VALUE } ]
   
    Entry
      : STR '^^' EntryType
      [ L:"Place" A:{ type = $TEXT ( "[" 3/special "]" 3/general ) } C:( 1/value ) ]
      ;
   
    EntryType
      : ID ':' ID
      [ L:"Type" A:{ general = 1/name special = 3/name } ]
      ;

  the piece of Entry syntax:

    "bar"^^less:top

  gets serialized as:

    <Place type="[top]less">bar</Place>

  .

Checking Annotation Consistency

• [Condition 1]

  An annotation for a terminal, or for a rule with an empty RHS, should not be allowed to use a tree address in any attribute specifier (only symbol, quoted string, or number). A terminal's CH may only contain wrappers and a reference to $VALUE

• [Condition 2]

  In an annotation AT : {...}, the name of an attribute following an XML tree reference must be a legal attribute of the element so referenced.

• [Condition 3]

  In a rule annotation CH : (... c_i[...] ...), the number c_i must be between 1 and the length of the rule's RHS.

• [Condition 4]

  In an annotation CH : (...), two distinct occurrences of XML content references must not be allowed to be one another's prefix or duplicate address. In other words:

  • no tree address may occur more that once in the same annotation; and,

  • whenever a tree address of the form c[x₁.x₂. ... .x_n] occurs, then neither c[x₁.x₂. ... .x_n-1], nor c[x₁.x₂. ... .x_n-2], ..., nor c[x₁], nor c, may be allowed to occur in the same annotation.

  For example, both CH : (1 2) and CH : (1 2[1] 2[2]) are legal; but, both CH : (1 2 1) and CH : (1 2[1] 1[2]) are illegal.

• [Condition 5]

  Note also that whenever a tree address of the form c[x₁.x₂. ... .x_n] occurs, then for it to be consistent, this entails that the XML form of the CST node referenced by c must consist of exactly one XML element - as opposed to none or many. This is true iff the referenced RHS symbol is either a value-carrying terminal, or a non-terminal all of whose possible XML forms are each single XML elements. This must be verified statically at grammar analysis time.

If all these conditions hold, then the code for the method xmlify(Element container) defined in the class ParseNode, and the method createXmlForm(ParseNode node, Element root) defined in the class XmlInfo, is guaranteed to work safely.

DTD/Schema extraction

Extracting the types of XML elements from annotations

To each grammar symbol A, we associate its _xmlFormType: a RegularExpression denoting the set of possible XML element types that A may expand into when serialized into its XML form:

• if A is an unannotated terminal that does not carry a value, then A's _xmlFormType is empty (i.e., RegularExpression.EMPTY);

• if A is an annotated or value-carrying terminal, then A's _xmlFormType is a single XML element whose name is the symbol's name if non-annotated, or specified by the annotation, otherwise;

• if A is a non-terminal whose ruleset is:

            A : A11 ... A1n1
              | A21 ... A2n2
              | ...
              | Am1 ... Amnm
              ;
            

  then A's _xmlFormType is the union, for each rule index i, of the X_i's, where each X_i is the _xmlFormType corresponding to the i^th rule for A (for 0≤i≤m), and computed as follows:

  • if the i^th rule for A is annotated, then X_i is the XML type of the single XML element specified by the annotation;

  • otherwise, X_i is the concatenation of those of the Aⁱ_j's (for 0≤j≤_ni).

Computing a DTD by fix-point closure of regular expressions

Example

  Sexp : Atom
       | '(' List ')' [ LO: List   CH: (2) ]
       ;
 
  Atom : NUMBER     [ LO: Number AT: {value = $VALUE} ]
       | NAME       [ LO: Name   AT: {value = $VALUE} ]
       | NIL        [ LO: Nil ]
       ;
 
  List :            [ LO: Nil ]
       | List Sexp
       ;