Re: Examples of disambiguation

There's a confusion of terminology that I have found very annoying in reading about parser theory etc. What a parser/recognizer does to decide how to transition between states is called "lookahead" - e.g. in LALR(k) parsers, where the "LA" stands for "lookahead". And then features like the (?=) syntax in extended regular expressions are also called "lookahead" - but this refers to what you've expressed in your grammar (or regex pattern), rather than how the parser transitions between states.

So, I should be completely clear that I'm talking about the second kind of lookahead/lookbehind, which allows someone to express non-consuming match patterns in their grammar. This isn't the same as the way a parser uses the next n symbols of the input to decide how to proceed whilst parsing.

Interestingly, it seems that lookahead operators in regular expressions don't change the language to be non-regular. I assume that's because regular expressions are closed under complement and intersection, so you can't make regular languages X and Y non-regular by saying "not X" or "not Y", or by saying "something that matches both X and Y". But for context-free languages A and B, there is no guarantee that "not A" or "not B" remains context-free, or that "something that matches both A and B" is a context-free language. That's why I think we need to be very, very careful in designing anything that touches on negation in iXML.

If we could find a way to limit lookahead/negation to the regular patterns that iXML can express, that wouldn't actually change the expressive power of the language. So, for example, a lookahead/negation operator that only applied to terminals in the grammar *should* (I think) be safe in this regard.

> Hmm. I think of it as a disambiguation construct, because it allows me to disambiguate grammars that would otherwise be ambiguous.

But it has all the functionality of a (negative) lookahead construct, so - in technical terms - that's what it is. You can absolutely use lookahead to disambiguate things. You can also use it to design grammars that recognize context-sensitive languages.

> Any construct that includes empty as one of its productions, either explicitly or implicitly, is a non-consuming structure. This one just gives the reason why.

Matching and consuming the empty string is not the same as matching (and, potentially, failing) without consuming. Norm already addressed this, but I want to go a bit more deeply into it, because I think it's interesting. This intersects with the fact I've already mentioned, that you can have lookahead for regular languages without changing them into non-regular languages.

The language recognized by any construct with a Kleene star explicitly includes the empty string. The Kleene star must consume the empty string when it runs out of non-empty strings to match, in order for the processor to transition into a new state where it can start trying to match the rest of the string (if any) against the remaining rules (if any). All of the quantification operators (?, *, and +) can be rewritten using only the empty string, alternatives, and (if necessary) recursion. They don't require any non-consuming state transitions, but they do require the ability to match and consume the empty string.

If you want lookahead for a regular language, you can generally rewrite it without a specific lookahead operator - it just gets really cumbersome fairly quickly. The same isn't true for a context-free language, though; the building blocks of CF grammars don't allow you to rewrite lookahead assertions for anything other than regular languages.

Say you wanted to do this:

	not_cat: ["a"-"z"]+, cat!.
	cat: "cat".

i.e., match any string of any length > 1, consisting of the characters a-z, as long as it doesn't start with "cat". The language containing the string "cat" is a regular language, as is the language "any alphabetic string not starting with 'cat'", so you can rewrite the lookahead like this:

	not_cat: ["ab"; "d"-"z"], ["a"-"z"]* ; "c", (["b"-"z"], ["a"-"z"]*  ; "a", (["a"-"s";"u"-"z"] ; ["a"-"s";"u"-"z"]["a"-"z"]* ) ).

But you can't rewrite lookaheads in the same way for a non-regular context-free language - e.g. anything that has centre-embedded recursion:

	not_palindrome: ["01"]+, palindrome!.
	palindrome: "1", palindrome, "1" ; "0", palindrome, "0"; "1"; "0".

This language (if I haven't messed it up!) should match any string consisting of "1" and "0"s, as long as the string isn't a palindrome. There's no way to rewrite a grammar for this language in iXML without a specific lookahead operator.

When rewriting the Kleene star, it's essential to consume the empty string in order for us to know not to follow the recursion back into the pattern. But the rewriting of a lookahead assertion doesn't necessarily require that we consume an empty string in order to transition. We only have to consume the non-empty characters of the input string.

BTW


___________________________________________________ 
Dr. Bethan Tovey-Walsh 

linguacelta.com

Golygydd | Editor geirfan.cymru

Croeso i chi ysgrifennu ataf yn y Gymraeg.

> On 7 Jul 2026, at 13:24, Steven Pemberton <steven.pemberton@cwi.nl> wrote:
> 
> > I think it would be a bit limiting to call this a "disambiguation" construct, to be honest. It provides lookahead and lookbehind*, which is a pretty major extension to what iXML can already do, as it makes the language context-sensitive.
> 
> Hmm. I think of it as a disambiguation construct, because it allows me to disambiguate grammars that would otherwise be ambiguous.
> 
> ixml can already do lookahead:
> 
>    input: aBook, "a";
>           bBook, "b'.
>    aBook: book.
>    bBook: book.
>     book: chapter+. {etc}.
> 
> But while ! can be considered as a lookahead operator, that's not how I think of it, I see it as a guard of what follows.
> 
> > That being the case, I don't think I'd agree that it's the same kind of thing as the repetition operators. It doesn't really say "match zero of this"; it says "ensure that this does not match". We don't have any other such non-consuming match patterns in the language at present.
> 
> I agree it is new, I do see it as related to *, +, ? because it does guarantee that exactly zero of those things are present at that point. Any construct that includes empty as one of its productions, either explicitly or implicitly, is a non-consuming structure. This one just gives the reason why.
> 
> Steven
>

Received on Tuesday, 7 July 2026 17:35:07 UTC