Before a parser can check a program, the grammar of the language has to be written down precisely. Learn to read and write Backus-Naur Form, including recursive rules, draw the equivalent syntax diagrams, and decide whether a string is valid by deriving it from the rules.
Backus-Naur Form (BNF) is a formal notation for the grammar (syntax rules) of a language. Each rule has a non-terminal in angle brackets on the left, ::= meaning "is defined as", and on the right a sequence of terminals and non-terminals, with | separating alternatives. Terminals are the actual characters or symbols that appear in the language. Repetition is expressed by recursion: a rule that refers to itself. A syntax diagram shows the same rules graphically, following arrows through boxes, with loops for repetition.
Fig. 1: one recursive BNF rule and the equivalent syntax diagram
Section 01
Reading BNF.
This grammar defines identifiers made from a small set of letters and digits.
<letter> ::= A | B | C | D | E
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<identifier> ::= <letter> | <identifier><letter> | <identifier><digit>
Non-terminals such as <letter> are names for parts of the grammar; they are replaced using their rule until only terminals remain.
Terminals such as A or 7 appear in the final string exactly as written.
::= means "is defined as"; | means "or"; writing two items side by side means one followed by the other.
Recursion: <identifier> appears on both sides of its own rule. Each time the rule is applied, one more letter or digit is added, so identifiers of any length can be defined. The non-recursive option, <letter>, stops the recursion and forces an identifier to start with a letter.
Worked example Valid or not?
Using the grammar above, decide whether BAD5, 3AB and AF are valid identifiers. Show a derivation for any valid one.
BAD5 ends in a digit, so use <identifier> ::= <identifier><digit>: <identifier> → <identifier><digit>.
Expand the inner identifier twice with <identifier><letter>: → <identifier><letter><digit> → <identifier><letter><letter><digit>.
End the recursion with <identifier> ::= <letter>: → <letter><letter><letter><digit> → B A D 5. All four terminals are allowed, so BAD5 is valid.
3AB: every identifier must begin with <letter>, and 3 is a digit. Invalid.
AF: F is not one of the terminals A to E in <letter>. Invalid.
Answer: BAD5 valid; 3AB invalid (starts with a digit); AF invalid (F is not a defined letter).
Examiner trap
Check every character against the terminals that are actually listed. In exam grammars <letter> or <digit> is often deliberately restricted, e.g. to A to E or to 1 to 9.
Section 02
Syntax diagrams.
A syntax diagram expresses a rule as a set of paths. Follow the arrows from the entry on the left to the exit on the right; any path you can trace gives a valid string.
Rectangles hold non-terminals: they refer to another syntax diagram.
Rounded boxes or circles hold terminals: the exact symbol that must appear.
Branches show alternatives (the | in BNF).
A loop back shows repetition, replacing the recursion in BNF. In Fig. 1, after the first letter the path can loop back any number of times through a letter or a digit.
digit: ten parallel branches, each through one rounded box 0, 1, ..., 9, joining at the exit.
integer: one rectangle digit, then a loop from after the box back to before it: one or more digits.
sign: two parallel branches through rounded boxes + and -.
signed: a branch that either passes through the rectangle sign or bypasses it, then joins a rectangle integer before the exit.
Check with test strings: -305 follows sign then three loops of digit (valid); +-4 would need two signs, and there is no path for that (invalid).
Answer: Four diagrams: digit (10 alternatives), integer (digit with a loop), sign (2 alternatives), signed (optional sign then integer).
Your turn
Using the grammar in the worked example, is +08 a valid <signed>? Explain.
Valid. + is a <sign> and 08 is <digit><integer> with 0 and 8 both digits. The grammar does not forbid a leading zero.
Stage 1 · Learn
Check what the sim just showed you
Four quick checks. Each correct answer earns XP and records this skill on your profile.
Quick check+10 XP
What does ::= mean in BNF?
Quick check+10 XP
In BNF, what is a terminal?
Quick check+10 XP
How does BNF express "one or more" items?
Quick check+10 XP
In a syntax diagram, what shows repetition?
Section 03
Writing your own rules.
Exam questions describe a format in words and ask you to write the BNF. Define the smallest parts first, then build up, and use recursion wherever the description says "one or more".
Worked example A registration code
A registration code is two letters from A, B, C, X, Y and Z, then a hyphen, then one or more digits from 1 to 9. Write BNF for <reg> and test AB-12, XYZ-1, CA-905 and AX-.
Smallest parts: <letter> ::= A | B | C | X | Y | Z and <digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.
"One or more digits" needs recursion: <number> ::= <digit> | <digit><number>.
The whole code is a fixed sequence: <reg> ::= <letter><letter>-<number> (the hyphen is a terminal).
AB-12: two letters, hyphen, number 12. Valid.
XYZ-1: three letters before the hyphen. Invalid. CA-905: 0 is not a <digit>. Invalid. AX-: <number> needs at least one digit. Invalid.
Answer: <reg> ::= <letter><letter>-<number>, with <number> ::= <digit> | <digit><number>. Only AB-12 is valid.
Examiner trap
A rule like <number> ::= <digit><number> with no non-recursive alternative can never finish, so it defines no strings at all. Every recursive rule needs a way out.
Stage 2 · Exam
Exam-style questions
Unlocks once the four checks above are done. Worth more XP, written to A Level Paper 3 and Paper 4 standard.
Finish the four checks above to unlock the exam questions
Exam style+20 XP
Using <identifier> ::= <letter> | <identifier><letter> | <identifier><digit>, which is invalid?
Exam style+20 XP
Which BNF rule defines a string of one or more <letter>s?
Exam style+20 XP
With <digit> ::= 1 | 2 | 3 and <code> ::= <digit><digit> | <digit><code>, which is valid?
Exam style+20 XP
Why is BNF used to define a programming language?
Skill unlocked
BNF and syntax diagrams, derived.
This skill is now recorded on your profile. Keep the chain going.