(This is the older material - click here - for current specification content)

8. Backus-Naur Form (BNF)

The syntactic analysis page mentioned that part of syntactic analysis involves checking that the code meets the grammar rules of the computer language.

But how is the grammar of a computer language written down in the first place?

One popular solution is to use a formal method developed by John Backus and Peter Naur nearly fifty years ago.

Their method is now called the 'Backus-Naur Form' or BNF.

BNF uses a small set of symbols to describe a grammar rule.

The authors of any programming language (e.g. C++, Visual Basic) need to write down the grammatical rules of that language. They often follow the BNF notation to describe these rules. The compiler author can then read this document and make their compiler program conform to it.

Some of the BNF notation include:

 < > used to enclose a syntactic item 

 ::= means "is defined by" or "consists of"

 | when placed between two items means an OR choice between them

 { } curly brackets means zero or more repetitions of the content.    

Example:

A programmer is about to develop a new database. However, other people will be writting other parts of the program and will need to know the grammatical rules that will be used to form a postal address.

The original programmer might write the grammatical rules in a document for others to follow

In English this says "A postal address consists of a name, a street address and a post code with a semi-colon separating them".

Thus, any programmers wishing to use 'postal address' as part of their module need to follow this rule. If they don't, a syntax error will be generated.

The <name> item has the following rule

In English this becomes "A name is defined by a first name, followed by a comma, then possibly a middle name, followed by a comma and finally a surname"

As you can see, writing a grammar rule using BNF is a lot more concise and accurate than stating the same rule in English.

English (or any other language!) is wonderful for human communication but pretty hopeless to guarantee accuracy and objecitvity!

The other handy thing is that BNF can easily be understood internationally, so making the rule available to compiler writers anywhere in the world..

Example 2 Defining a digit

So a digit is any number between zero and nine

Example 3 Defining an integer

Note that <integer> appears twice in the rule

This is called a 'recursive' statement. A recursive statement makes use of itself as part of its definition.

In this case the rule, stated in English becomes "An integer consists of a single digit or a single digit followed by another integer."

So you can see that this allows an integer to be any length and yet it is a very concise statement in BNF.

Recursive statements are very common in computer circles. PHP stands for "PHP Hypertext Preprocessor" which itself depends on the php definition. Its almost an in-joke!.