A-Level · Context-free languages

Syntax Diagram generator

Type production rules in BNF and the syntax diagrams are drawn as you type. Rectangles are non-terminals, rounded boxes are terminals, and recursion can be shown as a loop. Download any diagram for worksheets or slides.

BNF rules

One rule per line: <name> ::= option | option. A line starting with |, or with no ::=, continues the rule above. Characters written together make one terminal box (var); separate them with spaces for separate boxes (v a r). Put symbols in quotes to use them as terminals: "|", "<".
non-terminalterminal
About this resource · A-Level

Syntax diagrams and BNF

A syntax diagram shows the same production rules as Backus-Naur Form (BNF), but as a route to follow. A string is valid if you can trace it along some path from the entry arrow to the exit arrow. Rectangles are non-terminals, defined by their own diagram; rounded boxes are terminals, the actual characters in the string.

A branch is a choice (the | in BNF) and a line that loops back is repetition. BNF has no repetition symbol, so it uses recursion instead: <integer> ::= <digit> | <digit><integer> becomes one digit box with a loop round it. Recursion in the middle of an option, as in <S> ::= ab | a<S>b, can't become a loop, which is exactly why BNF can describe languages that regular expressions can't.

Type your own rules or start from an example. Untick Draw recursion as loops to see each rule drawn exactly as written, then compare the two.

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