Backus-Naur Form (BNF) Explained: Grammar Rules, Worked Derivations and Exam Traps

BNF can look like a wall of punctuation until angle brackets, ::=, alternatives, recursion, and terminals are read as parts of one grammar. The challenge is following what each production permits. Those productions determine the generated strings and parse trees; BNF supplies notation, while Chomsky and Greibach normal forms impose structural constraints.

Backus-Naur Form (BNF): what the notation actually defines

Backus-Naur Form, historically also called Backus Normal Form, is a notation for writing context-free grammar productions. For a grammar G = (V, T, P, S), names inside angle brackets represent non-terminals in V, quoted symbols represent terminals in T, ::= means "is defined as", and | separates alternative right sides. The name on the left is the non-terminal being defined.

For example:

<bit> ::= "0" | "1"

This rule generates the set {0, 1}. It does not generate the literal string 0|1, because the vertical bar is a meta-symbol, not a terminal. That distinction matters across GATE CS Exam Preparation, where grammar questions reward exact reading.

BNF is a notation, not a restricted grammar shape. Chomsky Normal Form and Greibach Normal Form constrain the structure of productions, while BNF simply gives us a readable way to write productions down.

BNF grammar rules: terminals, alternatives, concatenation and recursion

Consider a grammar for non-empty decimal strings:

<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<number> ::= <digit> | <digit><number>

Adjacency means concatenation. The recursive alternative <digit><number> lets another digit follow, while the base alternative <digit> stops the recursion.

A complete leftmost derivation of 507 is:

<number> ⇒ <digit><number> ⇒ "5"<number> ⇒ "5"<digit><number> ⇒ "50"<number> ⇒ "50"<digit> ⇒ "507"

The first two visits to <number> use the recursive choice. The final visit uses the base choice, after which <digit> becomes "7".

BNF worked example: derive id + id * id step by step

The following expression grammar separates expressions, terms, and factors:

<expr> ::= <expr> "+" <term> | <term>
<term> ::= <term> "*" <factor> | <factor>
<factor> ::= "id" | "(" <expr> ")"

The <expr> level handles addition, the <term> level handles multiplication, and the <factor> level handles identifiers or parenthesised expressions. This makes multiplication bind more tightly than addition. For the equivalent machine model, see the context-free grammar and its pushdown-automata connection. BNF is the notation; these layered productions create the precedence structure.

The full leftmost derivation is:

<expr> ⇒ <expr> "+" <term> ⇒ <term> "+" <term> ⇒ <factor> "+" <term> ⇒ "id" "+" <term> ⇒ "id" "+" <term> "*" <factor> ⇒ "id" "+" <factor> "*" <factor> ⇒ "id" "+" "id" "*" <factor> ⇒ "id" "+" "id" "*" "id"

The result groups as id + (id * id) because the multiplication is contained within the right-hand <term>.

BNF ambiguity: why one valid notation can still describe two parses

Now compare the layered grammar with this naive rule:

<expr> ::= <expr> "+" <expr> | <expr> "*" <expr> | "id"

For id + id * id, one parse first combines the addition and then multiplies, giving (id + id) * id. Another parse first combines the multiplication, giving id + (id * id). Both have the same terminal yield but different trees.

One string with two distinct parse trees is enough to prove that a grammar is ambiguous. Two distinct leftmost derivations for the same string prove it as well. BNF syntax neither creates precedence nor removes ambiguity, so the grammar writer must encode those choices.

BNF versus EBNF: the same list language written two ways

Let <item> ::= "x" | "y" | "z". Ordinary BNF can define a non-empty comma-separated list as <list> ::= <item> | <item> "," <list>.

The derivation of x,y,z is:

<list> ⇒ <item>","<list> ⇒ "x",<list> ⇒ "x",<item>","<list> ⇒ "x","y",<list> ⇒ "x","y",<item> ⇒ "x","y","z"

In a common EBNF convention, the list rule becomes:

<list> ::= <item> {"," <item>}

The braces mean zero or more repetitions, and square brackets conventionally mark an optional part. EBNF is shorter notation. Its repetition and optional constructs can be expanded into ordinary BNF productions, but EBNF does not automatically make a grammar unambiguous.

BNF recursion and parser constraints

The fragment E ::= E + T | T is a valid context-free grammar. However, a naive recursive-descent or predictive parser may expand E into E + T repeatedly without consuming any input.

Immediate left recursion can be removed as follows:

E ::= T E'
E' ::= + T E' | ε

After adding T ::= id, both versions generate strings such as id+id+id. Language generation and parser suitability are different questions: the first grammar is left-recursive, while the transformed grammar lets a top-down procedure consume input before continuing. The guide to Parsing in Compiler Design: Top-Down and Bottom-Up Explained develops that parser distinction further.

Removing left recursion alone does not settle semantic associativity. A compiler must preserve the intended associativity through grammar design, tree construction, or an explicit semantic action.

BNF exam questions: membership, language identification and trap checks

Representative questions ask you to identify a language, test a string, or enumerate a finite result. In each case, derive only what the productions permit: identify the generated pattern, expand the candidate string, or list every finite combination.

Use this fast checklist:

1. Do not count meta-symbols such as ::= or | as terminals.

2. Distinguish ε, which contains no symbols, from the empty set, which contains no strings.

3. Follow the requested leftmost or rightmost derivation.

4. Test every relevant production alternative.

5. Remember that one successful derivation proves membership, while one failed attempt does not prove non-membership.

For timed application after you understand the method, use the GATE Test Series: Mocks & Topic-wise Tests to practise selecting productions under pressure.

Backus-Naur Form: the short version and the next step

Use this five-point recall sequence:

1. Identify terminals and non-terminals.

2. Find the start symbol.

3. Expand one non-terminal at a time.

4. Write the terminal yield in order.

5. Check whether precedence, ambiguity, recursion, or ε changes the answer.

BNF tells you how productions are written, while the productions determine the language and parse structure. If you want the wider subject plan and guided sequence, use GATE Guidance by Sanchit Sir. If you only needed this concept, re-derive 507, id + id * id, aabb, and aaab unaided before moving on.