A2 · Practice questions · BNF and syntax diagrams

Define the grammar.

Six original Cambridge-style questions on Backus-Naur Form and syntax diagrams, with mark-scheme solutions.

Original questions All questions on this page are original work, written in the Cambridge AS & A Level style. They are not from past papers. They test the same concepts and skills the syllabus rewards.

Keep these straight

Smallest parts first.

Notation: <non-terminal>, ::= is defined as, | or, terminals written as themselves.
Recursion: "one or more" means a rule that refers to itself plus a non-recursive way out.
Syntax diagrams: rectangles for non-terminals, rounded boxes for terminals, branches for |, loops for repetition.
Validity: check every character against the listed terminals and the required order and length.

Recall

[3 marks]

State the meaning of each of these BNF symbols: (a) ::= (b) | (c) < >

(a) ::= means "is defined as". ✓
(b) | separates alternatives: "or". ✓
(c) < > enclose the name of a non-terminal (a part of the grammar that is defined by a rule). ✓

Apply

[4 marks]

A password is defined by:

<letter>   ::= a | b | c | d | e
<digit>    ::= 0 | 1 | 2 | 3
<name>     ::= <letter> | <letter><name>
<password> ::= <name><digit><digit> | <name>#<digit><digit>

State whether each is a valid <password> and give a reason for each invalid one: (a) cab#23 (b) ace3 (c) #12 (d) dd#4

(a) cab#23: valid. ✓
(b) ace3: invalid, as a password must end with two digits. ✓
(c) #12: invalid, as it must start with a <name> of at least one letter. ✓
(d) dd#4: invalid, as only one digit follows the #. ✓

Trace

[3 marks]

Using the grammar in the previous question, show how bad01 is derived from <password>.

<password> → <name><digit><digit>. ✓
<name> → <letter><name> → <letter><letter><name> → <letter><letter><letter>. ✓
Letters b, a, d and digits 0, 1 give bad01, so it is valid. ✓

Write

[4 marks]

A product code consists of one or two upper-case letters from P, Q and R, followed by a colon, followed by one or more digits from 0 to 9. Write BNF to define <product>.

<letter> ::= P | Q | R ✓
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ✓
<number> ::= <digit> | <digit><number> (recursive, for one or more digits) ✓
<product> ::= <letter>:<number> | <letter><letter>:<number> ✓

Write

[3 marks]

Describe the syntax diagram for the rule <number> ::= <digit> | <digit><number>, and explain how it represents the recursion.

An entry arrow leads into a rectangle labelled digit, and an arrow leads out to the exit. ✓
A path loops back from after the digit box to before it. ✓
The loop replaces the recursion: each time round the loop adds one more digit, so one or more digits are allowed. ✓

Analysis

[2 marks]

A student writes <word> ::= <letter><word> to define a word of one or more letters. Explain why this rule is incorrect and correct it.

There is no non-recursive alternative, so the recursion never ends and no finite string can be derived. ✓
Correct rule: <word> ::= <letter> | <letter><word>. ✓

Mark this once you have attempted all six and checked your working. It records a Practiced badge on the topic and adds a one-time bonus. Revealing the solutions alone does not count.