7
$\begingroup$

I've been learning about formal languages and grammars, and I came across two terms while studying my textbook:

Context-Free Grammar (CFG) and Backus-Naur Form (BNF). They both seem to be related to defining the syntax of programming languages, but I'm not entirely sure how they differ from one another.

Could someone explain the differences between CFG and BNF? Specifically:

  1. Are they the same thing, or do they serve different purposes?
  2. Is BNF just a way to write CFGs, or does it have its own set of rules?
  3. Are there any notable applications where one is preferred over the other?

Any help would be appreciated. Thanks.

$\endgroup$

1 Answer 1

14
$\begingroup$

Yes, Backus–Naur Form is a syntax for specifying a context-free grammar. It is named for members of the Algol committee who developed it for that specification with awareness of Chomsky's prior work on CFGs. It's a notation for specifying the grammar, while the CFG itself is a mathematical object typically identified formally with a tuple of other mathematical objects, and so more of a concept than a concrete thing. Any context-free language can be described with BNF, any BNF specification describes a context-free language, and a context-free language is exactly one that has a context-free grammar.

BNF is a way to write CFGs and it has its own set of rules defining its syntax. In general, a BNF specification can embed natural-language prose to give definitions, and informally we can treat those plain definitions as corresponding to the formal characterisations of the sublanguage they describe or as giving instructions to the author of a parser. There are BNF variations that tie that down more rigidly, and others that extend it further. Some of those variants have their own, additional formal rules: for example, RFC 5234 is the latest in a series of definitions used elsewhere in the IETF specification process.

It is overwhelmingly more common for practical specifications of programming languages, and non-programming languages designed to be parsed by practical computers, to use some variation of BNF than to define a production relation in $V \times (V \cup \Sigma)*$, which is pretty useless to most people. Many use other forms of specifying their grammar as well, often with more rigidly-defined characterisations of symbols and the ability to mechanically translate them to parsers, although a BNF grammar can be just as rigidly defined if desired. These are not opposed to one another, and both BNF and non-BNF formats for defining grammars are in pretty common use, with the choice tending to depend more on audience, tooling, and community norms than anything else.


In terms of formal language theory, a context-free grammar is a formal object that describes a context-free language using a set of nonterminal symbols, a distinct alphabet of terminal symbols, a start symbol, and a relation between single nonterminals and sequences of nonterminals and alphabet symbols. Such a language is exactly a set of strings accepted by a nondeterministic pushdown automaton, and a number of other equivalences. Backus–Naur form is a more practical shift of that theory and doesn't come up quite so much within that world itself.

$\endgroup$
3
  • 1
    $\begingroup$ I’ve upvoted, but I think this answer would be improved by more explicitly clarifying that a CFG is a concept (or, at the very least, a mathematical object) while BNF is a notation. $\endgroup$
    – Alexis King
    Commented Oct 11 at 6:11
  • $\begingroup$ Yes, that is a good framing to start with. $\endgroup$
    – Michael Homer
    Commented Oct 11 at 7:04
  • $\begingroup$ Wow this is great! Thanks so much guys! $\endgroup$
    – Joe
    Commented Oct 14 at 22:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .