What is the difference between EBNF and CFG
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.
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 ofV
.
(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?)