FOR FREE CONTENT

Backus Naur Form (BNF)

Backus Naur Form (BNF):

We can define a programming language by grammar. It is traditional in writing on programming languages to use a convention for specifying grammars called the Backus Naur Form (BNF).

In BNF, variables are enclosed in triangular brackets. Terminals symbols are written without any special marking.

::= denotes “is define as”

| denotes “or”

<> Used to hold category names that represent non-terminals or variables.

Example:

Here we describe a grammar as BNF:

<expression> :: = <expression> + <term> | <expression> * <term>

<term> :: = <factor> * <term>

In this grammar < expression>, <term>, <factor> are non-terminals or variables and +, * are terminals.

Now we can convert it to CFG:

We can take another example:

<number> :: = <number> + <digit> |  <digit>

<digit> :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0

Application:

Many of C-like programming languages are subject to definition by restricted forms of Context Free Grammars. For example, the while statement in C can be defined as: 

<while_statement> :: = while <expression> <statement>

Here while is terminal and all others are variables or non-terminals.

Q. Consider a grammar as Backus Naur Form:

<while start>: : = while <expression><start>

Which of the following grammar is correct?

a. Linear Grammar   

b. Context Free Grammar   

c. Simple grammar 

d. Regular

Solution:  Option c is correct

Explanation:

Initially, we can say that the given grammar is Context Free Grammar because BNF is one form of CFG.

So, if we write the grammar in CFG form: W → aAB.

Now if see the grammar properly W → aAB it is Simple grammar (For details follow Simple Grammar)

Though it is a CFG but strongest answer is simple grammar.      

Option (a) is not correct because Linear grammar production: 

V → T* | T*V | VT* | T* VT*  [at most a variable allowed]

Option (d) is not correct because Regular grammar production:

V → T* | VT*           (Left Linear)

V → T* |T* V            (Right Linear)

It also has a maximum of one variable allowed.