The Backus-Naur Form is a compact way to describe a
context-free grammar.If you have a context-free grammar G=(N,T,P,o), where N is the not empty, finite set of
non-terminal symbols, T is the not
empty,
finite set of
terminal symbols, P is the
finite set of
derivation rules and o is ∈ N is the start symbol.
Example:
T = {a,b}, N = {a}, P = { o → aob, o → ε}
This grammar describes the following language: L(G)={a^n b^n | n ≥ 0}
Now let's come to the Backus-Naur Form. In this form there are several derivation rules summed up to one rule.
The rules for reducing the rules are:
A → b1, A → b2, ..., A → bn can be reduced to A → b1|b2|...|bn
A → ac, A → abc can be reduced to A → a[b]c
A → ac, A → aBc, B → b, B → Bb can be reduced to A → a{b}c (this simply means 0,1 or more bs)
Example:
The example above is not useful for this. It would stay unchanged. So lets create a new example:
T={a,b,c,d}, N = {A,B,C,D}, P = {o → ABC, A → a, A → c, B → abc, B → ac, C → bDd, C → bd, D → a, D → Da}
The both A rules can be reduced to A → a|c
The both B rules can be reduced to B → a[b]c
The C and D rules can be reduced to C → b{a}d
Then P' = {o → ABC, A → a|c, B → a[b]c, C → b{a}d }