Theory of computation: Backus-naur form

Backus-Naur Form (also known as Backus Normal Form (BNF) or BNF for short) is a notation technique to express syntax of languages in computing. The expression is put in lists and can be used to see if syntax that is written is valid.

Structure and Layout

Symbols

BNF is represented using the following symbols:

 ::=   'is defined as'
 |     'or'
 <>    category names

The way that these symbols are laid out are as such:

 <Parent Expression> ::= <Child Expression 1> | <Child Expression 2>

In plain English, the expression above means "The parent expression is defined as the child expression 1 or the child expression 2". This means that to make up the parent expression, it must have a child expression and a child expression is made up of other things.

Example

In this example, The BNF structure is breaking down the syntax to create

Backus-Naur Form Breakdown of a Home Address <Address> ::= <House Number> <Street Name> <Town Name> <City Name> <Country> <Postcode> | <House Number> <Street Name> <City Name> <Country> <Post Code> <Postcode> ::= <Area Code> <Street Code> <Area Code> ::= <City Prefix> <digit> | <City Prefix> <digit> <digit> <Street Name> ::= <Name> <Street Type> <Flat Number> ::= <character> | <digit> <House Number> ::= <number> | <digit> <number> <number>::= <digit> | <digit> <number> <Name> ::= <string> <Street Type> ::= <string> <City Prefix> ::= <string> <Street Code> ::= <string> <Town Name> ::= <string> <City Name> ::= <string> <Country> ::= <string> <string> ::= <character> | <character><string> <character> ::= A|B|C|D|E|F|G|H|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z <digit> ::= 0|1|2|3|4|5|6|7|8|9 An Image to show how the address BNF would be laid out.

Practice Questions

Using the BNF from the example above about addresses, state whether each input is a valid input. 15 Jubilee Lane Blackpool England FY98 5ER Answer: NO 15 Jubilee Lane Blackpool England FY423 5ER Answer: NO 32 Parkstone Road Syston England Leicester LE7 3ZY Answer: NO