Question

For each of these strings, determine whether it is generated by the grammar for infix expressions from Exercise 40. If it is, find the steps used to generate the string.

\(\begin{array}{*{20}{l}}{{\bf{a) x + y + z}}}\\{{\bf{b) a/b + c/d}}}\\{{\bf{c) m*}}\left( {{\bf{n + p}}} \right)}\\{{\bf{d) + m - n + p - q}}}\\{{\bf{e) }}\left( {{\bf{m + n}}} \right){\bf{*}}\left( {{\bf{p - q}}} \right)}\end{array}\)

Short answer

a) Not generated

b) The grammar for expressions in infixed notation is reproduced below:

\(\begin{array}{*{20}{l}}\begin{array}{c}\left\langle {\exp ression} \right\rangle \mathop = \limits^* > \left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {term} \right\rangle {\bf{ }}\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {factor} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {factor} \right\rangle \end{array}\\{\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {identifier} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {identifier} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {identifier} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {identifier} \right\rangle }\\{\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > a/b + c/d}\end{array}\)

c) The given string can be derived as:

\(\begin{array}{*{20}{l}}\begin{array}{c}\left\langle {\exp ression} \right\rangle \mathop = \limits^* > \left\langle {term} \right\rangle {\bf{ }}\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {factor} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {\exp ression} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left( {\left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {term} \right\rangle } \right)\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left( {\left\langle {factor} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {factor} \right\rangle } \right)\end{array}\\{\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {identifier} \right\rangle \left\langle {mulOperator} \right\rangle \left( {\left\langle {identifier} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {identifier} \right\rangle } \right)}\\{\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > m*\left( {n + p} \right)}\end{array}\)

d) Not generated

e) The string can be derived as given below:

\(\begin{array}{c}\left\langle {\exp ression} \right\rangle \mathop = \limits^* > \left\langle {term} \right\rangle {\bf{ }}\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {factor} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {\exp ression} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {\exp ression} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left( {\left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {term} \right\rangle } \right)\left\langle {mulOperator} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left( {\left\langle {factor} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {factor} \right\rangle } \right)\left\langle {mulOperator} \right\rangle \left( {\left\langle {factor} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {factor} \right\rangle } \right)\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left( {\left\langle {identifier} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {identifier} \right\rangle } \right)\left\langle {mulOperator} \right\rangle \left( {\left\langle {identifier} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {identifier} \right\rangle } \right)\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left( {m + n} \right)*\left( {p - q} \right)\end{array}\)

Step-by-step solution

Definition of infit notation

Represent complicated expressions, e.g: compound propositions, set combinations and arithmetic expressions using ordered rooted trees.

Consider how an arithmetic phrase with the operators + (addition), - (subtraction), + (multiplication), / (division), and is represented (exponentiation).

Step 2: Create the steps used to generate the string.

The following is a reproduction of the syntax for infix notation expressions:

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

Create the steps to generate the string \({\bf{x  +   y  +  z}}\).

(a)

The given string \(x + {\rm{ }}y + {\rm{ }}z\), cannot be derived as it not possible to have more than one \( + \) in strings generated by the grammar.

As a can be an or an, if the string converted to \(x + {\rm{ }}\left( {y + {\rm{ }}z} \right)\)it can be produced by the grammar.

Therefore, the given expression is not obtained.

Step 4:Create the steps to generate the string \(\frac{{\bf{a}}}{{\bf{b}}}{\bf{  +   }}\frac{{\bf{c}}}{{\bf{d}}}\).

(b)

The given string can be derived as:

\(\begin{array}{*{20}{l}}\begin{array}{c}\left\langle {\exp ression} \right\rangle \mathop = \limits^* > \left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {term} \right\rangle {\bf{ }}\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {factor} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {factor} \right\rangle \end{array}\\{\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {identifier} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {identifier} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {identifier} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {identifier} \right\rangle }\\{\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \frac{a}{b} + \frac{c}{d}}\end{array}\)

To generate the string first it take the expression, and then it could be expanded using the rule;

\(\left\langle {\exp ression} \right\rangle :: = \left\langle {term} \right\rangle |\left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {term} \right\rangle \)

Then using the rule,

\(\left\langle {term} \right\rangle :: = \left\langle {factor} \right\rangle |\left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {factor} \right\rangle \)it is expanded again.

Now rule.

\(\left\langle {factor} \right\rangle :: = \left\langle {identifier} \right\rangle |\left\langle {\exp ression} \right\rangle \)is applied to generate next line.

Hence, the given expression is obtained.

Create the steps to generate the string \({\bf{m*}}\left( {{\bf{n  +  p}}} \right)\).

(c)

The given string can be derived as:

\(\begin{array}{*{20}{l}}\begin{array}{c}\left\langle {\exp ression} \right\rangle \mathop = \limits^* > \left\langle {term} \right\rangle {\bf{ }}\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {factor} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {\exp ression} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left( {\left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {term} \right\rangle } \right)\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left( {\left\langle {factor} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {factor} \right\rangle } \right)\end{array}\\{\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {identifier} \right\rangle \left\langle {mulOperator} \right\rangle \left( {\left\langle {identifier} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {identifier} \right\rangle } \right)}\\{\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > m*\left( {n + p} \right)}\end{array}\)

So, this is the required expression.

Step 6:Create the steps to generate the string \({\bf{ +  m   -  n  +   p  -  q}}\).

(d)

This is not generated as there cannot be more than a single \( + \) or a \( - \) in the grammar (more details are given in the solution for part (a)).

Thus, the given expression is not obtained.

Create the steps to generate the string \(\left( {{\bf{m  +  n}}} \right){\bf{*}}\left( {{\bf{p  -  q}}} \right)\).

(e)

The string can be derived as given below:

\(\begin{array}{c}\left\langle {\exp ression} \right\rangle \mathop = \limits^* > \left\langle {term} \right\rangle {\bf{ }}\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {factor} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {\exp ression} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {\exp ression} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left( {\left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {term} \right\rangle } \right)\left\langle {mulOperator} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left( {\left\langle {factor} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {factor} \right\rangle } \right)\left\langle {mulOperator} \right\rangle \left( {\left\langle {factor} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {factor} \right\rangle } \right)\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left( {\left\langle {identifier} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {identifier} \right\rangle } \right)\left\langle {mulOperator} \right\rangle \left( {\left\langle {identifier} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {identifier} \right\rangle } \right)\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left( {m + n} \right)*\left( {p - q} \right)\end{array}\)

Accordingly, this is the required expression.