Writing Invisible XML grammars

You can match any literal character, including end of line characters and other control characters, with an encoded character. An encoded character is a number sign (“#”) followed by hex digits. An encoded character can represent any Unicode character.

For example, the line feed character used to separate lines in text files on MacOS and Linux is “#a” (or in capitals, “#A”, or with leading zeros, “#000a”, if you prefer).

In the discussion of strings, we noted that you cannot put a line break in a string. So how would you match “one” followed by “two” separated by a single line feed?

One way is like this:

onetwo: "one", #a, "two" .

The commas that you put in to separate tokens don’t imply any delimiters in the input.

Line endings in XML are normalized, but Invisible XML just operates on the input that you give it. The preceding example would be more portable written this way:

onetwo: "one", #d?, #a, "two" .

That will work on filesystems, like Windows, where a new line is often a carriage return (“#d”) followed by a line feed. This might be easier to read if the encoded characters were identified with their own nonterminals:

onetwo: "one", cr?, lf, "two" .
-cr: -#d .
-lf: -#a .

But it will match the same input either way.

Strings and encoded characters match against the input exactly as they are written. Another way to match is with character sets which can be inclusive (all these characters) or exclusive (any characters except these).

Character sets are delimited by square brackets and contain literal strings, encoded characters, character ranges, or Unicode character classes. If the opening square bracket is preceded by a “~” (U+007E), the set is exclusive, otherwise it’s inclusive.

The following rule:

digit: ["0123456789"] .

Doesn’t match the string zero through nine, as it would if it wasn’t surrounded in square brackets, instead it matches exactly one character, any one of “0”, “1”, “2”, …, “9”.

Another way to write that would be with a range:

digit: ["0"-"9"] .

A range consists of a character string containing a single character (or an encoded character) followed by a hyphen-minus (-, U+002D), followed by another single character string (or encoded character). Unlike ranges in most regular expressions, the members of a character set are always quoted or encoded, so you don’t need extra escaping. A character set that includes left square bracket, both kinds of quote marks, and all of the characters from “-” to “\” could be written:

["[", "'", '"', "-"-"\"]

though it might be a little easier to read as

["[", "'", '"', #2d-"\"]

or even

[#5b, "'", '"', #2d - "\"]

Finally, a set can identify a Unicode character class. Unicode groups similar characters together into classes identified by one- or two-letter codes. The code “P”, for example, identifies all punctuation characters while “Pd” identifies those punctuation characters that are dashes. You can use these classes in character sets. To define the nonterminal “punct” that matches any single Unicode punctuation character, you can write this:

punct: [P] .

You can combine these various forms in a single set:

hexplus: ["0123456789"; "A"-#46; #61-"f"; Nd].

That defines “hexplus” as matching any single character zero through nine, or any upper-case latter “A” through “F”, or any lowercase letter “a” through “f”, or any character in the Unicode character class “Number, Decimal Digit” (which contains more than 600 characters as many languages have their own decimal digits). The Unicode class contains the Arabic decimal digits, so there’s a bit of redundancy in this set, but that’s not an error.

As noted earlier, you can negate a class (make it an exclusion) by placing a tilde in front of it:

notnumeric: ~[N].

The “notnumeric” nonterminal matches any single Unicode character that is not in the class of number characters. The set ~[] matches any character that is not in the empty set, in other words, any character.

(Invisible XML doesn’t let you build up more complicated character sets by composing them: you can’t mix inclusions and exclusions together in the same set.)

All the rules we’ve looked at so far match exactly one thing: one word, one symbol, or one character. What if you want to match more or less than one? Invisible XML gives you several options here as well starting with “*”, “+”, and “?” which behave just as you’d expect if you’re familiar with regular expression languages.

factor*

A factor followed by a “*” will match zero or more occurrences of that factor. Given this rule,

seq: 'a', '.'*, 'b'.

A “seq” will match “ab”, “a.b”, “a..b”, etc. with as many full stops as you like between the two letters.

factor+

A factor followed by a “+” will match one or more occurrences of that factor. Given this rule,

seq: 'a', '.'+, 'b'.

A “seq” will match “a.b”, “a..b”, “a...b”, etc. with as many full stops as you like between the two letters, but it will not match “ab”.

factor?

A factor followed by a “?” is optional. It will match zero or one occurrence of that factor. Given this rule:

seq: 'a'? .

A “seq” will match either nothing or a single “a”. Matching empty strings (accidentally or on purpose) as an important topic that we’ll come back to later.

factor1 * factor2

Invisible XML has two special forms of repeat that are convenient for grammar authors. If two factors are separated by a “*”, they will match zero or more occurrences of the first factor separated by the second factor. Given this rule:

seq: 'a'*',' .

A “seq” will match “”, “a”, “a,a”, “a,a,a”, etc. Matching as many “a”s as appear (including none) provided that they are separated by precisely one comma.

Note that because the separator is a factor as well, you can have more nuanced separators. You could match a sequence of “a” characters separated by commas followed by optional spaces like this: 'a'*(',', ' '*).

factor1 + factor2

If two factors are separated by a “+”, they will match one or more occurrences of the first factor separated by the second factor. Given this rule:

seq: 'a'+',' .

A “seq” will match “a”, “a,a”, “a,a,a”, etc. Matching as many “a”s as appear provided that they are separated by precisely one comma.

At this point, you have all the building blocks necessary to write your own grammars, but two common features deserve special attention: matching names (or other contiguous sequences of characters) and matching whitespace.

        name: namestart, namefollower*.
   namestart: ["_"; L].
namefollower: namestart; ["-.·‿⁀"; Nd; Mn].

           s: (whitespace; comment)*.
  whitespace: [Zs]; tab; lf; cr.
         tab: #9.
          lf: #a.
          cr: #d.
     comment: -"{", (cchar; comment)*, -"}".
      -cchar: ~["{}"].

As we saw in the previous article, grammars can be ambiguous and that’s not an error. Nevertheless, ambiguous grammars can slow down the parser and different implementations may give different answers, so it’s best to avoid them if you can. Consider this somewhat contrived example:

seq: (A; B), '.'*.
A: 'a', '.'+ .
B: 'b', '.'+ .

A “seq” is an “A” or a “B” followed optionally by full stops, an “A” is an “a” followed by one or more full stops, a “B” is an “b” followed by one or more full stops.

Asked to parse “a..”, the Invisible XML processor will report ambiguity:

<seq xmlns:ixml="http://invisiblexml.org/NS"
     ixml:state="ambiguous">
   <A>a..</A>
</seq>

CoffeePot will tell you that there were two possible parses, but it only returns one of them by default because that’s conformant behavior for a processor. Internally, it enumerates the parses and returns the first. You can ask for the other parse by passing --parse:2 on the command line (alternatively, you can pass --parse-count:all for all of them.) Here’s the second parse:

<seq xmlns:ixml="http://invisiblexml.org/NS"
     ixml:state="ambiguous">
   <A>a.</A>.</seq>

Ambiguity arises because there’s more than one way to parse an input. In this case, it’s pretty easy to see that the ambiguity is whether the second “.” is part of the A or part of the “seq”. Removing that ambiguity involves choosing one of the options and then adjusting the grammar to make that the only possible parse. In this case, one option is to make sure all the full stops are associated with either the A or the “B”:

seq: A; B.
A: 'a', '.'+ .
B: 'b', '.'+ .

The other option is to make sure they’re all associated with the seq:

seq: (A; B), '.'+.
A: 'a'.
B: 'b'.

Neither answer is more correct than the other. Which one is “right” depends on the output you want to get.

Ambiguity is a broader, and more nuanced topic, than we have space for here. It’s possible to make distinctions between grammars that are ambiguous and parses that are ambiguous. Try parsing a. with the first grammar above and you’ll find that there’s only one parse. Invisible XML reports ambiguous parses, not ambiguous grammars. It’s also possible to write a grammar that has loops in it: seq: 's', seq; seq; . A “seq” is an s or a “seq” or nothing. That grammar is infinitely ambiguous because it can have an unbounded number of empty “seq” matches.

Asked to parse “sss” with that grammar, CoffeePot will report:

There is 1 parse, but the grammar is infinitely ambiguous
<seq xmlns:ixml="http://invisiblexml.org/NS" ixml:state="ambiguous">s
   <seq>s
      <seq>s
         <seq/>
      </seq>
   </seq>
</seq>

(In the interests of space and time, CoffeePot won’t let you enumerate infinitely many parses; it ignores loops.)

seq: 'x', 'o'*, 'x'.

1phone-number: (areacode, sep)?, prefix, sep, number .
-sep: dash; space .
-dash: -'-'? .
-space: -' '? .
5number: digits .
prefix: digits .
areacode: digits; -'(', digits, -')' .
-digits: ['0'-'9']+ .

<phone-number>
   <areacode>512</areacode>
   <prefix>555</prefix>
   <number>0100</number>
</phone-number>

<phone-number xmlns:ixml="http://invisiblexml.org/NS"
              ixml:state="ambiguous">
   <areacode>51255501</areacode>
   <prefix>0</prefix>
   <number>0</number>
</phone-number>

1phone-number: (areacode, sep)?, prefix, sep, number .
-sep: dash; space .
-dash: -'-'? .
-space: -' '? .
5number: digit, digit, digit, digit .
prefix: digit, digit, digit .
areacode: digit, digit, digit;
          -'(', digit, digit, digit, -')' .
-digit: ['0'-'9'] .

There are 4 possible parses.
Ambiguity:
sep, 3, 3
        dashⁿ, 3, 3
        spaceⁿ, 3, 3
sep, 6, 6
        dashⁿ, 6, 6
        spaceⁿ, 6, 6

1phone-number: (areacode, sep)?, prefix, sep, number .
-sep: (dash; space)? .
-dash: -'-' .
-space: -' ' .
5number: digit, digit, digit, digit .
prefix: digit, digit, digit .
areacode: digit, digit, digit; -'(', digit, digit, digit, -')' .
-digit: ['0'-'9'] .

1         rule: name, s?, ':', s?, symbol+s .
       symbol: name .
 
           -s: whitespace+.
5  -whitespace: -[Zs]; tab; lf; cr.
         -tab: -#9.
          -lf: -#a.
          -cr: -#d.
 
10        @name: namestart, namefollower*.
   -namestart: ["_"; L].
-namefollower: namestart; ["-.·‿⁀"; Nd; Mn].

1         rule: name, s?, ':', s?, symbol+s .
       symbol: mark?, s?, name .
 
         mark: '^'; '@'; '-'.
5 
           -s: whitespace+.
  -whitespace: -[Zs]; tab; lf; cr.
         -tab: -#9.
          -lf: -#a.
10          -cr: -#d.
 
        @name: namestart, namefollower*.
   -namestart: ["_"; L].
-namefollower: namestart; ["-.·‿⁀"; Nd; Mn].

rule ⇒ name, s?, ':', s?, mark?, s?, name …

       symbol: (mark, s?, name); name .

         rule: name, s?, ':', symbol+s .
       symbol: mark?, s?, name .

Even with entities and numeric character references, the repertoire of XML characters is limited. You can’t, for example, have � (U+0000) in a well-formed XML document. Consequently, if you attempt to output those characters from your Invisible XML grammar, you’ll get errors. Similarly, if you create a nonterminal with a name that includes characters not allowed in XML names, you’ll get errors if it’s used for an element or attribute name.

Invisible XML is less restrictive. The following grammar accepts a sequence of letters separated by null characters:

letters: letter+#0.
letter: ['A'-'Z'; 'a'-'z'].

As long as you don’t attempt to output any invalid characters, it’s not an error to use them.

Whatever else your processor may be capable of, if it claims to be a conformant Invisible XML processor, it must be able to produce XML documents.

As a general rule, the Invisible XML processor makes an XML element out of every nonterminal that it matches. Consider this simple grammar for dates:

1date: day, ' '+, month, ' '+, year .
day: digit, digit? .
digit: ["0"-"9"] .
month: "January"; "February"; "March"; "April";
5       "May"; "June"; "July"; "August";
       "September"; "October"; "November"; "December".
year: digit, digit, digit, digit .

If you parse a date, “7 March 2022”, with that grammar, you’ll get:

<date>
   <day>
      <digit>7</digit>
   </day> 
   <month>March</month> 
   <year>
      <digit>2</digit>
      <digit>0</digit>
      <digit>2</digit>
      <digit>2</digit>
   </year>
</date>

Pretty soon after the observation, “cool, it works!”, you’ll probably want to see about getting rid of all those extra “digit” elements. The Invisible XML grammar allows you to annotate rules, nonterminals, and terminals with extra symbols, called “marks” in the specification, to control how they’re used to construct XML.

The mark on a nonterminal controls how it’s serialized. If a particular nonterminal on the right-hand-side of a rule doesn’t have a mark, the mark on the rule that defines that nonterminal is the default. The marks are:

^ (the default mark)

A “^” is the default. On a nonterminal, it indicates that an element should be created using the name of the nonterminal and what matches the nonterminal should be inside it. On a terminal, it indicates that the terminal should appear in the output.

@

An “@” only applies to nonterminals. It indicates that an attribute should be created using the name of the nonterminal and what matches the nonterminal should appear in the attribute value.

-

A “-” suppresses output. On a nonterminal, it suppresses the name of the nonterminal, not its content. On a terminal, it suppresses the text of the terminal.

Now we can go back to the grammar and suppress all those extra digit elements. Replacing the rule for “digit” with this one:

-digit: ["0"-"9"] .

Changes the output to:

<date>
   <day>7</day> 
   <month>March</month> 
   <year>2022</year>
</date>

Using an “@” mark will make an element into an attribute. Consider this alternative rule for year:

@year: digit, digit, digit, digit .

With that rule, you’ll get:

<date year="2022">
   <day>7</day> 
   <month>March</month>
</date>

We’ve been “pretty printing” the XML output in this article because it’s easier to read that way. But it has actually obscured a detail. The spaces between day and month and month and year are being output. That may be fine, but sometime’s it’s not. Let’s consider a grammar for ISO 8601 dates.

date: year, '-', month, '-', day .
year: digit+.
month: digit, digit.
day: digit, digit.
-digit: ["0"-"9"].

If you parse a date, “2022-03-07”, with that grammar, you’ll get:

<date>
   <year>2022</year>-
   <month>03</month>-
   <day>07</day>
</date>

Now those extra characters really stand out. Suppress them with “-”:

date: year, -'-', month, -'-', day .

That yields:

<date>
   <year>2022</year>
   <month>03</month>
   <day>07</day>
</date>

Note that suppressing nonterminals and terminals are independent. Try to predict what happens if you use this grammar:

date: year, dash, month, dash, day .
-dash: '-'.
year: digit+.
month: digit, digit.
day: digit, digit.
-digit: ["0"-"9"].

Try it out. Were you right? Can you figure out where to put another “-” to fix the problem?