A-Level · Context-free languages

BNF Checker step by step

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.

Production rules

Order of events (every step)

  1. 1Find the leftmost non-terminal in the working string.
  2. 2Look up its rule and choose one option that can still make the target.
  3. 3Replace the non-terminal with that option.
  4. 4Repeat until no non-terminals are left. Matches the target? Valid.

Target string

Green = already made. Yellow outline = the next character we need.

Working string

non-terminal (still to replace)terminal (finished)

Derivation so far

0.5 step/s
Step 0 / 0

Keyboard: ← → to step  ·  Space to play/pause  ·  R to reset

About this resource · A-Level

How the BNF checker works

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>.

Exam tips

Specification

AQA 7517 4.4.3.1 Backus-Naur Form (BNF)/syntax diagrams.

Related resources

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