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
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.