Backus-Naur

What is Backus-Naur form

Backus -Naur form is the rules of the given language. For a computer to easily translate source code into machine code, a language must be clear and concise. Backus-Naur is a method for defining syntax clearly and unequivocally.

Furthermore, regular expressions cannot be used to define some languages. As a result, we can employ backus Naur form which is a meta language.

Example 1

<DIGIT>::=0|1|2|3|4|5|6

It means, a digit is defined as 0 or 1 or 2 or 3 etc.

Example 2

<LETTER>::=A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z

It means a "LETTER" is defined as A or B or C etc.

<WORD>::=<LETTER><LETTER>

It means a word is defined as a "letter letter".

This means that a "LETTER" or a "letter letter" is defined as a word. The "W" and "WE" would be considered words under this definition, but "GOING" would not be because the rule only allowed for one or two letters, and "GOING" has five.

Recursion in Backus-Naur

Creating new rules for different letters would be tedious and time consuming, so we can use recursion to avoid the hassle. The example below demonstrates how to do it.

In this example, a "LETTER" is defined as A, B, C, and so on. A "LETTER" or a "LETTER" "WORD" is defined as a word. If you look at the second section of the or (|), you'll notice that <WORD> calls itself recursively. This means that a word can be made up of a single "LETTER" or a "LETTER" and a word.

This process of working out a given statement is called parsing

Syntax diagram

To read about regular expressions Form click here or to read about different topics, click here