Ambiguity

Steven Pemberton

Introduction

Ambiguity in ixml is a property of the input.

Although the aim of ixml is to describe input formats so that their structure can be recognised without the need for markup, ambiguity is nevertheless deliberately allowed, firstly from a usability point of view, since it allows you to get some result, with a warning that there are other possibilities, and secondly because some input ambiguities may not produce an output ambiguity, in which case it makes no difference which parse gets serialised.

Since ixml does not dictate which parser should be used, but only the properties of an acceptable parser, it is not reasonable to require a particular parse of the ambiguous input, so it is unspecified which parse is serialised.

Apart from the uncertainty of whether the serialisation represents what the grammar writer intended the structure of the document to be, there is another disadvantage, that of speed, since an ambiguous grammar requires the input to be parsed multiple times.

Types

Ambiguities can be divided into several classes.

Some ambiguities are only on the input, such as deleted spaces in this example:

  input: number*.
 number: spaces, digit, spaces.
  digit: ["0"-"9"].
-spaces: -" "+.

Even though this is ambiguous, all parses will produce an identical serialisation.

Some ambiguities are due to badly written grammars. For instance,

expression: number; identifier; expression, op, expression.
op: ["+-×÷"].
identifier: [L]+.
number: ["0"-"9"]+.

For an input like

a-b-c

this will produce two different parses one effectively

(a-b)-c

and the other

a-(b-c)

which have different meanings. The grammar has been incorrectly written.

We shouldn't do anything about this case. There is no doubt that tracking down ambiguities can be difficult, and time-consuming for inexperienced grammar writers, but trying to solve this by ad hoc means doesn't solve the underlying problem that the input is not properly described, nor would it guarantee that you get the serialisation that you want in all cases. It is a potential source of technical debt.

Some ambiguities are inherent in the input, such as US/World dates, like 4/5/2026,

 date: us; world.
   us: month, "/", day, "/", year.
world: day, "/", month, "/", year.
  day: d, d?.
month: d, d?.
 year: d, d, d, d.
    d: ["0"-"9"].

Still, even in these cases it is possible to rewrite it to an unambiguous grammar that identifies the ambiguous and non-ambiguous cases:

 date: us; world; ambig.
   us: month, "/", day, "/", year.
world: day, "/", month, "/", year.
ambig: md, "/", md, "/", year. 
  day: "1", ["3"-"9"]; "2", "0"-"9"; "3", ["0"-"1"]. {13-31}
month: "0"? ["1"-"9"]; "1", ["0"-"2"].               {1-12}
   md: -month.

Although this still identifies dates like 1/1/2026 as ambiguous, since they are syntactically ambiguous, even though they aren't semantically ambiguous, even these cases are in principle handleable with a more complex grammar; this wouldn't disambiguate the cases though, just choose one in favour of the other.

Approaches

There are two possible approaches to dealing with ambiguity. One is to allow it, and add the ability to select amongst ambiguous parses. The other is to add expressiveness to the grammar notation to ease making unambiguous grammars.

For instance, some approaches add priorities to rules, that allow the selection of one rule above another when it comes to ambiguity. I am personally dubious of this approach, primarily based on experience, for instance with its use in CSS, where the !important keyword gives one rule priority over others. This was introduced for a very particular (legal) use case, but has proven to be an enormous source of technical debt, making stylesheets very fragile, and hard to update.

One of the observable problems of specifying grammars is the difficulty of splitting input into distinct cases. For example:

catalogue: entry*.
    entry: header, item+.
   header: text, code.
     item: text.
     text: word++" ".
    -word: (l; d)+.
       -l: [L].
       -d: ["0"-"9"].
    @code: l, l, l, d, d, d.

Example input:

Fiction fic001
Ulysses
Brave New World
1984
NonFiction non123
Translating Beaudelaire
The Sixth Extinction

The problem here is that word and code are not distinct, so header also matches item. You could add a priority to a rule:

 header: text, code. !important

but this doesn't explicitly express what is going on, making it hard to understand, and harder to update later. Better would be the ability to say explicitly "A text is any string of characters where the last word doesn't match a code." For instance,

text: word**" ", " ", lastword.
-lastword: word!code.

Here word!code means a word, as long as it doesn't match a code, essentially the same as the proposed subtraction operator word - code.

In passing, I realised the two proposed disambiguation constructs could be unified:

word!code

means a word as long as it doesn't match a code, and

!code, word

means as long as there isn't a code here, accept a word.

Conclusion

Ambiguity is a nuisance that we must address in ixml. I believe the best way to address it is to add construct(s) to the language to make the ability to express non-ambiguous grammars easier, making grammars more explicit in their descriptions.