Question

Use Backus–Naur form to describe the syntax of expressions in infix notation, where the set of operators and identifiers is the same as in the BNF for postfix expressions given in the preamble to Exercise 39, but parentheses must surround expressions being used as factors.

Short answer

The Backus-Naur form for postfix expressions:

\(\begin{array}{*{20}{l}}\begin{array}{c}\left\langle {expression} \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 :: = + | - \\\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 {expression} \right\rangle }\\{\,\,\,\,\,\,\,\,\,\left\langle {identifier} \right\rangle :: = a|b|c|...|z}\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.

Step 2: Let’s use Backus–Naur form to describe the syntax of expressions in infix notation.

The syntax of expressions in infixed notation of the Backus-Naur form with the same set of operators and identifiers as in the Backus-Naur form for postfix expressions can be given as:

\(\begin{array}{*{20}{l}}\begin{array}{c}\left\langle {expression} \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 :: = + | - \\\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 {expression} \right\rangle }\\{\,\,\,\,\,\,\,\,\,\left\langle {identifier} \right\rangle :: = a|b|c|...|z}\end{array}\)

The difference between the syntax of expressions in postfix and infix is that the operators are inserted between their operands and not behind them as in postfix.

Also, the parentheses are required in expressions used as factors.