Chapter 4, Problem 9E

Explanation of Solution

Attribute Grammar:

• Assuming that the each id has synthesized attribute name and that each E and op has an attribute value both of type string.
• val attribute is the root of the parse tree to contain a translation of the expression.
• The following grammar represents the conventional infix notation.

$\begin{array}{l}{\text{E}}_1\to {\text{E}}_2{\text{ E}}_3\text{ op}\Rightarrow {\text{E}}_1\text{.val := cat('(}\text{'},{\text{E}}_2\text{.val, op}{\text{.val, E}}_2\text{.val},\text{'})\text{'})\\ \text{E }\to \text{ id}\Rightarrow \text{E}\text{.val := id}\text{.name}\\ \text{op }\to \text{ +}\Rightarrow \text{op}\text{.val := }\text{'}+\text{'}\\ \text{op }\to -\Rightarrow \text{op}\text{.val := }\text{'}-\text{'}\\ \text{op }\to *\Rightarrow \text{op}\text{.val := }\text{'}*\text{'}\\ \text{op }\to /\Rightarrow \text{op}\text{.val := }\text{'}/\text{'}\end{array}$

• To reduce the parentheses, let us take that constants have precedence 3, products and quotients have precedence 2, and sums and differences have precedence 1.
• To override left to right associativity, we need to parenthesize a right operand if its outermost operator has the same precedence as the current operator.
• To default precedence, one need to parenthesize either a right or left operand if its outermost operator has precedence lower than that of the current operator.

  $\begin{array}{l}{\text{E}}_1\to {\text{E}}_2{\text{ E}}_3\text{ op}\Rightarrow {\text{E}}_1{\text{.val := assemble(E}}_2{\text{.val, E}}_2{\text{.prec, E}}_3{\text{.val, E}}_3\text{.prec, op}\end{array}$