A-Level · Theory of Computation

BNF and Syntax Diagrams

BNF is a formal notation for defining exactly which strings count as valid syntax. The only real way to understand it is to build a string yourself, rule by rule, making genuine choices, not watching someone else's example play out. Every tool on this page is driven by your choices.

<signed-integer> ::= <integer> | '+' <integer> | '-' <integer> <integer> ::= <digit> | <digit> <integer> <digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Angle brackets mark a non-terminal, something that still needs expanding. Quoted characters are terminals, actual characters that appear in the final string. ::= means "is defined as", | means "or".

Section 2

Build your own derivation

Below is the current derivation string. Whenever it contains a non-terminal, you'll be offered every rule that could expand it. Your choices decide what gets built, try producing several different valid strings, not just one.

Controls

Choices made so far

Exam tips

  • Every single sequence of legal choices produces a valid string, and every valid string can be produced by some sequence of choices. That's what it means for BNF to define a language precisely.
  • Notice <integer> ::= <digit> | <digit> <integer> is recursive, choosing the second option always leaves another <integer> to deal with. The only way to finish is to eventually choose the first option instead.
Section 3

Trace the syntax diagram yourself

Same grammar, drawn as a diagram instead of written as rules. Click your way through it, left to right, the string builds as you go, exactly mirroring the choices you'd make in Section 2.

Controls

Exam tips

  • The loop back on the digit box is exactly the recursive rule <integer> ::= <digit> <integer>, every time you choose to go round again instead of exiting, that's this rule being applied.
  • The three branches at the very start (no sign, '+', '-') are the diagram's version of the BNF's three "|" separated alternatives for <signed-integer>.
Section 4

Trace to a target

This time you're not exploring freely, you're aiming at a specific string. Every choice is checked immediately against the target, a wrong choice is flagged the instant you make it, not at the end.

Target:

Pick a target

Controls

Section 5

Is this string a valid signed-integer?

Checked against the signed-integer grammar from Section 1 specifically, optional +/-, then one or more digits, nothing else. Not against "looks like a number" in general, and not against the identifier grammar coming up in Section 6, a string can satisfy one of these grammars and fail the other. Try something you built above, or something deliberately broken.

Try one

Section 6

A real language rule: identifiers

Numbers are a clean teaching example, but BNF's actual job is describing programming language syntax. Every language needs a rule for what counts as a valid variable name, here's a genuine one, built the same way.

<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit> <letter> ::= 'a' | 'b' | 'c' | ... | 'z' | 'A' | 'B' | ... | 'Z' <digit> ::= '0' | '1' | ... | '9'

This is precisely the rule the symbol table in the Translators lesson relies on: a name must start with a letter, then any mix of letters and digits is allowed, which is exactly why "1x" is never a legal variable name but "x1" is.

Watch how this feels different from Section 2's grammar as you use it below. <integer> ::= <digit> | <digit> <integer> is right-recursive (the recursive call comes last), so it immediately asks for a real digit at every step. This identifier rule is left-recursive (the recursive call comes first), so it asks you to decide the whole shape before any real letters or digits get filled in. Same underlying idea, recursion, genuinely different hands-on experience.

Controls

Check a variable name (identifier grammar, not signed-integer)

Section 7

The identifier grammar, drawn as a diagram

This diagram looks structurally different from Section 3's, and it should: a mandatory first box (you can't skip straight to the loop, a letter always comes first), then a loop that itself branches in two, letter or digit, every time round. That branch-inside-a-loop is something the signed-integer diagram never needed.

Controls

Exam tips

  • The very first box isn't optional, there's no path around it, which is exactly why an identifier can never be empty and can never start with anything other than a letter.
  • Inside the loop, the branch between letter and digit is a direct diagrammatic version of the two separate recursive BNF rules, <identifier> <letter> and <identifier> <digit>, drawn as one shared loop with two paths through it.
Section 8

A composed grammar: assignment statements

Real language grammars are built by combining smaller rules, not writing one giant rule from scratch. This one reuses both grammars already on this page, unchanged.

<assignment> ::= <identifier> '=' <value> <value> ::= <signed-integer> | <identifier>

<identifier> and <signed-integer> are exactly the same non-terminals defined earlier on this page, nothing about them changes here, they're simply being reused as building blocks inside a bigger rule. This is precisely how real language specifications are actually organised.

The two large boxes aren't drawn out here, they're the exact diagrams from Sections 3 and 7, referenced rather than repeated, the same way a real language spec would say "see the identifier rule" instead of redrawing it every time.

Try one

Exam tips

  • <value> ::= <signed-integer> | <identifier> is why "total=-42" and "total=item2" are both valid, but "total=-42.5" and "total=+" are not, in each invalid case, whatever comes after "=" fails to fully match either alternative.
  • This is exactly why "1x=5" is rejected: it fails before the grammar even reaches the "=", <identifier> itself already rules out a name starting with a digit.
Section 9

Check your understanding