Balisage Paper: Extending XML with SHORTREFs specified in RELAX NG

Introduction

SGML had this feature called SHORTREF. It allowed the DTD designer to specify that certain strings called shortrefs should in some contexts be interpreted as markup tags. For the authors using an SGML DTD with a well-designed set of shortrefs, the effect was similar to using a kind of Wiki markup.

As with other parts of SGML, the specification syntax for shortrefs was idiosyncratic.[s86] Furthermore, the method of their specification typically relied on some other rarely-used features of SGML DTDs, such as STARTTAG entities. This combination ensured that only an expert in SGML DTDs could hope to design shortrefs correctly, so they remained obscure and rarely used. When SGML was replaced by its simplified successor XML, nobody regretted their omission.

Or did they?

Many people stubbornly refuse to abandon their non-XML syntaxes. Programming language designers still use the old-fashioned EBNF grammars[b59] in their specifications instead of XML Schema. Even some languages that are at the very core of various XML technologies, such as XPath, are not XML. The RELAX NG schema language, though specified in XML syntax[c01], defines a non-XML compact syntax[c02c] as well.

The strongest evidence of yearning for shortrefs, however, is the myriad of Wiki languages in existence. Here we have a large family of actual markup languages, whose main purpose is to be converted to HTML, another markup language, and still they are not fully tagged XML. SGML DTDs with shortrefs and appropriate declarations could accomplish the task.[j04] Instead, Wiki engines typically store their pages as plain text, parse them using hand-coded parsers written in various general-purpose languages, and convert them directly to HTML for presentation.[b07]

There are many downsides to this architecture. Most Wiki pages are stored unvalidated and unstructured, which makes them suboptimal for searching and very difficult to automatically restructure. They are missing all XML tool chain support. All these problems are judged to be outweighed by the benefit of the special notation. A solution that preserves this notational convenience while keeping markup in XML documents would be a clear winner.

The present paper aims to deliver one solution that satisfies these criteria: given a relatively simple syntax specification that follows the established standards, it allows the author to create valid XML without entering XML tags. In other words, it resurrects SGML shortrefs in a more modern context of well-formed XML and RELAX NG schema specifications.

RELAX NG schema as a grammar

If our job is to specify how some text is to be parsed, one obvious place to start is from grammars, or more specifically context-free grammars; they have been successfully used for this purpose for more than half a century[b59]. Here is an example of such a grammar for a small fragment of a Wiki markup language, specified in a variant of the EBNF notation:

paragraph  ::= (plain-text | bold | italic)* "\n\n"?
bold       ::= "**" (plain-text | italic)* "**"
italic     ::= "//" (plain-text | bold)* "//"
plain-text ::= ([^\n*/]+ | "\n" [^\n] | "*" [^*] | "/" [^/])+

The plain-text production is rather tricky. This context-free grammar is working directly on plain-text input with no help from any lexical layer, so plain-text has to exclude the three markers (**, //, and the newline) in order to avoid ambiguity. The production would become even more complicated as more markup is added to the grammar.

Once the input text is parsed according to the grammar, we can represent the resulting abstract syntax tree as XML and use the following compact RELAX NG schema for its validation:

paragraph  = element para { (plain-text | bold | italic)* }
bold       = element bold { (plain-text | italic)* }
italic     = element italic { (plain-text | bold)* }
plain-text = text

The similarities between the two notations above are striking. The main difference is that the former specifies a concrete syntax, and the latter the abstract syntax[m62]. To become concrete, and thus useful for parsing text, the RELAX NG schema needs to specify the string markers, or terminal symbols. We could try the following modification, which brings the schema even closer to the EBNF grammar:

paragraph  = element para {
                (plain-text | bold | italic)*,
                "

"?
             }
bold       = element bold { "**", (plain-text | italic)*, "**" }
italic     = element italic { "//", (plain-text | bold)*, "//" }
plain-text = text

The RELAX NG specification[c01] unfortunately does not allow text-matching and element-matching patterns to be grouped together, and that makes the above schema invalid. To make our concrete-syntax schema syntactically correct, we need to enclose each string marker into an element of its own. These elements will belong to the special terminal namespace so we can distinguish them from the structural elements:

paragraph  = element para {
                (plain-text | bold | italic)*,
                paragraph_separator?
             }
bold       = element bold {
                bold_marker,
                (plain-text | italic)*,
                bold_marker
             }
italic     = element italic {
                italic_marker,
                (plain-text | bold)*,
                italic_marker
             }
plain-text = text

bold_marker         = element terminal:bold_marker { "**" }
italic_marker       = element terminal:italic_marker { "//" }
paragraph_separator = element terminal:paragraph_separator {
                         "

"
                      }

We could also replace the text pattern by string{pattern="([^\n*/]+|\n[^\n]|\*[^*]|/[^/])+"} to replicate the grammar even closer. As noted above, however, this pattern grows more complex as more markers are added to the grammar, which makes it difficult to maintain. Another downside is that the schema would lose the modularity properties that RELAX NG normally provides.

The plain-text pattern is meant to match any text up to any marker that is allowed in the context. Rather than require the user to construct this pattern every time a new marker is introduced, we can change the meaning of the text pattern to match what we need. In the standard RELAX NG semantics, text matches all text content up to the next element tag; in our modified semantics, it will match all text content until the next marker recognizable in the context, or until the next element tag.

Our parser must construct an abstract syntax tree with element nodes like bold that are not present in the input. To achieve this, we need to add another semantic extension and infer the missing element tags[b10]. This is especially necessary for features like Wiki lists, where a single indented asterisk can denote the beginning of both a list and a list item. This is similar to the OMITTAG feature of SGML, the main difference being that our input must be well-formed XML; the element's start-tag and its end-tag must both be present or both omitted.

The only elements with omissible tags will be those in the terminal namespace and those whose namespace URI begins with the prefix omissible+ (which is perfectly legal according to RFC 2396). In the schema fragment above, the default namespace should be made omissible; in other words, the schema should be preceded by

default namespace = "omissible+http://my.namespace.com/"
namespace terminal = "http://en.wikipedia.org/wiki/Terminal_and_nonterminal_symbols#Terminal_symbols"

The elements in the terminal namespace are perfectly ordinary XML elements; what gives them a special meaning is that the parser deletes them from the constructed syntax tree together with their content. The elements with the omissible+ namespace prefix will be kept in the normalized XML output, but their URI prefix will be removed. This stripping of terminal elements and omissible namespace prefixes is the default mode of operation. The parser can also be made to emit all the terminal nodes and keep the omissible namespace prefixes. For the above example schema and the input paragraph

Here's a **fat
and somewhat //slanted
// text**
example.

the default output of the parser is

<paragraph xmlns="http://my.namespace.com">Here's a <bold>fat
and somewhat <italic>slanted
</italic> text</bold>
example.</paragraph>

and the raw output, if requested, would be

<paragraph
   xmlns="omissible+http://my.namespace.com"
   xmlns:terminal="http://en.wikipedia.org/wiki/Terminal_and_nonterminal_symbols#Terminal_symbols"
>Here's a <bold><terminal:bold_marker>**</terminal:bold_marker>fat
and somewhat <italic><terminal:italic_marker>//</terminal:italic_marker>slanted
<terminal:italic_marker>//</terminal:italic_marker></italic> text<terminal:bold_marker>**</terminal:bold_marker></bold>
example.<terminal:paragraph_separator>

</terminal:paragraph_separator></paragraph>

Both these outputs are well-formed XML and contain no text markers. The former is valid against the original RELAX NG schema, and the latter is valid against the enriched schema. If we want to replicate the behaviour of an SGML DTD, where one can alternate between shortrefs and regular element tags, all we need do is combine the two schemata into one. The cleanest way to accomplish the same effect is to have the concrete-syntax schema include the original one, combining the original definitions with its own. If the original schema was defined in file strict.rng, the extended schema could be defined in a separate file as follows:

default namespace = "omissible+http://my.namespace.com/"
namespace terminal = "http://en.wikipedia.org/wiki/Terminal_and_nonterminal_symbols#Terminal_symbols"

include "strict.rng"

paragraph  |= element para {
                 (plain-text | bold | italic)*,
                 paragraph_separator?
              }
bold       |= element bold {
                 bold_marker,
                 (plain-text | italic)*,
                 bold_marker
              }
italic     |= element italic {
                 italic_marker,
                 (plain-text | bold)*,
                 italic_marker
              }
plain-text  = text

bold_marker         = element terminal:bold_marker { "**" }
italic_marker       = element terminal:italic_marker { "//" }
paragraph_separator = element terminal:paragraph_separator {
                         "

"
                      }

Both the default and the raw output (i.e., the abstract and the concrete syntax tree) now conform to the same RELAX NG schema, and we can use any conforming RELAX NG validator to verify this.

Implementation

The parser for the schema specifications described in the previous section has been implemented in Haskell and can be found at http://hackage.haskell.org/package/concrete-relaxng-parser. It compiles to a standalone executable that requires two file names as arguments: the target RELAX NG schema (with or without any concrete-syntax extensions), and the input XML document.

The implementation of the concrete-syntax parser is based on the RELAX NG reference implementation[c02] with its novel algorithm based on Brzozowski derivatives[b64] [s05], together with some extensions described in our previous work[b10]. In particular, the inference of the missing element tags is the same as in [b10], the only change being its restriction to the set of elements whose namespace URI begins with the string omissible+. The rest of this section will concentrate on details that have not been described elsewhere.

The biggest change from [b10] is in the textDeriv function. Both in the reference validator and in the previous normalizer implementation, this function must match its pattern argument against its entire text node argument. Now a pattern is allowed to consume only a prefix of the current text node, so the Brzozowski derivatives cannot be calculated as easily. One possible solution would be to calculate the derivative character by character, but its performance would be unacceptable. We also considered introducing a lexical layer that separates all possible syntactic markers from the rest of the text, but in the end we settled for a mixed derivative/continuation-passing algorithm. The textDeriv function takes two continuations, one invoked in case the pattern consumes the entire text node and the other in case there is some leftover text. This way each pattern is free to consume as much text as it can match in a single try, and pass the rest to the continuation pattern.

This technique unfortunately does not implement the interleave patterns properly. If their semantics from the RELAX NG specification was carried over to the text nodes literally, it would imply that an interleave pattern should match any interleaving of the character sequences matched by its two branches. This semantics would be very difficult to implement efficiently, but more importantly, it would probably be useless in practice. Instead, textDeriv implements the interleave pattern as an alternation: one of its branches is matched followed by the other. This semantics is unfortunately not composable. At this time we must recommend against the use of interleave in concrete syntax definitions. The semantics of interleave across multiple XML elements and text nodes is not affected by this problem.

Another significant hurdle to overcome in the adaptation of RELAX NG to the task of parsing text is its text pattern. Having been designed for the validation of XML documents, RELAX NG allows the text pattern to match any arbitrary contiguous region of text. The boundaries of this region are determined by the surrounding markup tags. Since we cannot count on these hard boundaries, we must keep track of all syntactic markers that can appear instead of element tags. These markers are divided into two sets, the alternate set and the follow set. The former contains all markers that can begin an alternative to the current pattern, while the latter contains all markers that can appear after the end of the current pattern.

The same approach is applied to data and dataExcept patterns: they are bounded by the next following marker. They consume the longest possible prefix, recognized by the data type, of the text preceding the marker.

Whitespace is for the most part handled the same as all other text. The only two exceptions are that the whitespace consumption does not affect the alternate set and follow set of syntactic markers, and that any amount of whitespace can precede an explicit element tag. The latter feature follows the behaviour of the standard RELAX NG validator, which ignores whitespace between elements.

Results and future directions

The presented RELAX NG extension could be applied to many RELAX NG schemata and used to shorten their instances. Whether it should be applied to any particular schema depends mostly on outside factors like the target audience and document corpus. There are also, however, several technical factors that must be taken into consideration.

As a proof of concept, the present paper has been written in concrete syntax and translated to the abstract syntax conforming with the target schema. The concrete-syntax schema extension is given in Appendix A.

The sample schema extension modifies seven elements: code, emphasis, listitem, para, programlisting, quote, and title. Their tags are made omissible in all contexts where they can occur, with the exception of emphasis which must be explicitly tagged inside programlisting and inside an inferred emphasis. Each of the seven elements is also given a concrete syntax with different terminal symbols. Authored with the full use of these extensions, the present paper contains a total of 141 element tags — mostly of elements with required attributes. Once parsed into an explicitly tagged XML instance, it gains additional 284 element tags.

Another example in Appendix B presents a small extension of the modularized RELAX NG schema for XHTML 1.0[c08]. We hope to prepare more concrete syntax extensions like these for other XML schemata in the future.

Related work

The tool presented herein treats the RELAX NG schema as an abstract syntax description, and sprinkles it with some extensions for describing the concrete syntax of the language. There have been other tools[p09] [q11] using the same approach of starting with the abstract syntax and extending it with concrete syntax annotations. The abstract syntax notation in these related works is tool-specific, since they don't use XML as the abstract syntax tree.

On the other hand, there are numerous reports[b00] [c03] [m04] [r05] that focus on using XML as the target abstract syntax tree (AST) notation of a parser for some concrete syntax. To perform their parsing, however, they use parser-generators such as ANTLR[p95] and other traditional parsing tools, so they specify their concrete syntax in the formalism those tools require. Those that use an XML schema at all, use it only to validate the generated AST.