18

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?

2
  • I think it is possible to define this in a very complicated way, by building the string using individual characters.
    – Jus12
    Jun 6, 2012 at 21:24
  • 1
    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' ;
    – Ira Baxter
    Jun 7, 2012 at 7:22

2 Answers 2

8

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.

5
  • 3
    So how do existing compilers check that variables are not reserved words?
    – Jus12
    Jun 6, 2012 at 21:17
  • 5
    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. Jun 6, 2012 at 21:18
  • 1
    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.
    – Ira Baxter
    Apr 1, 2014 at 20:04
  • 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.
    – Rick
    Jan 29, 2016 at 16:46
  • 2
    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.
    – Rick
    Feb 1, 2016 at 19:51
8

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.

1
  • 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.
    – Johann150
    Feb 24, 2021 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.