Grammar-Driven Markup Generation

Introduction

A grammar is a set of rules that describes the composition of a language. Grammars have existed for at least two and half millenia, but their use was mainly didactic. The practical applications of grammars started with their mathematical formalization in the 1950s [c56] and the emergence of computer programming languages [b59].

There are three ways to apply a grammar:

The historical motivation for development of the theory of formal languages was to explain the method of generation of valid sentences as well as their recognition and parsing. Generative grammars are still an active area of reasearch in linguistics. In computer science, however, it is parsing that is the primary role of grammars; their use for generation of valid sentences appears to be forgotten.

One reason for this lack of interest in grammar-driven generation is that the problem is poorly defined. The output of a generator is a grammatically valid sentence. But what is its input, other than the grammar? The task of a parser is clearer: while its output in practice can be anything, it is usually defined as a parse tree of some form.

While many kinds of generator inputs are possible and interesting to contemplate, we shall concentrate on the specific task of generating a grammatically valid sentence from a sequence of tokens (i.e., terminals) allowed by the grammar. Furthermore, the generator must exactly reproduce any input that is already a grammatically valid sentence. We shall use the term normalization to refer to this form of sentence generation, and the term normalizer for the generator that performs it.

Given a normalizer that maps a set of token sequences T into a set of cannonical, grammatically valid sequences S, one can define a new language S' as the union of the core language S and the non-core language T.

For an actual example of this kind of language definition, we need look no further than SGML. An SGML parser performs parsing, normalization, and validation at the same time. For example, given the following SGML DTD that declares the end tag of element a and both tags of element b to be omissible:

<!element a - o (b)>
<!element b o o (#pcdata)>

an SGML parser with OMITTAG feature enabled will parse the instance <a>Hello, World! into a syntax tree corresponding to <a><b>Hello, World!</b></a>. Any conformant SGML parser with support for omissible tags will consider these two instances as equivalent, as long as the same DTD is used to parse them. If the DTD should change, however, an instance that omits element tags may become not only invalid but unparsable.

For this reason and others, an XML parser does not perform any normalization. A well-formed XML instance is always parsed in the same way according to a fixed grammar, regardless of what DTD or schema the instance happens to also conform to. Various types of XML schemas are used only for validation, not for parsing or normalization.

This paper will demonstrate how an XML schema (a RELAX NG schema specifically) can be used to generate a valid instance of the schema from an invalid but well-formed XML instance. In other words, we shall normalize a well-formed XML instance so it conforms to a given schema.

The only element tags allowed in the input are those that occur in the target schema. If normalization succeeds with no errors, the output of the normalizer will:

The normalizer is much more forgiving than the SGML parser in what kinds of input it can normalize. The target grammar is allowed to be ambiguous, though this is not recommended for performance reasons. There is no unique particle contribution constraint [w04], nor is the generation restricted to contextually required elements [s86]. If the input instance is ambiguous, i.e., there is more than one way to normalize it, the normalization with the least amount of added markup will be chosen. This choice is not made at the point when the particle is encountered, because the subsequent content could make that choice invalid, but deferred until the enclosing element ends. The biggest constraint is that only plain element tags with no attributes can be inserted. Even this constraint could be overcome by automatically generating some arbitrary grammatically correct values for all required attributes, but we felt that this might cause more harm than benefit in practice.

The primary purpose of SGML's minimization features was making SGML easier to author. We do not recommend using the XML normalizer in this way; we feel that it is important that every XML document in permanent storage should conform to a clearly expressed schema.

The legitimate place for the normalization process is inside a processing pipeline, where it can usefully be applied to or produce a transient XML document instance. Normalization can thus be applied before another process in order to transform the input document into a form easier to process. The target schema for the normalizer may be just a stricter form of the input document's schema, or it may specify additional disambiguating markup.

Alternatively, a normalizer can appear at the opposite end of the processing pipeline, where it ensures that the output of the preceding process conforms to the target schema. We shall demonstrate this latter possibility of practical use in a later section.

The rest of the paper is organized as follows: the next section will present an example of normalizer's use, and afterwards its design and implementation will be explained. The section following after that explains the purpose and results of the normalizer in production, and the paper concludes with a discussion of related work.

Example

This section will demonstrate the capabilities of our normalizer through an example. Let us take the following RELAX NG schema as our target:

start = document
block = p | ol | ul

document = element document { title, block+, section* }
section  = element section { title, block+, section* }
title    = element title { text }
p        = element p { text }
ol       = element ol { li+ }
ul       = element ul { li+ }
li       = element li { block+ }

The goal is to convert our input to a valid instance of this grammar. As for the input, it may start as a plain text file like the following one:

Normalizer test input

This is a short test input for the normalizer.

Purpose

The purpose of this document is to demonstrate the capabilities of the normalizer.
The normalizer is schema-driven, and it tries to fit its input into the target schema.

Constraints

The goal of the normalizer is to produce output that conforms to the schema,
 while preserving complete input. It does not
always succeed:
- A piece of input that cannot be fit into the schema will be dropped.
- The normalizer does not attempt to conjure any required attribute values nor text data.
  These must be present in the input.

We first need to ensure that our input is a well-fomed XML document, which can be achieved simply by putting the entire text inside the <document>...</document> tags. If we then run this XML instance through the normalizer, it will be converted to

<document>
  <title></title>
  <p>
Normalizer test input

This is a short test input for the normalizer.

Purpose

The purpose of this document is to demonstrate the capabilities of the normalizer.
The normalizer is schema-driven, and it tries to fit its input into the target schema.

Constraints

The goal of the normalizer is to produce output that conforms to the schema, 
while preserving complete input. It does not
always succeed:
- A piece of input that cannot be fit into the schema will be dropped.
- The normalizer does not attempt to conjure any required attribute values nor text data.
  These must be present in the input.
</p>
</document>

As we can verify, the output indeed does conform to the target schema. The content model of document requires a title element, for example, and this element has been inserted. Since it has no content, though, it may not be all that useful.

In order to produce a more appropriate instance, we need to place certain constraints on the solution. One way to do this would be make the schema stricter. We could require the title content to be non-empty, and the paragraph content to contain no line-breaks. Alternatively, we can specify the constraints by adding the desired markup to the input document. For example, we can mark up all input lines that appear to be titles:

<document>
<title>Normalizer test input</title>

This is a short test input for the normalizer.

<title>Purpose</title>

The purpose of this document is to demonstrate the capabilities of the normalizer.
The normalizer is schema-driven, and it tries to fit its input into the target schema.

<title>Constraints</title>

The goal of the normalizer is to produce output that conforms to the schema,
 while preserving complete input. It does not
always succeed:
- A piece of input that cannot be fit into the schema will be dropped.
- The normalizer does not attempt to conjure any required attribute values nor text data.
  These must be present in the input.
</document>

Given this enriched input together with the original schema, the normalizer produces the following output:

<document>
  <title>Normalizer test input</title>
  <p>

This is a short test input for the normalizer.

</p>
  <section>
    <title>Purpose</title>
    <p>

The purpose of this document is to demonstrate the capabilities of the normalizer.
The normalizer is schema-driven, and it tries to fit its input into the target schema.

</p>
    <section>
      <title>Constraints</title>
      <p>

The goal of the normalizer is to produce output that conforms to the schema,
 while preserving complete input. It does not
always succeed:
- A piece of input that cannot be fit into the schema will be dropped.
- The normalizer does not attempt to conjure any required attribute values nor text data.
  These must be present in the input.
</p>
    </section>
  </section>
</document>
  

The good news is that the normalizer has not only respected and kept our title markup, it has inferred that every title but the first one has to start a new section. The bad news is that the second section has been nested within the first one. While this does conform to the target schema, the two sections belong at the same level. Furthermore, we want every line to be a separate paragraph; and there appears to be a list at the end of our document and it should be marked up as such.

In this simple example we could just visually determine where each section, paragraph, or list item starts and ends and mark them up with XML element tags. In practice, however, we'd rather have this work done automatically. A simple pattern-matching rule would be capable of inserting a start tag wherever there is a hyphen at the beginning of the line, but finding where it ends is much more difficult. To make this marking-up process easier, the normalizer recognizes a number of processing instructions as output constraints. Once we apply them, our input document might look like this:

<document>
<title>Normalizer test input</title>

<?derivative:start-anew <p>?>This is a short test input for the normalizer.

<?derivative:start-anew <section>?><title>Purpose</title>

<?derivative:start-anew <p>?>The purpose of this document is 
     to demonstrate the capabilities of the normalizer.
<?derivative:start-anew <p>?>The normalizer is schema-driven, 
     and it tries to fit its input into the target schema.

<?derivative:start-anew <section>?><title>Constraints</title>

<?derivative:start-anew <p>?>The goal of the normalizer is 
     to produce output that conforms to the schema, 
while preserving complete input. It does not always succeed:
<?derivative:proceed-with <ul>?><?derivative:start-anew <li>?>
A piece of input that cannot be fit into the schema will be dropped.
<?derivative:proceed-with <ul>?><?derivative:start-anew <li>?>
The normalizer does not attempt to conjure any required attribute values nor text data.
<?derivative:start-anew <p>?>These must be present in the input.
</document>

The processing instructions basically act as placeholders for element start tags, letting the normalizer know which element is supposed to enclose the following content. The exact location of the element's end tag will be inferred by the normalizer. The details of the processing instructions and the inference algorithm will be explained in the next chapter. The normalizer's output, based on our last enriched input above, looks as follows:

<document>
  <title>Normalizer test input</title>
  <p>This is a short test input for the normalizer.

</p>
  <section>
    <title>Purpose</title>
    <p>The purpose of this document is to demonstrate the capabilities of the normalizer.
</p>
    <p>The normalizer is schema-driven, 
	      and it tries to fit its input into the target schema.

</p>
  </section>
  <section>
    <title>Constraints</title>
    <p>The goal of the normalizer is to produce output that conforms to the schema,
	  while preserving complete input. 	 It does not always succeed:
</p>
    <ul>
      <li>
        <p>
A piece of input that cannot be fit into the schema will be dropped.
</p>
      </li>
      <li>
        <p>
The normalizer does not attempt to conjure any required attribute values nor text data.
</p>
        <p>These must be present in the input.
</p>
      </li>
    </ul>
  </section>
</document>

Design and Implementation

The basic idea that drove the normalizer design came after implementing the validator automaton [c02] for RELAX NG [c01]. This automaton uses a flexible validation algorithm based on Brzozowski derivatives [b64]. We shall now sketch the basic idea of this validation algorithm; a more thorough treatment can be found in the literature [a72].

Informally, the derivative of a grammar G with respect to a sequence of tokens S is the grammar G', such that a sequence S' is valid according to G' if and only if the concatenation of S and S' is valid according to G.

We can think of the grammar G as the initial state of a validating automaton, and the grammar derivative calculation as its transition function. A very simple and generic validator algorithm can be built on top of this concept [s05], and one such validator is the standard RELAX NG validation algorithm.

While working on the implementation of an RELAX NG validator library [s09b] for OmniMark [s09a], it became clear that the automaton could be relatively easily extended in two orthogonal ways: with additional pattern constructs, and with additional actions to perform. In particular, the validating automaton could be modified to produce arbitrary output, in the same way a deterministic finite automaton can be extended to a Moore machine [m56].

The original RELAX NG validation algorithm [c02] represents the grammar as a tree data structure. Here is its definition in Haskell [h02]:

data Pattern = Empty
               | NotAllowed
               | Text
               | Choice Pattern Pattern
               | Interleave Pattern Pattern
               | Group Pattern Pattern
               | OneOrMore Pattern
               | List Pattern
               | Data Datatype ParamList
               | DataExcept Datatype ParamList Pattern
               | Value Datatype String Context
               | Attribute NameClass Pattern
               | Element NameClass Pattern
               | After Pattern Pattern

The constructors of this data type, with the exception of the last one, correspond to the constructs of the RELAX NG schema language. The last constructor, After, appears when a start tag of an element is consumed, and matches the remainder of the XML input together with the corresponding end tag.

We need two extensions to this data structure in order to enable the automaton to perform normalization. First, we need to be able to assume the presence of an omitted element tag. Secondly, we must be able to output the normalized version of our input, together with the omitted and inferred tags. So we add two more data constructors:

data Pattern = Empty
               | ...
               | Region Bool QName Pattern
               | Result [ResultDelta] Pattern

data ResultDelta = StartTag ChildNode | Add ChildNode | EndTag | Inferred ResultDelta

The Result constructor keeps track of the output that should be emitted if the pattern it wraps succeeds. Whenever the current pattern (i.e., the state of the automaton) has a Result node at its root, the accumulated chunk of output is flushed and the root node is replaced by its child pattern.

The Region constructor denotes an open element region, which may have come from the input or may have been inserted in order to normalize it. In the former role, it acts as a replacement for the After node. To accomodate this change in the representation of open element regions, we have to make another adjustment to the Interleave constructor. It needs an extra integer field to keep track of which of its patterns has consumed unmatched start tags, and how many of them.

As long as the input conforms to the target schema, the normalizer acts the same way as the RELAX NG validator, except it builds the Result nodes and flushes them at the output. When a particle that doesn't match the current pattern is encountered, the normalizer attempts to recover by descending into the content models of elements that are allowed at the current point. The derivative of the current pattern is then the sum of derivatives of all content models that accept the particle, with each content derivative wrapped into a Region node and a Result node; these keep track of the inferred element start tag.

This modification of the RELAX NG validation algorithm results in the normalizer whose complete source code is listed in the paper's appendix Appendix A. This simple normalizer is completely correct, but far from perfect. It easily runs into a combinatorial explosion of the pattern tree, and it cannot be customized to resolve the ambiguity in a desired way. While the available space is too short to describe all of the additional features and optimizations, the role of the processing instruction guides is too important to leave out.

Many interesting target schemas contain a large number of elements which have nearly identical content models and which are allowed to appear in the same places. Such is the case, for example, with DocBook 5 elements glossary, bibliography, index, toc, dedication, acknowledgements, preface, chapter, appendix, article, and colophon. This represents a problem for the normalizer because it must keep track of all the alternative elements in case of recovery. If the user can specify which of the elements should be used for recovery, this improves the output and the performance at the same time.

At the moment, the normalizer accepts the following processing instructions:

where depth has the form region-identifier:integer.

Processing instructions are used instead of element tags because the input document has to be well-formed XML, so it cannot contain unmatched element start tags. Using empty element tags in a special namespace could cause difficulties because the target schema may or may not allow them in that position. Finally, since these instructions target one specific tool, the normalizer, this is an appropriate use of processing instructions if there ever was one.

The normalizer evaluates these processing instructions as follows:

Results

The schema-driven normalizer described above has been implemented in the OmniMark programming language, to serve as a component in various document conversion solutions. We shall now briefly describe this environment in order to illustrate the practical benefits of the approach.

The wider purpose is to convert documents from a legacy presentation-oriented format into a semantically richer XML format. Some examples of the source document format are FrameMaker, HTML, InDesign, or Quark Xpress. The target format of the conversion can be DITA, DocBook, or a user-specified XML format.

One obvious simplification when faced with converting M source formats to N target formats is to introduce an intermediate format, and thus replace M*N direct converters by M input converters to the intermediate format plus N output converters from the intermediate to the target format. Another benefit of having the intermediate document is that it can be enriched with user annotations to guide the output converter.

Experience we gained in building specific output converters showed that hand-written implementations were difficult to verify and maintain, so we needed a more robust and more flexible solution. Some customers required outputs that conform to a specialization of DITA, others wanted DocBook with various extensions.

The core of the output converters is the topic of this paper: the schema-driven normalizer. Its draft implementation, given in the appendix, was coded in Haskell and tested using the QuickCheck library [c10]. After this proof of concept, the production implementation was developed in OmniMark. Once the normalizer was ready, the old hand-coded output converters for DITA and DocBook were replaced with new converters in a matter of days.

Compared to the hand-written output converters they replaced, the converters based on the schema-driven normalizer provide several benefits:

One downside of the new converters is their performance, especially their worst-case memory consumption. The worst case in question is generally an input document which is annotated in a way that makes it non-conformant with the target schema. The hand-coded converters would in this situation either report errors (which is the desired behaviour) or generate invalid output (which is not). The schema-driven converters try to recover by inserting the missing element tags and by rearranging the input. The recovery eventually fails and the normalizer produces an error report, but its attempt costs a lot of time and memory. We are still looking for a way to fix this issue.

Related Work

Automatic grammar-driven sentence normalization has been done in linguistics, for the automatic correction of grammatically incorrect English sentences [v88].

For markup languages, particularly XML, there has been some related work in the area of automatic markup [f93] [k97] [t98]. The main difference with our work is that the input of an automatic markup system is typically plain text, usually produced by OCR. As a consequence, even those automatic markup systems whose output schema is not fixed require additional configuration in form of pattern-matching rules. The normaliser approach presented in this paper can be coupled with a pattern-matching engine as well, but it does not depend on one.

The automatic markup system that seems nearest to ours is the Vasari project [a03], which is also schema-driven to some extent. The target schema must be enriched using a special pattern-matching language which determines where the required element tags can be inserted. It is not clear if the location of every tag required by the target schema must be specified this way.

There is a large body of work on the automatic translation between structured documents that conform to similar schemas [a72] [m96] [t03]. The approaches based on the concept of syntax-directed translation schema [l68] and its extensions, such as extended syntax-directed translation schema [k95] and tree transformation grammars [l97], seem to be most related to our work. The syntax-directed translation is simpler and more direct than our approach to translation, but it requires both the source and target format to be well structured. Our problem, quite common in practice, is that the source format is only weakly structured. The transformation process presented in this paper proceeds in two stages: the weakly structured source document is first translated into another weakly structured document which uses the tags allowed by the target schema. This intermediate document is then normalized to a valid schema instance.