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.




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




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




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.