What is the difference between EBNF and CFG

Question

I understand that EBNF can be used to express Context Free Grammar, but is there any difference between the two?

I am asking because there are questions that ask to convert EBNF to CFG, but as of my current understanding, they look same. Therefore, what is the intention behind this conversion?

Answer 1

EBNF can be used to write a context-free grammar.

The latin alphabet can be used to write English.

Pascal can be used to express an algorithm.

A "context-free grammar" is an abstract thing which you can write out in EBNF form for machine input. The actual context-free grammar is a mathematical object. It has standard notation, but the standard notation is really for human consumption.

Answer 2

Summary: EBNF is not directly equivalent to the CFG formalism, but many EBNF grammars can be mechanically converted.

---

A context-free grammar is a four-tuple of:

• A set of nonterminals V

• A set of terminals Σ which is disjoint from V

• A set of productions of the form

    v → ω

where v is an element of V and ω is an element of (V ⋃ Σ)* (that is, a possibly-empty string of terminals and non-terminals.

• A starting symbol S which is an element of V.

(See Wikipedia article and its references. There is another equivalent formalism which uses the set of non-terminals V and an alphabet A which is the union of V and Σ.)

An early concrete syntax for CFGs was proposed by John Backus in 1959 in order to describe the Algol programming language; this formalism is generally referred to as Backus-Naur Form, a name proposed by Donald Knuth, recognizing the contributions of Algol report co-author Peter Naur. The main difference between BNF and the CFG formalism above is that productions with a common left-hand side are abbreviated using the | symbol:

     v → ω1 | ω2
    ⇒
      v → ω1
      v → ω2

However, in practice the use of regular operators, particularly repetition operators like the Kleene Star, has proven to be much easier to write and to understand. A number of extensions to BNF were proposed and used in various grammars, especially by Niklaus Wirth. In particular, it became common to use a form of extended BNF in standard protocol documents, both RFCs (IETF internet standards) and various ISO standards. These formalisms were eventually "standardized" as Extended BNF, ISO/IEC 14977 and the somewhat similar Augmented BNF, RFC-5234.

In order to convert EBNF to the CFG formalism, it is necessary to expand all uses of repetition -- including finite repetition--, alternation and optionality operators into primitive form, which requires the introduction of new non-terminals. Also, both EBNF and ABNF allow specifications which may be impossible to convert to CFG, including restrictions written in English. (See the first note in my answer to Ebnf – Is this an LL(1) grammar?)

Answer 3

Yes - Unlike ABNF and RBNF, the standard for EBNF allows for exceptions which mean that it can be used to define non context free languages.

Proof:

1. The language of L1 = {a^n b^n a^m | n, m ≥ 0} is generated by:

   L1 ::= X,A

   X ::= "a",X,"b" | Emptystring

   A ::= A,"a" | Emptystring

2. The language of L2 = {a^n b^m a^m | n, m ≥ 0} is generated by:

   L2 ::= A,X

3. L 1 ∩ L 2 = {a^n b^n a^n | n ≥ 0} is not context free by the pumping lemma since, for a given p ≥ 1 we can choose n > p such that s = a^n b^n a^n is in our language and we cannot pick any substring q of s such that q is of length p, s = xqy for some strings x and y and x q^n y ∈ L 1 ∩ L 2 (since q would have to take in at least one a and should take in the same number of as on the left as on the right).

   P ::= L1 − L2

   {a^n b^n a^n | n ≥ 0} is the language of Q where

   Q ::= L1 − P