An Invisible XML modularity proposal

Invisible XML (iXML) is a powerful tool for parsing implicit structures to reveal explicit structures. But at the moment, every iXML grammar is an island, entire of itself: all of the rules must be contained in a single file.

Reuse is a well established software engineering practice. As grammars proliferate, some mechanism for reuse is desirable. If grammars exist for parsing ISBNs or URIs or ISO 8601 dates and times, it would be useful to be able to reuse those grammars in our own grammars, without copying all of the rules. Having multiple copies of the same rules is a recipe for introducing errors.

In a complex system that supports reuse, it’s also valuable to be able to distinguish the parts of a system that are the “public interface”, which users can confidently expect to function consistently, even if the grammar is updated, from the parts that are implementation details, which the implementor may choose to refactor or change without affecting the behavior of the public interface.

An iXML grammar defines a set of rules. In this proposal for grammar reuse, the distinction between public interface and implementation details will, in practice, often boil down to the set of rule names (and semantics) that are expected to be unchanging. A grammar for ISO 8601 date times might, for example, declare that date and dateTime are what the grammar is designed to parse. It must contain other rules for parsing years, months, days, delimiters, etc., but those are implementation details. Authors of sharable grammars can, according to this proposal, specify that only date and dateTime are “safe” to import, that they will continue to function even if other aspects of the grammar change.

It was Michael Sperberg-McQueen who initially proposed that grammar modularity might be territory already mapped out by RELAX NG. RELAX NG is a grammar-based validation technology defined in terms of a set of rules (which RELAX NG calls patterns) operating over the names of, and relationships between, XML elements, attributes, and content.

RELAX NG has reuse mechanisms that have proven to be valuable and remarkably effective in practice. A thorough understanding of RELAX NG is not required to understand this proposal, it suffices to say that at a high level, one RELAX NG grammar can include another and, in doing so, replace or extend patterns.

If we take the capabilities of RELAX NG as a good starting point, we can formulate an initial set of requirements.

1. A grammar author must be able to include rules from one or more other grammars.
2. A grammar author must be able to define a public interface which specifies the nonterminals they expect to share.
3. It should be convenient to include all of the rules that are in the public interface and no others.
4. It should be possible to include any rule from a grammar. Ultimately, reuse should be in the hands of the author of the including grammar.
5. When combining grammars, simply including a nonterminal from another grammar does not change its definition.
6. It must, however, also be possible to redefine any nonterminal in the included grammar.
7. It may happen that two different grammars define a nonterminal with the same name and that an author wishes to include both of them. It must be possible to disambiguate their names. (It must be possible to include the “digit” nonterminal from bodyparts.ixml and the “digit” nonterminal from numbers.ixml into the same including grammar.)

Some terminology:

Including nonterminals from one grammar allows them to be visible in a second grammar distinct from that which defines them.

This can be visualized as a graph. Suppose that we have a grammar for a sentence, sentence.ixml:

sentence = "The", animal, verb, pphrase, punct .
  animal = -" ", ("cat" | "bat" | "rat") .
    verb = -" ", ("sat" | "spat") .
 pphrase = prep, " the mat" .
    prep = -" ", ("in" | "on" | "at") .
   punct = "." | "!" .

This grammar will parse sentences like “The cat sat on the mat.” (It’s a toy grammar that deals with spaces between words in an entirely impractical manner.)

Ignoring for the moment that there’s no syntax for including the sentence.ixml grammar in another grammar, we could imagine writing a book.ixml grammar for parsing books, where the sentence nonterminal is included from the sentence.ixml grammar.

   book = chapter++(-#a, -#a), -#a* .
chapter = number, -". ", para++-#a .
   para = sentence++" " .
@number = [N]+ .

This would parse “books” like this:

1. The cat sat on the mat.
The rat spat at the mat.
 
2. The bat sat in the mat.

This can be visualized as shown in Figure 3. The suppressed space terminals have been left out of the diagram for simplicity.

Figure 3. Visualization of the book grammar including the sentence grammar

The dashed line symbolizes that the sentence nonterminal in the including grammar (book.ixml) is defined in the included grammar (sentence.ixml).