Backus-Naur Form and syntax diagrams

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

A6.5Theory of computationA level25 min

A programming language needs a precise definition of what counts as a valid program, so that every compiler for it agrees. Regular expressions are not enough: they cannot describe brackets nested to any depth, and every real language has those. Backus-Naur Form (BNF) can. It was invented to define the language ALGOL 60 and is still how language syntax is written down. Syntax diagrams show the same rules as pictures.

Production rules

A BNF definition is a list of production rules. Each rule defines one non-terminal, written in angle brackets, in terms of other non-terminals and terminals, the actual characters that appear in the text.

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

• ::= means "is defined as".
• | means "or": the non-terminal may be any one of the alternatives.
• Things written next to each other come one after the other.

The second rule is recursive: an integer is a digit, or a digit followed by an integer. That is how BNF says "one or more" with no + or *. Is 507 an integer? 5 is a digit followed by 07; 0 is a digit followed by 7; 7 is a digit, which is an integer. So yes.

A robot command language

Here is BNF for a small language that drives BugBot. F20 means forward 20 cm, R90 means turn right 90 degrees, and [4F20R90] means do F20R90 four times.

<program>   ::= <command> | <command><program>
<command>   ::= <move> | <repeat>
<move>      ::= <direction><integer>
<direction> ::= F | B | L | R
<repeat>    ::= [<integer><program>]
<integer>   ::= <digit> | <digit><integer>
<digit>     ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

To check whether [2F10L90]F5 is a valid program, break it down using the rules:

1. It is a <command> ([2F10L90]) followed by a <program> (F5).
2. [2F10L90] is a <repeat>: [, the <integer> 2, a <program>, ].
3. That inner program F10L90 is the <move> F10 followed by the <program> L90.
4. F5 is a <move>: the <direction> F and the <integer> 5.

Every part is accounted for, so it is valid. F20R is not: R must be followed by an <integer>, and nothing is left.

Look at the <repeat> rule. A <program> sits inside the brackets, and a program can contain another repeat, so [2[3F5]L90] is valid, nested as deep as you like. That self-embedding is what a regular expression cannot do.

Syntax diagrams

A syntax diagram shows a rule as a railway track. Follow the arrows from the left to the right; any route you can follow spells a valid piece of text. Rectangles are non-terminals, which have their own diagram. Rounded boxes are terminals, which appear exactly as written. A branch is a choice, and a track that loops back means the part can repeat.

The loop under digit lets you go round as many times as you like, so an integer is one or more digits.

A command takes the top track (a direction then an integer) or the bottom track (a bracket, an integer, a program, a closing bracket). The two tracks join again before the exit.

Why BNF can do what a regex cannot

The language {aⁿbⁿ | n ≥ 1}, some as followed by the same number of bs, is not regular: no FSM can count the as without a limit. In BNF it is one rule:

<s> ::= ab | a<s>b

Each use of the second alternative wraps one more a and one more b around the middle, so they always balance. A regex has repetition (*) but no way to say "the same number again", and an FSM has a fixed, finite number of states to remember with. BNF rules can refer to themselves in the middle of a rule, and the program that checks them uses the call stack as unlimited memory. Every regular language can be written in BNF too, so BNF describes everything a regex can and more.

Checking syntax with recursion

A recursive descent checker has one function per non-terminal. Each function starts reading at a position in the text and returns the position just after what it matched, or -1 if the text there does not fit the rule. For <s> ::= ab | a<s>b:

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

def s(text, i):
    # <s> ::= ab | a<s>b
    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

def valid(text):
    return s(text, 0) == len(text)

for text in ["ab", "aabb", "aaabbb", "aab", "abab"]:
    print(text, valid(text))

Run this in the simulator

The whole string is valid only if the rule matched all of it, which is why valid compares the result with len(text). abab fails even though it starts with a valid ab. Slicing with text[i:i + 1] rather than text[i] means reading past the end gives an empty string instead of an error. This is what the syntax analysis stage of a compiler does, with a grammar hundreds of rules long.

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

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?