How to represent negation in BNF?

Question

Does BNF or ABNF support negation. That is exclude certain members of the set? I did not see any such negation operator in its syntax.

For example, suppose S is the set of all alphanumeric strings that are not equal to "foo" What is the BNF for S?

Angi

I think it is possible to define this in a very complicated way, by building the string using individual characters. – Angi

Yes, that you can do. You asked about negation in general. For your specific example, this grammar will do the trick: S = notF any* | 'f' notO any* | 'f' 'o' notO any* ; notF = 'a' | ... 'e' | 'g' | ... 'z' ; notO = 'a' | ... | 'n' | 'p' | ... 'z' ; any = 'a' | ... | 'z' ; – Bail

Answer 1

Context free grammars are not closed under "difference" or "complements". So while you might decide to add an operator "subtract" to your BNF, the result will not be a context free grammar even if it has a simple way to express it. Consequence: people don't allow such operators in BNF grammars used to express context-free grammars.

Bail

So how do existing compilers check that variables are not reserved words? – Angi

Recognizing key words is normally done in the lexer, not the parser. A lexer normally just orders the comparisons, so you look for keywords first. If and only if that fails, you have some other identifier. – Grummet

More sophisticated schemes treat identifiers as keywords in the context in which they can be treated as keywords. This requires the lexer and the parser to interact to make the choice, and/or the parser to try both keyword and identifier alternatives, and choose the keyword alternative if it works. We do this with our parsers and it works quite nicely. – Bail

While context free grammars aren't closed under "differences" or "compliments" in general, they are closed under differencing regular grammars, of which keywords are a subset. So the fact that it would be impossible to support general negation does not necessarily prohibit an notation for negation of regular grammars. – Graph

Looking into it turns out EBNF does support "negation" through exceptions. At least according to the ISO standard. Though it may not be implemented by most parsers. – Graph

Answer 2

While not in BNF, EBNF does have the except-symbol (typically defined as "-"). In your case, the syntax would be:

alphaNum="a"|"b"|...|"z"|"0"|"1"|...|"9"|"A"|...|"Z";
S= (alphaNum,{alphaNum}) - "foo";

Or if you want it to be case insensitive:

foo="f"|"F","o"|"O","o"|"O";
alphaNum="a"|"b"|...|"z"|"0"|"1"|...|"9"|"A"|...|"Z";
S= (alphaNum,{alphaNum}) - foo;

This results in a slightly different acceptance criteria than was done in the comments which would be equivalent to:

alphaNum="a"|"b"|...|"z"|"0"|"1"|...|"9";
S= alphaNum - "f", {alphaNum} 
  |"f", alphaNum - "o", {alphaNum}
  |"f", "o", alphaNum - "o", {alphaNum};

This leaves out the strings "f" and "fo".

However, it's important to note as Ira Baxter has in their answer, allowing anything as the excepted (negated) factor would cause problems. This is also pointed out in the ISO standard:

4.7 Syntactic exception

A syntactic-exception consists of a syntactic-factor subject to the restriction that the sequences of symbols represented by the syntactic-exception could equally be represented by a syntactic-factor containing no meta-identifiers.

NOTE - If a syntactic-exception is permitted to be an arbitrary syntactic-factor, Extended BNF could define a wider class of languages than the context-free grammars, including attempts which lead to Russell-like paradoxes, e.g.

xx = "A" - xx;

Is "A" an example of xx? Such licence is undesirable and the form of a syntactic-exception is therefore restricted to cases that can be proved to be safe. Thus whereas a syntactic-factor is in general equivalent to some context-free grammar, a syntactic-exception is always equivalent to some regular grammar. It may be shown that the difference between a context-free grammar and a regular grammar is always another context-free grammar; hence a syntactic-term (and hence any grammar defined according to this standard) is equivalent to some context-free grammar.

Graph

Instead of (alphaNum,{alphaNum}) you could also use another syntactic exception to disallow zero repeats: {alphaNum}-. This is also used in an example in the notes to section 5.8. – Fearnought