1
$\begingroup$

I am trying to use BNF to describe its own grammar to get used to it. What I can not find any information about is whether BNF must consist of zero or more rules or one or more rules. The difference would be:

<grammar> ::= <grammar> <rule> | <rule>

vs.

<grammar> ::= <grammar> <rule> | ""

The only difference I can see is that an empty language can be described by an emtpy BNF in the second case, but must use <grammar> ::= "" in the first case.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Concretely speaking, the Backus-Naur form is a notation for context-free grammars, applied to the (formal) description of languages at the syntactical level.

While there are extended versions of BNF that have been standardized, the BNF itself hasn't, so there is no way of determining if the empty grammar is "legal" BNF.

As a mathematical object, the possibility of an empty grammar will depend on the definition (of grammar) used. A grammar that has no productions is usually said to define the empty language, but any grammar whose set of possible terminal derivations is empty is also a candidate definition of the empty language.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Out of curiosity, what extended versions of BNF are completely standardized? $\endgroup$
    – SE - stop firing the good guys
    Commented Apr 22, 2017 at 14:39
  • $\begingroup$ For instance, EBNF ("extended") and ABNF ("augmented"). $\endgroup$
    – André Souza Lemos
    Commented Apr 22, 2017 at 14:47
-1
$\begingroup$

There is nothing logically wrong with allowing a grammar to have zero rules. But such a grammar would be entirely useless, as it would not define any language (not even the empty-string by itself).

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ It defines the empty language, which is a language (and even a useful one). $\endgroup$
    – rici
    Commented Apr 21, 2017 at 15:06
  • 2
    $\begingroup$ "Useless" is an opinion, but it is incorrect to say that the empty grammar defines no language. $\endgroup$
    – David Richerby
    Commented Apr 21, 2017 at 18:52

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.