Problem Solving: Backus-Naur Form

From Wikibooks, open books for an open world
Jump to: navigation, search

UNIT 3 - ⇑ Problem Solving ⇑

← Finite State Machines Backus-Naur Form (BNF) Reverse Polish Notation →

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. Backus-Naur means "not in normal form compared to convention".

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>
 <Street Type> ::= <string>
 <City Prefix> ::= <string>
 <Street Code> ::= <string>
 <Town Name> ::= <string>
 <City Name> ::= <string>
 <Country> ::= <string>
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 :

YES

15 Jubilee Lane Blackpool England FY423 5ER

Answer :

NO

32 Parkstone Road Syston England Leicester LE7 3ZY

Answer :

NO