Balisage Paper: Designing for change

Use cases

Among the use cases that motivate the proposal are these.

Note that some of these use cases may in practice be handled by future changes to the core syntax of ixml (and one has in fact been handled by a change already made). We include them in the list of use cases for pragmas not because we think pragmas are the best imaginable way to handle them but because they are (a) plausible ideas for things one might want to do which are (b) not supported by ixml in its current form (or in one case, its earlier form), and thus (c) natural examples of the kinds of things an extension mechanism like pragmas ought ideally to be able to support.

Some of these use cases seem most naturally handled by annotations which apply to a grammar as a whole, some by annotations which apply to individual rules, and some by annotations which apply to individual symbols in the grammar.

We do not currently see a strong use case for annotations which apply to arbitrary expressions in a grammar.

Requirements and desiderata

Our tentative list of requirements and desiderata is as follows.

By requirement we mean a property or functionality which must be achieved for a pragmas proposal to be worth adopting. By desideratum we mean a property or functionality that should be included if possible, but which does not doom the proposal to pointlessness if it proves impossible to achieve.

Design questions

Several design questions can be distinguished; they are not completely orthogonal.

Syntax in ixml

Extensibility mechanisms are designed to facilitate independent invention. At the same time, a processor which recognizes an extension pragma may behave differently because of that pragma. It follows that pragmas will benefit from some form of distributed naming mechanism. In an XML context, the obvious candidate for distributed naming is the namespace-qualified name or QName. The TEI “p” element is distinct from the XHTML “p” element because they are in different namespaces.

Invisible XML doesn’t provide any support for namespaces, so we must look elsewhere. In principle, the pragmas proposal could invent a pragma-based mechanism for defining namespace prefixes and then use QNames in pragmas. But such a mechanism wouldn’t extend to the nonterminals in a grammar without breaking syntactic compatibility with Invisible XML 1.0. There are at least some voices in the community that favor adding a namespace mechanism to Invisible XML, so it seems wise to leave that space open for future versions of Invisible XML.

The part of qualified names that guarantees distributed naming and thus distributed extensibility is the use of URIs to identify namespaces. As long as people coin names only in the parts of URI space where they have the authority to construct names, name collisions can be avoided. So we can take a step back from qualified names and employ the URI directly for distributed naming.

       pragma: -"{[", @pname, (whitespace, pragma-data)?, -"]}". 
       @pname: name.
  pragma-data: (-pragma-char; -bracket-pair)*.
 -pragma-char: ~["{}"].
-bracket-pair: '{', -pragma-data, '}'.

{[+pragma myPragma "https://example.com/pragmas/mine"]}

{[rewrite
    comment: -"{", cchars, (comment++cchars, cchars)?, -"}". 
    {[token]} -cchars:  cchar*. 
]}

 nonterminal: annotation, name, s.
 -annotation: (pragma, sp)?, (mark, sp)?.
         -sp: (whitespace; comment; pragma)*.

     -quoted: tannotation, string, s.
    -encoded: tannotation, -"#", @hex, s.
   inclusion: tannotation,          set.
   exclusion: tannotation, -"~", s, set.
-tannotation: (pragma, sp)?, (tmark, sp)?.

        rule: annotation, name, s, 
              -["=:"], s, -alts, (pragma, sp)?, -".".

     -prolog: version, s, ppragma++s, s. 
     ppragma: -"{[+", @pname, (whitespace, pragma-data)?, -"]}".

{[+pragma my "http://example.com/pragmas/g342"]}

{[my example rule pragma]}
symbol: A .

A: {[my example symbol 'a' pragma]} 'a',
   {[my example symbol B pragma]} B.
B: .

<ixml>
   <comment>[+pragma my "http://example.com/pragmas/g342"]</comment>
   <comment>[my example rule pragma]</comment>
   <rule name="symbol">
      <alt>
         <nonterminal name="A"/>
      </alt>
   </rule>
   <rule name="A">
      <comment>[my example symbol 'a' pragma]</comment>
      <alt>
         <literal string="a"/>
         <comment>[my example symbol B pragma]</comment>
         <nonterminal name="B"/>
      </alt>
   </rule>
   <rule name="B">
      <alt/>
   </rule>
</ixml>

<ixml>
   <prolog>
      <ppragma pname="pragma">
         <pragma-data>my "http://example.com/pragmas/g342"</pragma-data>
      </ppragma>
   </prolog>
   <rule name="symbol">
      <pragma pname="my">
         <pragma-data>example rule pragma</pragma-data>
      </pragma>
      <alt>
         <nonterminal name="A"/>
      </alt>
   </rule>
   <rule name="A">
      <alt>
         <literal string="a">
            <pragma pname="my">
               <pragma-data>example symbol 'a' pragma</pragma-data>
            </pragma>
         </literal>
         <nonterminal name="B">
            <pragma pname="my">
               <pragma-data>example symbol B pragma</pragma-data>
            </pragma>
         </nonterminal>
      </alt>
   </rule>
   <rule name="B">
      <alt/>
   </rule>
</ixml>

Syntax in XML

Following the normal rules of ixml, pragmas are serialized as elements named pragma or ppragma (for prolog pragmas), with an attribute named pname and an optional child element named pragma-data. In addition, in XML grammars pragma elements may contain any number of XML elements following the pragma-data element.

For example:

<pragma pname="blue"/>

<pragma pname="color">
    <pragma-data>blue</pragma-data>
</pragma>

<pragma pname="rewrite">
    <pragma-data>
    comment: -"{", cchars, (comment++cchars, cchars)?, -"}". 
    {[token]} -cchars:  cchar*.  
</pragma-data>
</pragma>

Processors which do not implement the pragma in question will as a matter of course produce pragma elements with just the one child element (or none). But processors which implement a given pragma are free to inject additional XML elements into the XML form of the pragma. It is to be assumed that the XML elements contain no additional information, only a mechanically derived XML form which makes the information in the pragma easier to process. It is to be expected that any software to serialize XML grammars in ixml form will discard the additional XML elements.

For example, note that a processor which understands the rewrite pragma (shown above in an example) might prefer to produce a different XML representation for it, e.g., one in which the embedded grammar rules are parsed into their normal XML representation.^[6] For such a processor, the XML representation might be:

<pragma pname="rewrite">
    <pragma-data>
    comment: -"{", cchars, (comment++cchars, cchars)?, -"}". 
    {[token]} -cchars:  cchar+. 
</pragma-data>
</pragma>
<rule name="comment">
   <alt>
      <literal tmark="-" string="{"/>
      <nonterminal name="cchars"/>
      <option>
         <alts>
            <alt>
               <repeat1>
                  <nonterminal name="comment"/>
                  <sep>
                     <nonterminal name="cchars"/>
                  </sep>
               </repeat1>
               <nonterminal name="cchars"/>
            </alt>
         </alts>
      </option>
      <literal tmark="-" string="}"/>
   </alt>
</rule>
<rule mark="-" name="cchars">
   <pragma pname="token"/>
   <alt>
      <repeat0>
         <nonterminal name="cchar"/>
      </repeat0>
   </alt>
</rule>

Note that because the additional XML elements within the pragma are just redundant XML representations of the pragma data, an application to rewrite XML grammars in ixml form will lose no information when transcribing this XML pragma as

{[rewrite
              comment: -"{", cchars, (comment++cchars, cchars)?, -"}". 
              {[token]} -cchars:  cchar*. 
]}

Pragma scope

In this proposal, pragmas always apply explicitly to some part of a grammar:

The relation between a pragma and the part of the grammar to which it applies is reflected in the XML form of a grammar: ordinary pragmas appear as child elements and prolog pragmas as grandchild elements of the part of the grammar they apply to (an element named ixml, rule, nonterminal, literal, inclusion, or exclusion).

These associations between pragmas and parts of grammars are specified here for clarity and to enable clearer discussion of pragmas, but they have no effect on the operational semantics of ixml processors. If a processor does not implement a given pragma, or any pragmas at all, it will not be affected by the pragmas, regardless of what they apply to, and a processor that does understand a given pragma may be able to tell from its definition what changes in behavior it requests and what it applies to. The associations given above are thus of most direct use to those specifying the meaning of specific pragmas.

Operational semantics

In describing the operational semantics of pragmas, we distinguish different classes of ixml processor:

With regard to a given pragma, processors either implement that pragma or they do not. A processor implements a pragma if and only if it adjusts its behavior as specified by that pragma. In the ideal case there will be some written specification of the pragma which describes the operational effect of the pragma clearly. This proposal assumes that a processor can use the URI of a pragma, possibly in conjunction with the pragma data, to determine whether the processor implements the pragma or not and thus decide whether to modify its normal operation or not.

Pragma-aware processors MUST accept pragmas when they occur in the ixml form of a grammar, and (if they are producing an XML form of the grammar) must produce the correct XML form of each pragma, just as they produce the corresponding XML form for any construct in the grammar.

Conformance requirements for pragmas

The conformance requirements mentioned in this section apply to pragma-aware processors; the qualifier pragma-aware is sometimes omitted for brevity.

Pragma-aware processors MUST be capable, at user option, of ignoring all pragmas and processing a grammar using the standard rules of ixml.

Processors which accept ixml grammars MUST accept pragmas in the ixml form of a grammar, whether they understand or implement the specific pragmas or not.

Processors which accept XML grammars MUST accept pragmas in the XML form of a grammar, whether they understand or implement the specific pragmas or not.

If a pragma which the processor does not understand or implement is present in a grammar used to parse input, the processor MUST process the grammar in the same way as if the pragma were not present.

When ixml grammars are processed as input using the processor's built-in grammar, processors MUST produce the correct XML form of each pragma, just as they produce the corresponding XML form for any construct in the grammar, except as the processor's behavior is affected by the presence of pragmas in the grammar for ixml used to parse the input.

Renaming

Use case: Using pragmas to specify that an element or attribute name serializing a nonterminal should be given a name different from the nonterminal itself.

In the grammar below, the two forms of month have different syntaxes, so they are required to have different nonterminal names, and so they are required to be serialized using different XML element names.

We define a renaming pragma which specifies the name to be used when serializing a nonterminal as XML. A parser which does not support the pragma will produce results in which some months are named month and others nmonth; a parser which does support the pragma will call them all month.

    {[+pragma rename
    "https://lists.w3.org/Archives/Public/public-ixml/2021Oct/0014.html"]}
    
    date: day, " ", month, " ", year.
    day: d, d?.
    month: "January"; "February"; "March"; 
           "April"; "May"; "June";
           "July"; "August"; "September";
           "October"; "November"; "December".
    year: d, d, d, d.
    
    iso: year, "-", {[rename month]} nmonth, "-", day.
    nmonth: d, d.

The fallback behavior of a parser that does not support these pragmas will be to produce output using both the element name month and the element name nmonth.

Name indirection

Use case: Using pragmas to specify that an element or attribute name should be taken not from the grammar but from the string value of a given nonterminal.

Consider the following grammar which recognizes a superset of a simple subset of XML. It's a subset of XML for simplicity, and it's a superset of the subset because a grammar written at this level cannot enforce all of the well-formedness constraints of XML.

{ A grammar for a small subset of XML, as an illustration. }

document: ws?, element, ws? .
    
element: starttag, content, endtag; soletag .
    
-starttag:  -"<", @gi, (ws, attribute)*, ws?, -">".
-endtag:  -"</", @gi2, (ws, attribute)*, ws?, -">".
-soletag:  -"<", @gi, (ws, attribute)*, ws?, -"/>".

attribute:  @name, ws?, -"=", ws?, @value.
@value: dqstring; sqstring.
-dqstring: dq, ~['"']*, dq.
-sqstring: sq, ~["'"]*, sq.
-dq: -['"'].
-sq: -["'"].

{ allow at most one PCDATA block between pieces of markup }
-content:  PCDATA?,
           ((processing-instruction; comment; element)++(PCDATA?),
	   PCDATA?)?.

PCDATA:  (~["<>&"]; "&amp;"; "&lt;"; "&gt;"; "&apos;"; "&quot;")+.
processing-instruction:  "<?", @name, ws, @pi-data, "?>".
comment:  "<--", comment-data, "-->".

gi: name.
gi2: name.
{ name is left as an exercise for the reader. }

ws:  (#20; #A; #C; #9)+.

Among the input sequences which should be accepted by this grammar is the following XML representation of a haiku.

<haiku author="Basho" date="1686">
    <line>When the old pond</line>
    <line>gets a new frog</line>
    <line>it's a new pond.</line>
</haiku>

We might like an ixml processor to read this and produce the same XML that any XML parser would produce. (This desire makes sense only when the ixml processor's results are supplied to a user in a DOM or XDM or SAX or other XML API or model. If they are supplied as an XML character stream, we might as well feed the XML straight to the downstream user; we don't need to parse it.) What the grammar above will produce has a clear structural similarity to the input XML, but it is not the same:

<document xmlns:ixml="http://invisiblexml.org/NS" ixml:state="ambiguous">
   <element gi="haiku" gi2="haiku"> 
      <attribute name="author" value="Basho"/> 
      <attribute name="date" value="1686"/>
      <PCDATA>
    </PCDATA>
      <element gi="line" gi2="line">
         <PCDATA>When the old pond</PCDATA>
      </element>
      <PCDATA>
    </PCDATA>
      <element gi="line" gi2="line">
         <PCDATA>gets a new frog</PCDATA>
      </element>
      <PCDATA>
    </PCDATA>
      <element gi="line" gi2="line">
         <PCDATA>it's a new pond.</PCDATA>
      </element>
      <PCDATA>
</PCDATA>
   </element>
</document>

We can invent suitable pragmas to allow ourselves to obtain normal XML from parsing with the grammar:

With these pragmas, we can annotate the element and attribute rules appropriately:

^ {[name @gi]} element:  start-tag, content, end-tag; sole-tag.
...
-end-tag:  "</", {[drop]} @gi2, (ws, attribute)*, ws?, ">".
...
^ {[serialize attribute]}
  {[name @name]}
  attribute:  @name, ws?, "=", ws?, @value.

Rule rewriting

Use case: Using pragmas to specify that a rule as given is shorthand for a set of other rules. Consider the following simple grammar for arithmetic expressions.

expr: term; expr, addop, term.
term: factor; term, mulop, factor.
factor: number; var; -'(', -expr, -')'.
...

We might find it inconvenient that the number 42 is represented with an XML element tree four elements deep:

<expr>
    <term>
        <factor>
            <number>42</number>
        </factor>
    </term>
</expr>

One simple rule to simplify the XML representation of sentences in this language is to specify that if an element E has only one child, E should not be tagged and only the child should appear in the XML.

We can do this in ixml by expanding the grammar, splitting each nonterminal into two rules, one producing a visible serialization and one hiding the nonterminal on serialization.

-EXPR: TERM; expr.
expr: EXPR, addop, TERM. 
-TERM: FACTOR; term.
term: TERM, mulop, FACTOR. 
-FACTOR: number; var; -'(', EXPR, -')'. 
...

Now 42 parses more simply as <number>42</number>.

The rewrite is mechanical enough that we can automate it, and error-prone enough that it is worth automating. If a rule has some right-hand sides guaranteed to produce at most one child each and some guaranteed to produce at least two children each, it's split into two rules. The first gets a new nonterminal and has the original single-child right-hand sides as alternatives, as well as a reference to the original nonterminal. It's marked hidden. The second rule gets the original nonterminal. All references to the original nonterminal are changed to be references to the new nonterminal.

If we call the relevant pragma no-unit-rules, or more briefly nur, the grammar takes the following form. In practice, we also need a rule that means don't rewrite the entire rule, but replace references to rules rewritten using nur; we call this second pragma ref.

^ {[nur]} expr: term; expr, addop, term.
^ {[nur]} term: factor; term, mulop, factor.
- {[ref]} factor: number; var; -'(', -expr, -')'.
...

The XML representation of this grammar can plausibly exploit the ability of extension elements to contain an XML representation of the new rules. Both the nur and the ref pragmas within a rule instruct the implementation to replace the enclosing rule with the rules appearing as children of the pragma elements.

    <ixml>
      <rule name="expr" mark="^">
    
        <pragma pname="nur">
          <pragma-data/>
      
          <rule name="EXPR" mark="-">
            <alt><nonterminal name="TERM"/></alt>
            <alt><nonterminal name="expr"/></alt>
          </rule>
      
          <rule name="expr" mark="^">
            <alt>
              <nonterminal name="EXPR"/>
              <nonterminal name="addop"/>
              <nonterminal name="TERM"/>
            </alt>
          </rule> 
        </pragma>
    
        <alt><nonterminal name="term"/></alt>
        <alt>
          <nonterminal name="expr"/>
          <nonterminal name="addop"/>
          <nonterminal name="term"/>
        </alt>
      </rule>
  
      <rule name="term" mark="^">
        <pragma pname="nur">
          <pragma-data/>
          
          <rule name="TERM" mark="-">
            <alt><nonterminal name="factor"/></alt>
            <alt><nonterminal name="term"/></alt>
          </rule>
          
          <rule name="term" mark="^">
            <alt>
              <nonterminal name="TERM"/>
              <nonterminal name="mulop"/>
              <nonterminal name="factor"/>
            </alt>
          </rule>
        </pragma>
        
        <alt><nonterminal name="factor"/></alt>
        <alt>
          <nonterminal name="term"/>
          <nonterminal name="mulop"/>
          <nonterminal name="factor"/>
        </alt>
      </rule>
      
      <rule name="factor" mark="-">
        <pragma pname="ref">
          <pragma-data/>
          <rule name="factor" mark="-">
            <alt><nonterminal name="number"/></alt>
            <alt><nonterminal name="var"/></alt>
            <alt>
              <literal string="(" tmark="-"/>
              <nonterminal name="EXPR" mark="-"/>
              <literal string="-" tmark="-"/>
            </alt>
          </rule>
        </pragma>
        <alt><nonterminal name="number"/></alt>
        <alt><nonterminal name="var"/></alt>
        <alt>
          <literal string="(" tmark="-"/>
          <nonterminal name="expr" mark="-"/>
          <literal string="-" tmark="-"/>
        </alt>
      </rule>
      ...
    </ixml>

The fallback behavior of a processor that doesn't support these pragmas will be to serialize expr and term elements even when they have only one child.

Tokenization annotation and alternative formulations

Use case: We can use pragmas to annotate nonterminals in an ixml grammar to provide a hint to the processor indicating that they define a regular language and can be safely recognized by a greedy regular-expression match.

For example, consider the grammar for a simple programming language. A processor might read programs a little faster if it could read identifiers in a single operation; this will be true if when an identifier is encountered, the identifier will always consist of the longest available sequence of characters legal in an identifier. In the toy Program.ixml grammar used as a running example in Hillman 2020, the rule for identifiers is:

identifier: letter+, S.

We can annotate identifier to signal that it's safe to consume an identifier using a single regular-expression match by using a pragma in a lexical scanning (ls) namespace:

{[token]} identifier:  letter+, S.

The rules for comments in ixml itself offer another wrinkle.

      comment: -"{", (cchar; comment)*, -"}".
      -cchar: ~["{}"].

Within a comment, any sequence of characters matching cchar can be recognized in a single operation; there is no need to look for alternate parses that consume only some of the characters. But there is no nonterminal here that matches all and only non-empty sequences of cchar. In order to use the token annotation here, we must first rewrite the grammar at this point. So we introduce an annotation named rewrite to be attached to a single grammar rule with the meaning that the pragma data provide an alternate form of the rule.

We can now annotate the grammar and supply an alternative formulation of comment that replaces it with two new rules:

      ^ {[rewrite
            comment: -"{", cchars, (comment++cchars, cchars)?, -"}". 
            {[token]} -cchars:  cchar*. 
        ]}
      comment: -"{", (cchar; comment)*, -"}".
      -cchar: ~["{}"].

Or we may find it easier to read if we inject the alternative formulation after, not before, the existing rule:

      comment: -"{", (cchar; comment)*, -"}"
      {[rewrite 
          comment: -"{", cchars, (comment++cchars, cchars)?, -"}". 
          - {[token]} cchars:  cchar*. 
      ]}.
      -cchar: ~["{}"].

Either way, the rewrite contains an alternative formulation of the grammar which recognizes the same sentences and provides the same XML representation but may be processed faster by some processors.

The fallback behavior of a processor that doesn't support these pragmas will be to parse as usual using the grammar as specified.

Note however that there is no way to guarantee or impose an effective requirement that the alternate rules in an rewrite pragma be equivalent to the fallback rules: pragmas may change the behavior of a processor, and they may change the meaning of an expression (or here the meaning of a grammar or part of it).

Text injection

Use case: Using pragmas to specify that additional text should be injected into the output at a particular point (as part of a text node, or attribute value).

The text injection use case stands as an example of how a language may evolve to incorporate features that make some pragmas unnecessary or obsolete. The insertions feature in Invisible XML 1.0 was a relatively late addition to the language. Work on a proposal for pragmas began more than a year earlier. The text injection pragma use case explored the question of whether the pragma mechanism could be used to inject text into the output. And indeed it could. But the insertions feature has made it obsolete.

Pragmas offer implementers and designers an opportunity to experiment with, and test designs for, functionality that may eventually become part of the specification.