StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q28E

Expert-verifiedFound in: Page 857

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:

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.

\(\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.**

\(\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}}\)**.**

94% of StudySmarter users get better grades.

Sign up for free