Question

a) What is Backus–Naur form?

b) Give an example of the Backus–Naur form of the grammar for a subset of English of your choice.

Short answer

a) Therefore, the definition of Backus–Naur form is “It is a description of a context-free grammar (type 2 grammar) with nonterminal symbols surrounded in angular brackets, the symbol \( \to \) substituted by \({\bf{:: = }}\), and all productions with the same nonterminal as their left-hand side joined with their various right-hand sides, each separated by a bar”.

b) Hence, the example of the Backus–Naur form is shown below.

\(\begin{array}{c}\left\langle {{\bf{identifier}}} \right\rangle( {\bf{:: = = }})\left\langle {{\bf{identifier}}} \right\rangle \left\langle {{\bf{letter}}} \right\rangle {\bf{|}}\left\langle {{\bf{letter}}} \right\rangle \\\left\langle {{\bf{letter}}} \right\rangle {\bf{:: = = a|b|c|d|}}...{\bf{|z}}\end{array}\)

Step-by-step solution

General form

Context-free Grammar (Definition) or type 2 grammar:

(a)

Atype 2 grammarcan have productions only of the form \({{\bf{w}}_{\bf{1}}} \to {{\bf{w}}_{\bf{2}}}\), where \({{\bf{w}}_{\bf{1}}}\)is a single symbol that is not a terminal symbol.

Backus–Naur form: a description of a context-free grammar in which all productions having the same nonterminal astheir left-hand side are combined with the different righthand sides of these productions,each separated by a bar, with nonterminal symbols enclosed in angular brackets and the symbol \( \to \) replaced by \({\bf{:: = }}\).

Step 2: Define and give an example of Backus – Naur form

(b)

Definition ofBackus–Naur form:

It is a description of a context-free grammar (type 2 grammar) with nonterminal symbols surrounded in angular brackets, the symbol \( \to \) substituted by \({\bf{:: = }}\), and all productions with the same nonterminal as their left-hand side joined with their various right-hand sides, each separated by a bar.

Hence, the definition of Backus–Naur form is shown above.

Give an illustration of the Backus-Naur version of the grammar for the selected subset of English.

For example,

The “identifier” must be at least one letter; thus the “identifier” is either one letter or an identifier followed by a letter.

The lowercase letters are a to z.

Bar (\({\bf{|}}\)) will be used to represent “or”.

Then, Backus–Naur form is

\(\begin{array}{c}\left\langle {{\bf{identifier}}} \right\rangle {\bf{:: = = }}\left\langle {{\bf{identifier}}} \right\rangle \left\langle {{\bf{letter}}} \right\rangle {\bf{|}}\left\langle {{\bf{letter}}} \right\rangle \\\left\langle {{\bf{letter}}} \right\rangle {\bf{:: = = a|b|c|d|}}...{\bf{|z}}\end{array}\)

Therefore, the example of the Backus–Naur form is shown above.