Re: Empty Alternatives (a.k.a epsilon).

Sorry, I'm an idiot and sent an early draft of that message! I think this one is clearer and expresses what I mean rather better. Sorry for the error!

I'd like to propose a different approach, which involves making a couple of different changes to the grammar.

Like Steven's proposal, mine also redefines the rule for alt. I redefine it so that it must contain at least one term, but I do not allow any representation of the empty string as a direct child of alt:

alt: term++(-",", s).

My proposal also redefines string and member, and introduces the new nonterminal charstring:

member: -"#", hex; range; class; charstring.
@string: -'"', dchar*, -'"'; -"'", schar*, -"'".
@charstring: -'"', dchar+, -'"'; -"'", schar+, -"'".
member: charstring; -"#", hex; range; class.

This allows the empty string, represented by two consecutive single quotation marks or double quotation marks, everywhere a string is permitted. Inside a character set, we now have a charstring instead of a standard string, which must contain at least one character between the quotation marks. 

This is semantically consistent with the usual understanding of strings and character sets. The empty string contains no characters, so it can't be added to a character set, which contains items that match exactly one character. In this proposal, the empty string is elsewhere treated just like any other string, which reflects its usual status in programming and computer science.

I prefer the use of "" or '' to represent the empty string because it will be familiar to users of most major programming languages. Using () is, I think, likely to confuse users - particularly new users. 

There's also the issue of whether whitespace would be permitted between the parentheses. If no whitespace is permitted, there will be a difference in behaviour between parentheses representing an alts (which can contain whitespace) and parentheses representing an alt (no whitespace allowed):

alts_rule: (  {comment} "cat" | "other thing" {more commenting}   ).

On the other hand, allowing whitespace inside an empty alt is, I think, not sensible: parentheses containing a comment would be a confusing representation of the empty string.

The use of an empty string represented by consecutive quotation marks also has another major advantage: it gives a clear and readable representation of the result of creating an attribute matching the empty string. With the current IXML grammar, you can get an empty attribute value with this:

@attribute: "cat"?.

or

@attribute: "cat"*.

If the empty string is matched here, you'll get 

@attribute=""

on the parent element. Both my proposal and the proposal for using () would still allow this.

But the fact that failing to match "cat" here will lead to an attribute with the empty string as its value doesn't seem entirely obvious.

Currently, an attribute with the value "" can also be created by either of the following:

@attribute: .

or

@attribute: ( | "cat" ).

(The second of these is equivalent to a rule matching "cat"?.)

Using () for the empty string means that those representations would no longer be allowed. In their place we'd have:

@attribute: ().

or

@attribute: ( () | "cat" ).

I'm instead proposing changes that would allow:

@attribute: "".

or

@attribute: ( "" | "cat" ).

To my mind, these are more intuitively readable than either what we currently have, or the version with () representing the empty string. 

Using consecutive quotation marks has the big advantage of consistency: both the empty string and "cat" are strings, and it's unsatisfying to me that they should be represented totally differently.

Any change we make is going to be somewhat backwards-incompatible. However, the proposal to use () will likely break few existing grammars, and any new grammars will still work with existing implementations.

My proposal for using "" and '', on the other hand, will break any existing grammars using () to represent the empty string; and any new grammars using "" or '' will not work with old implementations. I think this is a fairly small price to pay. Since we're going to have to accept some small amount of backwards-incompatibility however we make this change, I'd much prefer to have a slightly more backwards-incompatible choice that is much more user-friendly, semantically coherent, and consistent with other programming languages.

(I'd also be okay with adding a special symbol to represent the empty string (a.k.a an "epsilon" symbol, for those who are used to such things from other grammatical formalisms), alongside permitting its representation as double quotation marks.)

BTW

___________________________________________________ 
Dr. Bethan Tovey-Walsh 

linguacelta.com

Golygydd | Editor geirfan.cymru

Croeso i chi ysgrifennu ataf yn y Gymraeg.

> On 25 Aug 2026, at 15:38, Bethan Tovey-Walsh <accounts@linguacelta.com> wrote:
> 
> I'd like to propose a different approach to the empty string, which involves making a couple of different changes to the grammar.
> 
> Like Steven's proposal, mine also redefines the rule for alt. I redefine it so that it must contain at least one term, but I do not allow any representation of the empty string as an alternative to term(s):
> 
> alt: term++(-",", s).
> 
> My proposal also redefines string and member, and introduces the new nonterminal charstring:
> 
> member: -"#", hex; range; class; charstring.
> @string: -'"', dchar*, -'"'; -"'", schar*, -"'".
> @charstring: -'"', dchar+, -'"'; -"'", schar+, -"'".
> 
> This allows the empty string, represented by two consecutive single quotation marks or double quotation marks, everywhere a string is permitted. Inside a character set, we now have a charstring, which must contain at least one character between the quotation marks. 
> 
> This is semantically consistent with the usual understanding of strings and character sets. The empty string can't be put into a character set, because it contains no characters. However, the empty string is otherwise treated just like any other string, which reflects its usual status in programming and computer science. The proposal to use (), on the other hand, means that the empty string is treated as a direct child of alt, and has a different status from other strings, which are terminals. 
> 
> In the XML version of the grammar, an alt matching () will be empty, with no string attribute. It's a technical point, but an alt matching the empty string (however that's expressed) *does* match a string, so I think it's consistent for it to have a string="" attribute.
> 
> I mainly prefer the use of "" or '' to represent the empty string because it will be familiar to users of most major programming languages. Using () is, I think, likely to confuse users - particularly new users. 
> 
> If no whitespace is permitted between the parentheses representing the empty string, there will be a difference in behaviour between parentheses representing an alts (which can contain whitespace) and parentheses representing an alt (no whitespace allowed):
> 
> alts_rule: (  {comment} "cat" | "other thing" {more commenting}   ).
> 
> (Allowing whitespace inside () representing an empty alt, however, is obviously not sensible: parentheses containing a comment with the entire works of Shakespeare is not a reasonable representation of the empty string.)
> 
> I think the use of an empty string represented by "" or '' also has another major advantage: it gives a clear and readable representation of the result of creating an attribute matching the empty string.
> 
> With the current IXML grammar, you can get an empty attribute value with this:
> 
> attribute: "cat"?.
> 
> or
> 
> attribute: "cat"*.
> 
> If the empty string is matched here, you'll get 
> 
> attribute=""
> 
> on the parent element. Both my proposal and the proposal for using () would still allow this. But, to my mind, the fact that failing to match "cat" here will lead to an attribute with the empty string as its value is not entirely obvious.
> 
> Currently, an attribute with the value "" can also be created by either of the following:
> 
> attribute: .
> 
> or
> 
> attribute: (|"cat").
> 
> (The second of these is equivalent to a rule matching "cat"?.)
> 
> Using () for the empty string means that those representations would no longer be allowed. In their place we'd have:
> 
> attribute: ().
> 
> or
> 
> attribute: (()|"cat").
> 
> I'm instead proposing changes that would allow:
> 
> attribute: "".
> 
> or
> 
> attribute: (""|"cat").
> 
> To my mind, these are more intuitively readable than either what we currently have, or the version with () representing the empty string. I think using consecutive quotation marks has the big advantage of consistency: both the empty string and "cat" are strings, and it's unsatisfying to me that they should be represented so totally differently.
> 
> Any change we make is going to be somewhat backwards-incompatible. However, the proposal to use () will likely break few existing grammars, and any new grammars will still work with existing implementations. My proposal for using "" and '', on the other hand, will break any existing grammars using () to represent the empty string; and any new grammars using "" or '' will not work with old implementations.
> 
> Personally, I think this is a fairly small price to pay in order to represent the empty string in a way that's familiar from many other programming languages; that represents empty attribute values exactly as they will appear in the output; and that treats the empty string consistently with every other string.
> 
> I wouldn't be against also adding a separate symbol for epsilon, if people wanted one. But permitting the empty string is just consistent and, I feel, more usable and comprehensible than ().
> 
> Best,
> 
> BTW
> ___________________________________________________ 
> Dr. Bethan Tovey-Walsh 
> 
> linguacelta.com
> 
> Golygydd | Editor geirfan.cymru
> 
> Croeso i chi ysgrifennu ataf yn y Gymraeg.
> 
>> On 21 Aug 2026, at 15:55, Steven Pemberton <steven.pemberton@cwi.nl> wrote:
>> 
>> It has been pointed out that it is easy to let an empty alternative slip in to a grammar unintended, and therefore it would be advantageous to require an empty alternative to be explicitly marked as such, in other words, this would no longer be permitted:
>> 
>> thing-option: thing; .
>> 
>> and you would be required to write
>> 
>> thing-option: thing; SOMETHING HERE.
>> 
>> We have to agree on what that SOMETHING HERE is.
>> 
>> Strictly speaking, empty alternatives are not necessary, since anywhere you can write
>> 
>> a: b, c, d; .
>> you can just as easily write
>> 
>> a: (b, c, d)?.
>> 
>> So one option is just to forbid empty alternatives altogether. This would also be backwards compatible: existing implementations would still do the same thing.
>> 
>> On the other hand, converting grammars from other syntax languages would be made (slightly) harder if they have empty alternatives.
>> 
>> The syntax of a rule (for clarity leaving spacing out) is currently
>> rule: naming, -["=:"], -alts, -".".
>> and alts is
>>         alts: alt++-[";|"].
>>          alt: term**-",".
>>        -term: factor;
>>               option;
>>               repeat0;
>>               repeat1.
>>      -factor: terminal;
>>               nonterminal;
>>               insertion;
>>               -"(", alts, -")".
>> The fact that an alt can be empty is because of the ** in that rule.
>> That means that to require an alt to be non-empty needs to change the ** to ++, and add an explicit thing for the empty case:
>>    alt: term++-","; empty.
>>  empty: SOMETHING HERE.
>> Note that alts can also be bracketed in a rule:
>> a: b, (c, d; ), e.
>> so the visible empty alternative would be needed there too, but we don't have to do anything special for that case, since the syntax would already cover it.
>> 
>> OPTIONS
>> 
>> 1. As mentioned above, remove the concept of an empty alternative altogether:
>> alt: term++-",".
>> 
>> 2. Use some particular symbol(s) to mark an empty alternative, such as:
>> 
>> a special character such as &, 0, *, 𝛆  
>> (note this latter is not a Greek letter but a maths symbol)
>> an empty string ""
>> an empty bracket pair ()
>> an empty comment {}
>> 
>> Ideally it would be good to use something that is backwards compatible with existing implementations, so that grammars that used the new syntax still worked  with old implementations.
>> 
>> That would rule out the special characters, and the empty string. Empty comment would be hard to implement, since comments are already part of the definition of whitespace.
>> 
>> This leaves "()".
>> 
>> alt: term++-","; -"()".
>> 
>> Advantages: Backwards compatible; produces exactly the same XML serialisation of alts, still allows empty alternatives.
>> 
>> Steven
> 
> 
>

Received on Tuesday, 25 August 2026 16:12:59 UTC