The shape of the lesson
By the end of the lesson, learners can
- Reading BNF: This grammar defines identifiers made from a small set of letters and digits.
- Syntax diagrams: A syntax diagram expresses a rule as a set of paths.
- Writing your own rules: Exam questions describe a format in words and ask you to write the BNF.
- 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.
One picture every idea returns to
Backus-Naur Form (BNF) is a formal notation for the grammar (syntax rules) of a language. Each rule has a non-terminal in angle brackets on the left, ::= meaning "is defined as", and on the right a sequence of terminals and non-terminals, with | separating alternatives. Terminals are the actual characters or symbols that appear in the language. Repetition is expressed by recursion: a rule that refers to itself. A syntax diagram shows the same rules graphically, following arrows through boxes, with loops for repetition.
Forty-five minutes, phase by phase
| Time | Phase | What happens in the room | Grouping |
|---|---|---|---|
| 0 to 5 min | Hook: predict | Open with the question in the title, The rules of the language.. Before a parser can check a program, the grammar of the language has to be written down precisely. Put the figure on the board: it is the one picture every idea in the lesson returns to. | Whole class, then pairs |
| 5 to 13 min | Teach and check: Reading BNF | This grammar defines identifiers made from a small set of letters and digits. Model the worked example Valid or not? on the board, one line at a time. | Whole class, then pairs |
| 13 to 21 min | Teach and check: Syntax diagrams | A syntax diagram expresses a rule as a set of paths. Model the worked example BNF to syntax diagram on the board, one line at a time. Your turn: Using the grammar in the worked example, is +08 a valid | Pairs |
| 21 to 30 min | Teach and check: Writing your own rules | Exam questions describe a format in words and ask you to write the BNF. Model the worked example A registration code on the board, one line at a time. | Corners |
| 30 to 36 min | Check | The four Stage 1 questions from the student lesson, answered on mini whiteboards or by show of fingers. Re-teach the one most get wrong. | Individual, then whole class |
| 36 to 43 min | Plenary | The exam-style questions from Stage 2, one at a time: thirty seconds alone, then a random call. The feedback lines in the key give the examiner's wording. | Individual, random call |
| 43 to 45 min | Exit and homework | Set the worksheet below (6 questions, 19 marks). Learners self-assess against the objectives before they leave. | Individual |
Protect the parts that carry the learning
The sequence carries about fifty minutes of material, so the lab is driven by one student while the class predicts rather than explored freely. Times are a guide.
Protected: the check at 30 minutes. It is the only individual read on whether the key idea landed, and it is not cut.
Cut first if the build overruns: the last check in Writing your own rules, never the check or the plenary.
In a 60 minute block: run worksheet questions 1 to 3 in class as a Rally Coach set and model both the hardest worked example and its check live.
Corners
Put one answer or viewpoint in each corner of the room. Students move to the corner they agree with, justify the choice to a partner there, then hear one voice from each corner before the reveal.
The full structure, with its variations and the other twelve, is on the cooperative-learning page.
What to head off, and how
| Trap learners fall into | Teaching move that pre-empts it |
|---|---|
| Check every character against the terminals that are actually listed. | In exam grammars |
| A rule like::= with no non-recursive alternative can never finish, so it defines no strings at all. | efines no strings at all. Every recursive rule needs a way out. |
BNF and syntax diagrams: worksheet
6 questions, 19 marks. Written in the style of the papers; no past paper question is reproduced.
State the meaning of each of these BNF symbols: (a) ::= (b) | (c) < >
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
Using the grammar in the previous question, show how bad01 is derived from <password>.
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>.
Describe the syntax diagram for the rule <number> ::= <digit> | <digit><number>, and explain how it represents the recursion.
A student writes <word> ::= <letter><word> to define a word of one or more letters. Explain why this rule is incorrect and correct it.
Answer key and marking notes
- (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).
- (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 #.
- <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.
- <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>
- 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.
- There is no non-recursive alternative, so the recursion never ends and no finite string can be derived.
- Correct rule: <word> ::= <letter> | <letter><word>.
6 multiple-choice questions on this lesson
From the topic question bank. Assign them in the app for a marked score in your gradebook, or run the topic as a class game.
Why does the rule <number> ::= <digit> | <digit><number> include the alternative <digit> on its own?
- AIt gives the recursion a way to stop, so a number can end after its last digit
- BIt limits a number to exactly one digit
- CIt makes the rule recursive, so that numbers can be any length
- DIt shows that a digit is a terminal symbol in the language
Using this grammar, which string is a valid <identifier>?
<letter> ::= A | B | C | D | E <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 <identifier> ::= <letter> | <identifier><letter> | <identifier><digit>
- ADE4C
- BCAFE
- C2BAD
- DBE-1
How many different strings can be derived from <tag>?
<letter> ::= A | B | C <digit> ::= 0 | 1 <tag> ::= <letter><digit> | <letter><letter><digit>
- A24
- B6
- C18
- D12
A syntax diagram for <word> has a single rectangle labelled letter between the entry and the exit, with a path that loops back from after the box to before it. Which BNF rule matches the diagram?
- A<word> ::= <letter> | <letter><word>
- B<word> ::= <letter><word>
- C<word> ::= <letter> | <letter><letter>
- D<word> ::= <word> | <letter><letter>
Using this grammar, which string is a valid <code>?
<letter> ::= P | Q | R | S <digit> ::= 1 | 2 | 3 <tail> ::= <digit> | <digit><tail> <code> ::= <letter><tail> | <letter><letter>*<tail>
- AQQ*33
- BQR21
- CS*3
- DRS*0
A code is one or more digits from 1 and 2, optionally followed by a single letter X (so 1, 212 and 21X are valid, but X and 1XX are not). Which grammar defines <code> exactly?
- A<digit> ::= 1 | 2
<num> ::= <digit> | <digit><num>
<code> ::= <num> | <num>X - B<digit> ::= 1 | 2
<num> ::= <digit> | <digit><num>
<code> ::= <num>X - C<digit> ::= 1 | 2
<num> ::= <digit> | <num>X
<code> ::= <num> | <digit><code> - D<digit> ::= 1 | 2
<num> ::= <digit> | <digit><digit>
<code> ::= <num> | <num>X
Quiz key
The non-recursive alternative is the way out: without it, every expansion would contain another <number> and no finite string could ever be derived. It does not limit numbers to one digit, because the other alternative still allows more. The recursion comes from <digit><number>, not from <digit>. <digit> is in angle brackets, so it is a non-terminal defined by its own rule.
DE4C starts with the letter D and continues with E, 4 and C, all of which are listed, so it can be derived. CAFE contains F, which is not one of the letters A to E. 2BAD starts with a digit, but the recursion always ends with <letter> at the start of the identifier. BE-1 contains a hyphen, which is not a terminal anywhere in the grammar.
The first alternative gives 3 × 2 = 6 strings (A0 to C1). The second gives 3 × 3 × 2 = 18 (AA0 to CC1). The total is 6 + 18 = 24. 6 and 18 are each alternative on its own. 12 counts the second alternative as only 3 × 2, as if its two letters were a single choice.
The diagram allows one or more letters, which in BNF needs a non-recursive option plus a recursive one: <letter> | <letter><word>. <letter><word> alone has no way out, so it defines no strings. <letter> | <letter><letter> allows only one or two letters, with no repetition. <word> | <letter><letter> only ever produces exactly two letters, and its first alternative just refers to itself.
QQ*33 follows the second form: two letters, the terminal *, then a <tail> of two digits from 1 to 3. QR21 has two letters but no *, and the first form allows only one letter before the digits. S*3 has a * after a single letter, which neither form allows. RS*0 has the right shape, but 0 is not a <digit> in this grammar.
The first grammar has a recursive <num> for one or more digits and makes the X optional with the | in <code>. The second makes the X compulsory, so 1 and 212 cannot be derived. The third lets the recursion in <num> add X again and again, so 1XX would be accepted. The fourth has no recursion, so codes of three or more digits such as 212 cannot be derived.
Slides for this lesson
A projectable deck for every pack is on the way. Until then, present the student lesson full screen: its sections, figure and lab tabs follow the same order as the plan above.