Question

a) Explain what the productions are in a grammar if the Backus–Naur form for productions is as follows:

\(\begin{array}{*{20}{l}}{{\bf{ < expression > :: = }}\left( {{\bf{ < expression > }}} \right){\bf{ }}\left| {{\bf{ < expression > + < expression > }}} \right|}\\\begin{array}{c}{\bf{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;}}\,\,\,\,{\bf{ < expression > * < expression > |}}\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{\bf{ < variable > }}\end{array}\\{\,\,\,\,\,\,\,\,\,{\bf{ < variable > :: = xly}}}\end{array}\)

b) Find a derivation tree for \(\left( {{\bf{x*y}}} \right){\bf{ + x}}\) in this grammar.

Short answer

(a) The productions of the grammar in the usual form are as follows:

expression \(\to\) (expression),

expression \(\to\) expression + expression,

expression \(\to\) expression * expression,

expression \(\to\) variable,

variable \(\to\) x

variable \(\to\) y

(b) The derivation tree for \(\left( {{\bf{x*y}}} \right){\bf{ + x}}\) is the following:

Step-by-step solution

About Backus-Nour form.

A type-2 grammar is designated by the notation known as Backus-Naur form.

The left side of a type 2 grammar's production is one non-terminal symbol.

It can merge all of the productions into a single statement using the same left non-terminal symbolàrather than listing each one separately in production,

It use the symbol:: =

It encloses all non-terminal symbols in brackets <>, and it list all right-hand sides of productions in the same statement, separating them by bars.

The Backus-Naur form of production of grammar is as follow:

\(\begin{array}{*{20}{l}}{{\bf{ < expression > :: = }}\left( {{\bf{ < expression > }}} \right){\bf{ }}\left| {{\bf{ < expression > + < expression > }}} \right|}\\\begin{array}{c}{\bf{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;}}\,\,\,\,{\bf{ < expression > * < expression > |}}\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{\bf{ < variable > }}\end{array}\\{\,\,\,\,\,\,\,\,\,{\bf{ < variable > :: = xly}}}\end{array}\)

The productions of the grammar in the usual form are as follows:

expression \(\to\) (expression),

expression \(\to\) expression + expression,

expression \(\to\) expression * expression,

expression \(\to\) variable,

variable \(\to\) x

variable \(\to\) y

Hence, the above production is The Backus-Naur of a grammar.

Let’s find a derivation tree for \(\left( {{\bf{x*y}}} \right){\bf{ +  x}}\) in this grammar.

\(\begin{array}{*{20}{l}}\begin{array}{c}{\bf{expression}} \to {\bf{expression + expression}}\\ \to \left( {{\bf{expression}}} \right){\bf{ + expression}}\end{array}\\{ \to \left( {{\bf{expression*expression}}} \right){\bf{ + expression}}}\\{ \to \left( {{\bf{expression*expression}}} \right){\bf{ + variable}}}\\{ \to \left( {{\bf{expression*variable}}} \right){\bf{ + variable}}}\\{ \to \left( {{\bf{variable*variable}}} \right){\bf{ + variable}}}\\{ \to \left( {{\bf{variable*variable}}} \right){\bf{ + x}}}\\{ \to \left( {{\bf{variable*y}}} \right){\bf{ + x}}}\\{ \to \left( {{\bf{x* y}}} \right){\bf{ + x}}}\end{array}\)

Let’s construct a derivation tree for \(\left( {{\bf{x*y}}} \right){\bf{ + x}}\).

Hence, the above derivation tree for\(\left( {{\bf{x*y}}} \right){\bf{ + x}}\).