Theory of computation: Backus-naur form

PAPER 1 - ⇑ Theory of computation ⇑

← Regular expressions Backus-naur form Classification of algorithms →


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

edit

Symbols

edit

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

edit

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

edit
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