Normal Forms and BNF in Compiler Design: CNF, GNF and Worked CFG Conversions

BNF, CFG, CNF and GNF are often memorised as four unrelated abbreviations. That makes it easy to mix up notation with production-rule restrictions. BNF is notation; CNF and GNF restrict production shapes. Language-preserving conversions produce CNF and GNF grammars, while exact derivations verify representative strings. These CS Fundamentals support compiler design and theory of computation.

BNF and normal forms describe different things

A context-free grammar is G = (V, Sigma, P, S): variables V, terminal alphabet Sigma, productions P, and start variable S.

We use V = {S}, Sigma = {a, b}, P = {S -> aSb, S -> ab}, and start variable S. It generates L = {a^n b^n | n >= 1}.

In Backus-Naur Form, the same grammar is:

<S> ::= "a" <S> "b" | "a" "b"

<S> names a variable, ::= means "is defined as", | separates alternatives, and quotes mark terminals. BNF is notation, not a restricted CFG class. CNF and GNF restrict production shapes while preserving the language. See context-free grammars and pushdown automata for the wider recognition connection.

BNF reading: derive a real expression

Consider this compiler-style BNF:

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

Variables are <expr>, <term> and <factor>; terminals are +, *, (, ) and id. The layers give * tighter binding than +. Left recursion makes this unsuitable for a naive recursive-descent parser until rewritten.

The complete leftmost derivation of id + id * id is:

<expr> => <expr> + <term> => <term> + <term> => <factor> + <term> => id + <term> => id + <term> * <factor> => id + <factor> * <factor> => id + id * <factor> => id + id * id

Reading the arrows left to right, each replacement targets the current leftmost variable:

1. <expr> -> <expr> + <term>

2. <expr> -> <term>

3. <term> -> <factor>

4. <factor> -> id

5. <term> -> <term> * <factor>

6. <term> -> <factor>

7. <factor> -> id

8. <factor> -> id

So the left operand of + is id, while its right operand is one <term> containing id * id.

CNF and GNF: allowed production shapes

In CNF, every production is A -> BC or A -> a, where uppercase symbols are variables and a is one terminal. If the language contains the empty string, the controlled exception is S0 -> epsilon; under the strict convention here, fresh S0 never appears on a right-hand side.

In GNF, every production is A -> aA1A2...Ak: a terminal comes first, followed by zero or more variables.

BNF does not belong in this comparison because it is notation, not a production-shape restriction.

CFG to CNF: convert S -> aSb | ab

Start with G0: S -> aSb | ab. It has no epsilon-production, unit production or useless symbol. However, both alternatives mix terminals into longer strings, and aSb has length three.

1. Protect the start with S0 -> S.

2. Isolate terminals using A -> a and B -> b, so S -> ASB | AB.

3. Remove the new unit production by copying the alternatives to S0 -> ASB | AB.

4. Binarise the length-three sequence using C -> SB.

The final CNF is exactly:

S0 -> AC | AB
S  -> AC | AB
C  -> SB
A  -> a
B  -> b

AC, AB and SB are variable pairs; a and b are single terminals. Every rule passes the CNF test.

Now verify aabb and name each production used:

S0 => AC => aC => aSB => aABB => aaBB => aabB => aabb

The steps use S0 -> AC, A -> a, C -> SB, S -> AB, A -> a, B -> b, then B -> b. The shortest string also survives: S0 => AB => aB => ab.

CFG to GNF: reuse the same grammar

In S -> aSb | ab, both alternatives already start with terminal a. Only the later b needs a variable. Introduce B -> b:

S -> aSB | aB
B -> b

aSB starts with terminal a followed only by variables S, B. aB starts with a followed by B, and b is a single terminal. All fit GNF. In contrast, aSB and aB are invalid in CNF.

The same string follows as S => aSB => aaBB => aabB => aabb. One more recursive use generates aaabbb. The string abab is not in {a^n b^n | n >= 1} because every a must precede every b, with equal counts.

Normal-form traps that cost easy marks

For a general CNF conversion, protect the start when required, remove epsilon-productions, remove unit productions, remove useless symbols, isolate terminals in long rules, then binarise. Our compact grammar skipped the cleanup stages only because inspection found nothing to remove.

Equivalence preserves the generated language, not production spellings, derivation length or parse-tree shape. Checking ab and aabb is a useful sanity test, not a proof for every string.

Normal forms and BNF exam patterns: classify, convert, derive

The four common formats are classify a rule, convert a small CFG, follow a leftmost derivation, and test string membership. A quick drill is: A -> BC is CNF only, A -> aB is GNF only, A -> a fits both, and A -> BCd fits neither.

Use this 60-second verification order: scan for epsilon, unit rules and useless variables; check terminal placement and right-hand-side length; then test the shortest two generated strings. Our CNF passes these scans and derives ab and aabb exactly.

The broader Grammar and CFG in Compiler Design guide develops ambiguity, parse trees, FIRST, FOLLOW and left-recursion removal. Normal-form conversion has a narrower goal: change production shapes while preserving the generated language.

Normal forms and BNF: the short version

BNF = notation

CFG = language definition

CNF = two variables or one terminal

GNF = terminal first

Conversion preserves language

Verify with exact derivations

After reviewing the rules, practise by classifying single productions and converting two or three short grammars into CNF and GNF yourself. For a GATE-oriented subject sequence, continue with GATE Guidance by Sanchit Sir. For a broader core-CS route, use the Zero to Hero Complete CS Course.