parsinggrammarbnfebnfebnf-syntactic-exception

How to represent negation in BNF?


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?


Solution

  • 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.