Worksheet

A6.5 Backus-Naur Form and syntax diagrams

Theory of computation · A level · AQA 7517 4.4.3.1, Eduqas A500QS 1.8 · about 25 min

What this lesson is about

Production rules, syntax diagrams, a grammar for robot programs, recursive descent, and why BNF can describe what a regex cannot.

• Production rules
• A robot command language
• Syntax diagrams
• Why BNF can do what a regex cannot
• Checking syntax with recursion

Questions 6 marks in all

1. [1 mark]In BNF, what does ::= mean?

   1. AIs equal to
   2. BIs defined as
   3. COr
   4. DIs followed by

2. [1 mark]Using <integer> ::= <digit> | <digit><integer> and <move> ::= <direction><integer> with <direction> ::= F | B | L | R, which are valid moves?

   Tick every answer that is true.

   1. AF20
   2. BR7
   3. CF
   4. D20F
   5. EL005

3. [1 mark]Why can BNF describe some languages that regular expressions cannot?

   1. ABNF allows alternatives with |
   2. BBNF rules can be recursive in the middle of a rule, so they can describe nesting such as balanced brackets
   3. CBNF uses angle brackets
   4. DBNF can only describe finite languages

4. [1 mark]In a syntax diagram, what does a path that loops back round a box show?

   1. AThe item may be skipped
   2. BThe item may be repeated
   3. CThe item is a terminal
   4. DThe syntax is invalid

5. [1 mark]Given <s> ::= ab | a<s>b, how many times must the rule be used to produce aaabbb?

6. [1 mark]What does this program print?

   def s(text, i):
       if text[i:i + 2] == "ab":
           return i + 2
       if text[i:i + 1] == "a":
           j = s(text, i + 1)
           if j != -1 and text[j:j + 1] == "b":
               return j + 1
       return -1
   
   for t in ["aabb", "aab", "abb"]:
       print(t, s(t, 0))

The task: check robot programs

Write a recursive descent checker for the robot command language above and use it on the strings in tests. - Write one function per rule you need, each taking (text, i) and returning the position after the match, or -1 if it does not match. At least program, command and integer. - A string is valid only if program matches all of it. - Check the nesting with your functions. Do not use the re module: no regex can check matched brackets. - For each string in tests, in order, print the string, a space, then valid or invalid. For example F20R90 valid. Eight lines in all.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

tests = ["F20R90", "[4F20R90]", "[2F10[3L5]]", "F20R", "[4F20", "4F20", "[3]", "F1]"]

def integer(text, i):
    return -1

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/a6-5-bnf-and-syntax-diagrams/
The simulator checks it and tells you when it passes. Nothing to install, no account.

Challenges

1. Add a rule so a program may contain S, meaning stop, as a command on its own. Change both the BNF and the syntax diagram.
2. Write BNF for a signed integer that may start with + or -.
3. Is the language of your <integer> rule regular? Write a regex for it. Is <program> regular?