Theory of computation: Backus-naur form

 ← 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

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 ```
::= | ``` ```  ::=  ::= |  ::=  ::= |  ::= | ::= |  ::=  ::=  ::=  ::=  ::=  ::=  ::=  ::= |  ::= 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  ::= 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