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?

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.

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.