Balisage Paper: Aparecium

Invisible XML

In 2013, Steven Pemberton introduced an idea he called invisible XML (Pemberton 2013), which he describes as a method for treating non-XML documents as if they were XML (Pemberton 2019b). More recently, he has produced a more formal specification of the idea (Pemberton 2019a). From a data creator's or author's point of view, invisible XML (ixml, for short) allows authors to use formats other than XML if they prefer, while still retaining access to the XML tool chain. From the XML programmer's point of view, it allows people working within the XML eco-system to have more convenient access to non-XML data. The only prerequisite is that it must be possible to describe the data using a context-free grammar.

A great many resources are available in specialized formats like CSS, wiki markup, or domain-specific notations. Social-science data may interleave group-level records with individual-level records in a way that varies from project to project. Other resources are distributed in generic non-XML formats like comma-separated values or JSON. Nor is it only entire documents, files, or web resources which may use non-XML formats. SGML and XML documents have a long history of including elements or attributes whose value is written in a specialized notation: mathematical expressions are often written in TeX or LaTeX; pointers may be written as URLs, as other forms of URI, as ISSNs or ISBNs, or (not too long ago) in TEI extended-pointer notation; inline styles are now frequently written in CSS. All of these notations make visible some of the structure of the information; sometimes it would be convenient to have easy access to that structure in XML processing. Invisible XML is a way of making that possible.

Context-free grammars and parse trees

The main requirement of invisible XML is that the non-XML data to be read should be described by a context-free grammar. (Readers not familiar with this concept may think of it as a kind of DTD or schema for non-XML data.) For example, we might describe the language of arithmetic expressions like 23 * (2 + 7.2) with the following grammar, written in ixml notation:

    { An expression is the sum of one or more terms. }
    expression:  term, (add-op, term)*.
    
    { A term is the product of one or more factors. }
    term: factor, (mul-op, factor)*.
    { Addition operators and multiplication operators are
    +, -, *, and /. }
    add-op:  "+"; "-". 
    mul-op:  "*"; "/".

    { A factor is either a number or a parenthesized
    sub-expression. }
    factor: number; "(", expression, ")".
    number:  digit+, (".", digit*)?.
      

Here, braces surround comments, each rule of the grammar consists of a single non-terminal symbol followed by a colon, a regular expression on the right-hand side of the colon, and a full stop. On the right hand side, quoted strings denote terminal symbols, unquoted identifiers are non-terminal symbols, commas separate items which must appear in sequence, semicolons separate alternatives, parentheses enforce grouping when necessary, question mark signals that the immediately preceding expression is optional, plus that it may occur one or more times, and asterisk that it can occur zero or more times.

Parsed against the grammar above, the arithmetic expression 23 + 1834 / (60 - 3) - 9 has a parse tree of the form

Figure 1

It will not have escaped the reader that such a tree structure can readily be expressed in an XML document:

  <expr>
    <term>
      <factor>
	<number>23</number>
      </factor>
    </term>
    <add-op>+</add-op>
    <term>
      <factor>
	<number>1834</number>
      </factor>
      <mul-op>/</mul-op>
      <factor>
	<expr>
	  <term>
	    <factor>
	      <number>60</number>
	    </factor>
	  </term>
	  <add-op>-</add-op>
	  <term>
	    <factor>
	      <number>3</number>
	    </factor>
	  </term>    
	</expr>
      </factor>
    </term>
    <add-op>-</add-op>
    <term>
      <factor>
	<number>9</number>
      </factor>
    </term>    
  </expr>

Such deeply-nested tree structures and such a high markup-to-content ratio are unusual in XML vocabularies designed for hand authoring, but they can when well designed make processing the information much simpler.^[1] For example, it should be fairly easy to see that an XSLT stylesheet is capable not just of displaying but of evaluating arithmetic expressions represented in this way. Each node in the syntax tree which represents a well-formed (sub)expression can be assigned a value. For leaf nodes containing numerals, the value is the number denoted by the numeral. Leaf nodes denoting operators and whitespace are not well formed arithmetic expressions and have no numeric value. In the case of factors, terms, and expressions, the value depends on the values of their children, in the pattern known as compositional semantics (the meaning of the compound expression is composed from the meanings of its component parts). If we label each node with its value, the syntax tree looks like this:

Figure 2

In a nutshell, the idea of invisible XML is to regard the XML structure as latent in the original expression: present, but invisible. The task of Aparecium or any other invisible-XML parser is to make that invisible XML visible, so that it can be processed by standard XML tools.

Earley parsers

Many tools for using context-free grammars require that the grammar have particular properties which are necessary for particular parsing strategies to work: some tools require that the grammar be (as computer scientists say) LL(1), or LL(k); others like the classic parser generator yacc require that the grammar be LALR(1). I will not detain the reader with a description of what these different properties entail, or even what the abbreviations mean; suffice it to say that not all context-free grammars satisfy the constraints.

The advantage of such restrictions is that they allow the tool to use parsing techniques which are relatively simple, require relatively little storage, and are relatively fast. The disadvantage is that even experienced parser writers may find it difficult to write grammars which satisfy the constraints, and for existing notations such grammars may not even be possible. Worse, it is very difficult to explain to users of the tool even what the constraints are, without administering a short course in the relevant parsing algorithms.^[2]

Invisible XML takes a different approach: users are not required to supply grammars that satisfy any particular set of implementation-related constraints. Instead, implementations are required to accept any context-free grammar. This in turn suggests that implementations will need to use one of the algorithms which is guaranteed to work for all context-free grammars without restriction. There are several such algorithms^[3], but the invisible XML specification suggests the use of an Earley parser.

Earley parsers are guaranteed to handle arbitrary context-free grammars, including ambiguous ones. In the worst case they parse an input in time and space proportional to the cube of the length of the input, but on non-pathological grammars their performance is much closer to being linear in the length of the input. They will still however typically be slower than non-general parsers, because they have more housekeeping overhead. Issues arising in the use of functional languages like XQuery or XSLT to implement Earley parsing, and the extension of the algorithm to cover regular-right-part grammars (like invisible XML) instead of only grammars in Backus-Naur Form, have been discussed in general terms by Sperberg-McQueen 2017.

The Aparecium library

Pemberton's original description of invisible XML proposes that those who publish resources parseable by means of invisible XML should label them with the MIME type application/xml and including a link to the appropriate invisible-XML grammar in the HTTP header (Pemberton 2013). When the HTTP server is configured as proposed, a CSS stylesheet can be served both as text/css and as application/xml-invisible; content negotiation between the client and the server will determine which form is sent. When the client's request specifies a preference for the application/xml form, the server will serve the stylesheet as usual, but instead of the line

Content-Type: text/css
      

the HTTP header will include the line

Content-Type: application/xml-invisible;
    syntax=http://example.com/syntax/css.ixml
      

The syntax parameter allows suitably designed software on the client side to fetch the ixml grammar for the resource from the specified location, use it to parse the resource, and present the resource to the user in an XML form.

This design allows invisible XML to fit neatly into the architecture of the Web, but for the moment it has a certain flaw. Most of the non-XML resources which we might like to process as XML are served only in their default MIME type, not as application/xml.

The Aparecium library is intended to make it easy for people working in XSLT or XQuery to use invisible XML without requiring any cooperation from webmasters or servers belonging to other organizations. It does not rely on distant servers to label resources with the application/xml MIME type, although if they do, it can handle those cases, too.

For resources served as described by Pemberton 2013, Aparecium offers a call modeled on the doc() function of XPath 2.0: a call to

aparecium:doc($uri)
      

will (in the normal case) return an XML representation of the resource at the URI given.

For resources not served in this way, Aparecium offers a way for the XSLT or XQuery programmer to take matters into their own hands by specifying both the URI of the resource to retrieve and the URI of an ixml grammar describing it:

aparecium:parse-resource($uriR, $uriG)
      

When the non-XML material and its grammar are not on the Web or in files but are available in string form, Aparecium offers a similar function to parse a string:

aparecium:parse-string($string, $grammar)
      

Since ixml grammars are themselves described by an ixml grammar, they also have a defined XML representation, so the grammar can also be supplied by the user in XML form; this saves parsing the grammar into XML preparatory to parsing the resource the user is interested in. Given the XML form of a grammar, Aparecium pre-processes it before using it to parse input; this pre-processed form can also be used. A family of functions is provided to allow various combinations of these variations: input as URI or string; grammar as URI or as string or as standard XML or as pre-processed XML.

Basic interfaces

The implementation of Aparecium is spread across several modules; all public-facing functions are gathered into one module, so only one import instruction should be needed. The functions which need the least explanation have already been mentioned:

The workhorse function of the library requires that the grammar be provided neither as a URI nor as a string, but already pre-processed into annotated XML:

Aparecium also provides a function for fetching resources whose publishers provide access to them with the MIME type application/invisible-xml and a pointer to an appropriate ixml grammar, as described in Pemberton 2013.

Several functions are also available for preparing grammars.

Current state of implementation

The current implementation of Aparecium is probably best described as a proof of concept. The parsing functions work (on at least some inputs) and produce XML which does represent the abstract syntax tree specified in the relevant ixml grammar. The results are satisfactory enough to allow simple demo applications like the arithmetic-expression parse described above to be built.

On the other hand, a great deal of work remains to be done before the library reaches production quality. The current test suite contains 75 or so grammars, including some chosen to exhibit odd or pathological behavior like the infinite ambiguity described below, but many more are needed. The set of available unit tests also needs to be expanded greatly. Better diagnostics are needed for cases where things go wrong. And the code needs to be improved so that things go wrong less frequently.

Currently, the implementation is written only in XQuery; it has been tested with BaseX and with Saxon, but it has not yet been tested with eXist, MarkLogic, or any other XQuery processor.

The biggest single shortcoming of the current implementation, however, is speed. This results in part from a conscious decision to worry not about speed but only about correctness, and to postpone optimization until a more complete test suite has been developed and the code is passing all the tests. The current implementation has no trouble with short inputs like those foreseen in the arithmetic-expression demo, but parse times for larger documents, even ones of only a few hundred bytes, are painfully slow, measured in minutes rather than in seconds. Fortunately, there are a number of fairly obvious ways to improve performance, and the current code is as far as possible written to hide low-level details of data representation from the high-level functions that perform parsing.

Data structures: representation of Earley items

The central data structure of the Earley algorithm is the Earley item: a triple (x, y, L), where

In grammars written in Backus/Naur Form, each grammar rule consists of a single non-terminal symbol on the left-hand side and a sequence of symbols on the right-hand side. If the rules of the grammar are numbered, therefore, each Earley item can be represented by a tuple of four integers (x, y, r, i) giving the start position, end position, rule number, and index into the rule.

In regular-right-part grammars like those of invisible XML, the right-hand side of a rule is not a flat sequence of symbols but a regular expression whose basic symbols are symbols in the vocabulary of the grammar. It is possible in principle to translate a grammar from regular-right-part notation to the simpler structures of BNF-style grammars, and the translation could remain in ixml notation. But it seemed easier (as well as more fun) to make the Earley algorithm work directly with regular-right-part grammars, following the discussion in Sperberg-McQueen 2017.

The most convenient way to package together the bits of disparate information that constitute an Earley item is (or so it seemed to the implementor) to represent each Earley item as an XML element of type item, with from and to attributes giving the start and end points. The location information is given by including a rule element as the only child of the item, and giving the location within the rule in an attribute named ri (rule index). This in turn means that we need a way to denote positions within a rule; a brief digression on the representation of grammar rules in Aparecium appears to be necessary.

In the XML notation prescribed for ixml grammars, the first rule of the arithmetic grammar given above looks something like this:^[7]

  <rule name="expression">
    <def>
      <alt>
        <nonterminal name="term"/>
        <repeat0>
          <def>
            <alt>
              <nonterminal name="s"/>
              <nonterminal name="addop"/>
              <nonterminal name="s"/>
              <nonterminal name="term"/>
            </alt>
          </def>
        </repeat0>
      </alt>
    </def>
  </rule>	    
      

The XML element structure of the def element corresponds in a straightforward way to the structure of the regular expression on the right-hand side of the ixml rule, which was, it may be recalled:

  expression: term, (s, addop, s, term)*.
      

The def element and each of its descendants represents an expression, and like all regular expressions, these may be interpreted as defining regular languages. The usual way to determine whether a given sequence of symbols is in the language so defined is to translate the regular expression into a finite state automaton (FSA).

One common way of doing so is the Thompson construction (Thompson 1968), descriptions of which are readily and widely available. But the Thompson construction involves first creating an FSA with a potentially large number of states and epsilon-transitions (transitions that move from one state of the automaton to another without consuming any tokens of the input) and then performing a tedious and expensive process to eliminate the epsilon transitions again and reduce the number of states. The relation between the resulting FSA and the original regular expression is typically obscure.

For our purposes, a better algorithm is that given by Brüggemann-Klein 1993a, which constructs the Gluschkov automaton for the regular expression (so called for the Russian mathematician Viktor Gluschkov, whose work Brüggemann-Klein extends). I will not attempt to describe the algorithm here, but limit myself to a few observations. In the Gluschkov automaton, each state corresponds one-to-one with (or just: is) one of the basic symbols in the original regular expression^[8]; the automaton also has an additional start state which corresponds to no symbol in the expression. In the Gluschkov automaton, we move to a given state s whenever we read in the input a symbol matching the symbol associated with s. The relation between the regular expression and the automaton is thus very simple and straightforward, and the number of states in the FSA is predictable from the regular expression.

To simplify description and calculation of the automaton, it is convenient if each state (and each subexpression) has a name. So the first modification we make to the representation of the rule is to add an identifier for each state. With identifiers added, the rule for expression looks something like this:

  <rule name="expression">
    <def xml:id="exp_def_1">
      <alt xml:id="exp_alt_1">
        <nonterminal name="term" xml:id="term_1"/>
        <repeat0 xml:id="exp_repeat0_1">
          <def xml:id="exp_def_1" nullable="false">
            <alt xml:id="exp_alt_1" nullable="false">
              <nonterminal name="s" xml:id="s_1"/>
              <nonterminal name="addop" xml:id="addop_1"/>
              <nonterminal name="s" xml:id="s_2"/>
              <nonterminal name="term" xml:id="term_2"/>
            </alt>
          </def>
        </repeat0>
      </alt>
    </def>
  </rule>	    
      

Following Brüggemann-Klein's algorithm, we then calculate for each sub-expression (down to and including the basic symbols themselves, here all nonterminal elements) a number of properties:

This information is supplied as an attribute on each expression; the follow sets are given by attributes in a namespace created for the purpose: the attribute value specification follow:term_1 = "s_1" on the outermost def element means that within that expression, state s_1 can follow state term_1.

The process of calculating the values for these properties and assigning the appropriate attributes has been referred to elsewhere as compiling or annotating the grammar. The fully annotated rule now looks something like this:

  <rule name="expression"
	xmlns:follow =
	 "http://blackmesatech.com/2016/nss/ixml-gluschkov-automata-followset"> 
    <def xml:id="exp_def_1"
	 nullable="false"
	 first="term_1" last="term_1 term_2"
	 follow:term_1=" s_1"
	 follow:s_1=" addop_1"
	 follow:addop_1=" s_2"
	 follow:s_2=" term_2"
	 follow:term_2="s_1">
      <alt xml:id="exp_alt_1"
           nullable="false"
           first="term_1" last="term_1 term_2"
	   follow:term_1=" s_1"
	   follow:s_1=" addop_1"
	   follow:addop_1=" s_2"
	   follow:s_2=" term_2"
	   follow:term_2="s_1">
        <nonterminal name="term" xml:id="term_1"
		     nullable="false"
		     first="term_1" last="term_1"
		     follow:term_1=""/>
        <repeat0 xml:id="exp_repeat0_1"
		 nullable="true" first="s_1" last="term_2"
		 follow:s_1=" addop_1"
		 follow:addop_1=" s_2"
		 follow:s_2=" term_2"
		 follow:term_2="s_1">
          <def xml:id="exp_def_1"
	       nullable="false" first="s_1" last="term_2"
	       follow:s_1=" addop_1"
	       follow:addop_1=" s_2"
	       follow:s_2=" term_2"
	       follow:term_2="">
            <alt xml:id="exp_alt_1"
		 nullable="false" first="s_1" last="term_2"
		 follow:s_1=" addop_1"
		 follow:addop_1=" s_2"
		 follow:s_2=" term_2"
		 follow:term_2="">
              <nonterminal name="s" xml:id="s_1"
			   nullable="false" 
			   first="s_1" last="s_1"
			   follow:s_1=""/>
              <nonterminal name="addop" xml:id="addop_1"
			   nullable="false" 
			   first="addop_1"
			   last="addop_1"
			   follow:addop_1=""/>
              <nonterminal name="s" xml:id="s_2"
			   nullable="false" 
			   first="s_2" last="s_2"
			   follow:s_2=""/>
              <nonterminal name="term" xml:id="term_2"
			   nullable="false" 
			   first="term_2"
			   last="term_2"
			   follow:term_2=""/>
            </alt>
          </def>
        </repeat0>
      </alt>
    </def>
  </rule>	    
      

The finite state automaton whose states are the basic symbols of the expression rule (plus an extra start state) and whose transitions and other properties are given by the attributes first, last, and follow:* attributes on the outermost def element can be illustrated by the following diagram:

Figure 6

Our digression into the structure of rules is almost complete. It remains only to be observed that the current state of an FSA which has partially recognized a string is given fully by the name (the identity, really) of the state. (That is pretty much a defining feature of a finite state automaton: its future behavior is defined solely by the identity of the current state.)

So we can represent the current position in the right-hand side of a rule by recording the name of the current state: that is, given the way the Gluschkov automaton is constructed, the identifier assigned in the rule to the corresponding terminal or non-terminal symbol. If nothing has yet been read, we are in the start state for the rule. By convention, the start state of any rule is named q0.

This concludes the digression onto the structure of grammar rules in Aparecium.

We can now show an example of an Earley item as represented in the current implementation. At position 20 in the string 23 + 1834 / (60 - 3) - 9 (that is, just after the right parenthesis), the parsing algorithm will generate an Earley item that means, in effect, after reading the input string from position 0 to position 20, the FSA for rule expression is in state term_2. That Earley item will have the following form:

<item from="0" to="20" ri="term_2">
  <rule name="expression"
        xmlns:follow="http://blackmesatech.com/2016/nss/ixml-gluschkov-automata-followset">
    <def xml:id="exp_def_1"
         nullable="false"
         first="term_1" last="term_1 term_2"
         follow:term_1=" s_1"
         follow:s_1=" addop_1"
         follow:addop_1=" s_2"
         follow:s_2=" term_2"
         follow:term_2="s_1">
      <alt xml:id="exp_alt_1"
           nullable="false"
           first="term_1" last="term_1 term_2"
           follow:term_1=" s_1"
           follow:s_1=" addop_1"
           follow:addop_1=" s_2"
           follow:s_2=" term_2"
           follow:term_2="s_1">
        <nonterminal name="term" xml:id="term_1"
                     nullable="false"
                     first="term_1" last="term_1"
                     follow:term_1=""/>
        <repeat0 xml:id="exp_repeat0_1"
                 nullable="true"
                 first="s_1" last="term_2"
                 follow:s_1=" addop_1"
                 follow:addop_1=" s_2"
                 follow:s_2=" term_2"
                 follow:term_2="s_1">
          <def xml:id="exp_def_1"
               nullable="false"
               first="s_1" last="term_2"
               follow:s_1=" addop_1"
               follow:addop_1=" s_2"
               follow:s_2=" term_2"
               follow:term_2="">
            <alt xml:id="exp_alt_1"
                 nullable="false"
                 first="s_1" last="term_2"
                 follow:s_1=" addop_1"
                 follow:addop_1=" s_2"
                 follow:s_2=" term_2"
                 follow:term_2="">
              <nonterminal name="s" xml:id="s_1"
                           nullable="false"
                           first="s_1" last="s_1"
                           follow:s_1=""/>
              <nonterminal name="addop" xml:id="addop_1"
                           nullable="false"
                           first="addop_1"
                           last="addop_1"
                           follow:addop_1=""/>
              <nonterminal name="s" xml:id="s_2"
                           nullable="false"
                           first="s_2" last="s_2"
                           follow:s_2=""/>
              <nonterminal name="term" xml:id="term_2"
                           nullable="false"
                           first="term_2"
                           last="term_2"
                           follow:term_2=""/>
            </alt>
          </def>
        </repeat0>
      </alt>
    </def>
  </rule>           
</item>
      

This representation is convenient for the programmer but has a practical flaw. There will be at least one Earley item for each terminal symbol in the input; in ixml grammars, that means one for each character. Making the rule element a child of the item element makes it extremely convenient to consult the rule when needed, but it also requires that the XQuery or XSLT implementation make a new copy of the rule for each Earley item created (because each copy of the rule will have a different parent element). The frequent copying creates a perceptible strain on memory in the current implementation of Aparecium. A simpler representation of the Earley item would not reproduce the rule but merely point at it, thus:

<item from="0" to="20" rulename="expression" ri="term_2"/>
      

Better performance can also come from representing the Earley item not as an element but as a map which points at, rather than naming, the rule and state (assuming that the variables $rule and $state have been appropriately initialized:

map {
      "from": 0,
      "to": 20,
      "rule": $rule,
      "ri": $state
    }    
      

Changing the representation of items to use maps instead of elements reduced parse time for grammars in the test suite between 15% and 30%. This was much less than had been expected. A much more dramatic effect (seven-fold speedup) came from changing the representation of the set of Earley items being calculated by the algorithm to make the search for Earley items with specific properties faster.

Treatment of ambiguity

A sentence is ambiguous if it has more than one derivation that follows the rules of the grammar. One of the great advantages of Earley parsing is that it is robust in the presence of ambiguity: if there is exactly one derivation of a sentence, the Earley parser will find it; if there is more than one, the Earley parser will find more than one. This contrasts sharply with most widely used parsing techniques, which cannot function if the grammar has any ambiguous sentences. Unfortunately, existing parsing tools are often not much help detecting ambiguity or helping the grammar author remove it. So a great deal of time can be spent, with tools like yacc, trying more or less random changes to the grammar in an attempt to eliminate the parsing conflicts detected by the tool.

For ambiguous sentences, Pemberton 2013 prescribes that an ixml parse should return any one of the parse trees, with a flag to signal that there are other parse trees for the input. This is clearly satisfactory if it is known that any ambiguity is inconsequential. If a grammar for arithmetic expressions is ambiguous only because whitespace may be regarded either as a child of a term or as the child or an expression, then it does not matter for numerical evaluation which tree is selected: whitespace plays no role. The rule may be less satisfactory, however, if the two parses would assign different meanings to the sentence. In such a case, it may be useful for a grammar writer (though perhaps not a grammar user) to be able to compare the two parses; that comparison may help make the source of the ambiguity clear.

For this reason, the current version of Aparecium deviates from the rule enunciated by Pemberton: for ambiguous sentences Aparecium returns multiple parse trees. In some simple cases, it returns all parse trees, but that is not and cannot be true in general: in some cases, a sentence may have an infinite number of parse trees.

Consider the following grammar:

A: A; "a".	      
      

An A consists either of another A or of the letter a. The only sentence in the language defined by this grammar is a, but it has an infinite number of parse trees. XML representations of a few of these include:

<A>a</A>
<A><A>a</A></A>
<A><A><A>a</A></A></A>
...
      

Another small grammar illustrates a different kind of infinity in parse trees:

S: (X)*. X: "x"; {nil}.	      
      

Here the language consists of strings of zero or more occurrences of x, but each sentence has an infinite number of parse trees. For the sentence x, the parse trees include the following.

<X>x</X>
<X><X/>x</X>
<X>x<X/></X>
<X><X/><X/>x</X>
<X><X/>x<X/></X>
<X>x<X/><X/></X>
... 
      

In both of these cases, Aparecium will detect the infinite ambiguity and return only a finite number of parse trees.