• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q28E

Expert-verified
Found in: Page 857

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

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

(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:

See the step by step solution

## Step 1: 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.

## Step 2: 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.

## Step 3: 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}}$$.