Balisage Paper: On beyond Invisible XML: parsing with implicit (and explicit) next-generation markup

Uses of ixml-like processing

We identify the following three types of situations for ixml-like processing:

Adding markup to an input document (the first and third examples above) assumes that the input can be parsed successfully against a supplied grammar. The second example above makes no such assumption and, instead, seeks to learn whether a parse can or cannot succeed.^[7]

Failure vs error in ixml processing

There are four possible types of outcome of an ixml operation, with the following behaviors described in Invisible XML Specification:

We identify three places in which ixml processing (and our next-generation extension thereof) might fail to emit tagged output:

The first and third of the preceding types of failure are regarded as ixml errors, but the second, perhaps surprisingly, is not. An ixml processor must report the failure, but there is no associated numbered error message. Invisible XML Specification says:

The failure to parse an XML document against a RELAX NG schema that is, itself, valid is regarded as an error in RELAX NG; see, on this topic, the section entitled Error handling in Clark 2002. We find this discrepancy between what ixml and RELAX NG consider to be an error surprising and confusing for the following reason.

The primary use of ixml processing, as described in Invisible XML Specification, is:

The computational pipeline that implements this functionality has three parts:

ixml treats failure in the first of these three stages (cannot parse and interpret the ixml grammar) as a static error, it treats failure in the third stage (cannot emit well-formed XML) as a dynamic error, but it treats failure in the second stage as Not An Error—that is, Invisible XML Specification does not refer to failure as an error and it does not associate a numbered error message with this failure. We find this behavior unintuitive because:

For these reasons, our ixml-like application regards failure to parse an input document against a supplied grammar as a dynamic error.

Grammar terminology

A grammar is expressed as a set of rules (called productions) and map from a left-hand-side (LHS) to a right-hand-side (RHS). For example, ixml

article: metadata, content.

says that an article can be matched by a sequence, in the input, of whatever matches a metadata followed by whatever matches a content.

Syntactic operators that represent repetition, optionality, and alternation are common features of higher-level, human-facing grammars, such as XML schema languages and ixml. A lower-level grammar can be compiled for more convenient machine processing by rewriting the productions to remove those operators and introduce epsilon (ε, which signifies that that portion of a rule can be matched against no input). We discuss what we mean by higher and lower level in the Schemas and grammars section of Haentjens Dekker et al. 2025.

A context-free grammar (CFG) has a single symbol on the LHS and a single sequence of terminal and non-terminal symbols on the RHS.

A mildly context-sensitive grammar (MCSG) also has a single symbol on the LHS, but it may have two sequences on the RHS. The relationship between the two sequences on the right is similar (although not identical) to RELAX NG interleave. RELAX NG interleave is often understood as all of these items in any order, but in addition to that type of unordered content, interleave is also designed to model partially-ordered content. See the section titled Partially ordered content: how Interleave works in Haentjens Dekker et al. 2025 for details. A MCSG rule can be matched only if all parts of both sequences on the RHS are matched in a way that conforms to the ordering of each of the individual sequences, and the rule may incorporate an ordering constraint that describes how the two sequences can be interleaved.

Creole is a proposed schema language for next-generation markup languages, originally designed within the framework of the LMNL project. It is described in Tennison 2007.

In the Schemas and grammars section of Haentjens Dekker et al. 2025 we distinguished the term schema, for productions authored by users (as in a RELAX NG schema), and grammar, for a constrained set of productions, optimized for machine interpretation and processing, that is generated programmatically by compiling the schema into a grammar. While schema design prioritizes human legibility, grammar design prioritizes efficient computational implementation.

That distinction is comparable to the one in Norm Tovey-Walsh 2023 between Extended Backus-Naur forms (EBNF) and Backus-Naur forms (BNF), which explains that BNF grammars are simpler to reason about and simpler for implementations to process. EBNF grammars are easier to author. The How it works section of Coffeepot similarly distinguishes an Invisible XML grammar, authored by a human with EBNF-like syntax and comparable to what we called a schema, and the Earley grammar into which it is compiled, expressed with BNF-like syntax and comparable to what we called a grammar. Because the established term in Invisible XML Specification for the set of productions authored by a human is not schema, but grammar, for the present report we modify the terminology from Haentjens Dekker et al. 2025 and, in this discussion of ixml-like processing, we use the terms ixml-like grammar (instead of schema) and compiled grammar (instead of just grammar).^[11]

Grammars for next-generation features

Next-generation processing requires two additional operators, one for concurrency (overlap) and one for sets (unordered content). In this report and in our implementation we use the following operators:

The principal container unit in Haentjens Dekker et al. 2025 is an element, and elements are subject to possible concurrency (overlap). We followed Tennison 2007 in recognizing also a need for a container unit that would suspend overlap, until the end of the group, in an otherwise overlapping context, which Creole called an element. The term element was not available for this purpose for us because it was already used for our primary container unit, so we represented a container unit that is not subject to concurrency with the keyword PARTITION, with no operator. In our ixml-like grammar a nonterminal that represents a partition is preceded by a double caret (^^).

Our Creole-like schema language also models self-overlap, that is, overlaps of multiple elements of the same type. This sort of phenomenon is well known from annotation applications (such as https://web.hypothes.is/), where users might highlight overlapping strings of text and associate annotations with them. In our Creole-like schema language we adopted the Creole keywords concurOneOrMore and concurZeroOrMore for that purpose, with no assocated operators.

We do not advocate for the specific notations we adopt here for these operators. Our options are constrained by established and sometimes contradictory interpretations of operator characters in RELAX NG, Creole, and ixml, which makes it difficult to rely on user familiarity with the notational conventions of those other specifications. We leave open the question of whether alternative operator characters might ultimately prove more useful than those that we employ here. For what it’s worth, the operators in question appear only in the human-facing Creole-like schema or ixml-like grammar, and not in the compiled grammar, where, as we write in Haentjens Dekker et al. 2025, they are replaced by words like INTERLEAVE and CONCUR.^[13]

Types of grammars for ixml and ixml-like processing

ixml processors generally use context-free grammars (CFG), but, in our implementation, both Creole-like schema validation and ixml-like recognition or transformation rely instead on mildly context-sensitive grammars (MCSG).^[14] In particular, our support for partial order (interleave) requires functionality that is not available directly in a CFG. The Jing RELAX NG validator uses parsing with derivatives for this purpose; we use a MCSG. We illustrate this functionality below.

Thinking about invisible next-generation markup

In this paper we begin to explore the possibility of implementing ixml-like processing by using the same types of mildly context-sensitive grammars (MCSG) that we employed in Haentjens Dekker et al. 2025 for validation against a schema that used Creole-like syntax. We now ask (and answer) three related questions:

The remainder of this section explores the experimentation with invisible next-generation markup that led us to answer the preceding questions, at least provisionally, as we did.

Invisible markup and next-generation features

ixml is able to parse certain types of overlap, which it models as ambiguity. For example, assume we have the following excerpt from Shakespeare’s Hamlet:

GERTRUDE
Good Hamlet, cast thy nighted colour off,
And let thine eye look like a friend on Denmark.
Do not for ever with thy vailed lids
Seek for thy noble father in the dust:
Thou know'st 'tis common; all that lives must die,
Passing through nature to eternity.
HAMLET
Ay, madam, it is common.
GERTRUDE
If it be,
Why seems it so particular with thee?

These three speeches contain eight lines of iambic pentameter, and the detail that interests us is that the seventh metrical line is split over two speakers, where Hamlet speaks seven syllables and Gertrude speaks three.^[16] We can visualize these overlapping structures with the following graph:

Overlapping hierarchies in Hamlet

The left-most (Speeches) and rightmost (Metrical lines) nodes both represent the same root element and the gray rectangles in the middle represent the plain text, all of which is part of both hierarchies. We have chosen to model speaker names as part of the first metrical line of the speech, but we connect them to the Speech and Line nodes with dotted edges to distinguish them from spoken text. The last five gray textual rectangles are modeled, to the left, as two speeches, one by Hamlet and one by Gertrude, and, to the right, as two lines, one split between Hamlet and Gertrude and the other by Gertrude alone.That is, at this location speeches and metrical lines overlap, and neither type wholly and consistently contains the other.

As we ingest and parse the plain text input, we identify the transition between speeches by recognizing that each speech begins with a speaker name and each speech ends before the next speaker name or at the end of the document. We identify the transition between metrical lines by recognizing that each metrical line begins at the beginning of the document or after another metrical line and ends as soon as we have accumulated ten or eleven syllables with a (whitespace-separated) word before a newline character.^[17] Because English syllabification is not easily deduced from English orthography, we assume a pre-processing NLP operation that prepends a running syllable count to each word token (speech only, not counting speaker names), and resets when the total reaches 10 or 11.^[18] The output of that preprocessing step looks like:

GERTRUDE
1Good 3Hamlet, 4cast 5thy 7nighted 9colour 10off,
1And 2let 3thine 4eye 5look 6like 7a 8friend 9on 11Denmark.
1Do 2not 3for 5ever 6with 7thy 9vailed 10lids
1Seek 2for 3thy 5noble 7father 8in 9the 10dust:
1Thou 2know'st 3'tis 5common; 6all 7that 8lives 9must 10die,
2Passing 3through 5nature 6to 10eternity.
HAMLET
1Ay, 3madam, 4it 5is 7common.
GERTRUDE
8If 9it 10be,
1Why 2seems 3it 4so 8particular 9with 10thee?

Our goal is to tag both speeches (there are three: by Gertrude, then Hamlet, and then Gertrude again) and metrical lines (there are eight: six by Gertrude, then one shared by Hamlet and Gertrude, and then one more by Gertrude). A meaningful feature of this task is that the overlapping hierarchies are fully tesselated, that is, that the document could be tagged in XML as an uninterrupted (except by insignificant whitespace) sequence of metrical lines, which, in our modeling, may have speaker-name children, or as a sequence of of uninterrupted (except by insignificant whitespace) speeches, which must have, as a first child, a speaker-name element. These are easily modeled with ixml, as follows:

We can merge the two ixml grammars by changing the first rule (for hamlet) to allow either one or the other, that is, to separate the two with an or connector (;).^[19] Below is an ixml grammar that does that, which incorporates the following changes:

ixml version "1.1".
{ shared }
hamlet: (m_line)++eol; speech++eol.
-eol: -#a.
-sp: " ".

{ metrical only }
m_line>line: (token; m_speaker)+, f_token.
-f_token: ddigit, [L; P]+.
-token: digit, [L; P]+, (sp; eol).
m_speaker>speaker: ["A"-"Z"]+, eol.
-digit: -["0"-"9"].
-ddigit: digit, digit.
{ speech only }

speech: speaker, eol, line++eol.
speaker: ["A"-"Z"]+.
line: word++sp.
-word: digits, [L; P]+.
-digits: -["0"-"9"]+.

This grammar is ambiguous, with two possible parses, which correspond to the outputs of the two individual grammars:

<ixml parses="2" totalParses="2">
  <hamlet xmlns:ixml='http://invisiblexml.org/NS' ixml:state='ambiguous'>
     <line>
        <speaker>GERTRUDE</speaker>Good Hamlet, cast thy nighted colour off,</line>
     <line>And let thine eye look like a friend on Denmark.</line>
     <line>Do not for ever with thy vailed lids</line>
     <line>Seek for thy noble father in the dust:</line>
     <line>Thou know'st 'tis common; all that lives must die,</line>
     <line>Passing through nature to eternity.</line>
     <line>
        <speaker>HAMLET</speaker>Ay, madam, it is common.
        <speaker>GERTRUDE</speaker>If it be,</line>
     <line>Why seems it so particular with thee?</line>
  </hamlet>
  <hamlet xmlns:ixml='http://invisiblexml.org/NS' ixml:state='ambiguous'>
     <speech>
        <speaker>GERTRUDE</speaker>
        <line>Good Hamlet, cast thy nighted colour off,</line>
        <line>And let thine eye look like a friend on Denmark.</line>
        <line>Do not for ever with thy vailed lids</line>
        <line>Seek for thy noble father in the dust:</line>
        <line>Thou know'st 'tis common; all that lives must die,</line>
        <line>Passing through nature to eternity.</line>
     </speech>
     <speech>
        <speaker>HAMLET</speaker>
        <line>Ay, madam, it is common.</line>
     </speech>
     <speech>
        <speaker>GERTRUDE</speaker>
        <line>If it be,</line>
        <line>Why seems it so particular with thee?</line>
     </speech>
  </hamlet>
</ixml>

This application of renaming is seductive because it is easy to implement and because a human intuitively understands that the concept line has different meanings with respect to meter and orthographic lines in a printed script. At the same time, applying this type of renaming in an XML context associates the same element type with two different meanings, which impinges on the ability of the markup to make sameness and difference accessible in an intuitive way to automated processing. It is, to be sure, easy to preserve different names for the two types of lines, should that prove more useful down stream.

Our next task was to see whether ixml could create LMNL output that could contain overlapping markup in a single serialization. LMNL is, of course, able to represent overlap, but ixml is able to serialize only as XML. We work around that discrepancy in the following ways:

Here is an unambiguous ixml grammar that creates LMNL output:

hamlet: +#a, +"[hamlet}", +#a, first_speaker, body, +"{line]", +#a, +"{hamlet]", -#a?, +#a. 

{ First line precedes line traversal, open first line and first speech and process speaker 
  Transitions below depend on newline, and first line has no preceding newline
}
-first_speaker: +"[line}[speech}[speaker}", speaker, +"{speaker] ", no_eol. 
-body: soft_line; hard_line.

{ STATE MACHINE: each line transition signals one of four possible states based on end of line }
 
{ STATE 1: Line ending in a single-digit token continues metrical line with new speaker }
-soft_line: token_sp*, token_end, -#a, soft_speaker_change. 

{ STATES 2, 3, 4: Line ending in a double-digit f_token 
  STATE 2: new metrical line continues with same speaker 
  STATE 3: new metrical line changes speaker
  STATE 4: no new metrical line means end of file }
-hard_line: token_sp*, f_token_end, 
            (hard_continuation; hard_speaker_change; final_line). 

{ Inject a space explicitly between mid-line speech boundaries and continue }
-soft_speaker_change: +"{speech] [speech}[speaker}", speaker, +"{speaker] ", no_eol, body.

{ After a hard line ending insert line transition tags with newline between and continue }
-hard_continuation: +"{line]", #a, +"[line}", body. 

{ Remove space character between closing speech and line tags }
-hard_speaker_change: +"{speech]{line]", #a, +"[line}[speech}[speaker}", speaker, +"{speaker] ", no_eol, body. 

-final_line: +"{speech]". 

{ THREE TYPES OF METRICAL-LINE TOKENS, PLUS SPEAKER:
  token_sp: Mid-line tokens must be followed by a space 
  token_end: Line-final token that is not end of metrical line
  f_token_end: Line-final token that signals end of metrical line
  speaker: all upper case }
-token_sp: digit, [L; P]+, sp. 
-token_end: digit, [L; P]+. 
-f_token_end: ddigit, [L; P]+. 
-speaker: ["A"-"Z"]+. 

{ Misc }
-digit: -["0"-"9"]. 
-ddigit: digit, digit. 
-no_eol: -#a. 
-sp: " ".

The output is:

<hamlet>
[hamlet}
[line}[speech}[speaker}GERTRUDE{speaker] Good Hamlet, cast thy nighted colour off,{line]
[line}And let thine eye look like a friend on Denmark.{line]
[line}Do not for ever with thy vailed lids{line]
[line}Seek for thy noble father in the dust:{line]
[line}Thou know'st 'tis common; all that lives must die,{line]
[line}Passing through nature to eternity.{speech]{line]
[line}[speech}[speaker}HAMLET{speaker] Ay, madam, it is common.{speech] [speech}[speaker}GERTRUDE{speaker] If it be,{line]
[line}Why seems it so particular with thee?{speech]{line]
{hamlet]
</hamlet>

We note that this is not a general-purpose invisible LMNL processing model for at least the following reasons:

The most important detail is that the ixml that produces our LMNL output is complex because it needs to recognize and act on the interaction of two hierarchies, and not on each of them separately from the other. Non-ambiguous grammars that recognize transitions in these two hierarchies independently of each other are not supported directly in ixml, and we work around that limitation by consuming tokens from both the metrical-line and the speech hierarchies before recognizing and responding to a specific state that depends on sequences of those two types of tokens. Our ixml grammar that emits LMNL would be simpler if we allowed it to recognize and process transitions in the two hierarchies one by one, so that each could be managed independently of the other.

LMNL can regard adjacent tags as simultaneous, but for human legibility we wanted to avoid transitions like:

[line}Passing through nature to eternity.{line]
[line}{speech][speech}[speaker}HAMLET{speaker] Ay, madam, …

This requirement frustrated our ability to treat both line and speech transitions simply as milestones. For example, if we wanted always to rewrite an incoming metrical line transition (newline) as {line]\n[line} and also always to rewrite an incoming speech transition as {speech] [speech}, it would not be possible to emit {speech]{line]\n[line}[speech}. Our grammar works around this limitation successfully, but only by complicating the set of productions, and doing so in a way that does not scale well with the incorporation of additional overlapping hierarchies.

Input issues

Ambiguity not resolved by concurrency

Standard ixml parses the input into a forest, from which it then selects and serializes (or, rather, attempts to serialize) one tree. A MCSG, though, allows us to regard multiple parses of the same input not as ambiguity, but as concurrency. If we think of ambiguity as this or that and concurrency as both this and that simultaneously, we might model ambiguity as multiple trees, from which we then select exactly one for serialization, and concurrency as a graph, that is, a forest within which all trees are simultaneously available and selection among them is not part of the model. The preceding suggests two points of comparison, input parsing and output serialization, as follows:

The preceding addresses only the type of ambiguity that arises in ixml when the same input matches multiple patterns. It does not address some other types of ambiguity. Here are two examples:

Example #1: The following ixml grammar is ambiguous:

doc: CAT; ANIMAL.
CAT: "cat".
ANIMAL: "cat".

When used to parse the input cat, it would report ambiguity, with the following two parses: The same grammar would also be ambiguous under our proposed enhancements for next-generation features. The difference is that our proposal would also support the following alternative grammar (where ~~ means CONCUR), where:

doc: CAT ~~ ANIMAL.
CAT: "cat".
ANIMAL: "cat".

The single unambiguous LMNL output of parsing the input cat against this grammar is [ANIMAL}[CAT}cat{ANIMAL]{CAT]

If we regard the context as overlap, that is, if we want to tag the text as both <CAT> and <ANIMAL> simultaneously, we could select the concur operator, and if we want to regard the document as having two competing parses, we could select the alternation operator. Our point with this example is that if we want to describe the situation as an alternative, the availability of a concur operator does not help avoid ambiguity because the concept of alternative, in this example, is inherently structurally ambiguous.

Example #2: Given the Creole-like grammar like the following:

doc: A+ ~~ B+.
A: [“x”]+.
B: [“x”]+.

This says that a doc contains one or more instances of A that run concurrently with one or more instances of B. Since the only content of both A and B is x, it means that every instances of the character x must be within both an A and a B. This, in turn, means that: The examples above correspond to what Norm Tovey-Walsh 2025 calls vertical (our example #1) and horizontal (our example #2) ambiguity. The point of this example is that although concurrency is a way of understanding some instances of ambiguity, here we have both vertical and horizontal ambiguity even within a concurrent model.

Serialization considerations

Standard ixml parses the input into a forest, from which it then selects and serializes (or, rather, attempts to serialize) one tree. A grammar that supports concurrency, though, allows us, at least in some situations, to regard multiple parses of the same input not as ambiguity, but as concurrency. If we think of ambiguity as this or that and concurrency as both this and that simultaneously, we might model ambiguity as multiple trees, from which we can then select exactly one at a time for serialization, and concurrency as a graph, that is, a forest within which all trees are simultaneously available and selection among them is not part of the model. A forest with concurrent hierarchies could then be serialized, in its entirety, with a next-generation markup language like LMNL or TexMECS or TAGML.

The preceding suggests two points of comparison, input parsing and output serialization, as follows:

The preceding suggests that where users need to model concurrency, parsing with a concurrency operator and modeling as a graph that can be serialized in its entirety offers a formal model that matches the mental model. Furthermore, it does so without structural ambiguity because instead of having to choose between coexisting paths it regards all paths as simultaneously available.

How validation and generation are similar and different

The Creole-like and ixml-like technologies described above are similar on both the syntactic and modeling levels, which we elaborate below.

What those similarities and differences mean for tool development

Our approaches to schema validation (Creole-like) and to adding markup (ixml-like) are sufficiently similar that we found it useful to explore the development of a shared data model and a shared code base. Below we discuss where our Creole-like processing and our ixml-like processing are similar and where they are different.

Discussion

As this section has shown, despite the patent differences in the XML ecosystem between the roles of schema validation, one the one hand, and the addition of explicit markup, on the other, the tasks have much in common. Those similarities create an opportunity to develop tools that rely on a shared data model and a largely shared code base.

There is, at the same time, good reason that the XML toolkit does not include validation and markup-generation tools that employ a shared data model and code base. These include: