Rabbit/duck grammars: a validation method for overlapping structures

Well-formedness checking

Brzozowski derivatives are conventionally used to recognize or reason about regular languages. But with a couple of extensions, they can also be used to parse well-formed XML.

The first extension is to define an expression language slightly different from regular expressions as defined either conventionally or by Brzozowski. I shall call these language expressions rather that regular expressions, because the languages they denote are not necessarily regular. Each expression denotes a set of strings, and may be said to match any string in that language. The language expressions of interest here may take any of the following forms:

• elem( g ) matches an element with generic identifier g.
• stag( g ) matches a start-tag for an element with generic identifier g.
• etag( g ) matches an end-tag for an element with generic identifier g.
• #PCDATA matches a sequence of zero or more characters. It is intrinsically nullable.
• W denotes a string of well-balanced XML; i.e., it is (#PCDATA | elem( g ))*, where g need not be the same for all elements matched. When parsing well-formed XML, W can be used to represent the expected content of any element.
• X matches an arbitrary XML document; i.e., it is elem( g ) for any generic identifier g
• ε matches the empty string.
• ∅ matches nothing (it denotes the empty set).
• If F and G are expressions, then (F G) is an expression denoting the set of strings formed by concatenating a string in F with one in G.
• If F and G are expressions, then (F | G) is an expression denoting the union of F and G.
• If F and G are expressions, then (F & G) is an expression denoting the set of strings formed by interleaving a string in F with a string in G.¹⁸
• If F and G are expressions, then (F ∧ G) is an expression denoting the intersection of F and G.

The second extension is to define an infinite input alphabet. Assume that the input stream is a sequence of symbols each of which is one of the following:

• sole( g ) denotes a sole-tag for an empty element with generic identifier g. For purposes of calculating derivatives, this is treated as if the input were the two-symbol string “stag( g ) etag( g )”.
• stag( g ) denotes a start-tag for an element with generic identifier g.
• etag( g ) denotes an end-tag for an element with generic identifier g.
• pcdata() denotes a sequence of one or more characters.

As usual, the derivative of an expression E with respect to a sequence of symbols x ₁, x ₂, x ₃, ..., x _n ,is found by finding the derivative of E with respect to x ₁, then the derivative of D _{x 1} E with respect to x ₂, and so on. Formally,

A sequence of input symbols d is well-formed XML if and only if D _d X is nullable, when the rules for derivatives are as described below.

The third extension is the the derivative of a primitive language expression with respect to an input symbol may be something other than ε or ∅. Derivatives of compound expressions (concatenation, disjunction, conjunction) are given in [Brzozowski 1964] and need not be repeated here. [Sperberg-McQueen 2005] defines derivatives for interleave.

When x = stag( h ), then

• D _x elem( g ) = (W etag( g )) if h = g, otherwise ∅.
• D _x stag( g ) = ε if h = g, otherwise ∅.
• D _x etag( g ) = D _x #PCDATA = ∅.
• D _x W = (W etag( g ) W).
• D _x X = (W etag( g )).
• D _x ε = D _x ∅ = ∅.

When x = etag( h ), then

• D _x elem( g ) = D _x stag( g ) = ∅.
• D _x etag( g ) = ε if h = g, otherwise ∅.
• D _x #PCDATA = D _x W = D _x X = D _x ε = D _x ∅ = ∅.

When x = pcdata(), then

• D _x elem( g ) = D _x stag( g ) = D _x etag( g ) = ∅.
• D _x #PCDATA = ε.
• D _x X = D _x W = D _x ε = D _x ∅ = ∅.

Examples of using these rules to check XML well-formedness are given in appendix 7-1.

The reader will note that the derivative, which represents the expected sequence of tokens to come, is being used as a stack: when we encounter a start-tag in the input which matches an elem( g ) in the expression being matched, we push (W etag( g )) onto the stack by placing it at the front of the derivative.

Validation

This method can be applied to validation as well, by changing just one rule. When stag( g ) in the input matches the expression elem( g ), the rules just given make the derivative be (W etag( g )): in well-formed XML, what follows the start-tag of any element is well-formed XML followed by the end-tag of that element. To validate against a DTD, all we need to do is to replace W in the derivative with the content model of the element. If we write the expression “cm( g )” to denote the content model of element type g, and “[[cm( g )]]” to denote the value of that expression (i.e. to indicate that the expression should be replaced by its value), the rule becomes:

• D _stag(h) elem( g ) = ([[cm( g )]] etag( g )) if h = g, otherwise ∅.

For example, consider a vocabulary for serializing binary trees whose definition (in DTD syntax) is:

<!ELEMENT tree ((tree, tree) | leaf) >
<!ELEMENT leaf (#PCDATA) >

<tree><leaf>42</leaf></tree>

We start with the expression elem(tree) and validate the input stream “stag(tree), stag(leaf), pcdata(), etag(leaf), etag(tree)”:

E ₀ = elem(tree)

E ₁ = D _stag(tree) E ₀ = [[cm(tree)]], etag(tree) = ((elem(tree), elem(tree)) | elem(leaf)), etag(tree)

E ₂ = D _stag(leaf) E ₁ = ((∅, elem(tree)) | ([[cm(leaf)]], etag(leaf))), etag(tree) = ((∅) | ([[cm(leaf)]], etag(leaf))), etag(tree) = [[cm(leaf)]], etag(leaf), etag(tree) = #PCDATA, etag(leaf), etag(tree)

E ₃ = D _pcdata() E ₂ = ε, etag(leaf), etag(tree) = etag(leaf), etag(tree)

E ₄ = D _etag(leaf) E ₃ = ε, etag(tree) = etag(tree)

E ₅ = D _etag(tree) E ₄ = ε

Further examples of validation using Brzozowski derivatives are given in appendix 7-2.

The extended-link structure

From the point of view of the extended link markup, the structure of a document is quite simple: a text is a series of link elements intermixed with character data.

<!GRAMMAR text [
<!ELEMENT text (#PCDATA | link)* >
<!ELEMENT link (end+) >
<!ATTLIST link
          type CDATA     #REQUIRED >
<!ELEMENT end  EMPTY >
<!ATTLIST end
          role CDATA     #REQUIRED
          loc  IDREFS    #REQUIRED >
]>

<!GRAMMAR text [
<!ENTITY % tags.comp "#tag(div) | #tag(head) 
  | #tag(p) | #tag(s)" >
<!ENTITY % tags.phys "#tag(vol) | #tag(page) 
  | #tag(col) | #tag(block) | #tag(line)" >
<!ENTITY % tags.inscr "#tag(add) | #tag(del) 
  | #tag(restore) | #tag(hi)" >
<!ENTITY % tags.other "%tags.comp; 
  | %tags.phys; | %tags.inscr;">

<!ELEMENT text (#PCDATA | link | %tags.other;)* >
<!ELEMENT link (end+) >
<!ATTLIST link
          type CDATA     #REQUIRED >
<!ELEMENT end  EMPTY >
<!ATTLIST end
          role CDATA     #REQUIRED
          loc  IDREFS    #REQUIRED >
]>

The compositional hierarchy

The compositional hierarchy has a structure whose general outline will be familiar from many familiar document markup languages.

<!GRAMMAR text [
<!ELEMENT text (head, p*, div*) >
<!ELEMENT div  (head?, p*, div*) >
<!ELEMENT p    (s+) >
<!ELEMENT head (#PCDATA) >
<!ELEMENT s    (#PCDATA | a)* >
<!ELEMENT a    (#PCDATA)* >

<!ELEMENT link IGNORE >
]>

The declaration of link as IGNORE makes link elements and their content invisible to this grammar. It follows that no start- or end-tags for text, div, etc., will be seen inside any link elements, and thus that link elements cannot overlap any first-class elements declared in this grammar. We need not declare end elements as fourth-class here: since they occur only within link elements, they are guaranteed invisible to this grammar.

One might be tempted to try to enforce the prohibition on overlaps with headings by a similar maneuver, and declare head as IGNORE in all the other grammars. But this would prevent multi-line headings, as well as preventing highlighting from occurring in headings. To enforce the prohibition effectively, we will need a more complicated version of the compositional grammar, which explicitly allows tags from the physical hierarchy everywhere except in headings:

<!GRAMMAR text [
<!ENTITY % tags.phys "#tag(vol) | #tag(page) 
  | #tag(col) | #tag(block) | #tag(line)" >
<!ENTITY % x "(%tags.phys;)*">

<!ELEMENT text (%x;, head, %x;, 
                     (p, %x;)*, 
                     (div, %x;)*) >
<!ELEMENT div  (%x;, (head, %x;)?, 
                     (p, %x;)*, 
                     (div, %x;)*) >
<!ELEMENT p    (%x;, (s, %x;)+) >
<!ELEMENT head (#PCDATA)* >
<!ELEMENT s    (#PCDATA | a | %tags.phys;)* >
<!ELEMENT a    (#PCDATA | %tags.phys;)* >

<!ELEMENT link IGNORE >
]>

Note that this grammar does nothing to enforce the constraint forbidding any of these elements from overlapping with volumes. That will be taken up in section 5-1-5.

The physical hierarchy

The physical grammar defines a fairly straightforward hierarchy of volumes, pages, columns, text blocks, and lines. Some of the levels of hierarchy are of interest only for particularly detailed markup or particularly complex physical organization of the source; they can be omitted when not necessary. Thus col should be used only if there are at least two columns on the page, block only if there are at least two text blocks in the column, etc.

<!GRAMMAR text [
<!ELEMENT text  (page+ | vol{2,∞}) >
<!ELEMENT vol   (page+) >
<!ATTLIST vol   n CDATA #IMPLIED >
<!ELEMENT page  (line+ 
                   | block{2,∞} 
                   | col{2,∞}) >
<!ATTLIST page  n CDATA #IMPLIED >
<!ELEMENT col   (line+ 
                   | block{2,∞}) >
<!ATTLIST col   n CDATA #IMPLIED >
<!ELEMENT block (line+) >
<!ATTLIST block n CDATA #IMPLIED >
<!ELEMENT line  (#PCDATA) >
<!ATTLIST line  n CDATA #IMPLIED >

<!ELEMENT link IGNORE >
]>

The inscription hierarchies

Since the elements related to inscription can overlap each other, they cannot all be in the same grammar; we will require one grammar each for additions, deletions, and highlighting. Since the elements are defined as not spanning page boundaries, we can conveniently include the page element in each of the inscription grammars.

Since additions do not self-overlap, their grammar is very straightforward:

<!GRAMMAR text [
<!ELEMENT text (page+) >
<!ELEMENT page (#PCDATA | add)* >
<!ELEMENT add  (#PCDATA | add)* >

<!ELEMENT link IGNORE >
]>

Highlighting is slightly more complex, since highlighted phrases can both nest within each other and overlap each other:

<!GRAMMAR text [
<!ELEMENT text (page+) >
<!ELEMENT page #overlap((#PCDATA 
                       | ~hi~ | #tag(hi))*) >
<!ELEMENT hi   #overlap((#PCDATA 
                       | ~hi~ | #tag(hi))*) >

<!ELEMENT link IGNORE >
]>

Deletions add the complication that restore elements may occur within deletions and may be overlapped by deletions other than their parent(s):

<!GRAMMAR text [
<!ELEMENT text (page+) >
<!ELEMENT page #overlap((#PCDATA 
                       | ~del~ | #tag(del))*) >
<!ELEMENT del  #overlap((#PCDATA | restore
                       | ~del~ | #tag(del))*) >
<!ELEMENT restore #overlap((#PCDATA
                       | ~del~ | #tag(del))*) >

<!ELEMENT link IGNORE >
]>

Miscellaneous constraints

The grammars thus far given have enforced all of the constraints outlined except one: that nothing may overlap any vol element.

This could probably be accomplished by suitably careful inclusion of #tag(vol) tokens at the right places in the right content models, but it is simpler just to ensure that vol is described as containing (directly or indirectly) each element other than text from all of the other hierarchies. Part of this has already been done: it follows from the physical and inscription grammars given above that the first-class elements in those grammars all nest within vol elements.¹⁹ The physical grammar also guarantees that vol does not overlap link. The remainder of the elements in the vocabulary can be handled with the following grammar, which requires only that the first-class elements all nest properly:

<!GRAMMAR text [
<!ELEMENT text (vol | head | div | p | s | a)* >
<!ELEMENT vol  (vol | head | div | p | s | a)* >
<!ELEMENT head (vol | head | div | p | s | a)* >
<!ELEMENT div  (vol | head | div | p | s | a)* >
<!ELEMENT p    (vol | head | div | p | s | a)* >
<!ELEMENT s    (vol | head | div | p | s | a)* >
<!ELEMENT a    (vol | head | div | p | s | a)* >
]>

A well-formed document

A simple example may serve to illustrate the process. Let the input stream d be

<a>www<b><c/>xxx</b>yyy<d/>zzz</a>

E ₀ = X

E ₁ = D _stag(a) E ₀ = W etag(a)

E ₂ = D _pcdata() E ₁ = E ₁

E ₃ = D _stag(b) E ₂ = W etag(b) W etag(a)

E ₄ = D _stag(c) E ₃ = W etag(c) W etag(b) W etag(a)

E ₅ = D _etag(c) E ₄ = W etag(b) W etag(a) = E ₂

E ₆ = D _pcdata() E ₅ = E ₅

E ₇ = D _etag(b) E ₆ = W etag(a) = E ₁

E ₈ = D _pcdata() E ₇ = E ₇

E ₉ = D _stag(d) E ₈ = W etag(d) W etag(a)

E ₁₀ = D _etag(d) E ₉ = W etag(a) = E ₁

E ₁₁ = D _pcdata() E ₁₀ = E ₁₀

E ₁₂ = D _etag(a) E ₁₁ = ε

An ill-formed data stream

If we parse an ill-formed stream, however, we should get an error. Let the input stream d be

<a>xxx<b>yyy</a>zzz</b>

E ₀ = X

E ₁ = D _stag(a) E ₀ = W etag(a)

E ₂ = D _pcdata() E ₁ = E ₁

E ₃ = D _stag(b) E ₂ = W etag(b) W etag(a)

E ₄ = D _pcdata() E ₃ = E ₃

E ₅ = D _etag(a) E ₄ = ∅

E ₆ = D _pcdata() E ₅ = ∅

E ₇ = D _etag(b) E ₆ = ∅

A valid instance

Let the DTD be

<!DOCTYPE a [
<!ELEMENT a (b, (c | d | e){2,&infin;}, b*) >
<!ELEMENT b EMPTY >
<!ELEMENT c EMPTY >
<!ELEMENT d EMPTY >
<!ELEMENT e EMPTY >
]>

<a><b/><d/><e/></a>

E ₀ = X

E ₁ = D _stag(a) E ₀

= cm(a) etag(a)

= (elem(b) (elem(c) | elem(d) | elem(e)){2,∞} (elem(b))*) etag(a)

E ₂ = D _sole(b) E ₁

= D _sole(b)(elem(b) (elem(c) | elem(d) | elem(e)){2,∞} (elem(b))* etag(a))

= (D _sole(b)(elem(b)) (elem(c) | elem(d) | elem(e)){2,∞} (elem(b))* etag(a))

= (ε (elem(c) | elem(d) | elem(e)){2,∞} (elem(b))* etag(a))

= ( (elem(c) | elem(d) | elem(e)){2,∞} (elem(b))* etag(a))

E ₃ = D _sole(d) E ₂

= D _sole(d)((elem(c) | elem(d) | elem(e)){2,∞} (elem(b))* etag(a))

= (D _sole(d)((elem(c) | elem(d) | elem(e)){2,∞}) (elem(b))* etag(a))

= ((D _sole(d)(elem(c) | elem(d) | elem(e)) (elem(c) | elem(d) | elem(e)){1,∞}) (elem(b))* etag(a))

= (((D _sole(d) elem(c) | D _sole(d) elem(d) | D _sole(d) elem(e)) (elem(c) | elem(d) | elem(e)){1,∞}) (elem(b))* etag(a))

= (((∅ | ε | ∅) (elem(c) | elem(d) | elem(e)){1,∞}) (elem(b))* etag(a))

= (((ε)) (elem(c) | elem(d) | elem(e)){1,∞} (elem(b))* etag(a))

= ( (elem(c) | elem(d) | elem(e)){1,∞} (elem(b))* etag(a))

E ₄ = D _sole(e) E ₃

= D _sole(e)( (elem(c) | elem(d) | elem(e)){1,∞} (elem(b))* etag(a))

= (D _sole(e)((elem(c) | elem(d) | elem(e)){1,∞}) (elem(b))* etag(a))

= (((D _sole(e)(elem(c) | elem(d) | elem(e)) (elem(c) | elem(d) | elem(e)){0,∞})) (elem(b))* etag(a))

= ((((D _sole(e) elem(c) | D _sole(e) elem(d) | D _sole(e) elem(e)) (elem(c) | elem(d) | elem(e)){0,∞})) (elem(b))* etag(a))

= ((((∅ | ∅ | ε) (elem(c) | elem(d) | elem(e)){0,∞})) (elem(b))* etag(a))

= ((((ε) (elem(c) | elem(d) | elem(e)){0,∞})) (elem(b))* etag(a))

= ( (elem(c) | elem(d) | elem(e)){0,∞} (elem(b))* etag(a))

E ₅ = D _etag(a) E ₄

= D _etag(a)((elem(c) | elem(d) | elem(e)){0,∞} (elem(b))* etag(a))

= (D _etag(a)((elem(c) | elem(d) | elem(e)){0,∞}) (elem(b))* etag(a)) | (D _etag(a)(elem(b))* etag(a)) | (D _etag(a) etag(a))

= (∅ (elem(b))* etag(a)) | (∅ etag(a)) | (D _etag(a) etag(a))

= (∅ | ∅ | D _etag(a) etag(a))

= D _etag(a) etag(a)

= ε

An invalid document

If we try an invalid document, we produce ∅, not a nullable expression. Let d be

<a><b/><d/></a>

E ₀ = X

E ₁ = D _stag(a) E ₀

= cm(a) etag(a)

= (elem(b) (elem(c) | elem(d) | elem(e)){2,∞} (elem(b))*) etag(a)

E ₂ = D _sole(b) E ₁

= D _sole(b)((elem(b) (elem(c) | elem(d) | elem(e)){2,∞} (elem(b))*) etag(a))

= ( (elem(c) | elem(d) | elem(e)){2,∞} (elem(b))* etag(a))

E ₃ = D _sole(d) E ₂

= D _sole(d)( (elem(c) | elem(d) | elem(e)){2,∞} (elem(b))* etag(a))

= (D _sole(d)(elem(c) | elem(d) | elem(e)) (elem(c) | elem(d) | elem(e)){1,∞} (elem(b))* etag(a))

= (ε (elem(c) | elem(d) | elem(e)){1,∞} (elem(b))* etag(a))

= ( (elem(c) | elem(d) | elem(e)){1,∞} (elem(b))* etag(a))

E ₄ = D _etag(a) E ₃

= D _etag(a)( (elem(c) | elem(d) | elem(e)){1,∞} (elem(b))* etag(a))

= (D _etag(a)((elem(c) | elem(d) | elem(e)){1,∞}) (elem(b))* etag(a))

= ((D _etag(a)(elem(c) | elem(d) | elem(e)) (elem(c) | elem(d) | elem(e)){1,∞}) (elem(b))* etag(a))

= (((D _etag(a) elem(c) | D _etag(a) elem(d) | D _etag(a) elem(e)) (elem(c) | elem(d) | elem(e)){1,∞}) (elem(b))* etag(a))

= (((∅ | ∅ | ∅) (elem(c) | elem(d) | elem(e)){1,∞}) (elem(b))* etag(a))

= (∅ (elem(c) | elem(d) | elem(e)){1,∞} (elem(b))* etag(a))

= ∅

A valid instance

Let grammar 1 be the grammar given in section 2-2 for the dramatic hierarchy; let grammar 2 be the (first) grammar given for the verse hierarchy.

Let the input be the fragment of Peer Gynt given in the text, with the addition of start- and end-tags for play, act, and scene.

<play|<act|<scene|
<sp who="Aase"|<L|Peer, you're lying!|sp>
<sp who="Peer"|<stage|without stopping|stage> 
    No, I'm not!|L>|sp>
<sp who="Aase"|<L| Well then, swear to me it's true! |L>|sp>
<sp who="Peer"|<L| Swear? Why should I? |sp>
<sp who="Aase"| See, you dare not! |L>
<L| Every word of it's a lie! |L>|sp>
|scene>|act>|play>

A trace generated by a validator for rabbit/duck grammars (and slightly cleaned up for presentation here) contains the following information. Each derivative takes the form E = F ∧ G; the sub-expression before the ∧ connector is from grammar 1 (dramatic hierarchy), the one after the ∧ is from grammar 2 (verse hierarchy).

• E ₁ = D _stag(play) play ₁ ∧ play ₂

  = (act ₁+, #etag(play)) ∧ (act ₂+, #etag(play))

• E ₂ = D _stag(act) E ₁

  = (scene ₁+, #etag(act), act ₁*, #etag(play)) ∧ (scene ₂+, #etag(act), act ₂*, #etag(play))

• E ₃ = D _stag(scene) E ₂

  = ((sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₄ = D _stag(sp) E ₃

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₅ = D _stag(L) E ₄

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₆ = D _pcdata() E ₅

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₇ = D _etag(sp) E ₆

  = ((sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₈ = D _stag(sp) E ₇

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₉ = D _stag(stage) E ₈

  = (#PCDATA, #etag(stage), (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ (#PCDATA, #etag(stage), (#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₁₀ = D _pcdata() E ₉

  = (#PCDATA, #etag(stage), (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ (#PCDATA, #etag(stage), (#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₁₁ = D _etag(stage) E ₁₀

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₁₂ = D _pcdata() E ₁₁

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₁₃ = D _etag(L) E ₁₂

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₁₄ = D _etag(sp) E ₁₃

  = ((sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₁₅ = D _stag(sp) E ₁₄

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₁₆ = D _stag(L) E ₁₅

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₁₇ = D _pcdata() E ₁₆

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₁₈ = D _etag(L) E ₁₇

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₁₉ = D _etag(sp) E ₁₈

  = ((sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₂₀ = D _stag(sp) E ₁₉

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₂₁ = D _stag(L) E ₂₀

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₂₂ = D _pcdata() E ₂₁

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₂₃ = D _etag(sp) E ₂₂

  = ((sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₂₄ = D _stag(sp) E ₂₃

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₂₅ = D _pcdata() E ₂₄

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₂₆ = D _etag(L) E ₂₅

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₂₇ = D _stag(L) E ₂₆

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₂₈ = D _pcdata() E ₂₇

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₂₉ = D _etag(L) E ₂₈

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₃₀ = D _etag(sp) E ₂₉

  = ((sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₃₁ = D _etag(scene) E ₃₀

  = (scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ (scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₃₂ = D _etag(act) E ₃₁

  = (act ₁*, #etag(play)) ∧ (act ₂*, #etag(play))

• E ₃₃ = D _etag(play) E ₃₂

  = ε ∧ ε

An invalid instance

If we make the document invalid against the verse hierarchy by attempting to embed a line within another line, the input is:

<play|<act|<scene|
<sp who="Aase"|<L|<L|Peer, you're lying!|L>|sp>
<sp who="Peer"|<stage|without stopping|stage> 
    <L|No, I'm not!|L>|L>|sp>
<sp who="Aase"|<L| Well then, swear to me it's true! |L>|sp>
<sp who="Peer"|<L|<L| Swear? Why should I? |L>|sp>
<sp who="Aase"|<L| See, you dare not! |L>|L>
<L| Every word of it's a lie! |L> |sp>
|scene>|act>|play>

A validation trace for this element (cleaned up slightly for presentation) follows:

• E ₁ = D _stag(play) play ₁ ∧ play ₂

  = (act ₁+, #etag(play)) ∧ (act ₂+, #etag(play))

• E ₂ = D _stag(act) E ₁

  = (scene ₁+, #etag(act), act ₁*, #etag(play)) ∧ (scene ₂+, #etag(act), act ₂*, #etag(play))

• E ₃ = D _stag(scene) E ₂

  = ((sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₄ = D _stag(sp) E ₃

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₅ = D _stag(L) E ₄

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ((#PCDATA | stage ₂ | #tag(sp))*, #etag(L), (L ₂ | stage ₂ | #tag(sp))*, #etag(scene), scene ₂*, #etag(act), act ₂*, #etag(play))

• E ₆ = D _stag(L) E ₅

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₇ = D _pcdata() E ₆

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₈ = D _etag(L) E ₇

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₉ = D _etag(sp) E ₈

  = ((sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₁₀ = D _stag(sp) E ₉

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₁₁ = D _stag(stage) E ₁₀

  = (#PCDATA, #etag(stage), (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₁₂ = D _pcdata() E ₁₁

  = (#PCDATA, #etag(stage), (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₁₃ = D _etag(stage) E ₁₂

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₁₃ = D _stag(L) E ₁₂

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₁₄ = D _pcdata() E ₁₃

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₁₅ = D _etag(L) E ₁₄

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₁₆ = D _etag(L) E ₁₅

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₁₇ = D _etag(sp) E ₁₆

  = ((sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₁₈ = D _stag(sp) E ₁₇

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₁₉ = D _stag(L) E ₁₈

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₂₀ = D _pcdata() E ₁₉

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₂₁ = D _etag(L) E ₂₀

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₂₂ = D _etag(sp) E ₂₁

  = ((sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₂₃ = D _stag(sp) E ₂₂

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₂₄ = D _stag(L) E ₂₃

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₂₅ = D _stag(L) E ₂₄

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₂₆ = D _pcdata() E ₂₅

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₂₇ = D _etag(L) E ₂₆

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₂₈ = D _etag(sp) E ₂₇

  = ((sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₂₉ = D _stag(sp) E ₂₈

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₃₀ = D _stag(L) E ₂₉

  = ((#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₃₁ = D _pcdata() E ₃₀

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₃₂ = D _etag(L) E ₃₁

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₃₃ = D _etag(L) E ₃₂

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₃₄ = D _stag(L) E ₃₃

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₃₅ = D _pcdata() E ₃₄

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₃₆ = D _etag(L) E ₃₅

  = (#PCDATA, (#PCDATA | stage ₁ | #tag(L))*, #etag(sp), (sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₃₇ = D _etag(sp) E ₃₆

  = ((sp ₁ | stage ₁ | #tag(L))*, #etag(scene), scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₃₈ = D _etag(scene) E ₃₇

  = (scene ₁*, #etag(act), act ₁*, #etag(play)) ∧ ∅

• E ₃₉ = D _etag(act) E ₃₈

  = (act ₁*, #etag(play)) ∧ ∅

• E ₄₀ = D _etag(play) E ₃₉

  = ε ∧ ∅

As may be seen, the result makes clear that the document is valid against grammar 1 but invalid against grammar 2.