Balisage Paper: A schema language and parser for next-generation markup languages^[1]

Markup and markup languages

Document markup can be understood as a means of making explicit an interpretation of a text, that is, of making explicit what is conjectural or implicit, a process of directing the user as to how the content of the text should be (or has been) interpreted. A markup language, in turn, is a set of markup conventions used together for encoding texts. (TEI Gentle introduction) Markup languages may vary in the structures and interpretations that they are (or are not) able to represent, and, where they are able to represent a structure, in the quality of the representation. Assessing the adequacy and quality of a markup language inevitably has a subjective aspect, but however the following terms are understood, any assessment would value clarity and legibility (humans typically need to read and write markup), as well as suitability for any intended automated processing (computers need to be able to process markup efficiently).

An optimal markup language would be able to represent—clearly, legibly, and in a machine-tractable way—any feature of a document that a user considers important. The predominant ecosystem of document markup conventions and tools today, based on the XML-related family of W3C (and other) specifications, struggles to support, in a clear, legible, and machine-tractable way, many concepts that are required to represent the expressive richness of documents. Although workarounds exist, structural document features that cannot easily or naturally be expressed in XML and managed with existing XML tooling include Discontinuity,^[2] Overlap,^[3] Non-linearity,^[4] Multi-ordered content,^[5] and Unordered content.^[6] We refer to a markup language that retains the intellectual and engineering virtues of XML while also supporting the preceding features as a next-generation markup language.

Tokenization, parsing, and validation

A principal goal of the present contribution is to imagine, and to begin to implement, a document authoring and processing environment that meets the needs of a next-generation markup language as naturally and effectively as the existing XML ecosystem meets the needs of XML markup. Similarly to the way the use of specific elements and attributes in documents tagged with XML can be represented by schema languages designed to support XML features, our goals for a next-generation markup language include that it be possible to parse and validate documents tagged according to such a language against a user-defined schema that recognizes and manages all features, including next-generation features, similarly to the way the current XML ecosystem recognizes and manages features of XML.

Parsing, as a high-level term, is the process of recognizing the subcomponents of a text stream. For example, parsing XML entails recognizing the different types of nodes that make up an XML document instance. Parsing in this high-level sense is sometimes subdivided into smaller tasks, such as, for example, an operation to distinguish markup from content and an operation to analyze the structural relationships among the markup and content components. In this two-part model, the part that involves recognizing markup and content tokens is typically called tokenization or lexing (lexical analysis) and the term parsing is reserved for grammatical analysis, that is, analyzing the relationships among the tokens identified during lexing.^[7] It may be possible to tokenize an invalid document, so that, for example, a tokenization process might be able to recognize an end-tag at the very beginning of an XML document, where it is not permitted, by rules of well-formedness, to appear. Detecting the well-formedness violation is the responsibility of the parser (in the narrow sense of the term); the lexer identifies the tokens (structurally meaningful units in the text stream) and the parser either succeeds or fails to make sense of them.

Common reasons for parsing documents include validation (see below), enhancing information (some schema languages record datatype information that is not explicit in a document instance but can be accessed during parsing), or performing transformations or other operations. The opposite of parsing can be considered serialization, where parsing translates a sequence (series) of characters into a structure that is convenient for subsequent processing (e.g., a tree in XML) and serialization turns that type of structure into a series (thus the term serialize) of characters that is convenient for storage or transmission.

Validation is verification that the grammatical structure of a specific document conforms to the types of structures permitted by a schema used for that purpose. Schemas describe a domain-specific language, that is, they are authored to enable and enforce domain-specific structural requirements. XML distinguishes validation against a schema from well-formedness checking, that is, from verifying that the document observes requirements that must be met by all XML documents, regardless of domain-specific requirements and regardless of whether they are also validated against a schema. Strictly speaking, a document with angle-bracketed markup that does not conform to XML well-formedness requirements is not XML, which means that it cannot be validated against a (domain-specific) schema. More informally, though, users ultimately care whether documents do or do not meet expectations and requirements, and may therefore regard verifying well-formedness and verifying schema validity as parts of a single process of verifying the acceptability of the document markup.^[8]

A validator that simply accepts or rejects a document according to whether it conforms to structures permitted by a schema is called a recognizer. Beyond distinguishing valid from invalid documents, a validation process may emit error messages of varying granularity, which can be helpful for users who would want to correct structural invalidities. Validation can be performed in real time, and real-time validation is often incorporated into code editors to guide users through the process of adding valid markup. Alternatively, validation can be performed on completed documents.

Schemas and grammars

One difference between XML and SGML is that SGML always required a schema (the only type of schema supported by SGML was DTD), while schema validation is optional for XML. The decision by the original developers of XML that schemas should be optional recognized that a schema may be important during or immediately after authoring, but once a document is complete, has been validated, and will not be changed again, there is no need to continue to check it for validity. SGML made use of markup features that could not be interpreted without reference to a schema, which is one reason that a schema had to be obligatory for SGML, and those features were excluded from XML requirements to ensure that XML could be processed without reference to a schema.

In its current form our system requires a schema, that is, we integrate well-formedness checking with schema validation. We do not preclude separating these operations later, but for now that separation is out of scope because it is not clear how we would reliably analyze and interpret next-generation features like Overlap and Discontinuity without the guidance provided by schema rules.

Schemas that can be used to support parsing and validation of XML markup can be authored in W3C XML Schema (XML Schema 1.1), Relax NG (Clark 2002, Compact), or DTD (defined as part of XML 1.0), none of which is designed to represent the next-generation features described above. One of our goals, then, is to begin to develop a schema language and associated tooling for next-generation markup languages that is analogous to the schema languages and associated tooling currently available in the XML ecosystem.

The terms schema and grammar are sometimes used interchangeably in the structured-text community, but we use them here as technical terms with different meanings and properties.

Human developers interact directly with the schema, but not directly with the grammar, much as XML developers author XML Schema or Relax NG or DTD schemas to meet project-specific needs. A schema language is the declarative, human-facing component of formal document modeling, which means that it describes what is and is not permitted in a valid, conformant document instance, but it does not describe how parsing and validation is performed. If a schema is to be usable for parsing and validation, it must be amenable to compilation into a grammar that can perform the parsing and validation operations in a robust, efficient, and scalable way. The present contribution aims to:

The three schema languages in wide use in the XML ecosystem, listed above, have mature implementations that have been in use for many years,^[9] and we have no doubt that the next-generation schema language and implementation introduced here will be improved as they are tested against a broad variety of real-world documents and research needs. At the same time, the next-generation schema language we describe here, and our reference implementation of a validating parser for documents tagged in conformity with schemas expressed in that schema language, provide a viable starting point for a broad user community that is eager for next-generation functionality that is not easily or naturally implemented purely with XML markup and the existing XML toolkit.

Current widely used parsing strategies for markup technologies are often based on context-free grammars (CFGs), although the properties and restrictions they aim to describe and validate cannot always be expressed without recourse to features that cannot be represented completely within a CFG.^[10] For example, the XML specification (XML 1.0) incorporates a formal, context-free grammar in EBNF notation (EBNF) that seeks to represent what is and is not permitted with XML markup, but that formal grammar must be supplemented, within the specification, with plain prose validity constraints (VC, e.g., An element type must not be declared more than once, §3.2)) and well-formedness constraints (WFC, e.g., The Name in an element’s end-tag must match the element type in the start-tag, §3) because not all requirements for well-formed XML can be represented completely by the features available within a CFG. XML validity and well-formedness constraints can be implemented computationally in a robust, efficient, and scalable manner, but only through processing that transcends parsing and validation against the formal CFG grammar. Insofar as a grammar is a formal representation of a theory of the text, the system we describe in this contribution aims to be sufficiently expressive to admit all desired textual structures (as represented by a project-specific document schema), to recognize any structure not licensed by the schema as invalid, and to do so without recourse to extra-grammatical annotations and implementation features. Insofar as a grammar is also an engineering resource, a priority for our work is that our schema language, designed to maximize legibility for human schema designers, should be able to be compiled (translated) by the computer into a formal grammar that is adequate for efficient, scalable automated parsing and validation.

We regard the general process by which a schema is compiled into a grammar against which a document instance can be parsed and validated as an abstract, high-level metamodel, that is, as independent of any specific implementation in any specific programming language. We provide a particular implementation, then, primarily as a way of verifying whether the metamodel is implementable in principle. The distinction between the abstract metamodel and a concrete implementation invites an eventual comparison of implementations, whether with respect to performance, user experience, or other criteria, even as all implementations are required to emit what is functionally the same result because all implementations must implement the shared metamodel.

Conclusion

Ultimately, the primary aim of this contribution is to elaborate a formal model that is able to express complex phenomena of texts that users might reasonably wish to record, including those not easily represented with XML, and to do so in a way that is theoretically coherent and formally computable. This goal engages with several hard challenges that have not yet been resolved in a satisfactory way in the domain of markup languages, as is clear from, for example, the way Overlap has been a recurrent theme in markup conferences for decades. Much of the present contribution engages explicitly with formal grammar theory, but we also introduce an implementation of a proof-of-concept parser-validator that goes beyond the XML toolkit in being able to process next-generation features not as secondary or external operations, but as part of both the schema language and the grammar to which it compiles. Although our proposal emerged from our work on TagML, it is intended to be usable with any markup language that supports the next-generation features we discuss.^[11]

Left-hand side and right-hand side

A grammar is primarily a set of productions (rules), each of which maps from a left-hand side (LHS) to a right-hand side (RHS). Grammatical productions are similar in some respects to statements in Relax NG compact syntax, where, for example:

chapter = element chapter { title, paragraph+ }

Terminals and non-terminals

The items in the LHS and RHS are either terminals or non-terminals, which can be understood as follows:

For example, a Relax NG production like:

published = attribute published { "yes" | "no" }

Parts of a grammar

A complete grammar has 1) a starting point, 2) a set of non-terminals, 3) a set of terminals, and 4) a set of productions that must ultimately define all non-terminals in terms of terminals.^[13] The LHS of a grammar production must always include a non-terminal; whether it can also include terminals or other non-terminals depends on the type of grammar.^[14]

A schema language may come with built-in, predefined productions, so that, for example, Relax NG compact syntax knows how to compile the grammatically non-terminal keyword text into productions with only terminals (defined with reference to a set of one-character string values) on the RHS. One difference between a schema and a grammar, then, is that a grammar must be complete (that is, must ultimately define everything using only terminals), while a schema language can come with implicit productions that do not need to be spelled out in the schema itself. This is consistent with the fact that a schema prioritizes human legibility because it is intended to be authored directly by humans, while a grammar prioritizes computational tractability because it is intended to be processed by a machine. Part of the parsing process involves compiling (transforming) human-oriented schema rules into machine-oriented grammar productions.

Three classes of grammars

This contribution discusses three types of grammars, which differ with respect to what is or is not permitted on the LHS and RHS. We say more about these types of grammars below, but we can distinguish them concisely now as follows:

Schema languages for XML

There is no need to tell a Balisage audience that there are three grammar-based schema languages in wide use for modeling XML, as listed above: DTD, XML Schema, and Relax NG.^[17] The three schema languages can all be considered tree grammars (thus Manguinhas 2009, §2), and they are largely comparable in the XML structures they are able to model, with two conspicuous exceptions:^[18]

This second difference, concerning Interleave patterns, is important for next-generation features for two reasons:

We discuss the relationship between Interleave and next-generation markup features later in this report.

Existing schema and grammar proposals for managing Overlap

As we look beyond XML, data models and schema languages that have been proposed for managing Overlap include SGML Concur and its XML variant XConcur; Rabbit/duck grammars; and Creole. Because Tennison 2007 includes detailed explanations, examples, bibliography, and critiques of the multiple-hierarchy models Concur, XConcur (including XConcur-Cl, which is the validation component of XConcur), and Rabbit/duck grammars, we say nothing more about those technologies here except to point out that none of them engages explicitly with any next-generation feature other than Overlap. Luminescent, a LMNL parser implemented in XSLT, reflects a perspective similar to that of Rabbit/duck grammars in that it processes LMNL ranges with reference to XML milestone start- and end-markers.^[20] (Tennison and Piez 2002, Luminescent) But because LMNL lacked a schema language at the time Luminescent was developed, Luminescent was designed to perform well-formedness checking, but not schema validation. Other proposals for managing Overlap have included the GODDAG data model and TexMECS markup language (Sperberg-McQueen and Huitfeldt 2004, Huitfeldt and Sperberg-McQueen 2001), which seek to model and manage not only Overlap, but also Discontinuity (Sperberg-McQueen and Huitfeldt 2008). Modeling and tooling based on Rabbit/duck grammars, GODDAG, and TexMECS have been employed in projects implemented by the resource designers and developers (e.g., Sperberg-McQueen 2018), but have not been adopted broadly elsewhere.

Schema-aware Extended Annotation Graphs offers a graph-based approach to validating some next-generation features, performing simulation-based validation by construction. (SAEAG) The authors observe that since Dataguides and Graph Schemas are inferred from the data, they cannot be used as authoring tools (§4), which makes the method unsuitable for our purposes.

Why Creole is different

As far as we have been able to determine, Creole is the only detailed proposal for managing Overlap that is designed to process all structural properties of an entire document with a single grammar instead of validating overlapping hierarchies in ways that are partially or entirely separated from one another. This is consistent with our aim of managing Overlap as an integral feature of our document model. The one detailed publication about Creole, Tennison 2007, describes the design principles, some of which we adopt directly and some of which we either modify or replace with alternatives. Alongside a thorough explanation of the design of Creole and the strategy for processing it, Tennison 2007 reports having built a proof-of-concept implementation in XSLT 2.0 that worked as expected, except that it was insufficiently performant for production use. (25) We discuss performance in greater detail below, when we introduce our own design and implementation.

Attributes and patterns that resolve to attributes do not accept repeatable occurrence indicators (+, *)

Attributes are not repeatable in both XML and the next-generation markup languages that we aim to model. Relax NG compact syntax nonetheless allows attributes and patterns that resolve to attributes to be attached to the repetition indicators + and *. Because a schema cannot override a well-formedness constraint and well-formedness does not permit repetition of attributes, attempts to repeat an attribute because the schema says that it is permitted will nonetheless raise a well-formedness error. Any use of + in association with an attribute is actually understood as required but not repeatable (otherwise represented in Relax NG compact syntax by the absence of any explicit occurrence indicator) and * is understood as optional and not repeatable (otherwise represented by ?). Allowing the schema to say that attributes are repeatable when well-formedness prohibits their repetition means that the schema purports to license XML expressions that are not, in fact, allowed in XML. This means that the schema misrepresents what is possible in the XML it will be used to validate.

Because we take seriously the role of a schema as a human-readable statement of what is and is not permitted in associated document instances, our schema language does not permit the repeatable occurrence indicators + and * to be associated with (non-repeatable) attributes. Because attributes may be optional, they do accept the ? occurrence indicator.

text requires at least one textual character and does not accept repetition occurrence indicators (+, *)

The reserved word text in Relax NG compact syntax means zero or more contiguous textual characters. This is potentially confusing for at least two reasons:

In our schema language the keyword text means one or more textual characters. The Relax NG definition of zero or more textual characters is implicitly optional, but ours is not, which means that text in our system may be followed by ? to mean either no text node, and therefore no characters, or exactly one text node, and therefore one or more characters.

The next-generation markup languages we target continue the XML practice of not permitting adjacent text nodes. In the case of both these next-generation languages and XML, then, any construction involving adjacent text nodes is interpreted as a single merged text node. For that reason we do not permit the repetition occurrence indicators + and * after the keyword text.

Finally, we do not allow the keyword text in Interleave patterns. The only way to interleave text nodes with elements in our schema language is by using the mixed keyword. We require the mixed keyword because it signals to the user that an element contains mixed content more clearly than a repeatable or-group that includes the keyword text.

Attributes are not content

In Relax NG attributes and patterns that resolve to attributes are included in content models alongside elements and the keyword text. Because attributes are properties of elements, rather than content, this is misleading; a Relax NG content model may appear to impose ordering relationships on attributes with respect to both other attributes and actual element content items even though no such ordering relationships are possible. Our schema language will represent attributes separately from actual element content. but the exact mechanism for doing so is still under development.

Mixed content must be represented with the keyword mixed

Relax NG compact syntax can represent mixed content with the keyword mixed, as in

p = element p { mixed { ( a | b )* } }

p = element p { ( a | b | text )* }

p = element p { a* & b* & text }

About our notation

In this report we use the term <element> differently than Tennison 2007. Creole was designed to meet the requirements of LMNL, although Creole is intended to be data-agnostic and therefore applicable to parsing other markup languages that support overlap (Creole is not designed to support discontinuity). (Tennison 2007 26) LMNL is based on ranges, which, unlike XML elements, are generally (but not universally) allowed to overlap.^[24] Tennison 2007 uses the following terms:

Example of Overlap in Creole

Tennison 2007 uses a brief biblical example to review and critique the representation of Overlap in SGML Concur and elsewhere and to illustrate an alternative model and notation for Creole that address the perceived limitations. The biblical example is illustrative and the point is more general: markup hierarchies under a shared root (in this case a root element like <bible>) can overlap in a variety of meaningful ways. This particular example encodes four overlapping structures, as follows: (5–6)

The first two hierarchies are loosely coupled semantically in that books (also chapters) and sections tend to be about something, and we would not expect a titled, topical section to begin in one titled, topical book and end in another. One way to understand this is that a <book> in one hierarchy has a <title> followed by <chapter> children, while the same <book>, in another hierarchy, has the same <title> followed by <section> children. That is, the hierarchies are congruent at a higher (<book>) level and then diverge partially (shared <title> but then <chapter> vs <section>) below that. Neither of these two hierarchies is subordinate to the other structurally because sections may start or end in the middle of chapters (and even, at least potentially, verses) and vice versa. A similar relationship obtains within paragraphs, where a paragraph is the parent of mutually independent tessellated sequences of sentences and of verses.

The example in Tennison 2007 models pages as milestone XML processing instructions with the name new-page; alternatively, pages could be modeled with tessellated milestone start- and end-markers, which is the structure used in the example to model index references. In either case we might consider pages to be subcomponents of the entire Bible (and not only of books or anything at a lower hierarchical level) insofar as new pages may begin either within or between books.

How Concur works in SGML and in Creole

In a traditional context-free production in a schema, the RHS is expanded in order, except that, as described above, Interleave relationships are partially ordered because the operands to the Interleave operator may occur in any order, with the restriction that any order within any of the subcomponents must be maintained. For example, if A, B is interleaved with C, D, the four components may occur in any order only as long as A precedes B and C precedes D. In this case, then, of the 24 possible permutations of the four components, only the following six are allowed: A, B, C, D; A, C, B, D; A, C, D, B; C, D, A, B; C, A, D, B; and C, A, B, D.^[27]

SGML Concur applies to entire documents, while Creole Concur can apply to subtrees within a document. The Creole Concur operator is similar to the Relax NG (and Creole) Interleave operator in that any order within a model that participates in a Concur relationship must be respected. For example, given the first two biblical hierarchies above, neither has a defined relative order with respect to the other, but within the hierarchy of titled sections, each <section> must contain exactly one <header> element followed by one or more <paragraph> elements.

In SGML Concur text tokens in the document instance, unlike element tags, are allowed only in positions where they are simultaneously valid in all concurrent content models. The same is true of Creole Concur, but with an important exception involving partitions that we discuss below. This distinction between markup tokens (which may be part of some but not all models) and text tokens (which must be part of all models unless, under Creole, they are part of partitions) is consistent with our understanding of Concur as concurrent markup over a single, shared document, rather than as concurrent documents. At the same time, the behavior of text tokens has important implications for how sequences can be combined with Concur. Consider, for example, the following Creole schema production:

element root {
  concur {
    element section {
      text
    },
    element chapter {
      text
    }
  }
}

<root><section><chapter>This is an example text</section></chapter></root>

<root><chapter><section>This is an example text</chapter></section></root>

<root><chapter><section>This is an example text</section></chapter></root>

<root><section><chapter>This is an example text</chapter></section></root>

That is, the document tokens are partially ordered because the relative order of the start- and end-tags for the <section> and <chapter> elements is not informational, but the start-tag of each element must precede its corresponding end-tag. The content model for <section> elements does not allow a <chapter> as a child of <section>, and vice versa, but the last two examples are nonetheless valid and unambiguous because the schema defines the elements as concurrent, rather than nesting. It should be clear from this example that schema information may be required to distinguish concurrent relationships from hierarchical (nested) ones.

The following sequence, on the other hand, is not allowed under the production above:

<root><section>This is an </section><chapter>example text</chapter></root>

This example respects the relative order of the markup tokens (the start- and end-tags) in both of the two concurrent sequences: either sequence, by itself, has the correct root element, the correct child element, and correct textual content. The reason this example is invalid is that the text tokens do not adhere to the rule that all text tokens in concurrent hierarchies, unlike markup tokens (start- and end-tags), must be valid in both hierarchies simultaneously. In the example above, the text between the <chapter> tags makes the <section> part of the Concur relationship invalid because the <section> part is defined in a way that does not permit text after the </section> end-tag. Similarly, the text between the <section> tags makes the <chapter> part of the Concur relationship invalid because text is not permitted before the <chapter> start-tag. We will see below that we can resolve this issue by allowing text to appear more broadly in the concurrent content models.

A Concur relationship between two single elements that have textual content is not very interesting, and we can enhance it by adding occurrence indicators that allow the components of the Concur relationship to repeat, as in the following example:

element root {
  concur {
    element section+ {
      text
    },
    element chapter+ {
      text
    }
  }
}

The schema above allows for one or more sections and one or more chapters to overlap in any way as long as all text tokens in a valid document instance are allowed under both hierarchies. This means that:

Under the preceding schema the following sequence is now allowed:^[28]

<root><section><chapter>This is </section><section> an example text</chapter><chapter> And more text</chapter></section></root>

Concur and mixed content

Because the Creole mixed keyword, borrowed from Relax NG, effectively makes text optional before, between, and after the elements to which it is applied, it can be used to simplify the modeling of some Concur relationships. Consider, for example:

element root {
  concur {
    element section {
      text
    },
    mixed {
      element chapter {
        text
      }
    }
  }
}

<root><section><chapter>This is an example text</chapter>more text</section></root>

<root><section><chapter>This is an example text</section></chapter>more text</root>

Using mixed content as described above can simplify modeling concurrent relationships, but that simplification comes with the cost of allowing plain text in places where it might not be part of our mental model of one or another hierarchy in a concurrent relationship. That is, although we can choose to ignore text that we don’t consider an informational part of one or another hierarchy during downstream processing, it is nonetheless part of the content according to the model. This is unlike the situation with markup tokens, as illustrated in the example above, where we can include <chapter> start- and end-tags inside a concurrent <section> element without making the <chapter> part of the content of the <section>.

Tennison 2007 recognized the requirement that all text tokens be part of all overlapping hierarchies as a challenge for effective modeling. For example, the biblical <section> hierarchy requires that a <section> begin with a <header>, but the section header is an editorial intervention that is not part of the text of the Bible, and therefore not part of the hierarchy of chapters and verses. Creole Concur addresses this concern by diverging from SGML Concur in allowing <element> structures alongside <range> structures, where <element> is shorthand for wrapping a <partition> around a <range>. (16) This allows Creole to model text tokens that are not part of all concurrent hierarchies:

In summary, then: Concur in Creole allows the symbols (tags and text tokens) of multiple sequences to be intertwined at the token level as long as:

Concur and Interleave

Although the Concur and Interleave operators are similar in that both model partially ordered content, there are subtle but important differences:

Handling overlap and implementing the Concur operator

Now that we have an understanding of the kinds of sequences that a Concur operator in a schema can validate, we need to find equivalent grammar rules that we can create from those sequences. A CFG, which requires exactly one sequence on the right-hand side of a production, is not capable of expressing a Concur relationship, but a MCSG, which allows one or two sequences on the right-hand side, is. Within the grammar, each production of this type has reorder constraints associated with it that define all possible combinations of tokens of the sequences. All of this apparatus—the two sequences on the right-hand side and the reorder constraints—is invisible to the end user, who interacts directly only with the schema syntax, including the Concur operator.

Grammars are typically written as expressions over symbols, and in our markup domain we use tokens as symbols. The set of token types is derived from the element names, which for any finite set of documents is also a finite set. The tokens can be categorized as:

The following simplified biblical example, tagged with TexMECS Concur, is based on a more elaborate example in Tennison 2007:^[30]

<genesis|
  <chapter n="7"|
    <section|
    <verse n="24"|… a hundred and fifty days.|verse>
  |chapter>
  <chapter n="8"|
  <verse n="1"|God thought of Noah …|verse>
    |section>
  |chapter>
|genesis>

The following schema for the biblical example above is based on features introduced in Tennison 2007. The ~ symbol is the Concur operator, so the second line means that a <genesis> element contains a concurrence of one or more <chapter> elements with one or more <section> elements. Note that we use the term <element> where Tennison 2007 uses <range>):

start = genesis   
genesis = chapter+ ~ section+
chapter = element chapter { attribute n, verse }
section = element section { verse }
verse = element verse { attribute n, text }

This can be compiled to a MCSG as follows:

start := <genesis| genesis_content |genesis>;
genesis_content :=  section optional_more_sections; , chapter optional_more_chapters; 
section := <section| verse |section>;
chapter := <chapter attribute_n | verse |chapter>;
verse := <verse attribute_n "|" text |verse>;
attribute_n := "n" "=" string;
optional_more_sections := section optional_more_sections;
optional_more_sections := epsilon;
optional_more_chapters := chapter optional_more_chapters;
optional_more_chapters := epsilon;

In our notation a semicolon (;) in a production rule marks the end of a single sequence of a symbols on the right-hand side. In a MCSG the right-hand side can contain up to two sequences of symbols, and in such cases we use a comma (,) as a separator between them.

The following table shows the alignment of the input tokens with the tokens of operand 1 (<chapter>) and 2 (<section>) of the Concur operator:

In this table, as in the schema above, sequences of <chapter> and <section> elements observe a Concur relationship. <verse> elements are part of both concurrent hierarchies. An X (in the rows for the <genesis> start- and end-tags) means that the element is not a participant in a Concur relationship. Text nodes (except inside a <partition>, which is not relevant here) are always part of both concurrent hierarchies.

We refer to the relationship between concurrent sequences as a reorder constraint because the right-hand side of the production rule lists one entire sequence before the other entire sequence, regardless of the order of the tokens in the input. When such a rule is used for validation, the goal is to confirm that the input matches a concurrence of the two sequences on the right-hand side. That confirmation requires knowing what is and is not permitted in a concurrence, and those rules are:

The reorder rule of the two sequences means that any implementation must adhere to three rules:

We have to determine whether the input sequence is valid for the operands of the Concur operator, recalling that the text tokens of the two operands have to line up. We do this by thinking of it as an alignment problem, which we address using a method called dynamic programming.^[32] We can approach the task by arranging the tokens in a matrix with the tokens of the first operand serving as column labels and the tokens of the second operand serving as row labels. Initially we enter only the column and row labels; we explain below where the cell values (x) come from:

Starting with just column and row labels, we will fill in the cells as we use the sequence of input tokens to guide our traversal of the matrix from the upper left to the lower right. We can think of this traversal as moving two pointers, both of which start at 0, so that the start coordinate would be (0, 0). When we say that a pointer is on 1, we mean that it is located after the first token. In other words, each pointer is always between the most recently processed token and the next token to be expected in the input. Both pointers start on 0, that is, before the first token in the two sequences has been processed. Our traversal must observe the following output requirements:

Whenever a markup token comes in it must be allowed in the next position in either or both sequences, in which case we increment the respective pointer(s). If a markup token is not allowed at that location in either sequence, the input is not valid. For example:

Text tokens are handled differently. In case of text input, both pointers must point to a text token in their respective operand sequences of tokens. The unusual detail is that this can happen in two ways:

<genesis|
  <section|
  <chapter|Hi|chapter>
  <chapter|Mom|section>
  |chapter>
|genesis>

A schema that supports this markup is:

start = genesis   
genesis = chapter+ ~ section+
chapter = element chapter { text }
section = element section { text }

A matrix that represents how we might traverse this concurrent input, based on the method described above, is:

Handling discontinuity

Discontinuity in TexMECS and TAGML is expressed through the use of suspend- and resume-tags (see the example below), which are allowed only where either an Interleave (recall that mixed content is an Interleave of an element sequence with text) or a Concur relationship is active. This constraint is expected because what discontinuity shares with Interleave and Concur is that the content is partially ordered, that is, tokens that are part of the discontinuous segments must appear in the correct order, but tokens that are not part of the discontinuity may appear before, between, and after them. Sperberg-McQueen and Huitfeldt 2008 explains that:

To accommodate elements that participate in a discontinuity relationship we adjust our MCSG slightly. Here is a sample input file with TexMECS tagging, taken from Sperberg-McQueen and Huitfeldt 2008:

<p|Alice
was beginning to get very tired of sitting
by her sister on the bank, and of having
nothing to do: once or twice she had peeped
into the book her sister was reading, but
it had no pictures or conversations in it,
<q|and what is the use of a book,|-q>
thought Alice
<+q|without pictures or conversation?|q>
|p>

In the example above, Alice’s single thought is tagged as a discontinuity of <q> (quote) elements, interrupted by the phrase thought Alice, which is in the narrator’s voice. The following schema supports this markup:

start = paragraph   
paragraph = element p { mixed { quote } }
quote = element q { text }

The schema compiler translates the preceding schema in the following MCSG:

start := <p| mixed_quote |p>;
mixed_quote = text; , quote;
quote := <q| text optional_discontinuity_quote |q>;
optional_discontinuity_quote := |-q> <+q| text optional_discontinuity_quote;
optional_discontinuity_quote := epsilon

The table below illustrates how the input tokens (leftmost column) are allocated between the two participants in a mixed-content (that is, Interleave) relationship, the discontinuous quotation (operand 1) and the text with which it is mixed (operand 2):

The <p> tags are the parent of both parts of the Interleave; they are marked with an X to show that they are not part of either of the interleaved sequences. When the <q> element is paused, the content needs to come from the other operand until the <q> resume-tag is reached. In this sense discontinuity is comparable to a <partition> within a Concur operator.

Self-overlap with a mildly context-sensitive grammar

Creole introduces concurOneOrMore and concurZeroOrMore operators to manage self-overlap, that is, situations where an element of a particular type overlaps with another element of the same type. Self-overlap requires special handling for two reasons:

The challenge is that the exact disambiguating identifiers that will occur in the document instance cannot be specified in the schema if the schema is to be applicable to more than a single document, as schemas typically are. For that reason, processing will need to recognize when a start-tag with an identifier comes along and store it somewhere until an end-tag with a matching identifier is encountered, so that the parsing process can verify that each opened element is closed in a way that is consistent with schema requirements. We implement this functionality with an attribute grammar, which is an extension on top of context-free grammars that allows production rules to capture part of the input stream, store it in what is called an attribute, and reuse that attribute later in the input stream to recognize whether an identifier given in an end-tag is valid at the location where it occurs.^[35]

Consider the following TexMECS example:

<verse no="23"|God wiped out every living thing
that existed on earth, <index~1 ref="i0037"|man and
<index~2 ref="i0038"|beast|index~1>, reptile and 
bird|index~2>; they were all wiped out over the whole 
earth, and only Noah and his company in the
ark survived.|verse>

In the TexMECS example above, which has been simplified from an example at Tennison 2007 11, Verse 23 contains (self-)overlapping targets of index references, that is, of target spans of text to which entries in an index point. Index reference i0037 refers to the string "man and beast" and index reference i0038 refers to the string "beast, reptile and bird". The two overlap in containing the same substring "beast". If this were XML and the markup read:

<index ref="i0037">man and <index ref="i0038">beast</index>, reptile, and bird</index>

In TexMECS notation, a normal start-tag looks like <index| and a normal end-tag looks like |index>. Self-overlap is a type of concur relationship, and to avoid the misreading of the XML markup described above, self-overlapping elements must record information that associates start-tags with the correct corresponding end-tags, so that, for example, <index~1| and |index~1> are start- and end-tags for the same instance of an <index> element. A schema used to author or validate this document would recognize that the two index reference targets (i0037 and i0038) as instances of an element type <index>, which is to say that the ~1 and ~2 are attributes of the element instance, and not part of the element name. The same relationship might be spelled, in a hypothetical alternative syntax, as <index id="1" ref="i0037"> for the start-tag and </index id="1"> for the end-tag.

Attribute grammars enhance a traditional grammar with the ability to perform (typically small) computations. In the case of a CFG or a MCSG, the left-hand side of a production is a single non-terminal. The right-hand side contains an expansion of the left-hand side into a sequence of terminals and non-terminals (in the case of a CFG) or up to two such sequences (MCSG), and with an attribute grammar the items on the right-hand side may be enriched with expressions that compute a value.

For example a schema containing self-overlapping <index> tags could look like the following:

indexedText = concurOneOrMore { mixed { index* } }
index = element index { attribute ref { text }, text }

A set of grammar rules governing the self-overlapping <index> elements looks like this:

open_index_tag := <index "~" identifier attribute_ref "|";
close_index_tag := |index "~" identifier ">";
identifier := string;
attribute_ref := "ref" "=" string;
indexed_text := interleave_text_index;
interleave_text_index := text; , optional_index;
optional_index := epsilon;
optional_index := open_index_tag concur_close_tag_new_index_tag; [concur_close_tag_new_index_tag.identifier = open_index_tag.identifier]
concur_close_tag_new_index_tag := text close_index_tag; , optional_index; [close_index_tag.identifier == concur_close_tag_new_index_tag.identifier]

An attribute on a grammar should not be confused with an attribute in the XML domain. An attribute on a grammar is implemented as an index number on non-terminals on the right-hand side of a production rule. Next to the production rules are extra statements that specify whether attributes should capture incoming data or whether they should inherit data from an earlier non-terminal in the input stream in order to validate the current input token.