SLIDE 1 / 10
CSZone.co.uk
Click anywhere to advance · Arrow keys also work
AQA 7517 · Paper 1 · 4.4.2a

Backus-Naur
Form (BNF)

Context-free grammars · Formal syntax definition · Section 4.4

WHAT YOU'LL LEARN
BNF notation · Terminals vs non-terminals · Production rules · Derivation · Recursion
AQA SPEC LINK
4.4.2 — Backus-Naur Form and syntax diagrams
Why BNF?

Why Do We Need BNF?

Programming language syntax must be defined precisely — natural language is too ambiguous. BNF is a formal notation for defining the grammar (syntax rules) of languages.
Used to define syntax of programming languages (Python, Java, C#…)
Compilers use BNF grammar to check if programs are syntactically valid
BNF defines context-free grammars (Type 2 in Chomsky hierarchy)
BNF Symbols

BNF Notation

::= means "is defined as"
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<angle brackets> = non-terminals (can be expanded)
<letter>, <expression>, <statement> — placeholders for further rules
Bare text = terminals (literal characters — cannot be expanded)
0, 1, a, b, +, -, if, while — actual characters in the language
| means OR — alternative production choices
Simple Grammar

Simple BNF Grammar Example

Grammar for integers (one or more digits):
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<integer> ::= <digit> | <integer> <digit>
The second rule is recursive: <integer> is defined in terms of <integer> — this allows arbitrarily long integers.
Derivation

Deriving a String from BNF

To show a string belongs to a grammar, perform a derivation — repeatedly replace non-terminals using production rules until only terminals remain.
# Derive "342" using the integer grammar
<integer>
→ <integer> <digit> # apply rule 2
→ <integer> 2 # expand digit
→ <integer> <digit> 2
→ <integer> 4 2
→ <digit> 4 2
→ 3 4 2 ✓
Larger Grammar

Expression Grammar

Grammar for arithmetic expressions:
<expression> ::= <term> | <expression> + <term> | <expression> - <term>
<term> ::= <factor> | <term> * <factor> | <term> / <factor>
<factor> ::= <integer> | ( <expression> )
Recursion in grammar naturally encodes operator precedence (×/÷ binds tighter than +/−)
Parse Trees

Parse Trees

A parse tree shows the hierarchical derivation of a string from the grammar. Each internal node is a non-terminal; each leaf is a terminal.
<expression>
    /   |   \
<term>  +  <term>
 |           |
<int>     <int>
 |           |
 3           4
Applications

BNF in Real Programming

Compiler design — BNF defines the grammar the parser checks against
Language specification — Python, Java, SQL all have formal BNF-like grammars
Error detection — parser reports "syntax error" when derivation fails
EBNF (Extended BNF) adds repetition {...} and optional [...] for convenience
AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style
Consider this BNF grammar:
<letter> ::= a | b | c
<digit> ::= 0 | 1 | 2
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
(a) Give TWO strings that can be derived from <identifier>. [2]
(b) Explain what the | symbol means in BNF. [1]
(c) Write a derivation for the string "ab2". [3]
[6 marks]
2 marks
(a) "a", "abc", "a1", "b2c" — any valid identifiers using a/b/c and 0/1/2
1 mark
(b) OR — it means the item can be replaced by any of the alternatives separated by |
3 marks
(c) <id> → <id><digit> → <id><letter><digit> → <letter><letter><digit> → a<letter>2 → ab2 ✓
Summary

Key Points to Remember

BNF — formal notation for grammar; defines syntax of languages
<non-terminal> — in angle brackets; can be replaced; terminal = actual character
::= "is defined as"; | means OR; rules can be recursive
Derivation — repeatedly replace non-terminals until all terminals remain
Parse tree shows hierarchical structure of a valid string
🎉 Lesson complete — move to the quiz!