Home  Back Topics CD Orders  INDEX 
Backus-Naur Form (BNF)

BNF defines the syntax of a high level language using these symbols -

::= 'is defined by'
| 'OR'
< > define a meta variable

Example definition:

<hexdigit> ::= 0|1|2|3|4|5|6|7|8|9|A|B|C|D|E|F

One definition can then be used as part of another...

<hexnumber> ::= <hexdigit> | <hexdigit> <hexnumber>

This is an example of a recursive definition - one where the definition uses the thing being defined (!)

Example

1 <digit> ::= 0|1|2|3|4|5|6|7|8|9
2 <letter> ::= A|B|C|D|E|......|X|Y|Z
3 <integer> ::= <digit> | <digit> <integer>
4 <word> ::= <letter> | <letter> <word>
5 <variable> ::= <letter> | <letter> <integer>
6 <relation> ::= < | > | =
7 <condition> ::= <variable> <relation> <integer>

Which are the recursive definitions ?

Parsing is testing whether the rules of syntax have been obeyed.

Example of parsing (using the above definitions)

Test if 'B8>145' is a valid 'condition'.

Rules used: condition
7 variable relation integer
5,3 letter integer   digit integer
3         digit integer
3           digit
2,1,6 B 8 > 1 4 5

This parse tree shows that 'B8>145' is a valid 'condition'.

Part of the task of a compiler is to check the syntax of every statement in a high level language program. (The second stage of compilation is 'Syntax Analysis')