The Formal Description of Languages I

Backus-Naur Form

"Backus-Naur Form (BNF)" is the term attributed to a standard formal notation used to describe the syntax of programming languages. The notation is based on the work of John Backus and that of Peter Naur. We briefly review BNF as background for the study of Automata and Languages .

_________________________________________________________________________________

The meta-symbols of BNF are:

$\QTR{Large}{::=}$

meaning "is defined as"

$\QTR{Large}{|}$

meaning "or"

MATH

meaning zero or more occurences of ......

MATH

meaning zero or one occurence of ......

Moreover, $\QTR{Large}{<>}$ ,angle brackets, are used to distinguish non-terminal symbols from terminal symbols which are written exactly as they are to be represented.

A BNF rule defining a nonterminal has the form:

nonterminal $\QTR{Large}{::=\ }$a sequence consisting of strings of

terminals or nonterminals separated by the meta-symbol $\QTR{Large}{|}$

Here are some examples:

MATH MATH

$\vspace{1pt}$

MATH

MATH if (MATH ){

MATH

$\QTR{Large}{[}$ }else{

MATH }]

}

MATH

MATH a$\QTR{Large}{|}$ b$\QTR{Large}{|}$ c $\QTR{Large}{|}$d $\QTR{Large}{|}$......$\QTR{Large}{|}$A$\QTR{Large}{|}$ B$\QTR{Large}{|}$ C$\QTR{Large}{|}$.....

MATH0$\QTR{Large}{|}$ 1$\QTR{Large}{|}$ .... $\QTR{Large}{|}$8 $\QTR{Large}{|}$9 $\QTR{Large}{|}$

______________________________________________________________________

Recognizing a string

Example : a2H

MATH

MATH

MATH

.

.

MATHa2H