Question

Describe how productions for a grammar in extended Backus–Naur form can be translated into a set of productions for the grammar in Backus–Naur form.

This is the Backus–Naur form that describes the syntax of expressions in postfix (or reverse Polish) notation.

\(\begin{array}{c}\left\langle {{\bf{expression}}} \right\rangle {\bf{ :: = }}\left\langle {{\bf{term}}} \right\rangle {\bf{|}}\left\langle {{\bf{term}}} \right\rangle \left\langle {{\bf{term}}} \right\rangle \left\langle {{\bf{addOperator}}} \right\rangle \\{\bf{ }}\left\langle {{\bf{addOperator}}} \right\rangle {\bf{:: = + | - }}\\\left\langle {{\bf{term}}} \right\rangle {\bf{:: = }}\left\langle {{\bf{factor}}} \right\rangle {\bf{|}}\left\langle {{\bf{factor}}} \right\rangle \left\langle {{\bf{factor}}} \right\rangle \left\langle {{\bf{mulOperator}}} \right\rangle {\bf{ }}\\\left\langle {{\bf{mulOperator}}} \right\rangle {\bf{:: = *|/}}\\\left\langle {{\bf{factor}}} \right\rangle {\bf{:: = }}\left\langle {{\bf{identifier}}} \right\rangle {\bf{|}}\left\langle {{\bf{expression }}} \right\rangle \\\left\langle {{\bf{identifier}}} \right\rangle {\bf{:: = a }}\left| {{\bf{ b }}} \right|...{\bf{| z}}\end{array}\)

Short answer

Translate a set of productions for the extended Backus-Naur form grammar into a set of productions for the Backus-Naur form grammar

\(\begin{array}{l}{\rm{ < A + > :: = A| < A + > A}}\\{\rm{ < X* > :: = \lambda I < X* > X}}\\{\rm{ < Q? > :: = \lambda | Q}}\\{\rm{ < }}\left( {{\rm{String}}} \right){\rm{? > :: = \lambda |String}}\end{array}\)

Step-by-step solution

About Backus-Nour form.

The Backus-Naur form is a notation for specifying a type 2 grammar.

Productions in a type 2 grammar have a single non-terminal symbol on the left.

Rather of listing all the productions separately, we can merge all those with the same non terminal symbol on the left-hand side into one statement instead of using the symbolàin a production,

The symbol:: =

All non-terminal symbols are enclosed in brackets (>), and all productions' right-hand sides are listed in the same statement, separated by bars.

The Backus-Naur form now includes the following extensions:

"+": denotes that the symbol to the left of it may appear once or more.

The symbol or group of symbols enclosed in parenthesis to the left of the sign "?" may appear zero or once.

"*": denotes that the sign to the left of it may appear once or more.

Step 3: For translating a set of productions for the grammar in extended Backus-Naur form to a set of productions for the grammar in Backus-Naur form,

Replace the use of +, * and “?”, so that rules have the same effect.

For replacing '+' sign: let us take a symbol A, so we have to replace A+.

Hence the new rule can be as:

\({\rm{ < A + > :: = A| < A + > A}}\)

For replacing ‘*’ sign: let us take a symbol X. so we have to replace X*. So; the new rule can be as:

\({\rm{ < X* > :: = \lambda I < X* > X}}\), where ‘?’ is the empty string Comment

To replace the "?" sign, let's use the letter Q. What should we use in its place?

The new regulation will be:

\({\rm{ < Q? > :: = \lambda | Q}}\)

For a string of symbols. let us assume it as the non-terminal String.

So, replace (String)? with:

\({\rm{ < }}\left( {{\rm{String}}} \right){\rm{? > :: = \lambda |String}}\)

Therefore, productions for a grammar in extended Backus–Naur form can be describe as above.