One of the observed difficulties for newcomers to ixml when writing a grammar is dealing with whitespace in the input, since it can often be the source of unintended ambiguity.
This talk describes a methodology for constructing grammars that minimises the possibilities of creating ambiguities due to whitespace.
One of the challenges when describing free-format input languages in ixml, is describing where whitespace may go.
Inexperienced ixml authors, and sometimes even experienced ones, will add spacing that can cause ambiguities in the resultant parse.
bundle: -"bundle", -s, identifier, -s,
namespaceDeclarations?, -s,
expression**-s, -s,
"endBundle", -s.
The problem is some of the things that the spaces are separating are optional and therefore may be absent in an input, and then the parser doesn't know where to place the spaces.
Both namespaceDeclarations?, and expression**-s
may be empty, leaving a parse like
-"bundle", -s, identifier, -s, -s, -s, "endBundle", -s.
with three optional sets of spacing next to each other: an ambiguity.
The author could solve this by writing
bundle: -"bundle", -s, identifier, -s,
(namespaceDeclarations, -s)?,
(expression++-s, -s)?,
"endBundle", -s.
making the thing and its trailing space optional, but has to be aware of the problem in order to fix it.
The problem may be that authors are used to writing grammars for systems where there is a lexical analysis phase, so that spaces don't appear in the parsing stage, and therefore don't have to be dealt with in the main grammar.
Lexical analysers were historically necessary to enable the use of fast but limited parsers such as LL1, however, using a general parser, ixml not only has no lexical analyser, it has no need for one, and it would actually be disadvantageous to introduce one, since lexical analysers in general do not have any context to help decide what the next token might be.
In ixml token recognition is an integral part of the grammar recognition process, adding more context to the process.
This is why it is necessary to include all aspects of the input in an ixml description, including whitespace.
The grammar is written as if there were a lexical analyser, with a separate part defining 'tokens'.
The definition for any token then also skips the spaces following it.
In this way, at the upper level of the grammar you barely have to worry about spaces at all.
To start off with a very simple example, let us consider the following small grammar for simple arithmetic expressions (which at this point doesn't accept whitespace except newlines between expressions):
input: expression++-#a, -#a?.
-expression: sum; difference; term.
sum: expression, -"+", term.
difference: expression, -"-", term.
-term: product; division; operand.
product: term, -"×", operand.
division: term, -"÷", operand.
-operand: id; number; -"(", expression, -")".
id: [L]+.
number: ["0"-"9"]+.
For instance, with the input
a+(b×2)
this produces
<input>
<sum>
<id>a</id>
<product>
<id>b</id>
<number>2</number>
</product>
</sum>
</input>
You can identify potential tokens by the presence of
For visibility, we are going to write such tokens with all capitals:
input: expression++-#a, -#a?.
-expression: sum; difference; term.
sum: expression, -"+", term.
difference: expression, -"-", term.
-term: product; division; operand.
product: term, -"×", operand.
division: term, -"÷", operand.
-operand: id; number; -"(", expression, -")".
id: [L]+.
number: ["0"-"9"]+.
You can identify potential tokens by the presence of
For visibility, we are going to write such tokens with all capitals:
input: expression++NL, NL?.
-expression: sum; difference; term.
sum: expression, PLUS, term.
difference: expression, MINUS, term.
-term: product; division; operand.
product: term, TIMES, operand.
division: term, DIVIDE, operand.
-operand: id; number; OPEN, expression, CLOSE.
id: ID.
number: NUMBER.
Define the tokens, with trailing spaces added:
-PLUS: -"+", s.
-MINUS: -"-", s.
-TIMES: -"×", s.
-DIVIDE: -"÷", s.
-OPEN: -"(", s.
-CLOSE: -")", s.
-ID: [L]+, s.
-NUMBER: ["0"-"9"]+, s.
-NL: -#a, s.
-s: -[" "; #9]*.
This guarantees that spaces after every symbol are consumed by the token, and so there is never any doubt about where spaces belong.
It also means that rules always begin with non-whitespace.
Therefore we have to allow leading spaces at the point there hasn't been any token yet: the beginning.
input: s, expression++NL, NL?.
Capitals for the names of tokens is purely a convention; other possibilities:
Plusplus-symbolplus-symA simplified version of ixml: rules only contain alternatives, terminal strings, and nonterminals:
subset: rule+.
rule: name, -":", alternatives, -".".
-alternatives: alternative++-";".
alternative: term**-",".
-term: terminal; nonterminal.
nonterminal: name.
terminal: string.
@string: -'"', ~['"']*, -'"'.
@name: [L]+.
Note that we are defining a subset of ixml, but using full ixml to do it; again, in this grammar we haven't yet dealt with spaces.
A simplified version of ixml: rules only contain alternatives, terminal strings, and nonterminals:
subset: rule+.
rule: name, COLON, alternatives, STOP.
-alternatives: alternative++SEMICOLON.
alternative: term**COMMA.
-term: terminal; nonterminal.
nonterminal: name.
terminal: string.
@string: STRING.
@name: NAME.
Note that we are defining a subset of ixml, but using full ixml to do it; again, in this grammar we haven't yet dealt with spaces.
Define the tokens, with trailing whitespace added:
-COLON: -":", s.
-STOP: -".", s.
-SEMICOLON: -";", s.
-COMMA: -",", s.
-NAME: [L]+, s.
-STRING: -'"', ~['"']*, -'"', s.
-s: -[" "; #9; #a]*.
Note that NAME and STRING contain non-deleted meaningful characters.
Finally, add leading spaces before the grammar, since at that point there hasn't been any token yet:
subset: s, rule+.
Let us now apply the technique to the real ixml grammar itself.
In the ixml grammar the rule s represents optional
whitespace.
There is a complication that spacing covers comments as well, which we will treat shortly.
For the time being assume it is only true whitespace.
Let's start with the definition of a rule as it appears:
rule: naming, -["=:"], s, -alts, -".". -naming: (mark, s)?, name, s, (-">", s, alias, s)?.
Note that this grammar does already deal with spaces, so we will remove the existing spacing from these rules:
rule: naming, IS, -alts, STOP. -naming: mark?, name, (GT, alias)?.
As you can see, the grammar is already easier to read.
-IS: -["=:"], s. -STOP: -".". -GT: -">", s.
STOP is a special case which we will talk about shortly.
@mark: ["@^-"].
which we replace with:
@mark: MARK.
with token:
-MARK: ["@^-"], s.
@name: namestart, namefollower*. -namestart: ["_"; L]. -namefollower: namestart; ["-.·‿⁀"; Nd; Mn].
we replace it with:
@name: NAME.
with the token:
-NAME: namestart, namefollower*, s.
-namestart: ["_"; L]. -namefollower: namestart; ["-.·‿⁀"; Nd; Mn].
An alias is also just a NAME:
@alias: NAME.
alts: alt++(-[";|"], s). alt: term**(-",", s).
becomes:
alts: alt++ALSO. alt: term**COMMA.
with the new tokens:
-ALSO: -[";|"], s. -COMMA: -",", s.
-term: factor;
option;
repeat0;
repeat1.
-factor: terminal;
nonterminal;
insertion;
-"(", s, alts, -")", s.
so factor gets replaced with:
-factor: terminal;
nonterminal;
insertion;
OPEN, alts, CLOSE.
with tokens:
-OPEN: -"(", s.
-CLOSE: -")", s.
The other options for term are:
option: factor, -"?", s. repeat0: factor, (-"*", s; -"**", s, sep). repeat1: factor, (-"+", s; -"++", s, sep).
which are replaced by:
option: factor, QUESTION. repeat0: factor, (STAR; STAR2, sep). repeat1: factor, (PLUS; PLUS2, sep).
with tokens
-QUESTION: -"?", s.
-STAR: -"*", s.
-STAR2: -"**", s.
-PLUS: -"+", s.
-PLUS2: -"++", s.
In ixml, rules must be separated by some white space: they may not abut each other. This means you may not write:
@alias:name.alts:alt++ALSO.
but must write something like
@alias:name. alts:alt++ALSO.
or
@alias:name. alts:alt++ALSO.
Consequently, the top-level rule for ixml is:
ixml: s, prolog?, rule++RS, s.
(where RS is 'required spacing'), so that rules are
separated by spacing, and not followed by it
We have to include optional spacing at the end of the grammar as well as the beginning.
It also means that the token for STOP must not consume any
spaces (since the very last STOP might not have trailing
whitespace).
In ixml, whitespace also includes comments:
-s: (whitespace; comment)*.
-whitespace: -[Zs; -#9 {tab}; -#a {lf}; -#d {cr}].
comment: -"{", (cchar; comment)*, -"}".
-cchar: ~["{}"].
(Zs is any character defined as whitespace in Unicode; this
doesn't include tab or newlines).
BUT: comments are not deleted, but are kept in the serialisation.
This won't occur often in grammars, but is worth describing how to deal with it.
This means that if we had an input rule like
subset {top}: {next} rule; rule, subset.
with the rules as we have defined them
@name: NAME. -NAME: [L]+, s.
we would get output where the comment after a NAME gets
included in the attribute:
<rule name='subsettop'>
<comment>next</comment>
<alternative>
<nonterminal name='rule'/>
</alternative>
<alternative>
<nonterminal name='rule'/>
<nonterminal name='subset'/>
</alternative>
</rule>
So we have to ensure that comments don't appear in attribute content.
This involves the ixml rules that define attributes, namely:
mark, tmark, name, alias,
string, hex, from, to, and
code.
One solution is to make all uses of the mark rule into a token.
From:
-naming: mark?, name, (GT, alias)?. -MARK: ["@^-"], s.
to
-naming: MARK?, name, (GT, alias)?. -MARK: mark, s. @mark: ["@^-"].
so that the spacing and comments are not part of the attribute.
Similarly for NAME:
-naming: MARK?, NAME, (GT, alias)?.
with the token defined as:
-NAME: name, s. @name: namestart, namefollower*.
and again for alias:
-naming: MARK?, NAME, (GT, ALIAS)?.
with token:
-ALIAS: alias, s. @alias: name.
and so on for the other attributes.
The other option would be to move the s out of the token for attributes, and in to the main body of the grammar:
-naming: (mark, s)?, name, s, (GT, alias, s)?.
with
@mark: MARK. @name: NAME. @alias: NAME.
and tokens
-MARK: ["^-@"]. {no trailing space}
-NAME: namestart, namefollower*.
But this is quite ugly.
An attribute where spacing is completely deleted looks like this:
member: code. @code: CODE. -CODE: capital, letter?, s.
and where something is retained in the spacing:
member: CODE. -CODE: code, s. @code: capital, letter?.
Strictly speaking, this second version would also work if the spacing is completely deleted, so the choice is yours.
(Full syntax in the paper)
The methodology ensures that all rules start with non-space, and consume all trailing space.
This is why we add an extra term to consume any spaces before the root rule, such as we saw above:
input: s, expression++NL, NL?.
The root rule is thus the only one which can start with spaces.
However, a modularisation method is planned for ixml in the future.
This allows the composition of grammars from several sub-grammars.
Example:
+uses ixml, name, s, RS from ixml.ixml;
iri from iri.ixml
+shares module
module: s, (multiuse; shares)*, ixml.
-multiuse: -"+uses", RS, uses++(-";", s).
shares: -"+shares", RS, entries.
uses: entries, RS, -"from", RS, from.
-entries: share++(-",", s).
share: @name, s.
@from: iri, s.
If a grammar is also to be a (future) module, there would be an ambiguity if the root rule can start with spaces, which breaks the methodology.
For a grammar to serve as both a standalone grammar and a potential module, we have to do something special for the root rule. Here is an example:
+shares input
-standalone: s, input.
input: expression++NL, NL?.
This creates a new root rule which doesn't appear in the serialisation but accepts leading spaces and uses the old root rule, while the module shares the old root as a rule that doesn't accept leading spaces.
The methodology describes a straightforward way to write grammars that guarantees non-ambiguous whitespace.
If the whitespace gets completely deleted, or the grammar doesn't use attributes, it is very simple.
In the rare cases where (parts of) the whitespace are preserved in the serialisation, and attributes are used, care has to be applied to the definition of attributes.
If you want to make grammars future-proof for use with modularisation, you need to make a special new root rule.