4.4.3.1 - BNF and syntax diagrams

Terminals, non-terminals and productions

A language's syntax specifies which arrangements of symbols or tokens are permitted. Backus–Naur Form (BNF) describes syntax using production rules. A terminal is a literal symbol or token appearing in a finished string. A non-terminal names a syntactic category that must be expanded using a rule.

In the convention used here, angle brackets enclose non-terminals, ::= means “is defined as”, and | separates alternatives. Quotation marks identify terminals; the quotation marks themselves are not part of the generated string. Adjacent items must occur in sequence.

<letter> ::= "A" | "B"
<digit> ::= "0" | "1"
<code> ::= <letter><digit><digit>

This grammar defines a code as exactly one A or B followed by exactly two binary digits. A01 and B11 are valid. C01 is invalid because C cannot be produced by <letter>. A1 is invalid because a digit is missing. A011 is invalid because the code rule has no place for a third digit. Formatting spaces around BNF operators are not automatically terminals.

A rule names alternatives, not a menu of optional ingredients. The code rule requires all three positions. The digit rule requires one of its alternatives. A complete derivation must replace every non-terminal with terminals.

Syntax validity does not establish meaning or suitability. A syntactically valid code could refer to a product that does not exist. A grammar checks the permitted form; separate semantic rules or data checks determine what that code denotes.

Deriving strings and writing rules

To derive a string, begin with the required start non-terminal and repeatedly substitute an allowed right-hand side. For the code grammar, one derivation is:

<code>
⇒ <letter><digit><digit>
⇒ B<digit><digit>
⇒ B1<digit>
⇒ B10

Each substitution obeys one production. The final line contains only terminals, so it is a finished string. A derivation is evidence that a particular string belongs to the grammar; seeing one valid example does not show that every possible string is valid.

To formulate a rule, identify the required order, alternatives and number of occurrences. If a label is exactly an X followed by one A or B, <label> ::= "X"<letter> uses the earlier letter rule. It accepts XA and XB and excludes XAA. Check both intended examples and nearby invalid ones before accepting your rule.

Recursion permits a non-terminal to reappear in its own definition. For a non-empty sequence of binary digits:

<digits> ::= <digit> | <digit><digits>

The first alternative is the base case: it stops expansion after one digit. The second emits a digit then asks for another valid non-empty sequence. Repeated use can produce 0, 11 or 0101, with no fixed maximum length. It cannot produce the empty string. A recursive rule with no terminating alternative may never produce a finished string.

For an optional item, give a genuine empty alternative if the grammar convention allows it. Here $\varepsilon$ denotes the empty string:

<suffix> ::= "!" | ε

This is an alternative between one exclamation mark and no symbol. It is not the literal Greek letter ε in the finished string. Always follow the convention supplied with a task; do not assume that every grammar uses the same empty-string notation.

Following and constructing syntax diagrams

A syntax diagram presents a grammar as paths that can be followed from entry to exit. In the diagram below, rounded boxes contain literal terminal tokens. Follow arrow direction, selecting a branch where paths divide. Every terminal visited on the chosen path must occur in that order.

[DIAGRAM: asset_slug: syntax-move-command; description: Syntax diagram for MOVE followed by LEFT or RIGHT and an optional FAST token]

This command has three decisions: MOVE is compulsory; exactly one of LEFT or RIGHT follows; FAST is optional because a bypass path goes around it. Tokens in the written commands are separated by one space. Valid commands include MOVE LEFT, MOVE RIGHT and MOVE LEFT FAST. MOVE FAST LEFT is invalid because FAST cannot precede the direction. MOVE LEFT RIGHT is invalid because the direction paths are alternatives, rather than a sequence of both.

An equivalent BNF grammar can make the same choices explicit:

<command> ::= "MOVE" <direction> <speed>
<direction> ::= "LEFT" | "RIGHT"
<speed> ::= "FAST" | ε

Here each quoted word is a token, and the task's spacing convention separates the non-empty tokens. The empty speed emits no token and no extra trailing space. BNF and the diagram must accept the same token sequences.

A branch that bypasses a component makes it optional. A backward return path can permit repetition, provided its arrows allow a legal route through another occurrence. One-or-more repetition must require a first traversal; zero-or-more needs a bypass of the first occurrence as well. A plain forward fork gives alternatives and is not a repetition loop.

To construct a simple diagram in your notebook, place the compulsory sequence along a forward path, split and rejoin paths for alternatives, and add a bypass or return path only when the rule permits it. Clearly distinguish literal tokens from named non-terminals using the diagram's stated shape convention. Check by tracing shortest valid examples, examples using every alternative, and invalid examples that should have no complete path. The marked questions assess interpretation; notebook construction develops drawing without claiming automated grading of your sketch.

Why recursive BNF can exceed regular expressions

Some languages require a relationship between arbitrarily long parts of a string. Consider $L=\{0^n1^n\mid n\ge1\}$: a positive block of zeros followed by exactly the same number of ones. BNF can describe this with:

<S> ::= "0""1" | "0"<S>"1"

The base produces 01. Each recursive expansion puts one extra 0 before the existing string and one extra 1 after it. Thus it produces 0011, 000111 and every larger matching pair of blocks. It produces neither 0101 nor 00011. Each expansion preserves the equal-count relationship.

An ordinary regular expression describes a regular language, and a finite-state machine can recognise that same language. An FSM has only finitely many states. It cannot remember an unbounded number of preceding zeros in order to require exactly that many following ones. It can check such a condition up to a fixed bound if given enough states, but this language has no bound on n.

Recursive BNF can represent context-free structure such as matching nested delimiters or these paired blocks. This is why BNF can describe some languages that regular expressions cannot. BNF can also describe many regular languages; using BNF does not imply a language is non-regular. Nor does BNF describe every conceivable language.

Here “regular expression” means the formal regular expressions associated with FSMs. Some software libraries add features, such as backreferences, which go beyond that formal model. Such extensions do not contradict the syllabus comparison.