Paste your own BNF rules and a test string to see whether it passes or fails. Then step through the derivation: every step follows the same order. Find the leftmost non-terminal, choose an option from its rule, replace it. Keep going until only terminals are left.
Green = already made. Yellow outline = the next character we need.
Keyboard: ← → to step · Space to play/pause · R to reset
Backus-Naur Form (BNF) describes the syntax of a language as a set of production rules. Names in angle brackets, like <integer>, are non-terminals that must be replaced using a rule. Plain characters, like 4, are terminals that appear in the final string.
BNF has no symbol for "repeat", so it uses recursion. The rule <integer> ::= <digit> | <digit><integer> says an integer is a single digit, or a digit followed by another integer. Choosing the second option (the recursive case) means "more digits to come"; choosing the first (the base case) means "this is the last digit".
To show a string is valid you derive it: start from the non-terminal being tested and repeatedly replace the leftmost non-terminal using one of its options, until only terminals remain. If you ever need a character that no option can produce, as with 4a2, the string is invalid.
Paste your own rules to check answers to production-rule questions. Write one rule per line; a line starting with |, or with no ::=, continues the rule above, and ranges such as A|B|…|Z or 0|1|...|9 are filled in for you. The checker searches every possible way of applying the rules, so it also works for rules that use themselves at the start, like <identifier> ::= <identifier><letter>.
AQA 7517 4.4.3.1 Backus-Naur Form (BNF)/syntax diagrams.
Browse all free Computer Science resources →
Want one-to-one help with this topic? I'm Damian Biasone, a qualified Computer Science teacher with 20 years' experience, tutoring GCSE and A-Level students online.
AQA A-Level (7517) tuitionOCR A-Level (H446) tuition