Backus-Naur Form (BNF)

Backus-Naur Form (BNF) is a formal notation for describing the syntax of programming languages. It is a type of context-free grammar (CFG) and uses rules called productions.

BNF notation

Example BNF grammar for integers

<integer> ::= <sign><digits> | <digits>
<sign>    ::= + | -
<digits>  ::= <digit> | <digit><digits>
<digit>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

How BNF works — derivation

Start with the top-level non-terminal and apply rules until only terminals remain. This is called a derivation.

// Derive "-37":
<integer> → <sign><digits>
           → - <digits>
           → - <digit><digits>
           → - 3 <digits>
           → - 3 <digit>
           → - 3 7

Extended BNF (EBNF)

EBNF extends BNF with additional notation to make grammars more concise:

// EBNF for integer (equivalent to above):
<integer> ::= [+ | -] <digit> {<digit>}

Recursion in BNF

BNF naturally handles recursion — a rule that refers to itself. This is used to express repetition:

// Recursive definition of a list of digits:
<digits> ::= <digit> | <digit><digits>

// This generates: 0, 1, 00, 01, 10, 123, 4567, ...

// Recursive definition for balanced brackets:
<expr> ::= (<expr>) | ε

Syntax Diagrams (Railroad Diagrams)

A syntax diagram (also called a railroad diagram) is a visual alternative to BNF. It shows valid syntax as paths through a diagram.

Shapes used

Reading syntax diagrams

• Follow arrows from left to right
• Where paths split, choose one branch (alternation)
• Where a path loops back, the element can repeat
• A valid string follows any valid path from start to end

BNF and Context-Free Grammars

BNF describes context-free languages — more powerful than regular languages. CFLs can express nested/recursive structures (like balanced brackets, arithmetic expressions) that regular expressions cannot.