BNF Grammar and Syntax Diagrams

AQA 4.4.15–4.4.16 — BNF grammar and syntax diagrams

Retrieval: the previous lesson proved that no regular expression or FSM can recognise a language requiring unbounded, matched nesting (balanced brackets). Backus–Naur Form (BNF) is a grammar formalism built specifically to describe exactly these languages — this lesson picks up precisely where the last one's limitation left off.

Key vocabulary

• Production rule — a rule of the form <name> ::= ..., defining what a symbol can expand into.
• Non-terminal — a symbol (written <in angle brackets>) that can be further expanded by a rule.
• Terminal — a symbol that appears literally in the final string; it cannot be expanded any further.
• Derivation — the step-by-step process of repeatedly expanding non-terminals according to the rules, until only terminals remain.
• Syntax diagram — a visual, diagrammatic representation of the same rules a BNF grammar expresses.

Understand — reading a BNF grammar

<digit>  ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<number> ::= <digit> | <digit> <number>

<digit> and <number> are non-terminals; the ten quoted digits are terminals. <number>'s rule is recursive: a number is either a single digit, or a digit followed by another (shorter) number — this recursive self-reference is exactly what lets a finite set of rules describe numbers of any length, something no fixed number of FSM states could do directly.

Trace it — deriving a string, step by step

Deriving "42" from <number>:

Every non-terminal has now been expanded into terminals only: "42".

Generate it

Generate three different valid strings from the grammar above. (For example: "7" (a single digit); "19" (digit "1" followed by number "9"); "305" (digit "3" followed by number "05" — noting this simple grammar does permit leading zeros, since nothing in the rules forbids a digit from being "0" at the start; the Challenge task below asks you to fix exactly this.))

Identify invalid strings

Which of the following are not valid strings under this grammar, and why? "4a"; "" (empty string); "100".

("4a" is invalid - 'a' is not a <digit>, and the grammar has no rule producing letters at all. "" (empty) is invalid - every derivation of <number> must produce at least one <digit>, so the empty string can never be derived. "100" is valid - it derives as digit "1" followed by number "00", which itself derives as digit "0" followed by number "0".)

See it — the balanced-brackets payoff

<brackets> ::= "" | "(" <brackets> ")" | <brackets> <brackets>

This single, small grammar generates "", "()", "(())", "()()", "(()())", and every other correctly-balanced bracket string, to any depth of nesting — precisely the language the previous lesson proved no regular expression or FSM could recognise. The recursive rule "(" <brackets> ")" is what makes unbounded nesting possible: each application adds one matched pair, and the rule can be applied to itself as many times as needed.

Understand — syntax diagrams

A syntax diagram is a visual alternative to writing out BNF rules symbolically, tracing a path from a start point to an end point, where each element on the path is either a terminal (drawn as a literal box) or a non-terminal (referring out to another diagram). The <digit> rule above, as a simplified syntax diagram:

──▶── choose one: [0]─[1]─[2]─[3]─[4]─[5]─[6]─[7]─[8]─[9] ──▶──

Both notations express exactly the same rule — BNF is more compact and precise for writing down by hand; syntax diagrams are sometimes easier to follow visually, especially in language-reference documentation.

Debug it — diagnose, explain, fix, test, justify (permits an unintended string)

A grammar intends to describe "one or more consecutive a characters":

<a-string> ::= "a" | <a-string> "b"

1. Diagnose: derive a string using the recursive rule twice — what does it actually produce?
2. Explain: compare the terminal appended in the recursive rule against what the specification actually requires.
3. Fix: correct the rule.
4. Test: confirm "aaa" can now be derived, and "ab" can no longer be.
5. Justify: explain why this specific mistake (the wrong terminal in a recursive rule) is easy to introduce, especially when a grammar is adapted by copying a similar existing rule.

(Deriving twice: <a-string> => <a-string> "b" => "a" "b" "b" = "abb" - the rule actually appends "b", producing strings like "a", "ab", "abb", never a string of only a's beyond the first. The fix changes the recursive rule to <a-string> ::= "a" | <a-string> "a". This mistake is easy to introduce because "b" and "a" look equally plausible as a base terminal if a rule was copied and only partially edited - checking a derivation by hand, not just reading the rule, is what catches it.)

Debug it — diagnose, explain, fix, test, justify (rejects a valid string)

A grammar intends to describe "a value is either a number or a single letter":

<value> ::= <number>

1. Diagnose: can the string "x" (a single letter) be derived from <value> using only this rule?
2. Explain: what alternative does the specification require that this rule is missing?
3. Fix: correct the rule.
4. Test: confirm "x" is now derivable, and "42" remains derivable.
5. Justify: explain how this fault type (a missing alternative) differs from the previous task's fault type (a wrong terminal).

(No - <value> ::= <number> only ever expands to digit-based strings; "x" cannot be derived at all, since <number> has no rule producing letters. The fix restores the missing alternative: <value> ::= <number> | <letter> (with <letter> defined separately). This differs from the previous task because that rule was present but WRONG (the wrong terminal); this rule is simply INCOMPLETE - an entire valid case was left out of the grammar altogether, a different kind of construction error from a typo within an existing rule.)

Common mistake

Assuming a grammar that correctly generates several example strings is therefore complete and correct. As both Debug it tasks show, a grammar can generate plausible-looking strings while still containing a genuine, hidden error — checking a grammar against its specification, not just against a few example derivations, is what actually verifies correctness.

Modify it

The <number> grammar from earlier permits leading zeros (e.g. "007"). Modify the grammar so that a number greater than one digit long cannot start with 0, while "0" on its own remains valid.

(<number> ::= "0" | <nonzero-digit> | <nonzero-digit> <digit-string>, where <nonzero-digit> ::= "1"|"2"|...|"9" and <digit-string> ::= <digit> | <digit> <digit-string> - separating the FIRST digit's rule (which must be "0" alone, or start with a nonzero digit) from subsequent digits (which may be any digit, including 0) is what enforces the no-leading-zero rule while still allowing "0" itself and numbers like "20" or "105".)

Why this matters for the NEA

Designing a simple command syntax or file format for an NEA project — even informally, without writing out full BNF — is implicitly grammar design: deciding what's a fixed keyword (a terminal) versus what varies (a non-terminal), and what combinations are actually valid. Understanding BNF makes that design more precise and less prone to the exact "accepts too much" or "rejects too much" errors this lesson has covered directly.

Check your understanding

Given <greeting> ::= "hi" | "hello" <name> and <name> ::= "sam" | "alex", trace a derivation for "hello alex" and identify one string this grammar does not permit. (3 marks)

(Derivation: <greeting> => "hello" <name> => "hello" "alex" = "hello alex". A string not permitted: "hi sam" (or "hey alex", or "hello" alone without a name) - "hi" has no <name> following it in this grammar's rules, so "hi sam" cannot be derived.)

Challenge

Write a BNF grammar for a simple traffic-light sequence that must always go red → red-amber → green → amber → back to red, for one or more full cycles. Trace a derivation for two complete cycles.

Looking ahead: Sequence 16 (Databases & Big Data) moves from formal language theory to genuinely new territory — relational databases and SQL — the first entirely new subject area since Year 12.