Copyright © 2006 Gradiance Corporation.

 

 

     

Intermediate-Code Generation --- Assignment

 

 

 

Postfix form, syntax trees, translation of simple expressions.

 

1.  

Suppose we use the following simplified translation scheme for assignment statements, where no error checking is performed.

E → id = E

{gen(id.name() "=" E.place)}

 

 

E → E1 + E2

{E.place = newTemp();

 

gen(E.place "=" E1.place "+" E1.place)}

 

 

E → E1 * E2

{E.place = newTemp();

 

gen(E.place "=" E1.place "*" E1.place)}

 

 

E → - E1

{E.place = newTemp();

 

gen(E.place "=" "-" E1.place)}

 

 

E → ( E1 )

{E.place = E1.place}

 

 

E → id

{E.place = id.name()}

Here, name() is a method that returns the name of an id token from the symbol table, and newTemp() is a function that returns a new temporary. Assume that newTemp() returns T1, T2,... in order, when in it is called. Function gen(...) emits a line with a three-address statement, using the constituents inside parentheses, in order.

Apply this translation scheme to the assignment: 

     x = a * (-b + c)

To be specific, assume that the parse is bottom-up, and a rule is applied during reduction by the associated production. Also, assume normal precedence for operators, to resolve conflicts. Then, identify the three-address statement that appears in your result.

 

 

 

 a) 

x = T4

 

 b) 

T1 = - b

 

 c) 

T3 = a

 

 d) 

T2 = a * T1

 

 

 

 

 

2.  

Translate the infix expression

((a+b)-(c*d))+e

to prefix form. Then, identify the pair of symbols that appear consecutively in your prefix expression.

 

 

 

 a) 

+c

 

 b) 

de

 

 c) 

dc

 

 d) 

b+

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.  

The following syntax tree:

Represents the assignment

a = (b - (c+d)) + e*f;

Convert this tree to (op, arg1, arg2) triples, following these rules:

  1. Evaluate the right subtree of a node before the left subtree.
  2. Number the instructions (1), (2),...

Then, identify from the list below, the one triple, with its instruction number, that would appear in your translation.

 

 

 

 a) 

(1) [+, e, f]

 

 b) 

(3) [-, b, (2)]

 

 c) 

(5) [a, =, (4)]

 

 d) 

(3) [-, b, d]

 

 

 

 

 

4.  

The following syntax tree:

Represents the assignment

a = (b - (c+d)) + e*f;

Convert this tree to (op, arg1, arg2, result) quadruples, following these rules:

  1. Evaluate the right subtree of a node before the left subtree.
  2. Use temporaries t1, t2,..., in that order.

Then, identify from the list below, the one quadruple that would appear in your translation.

 

 

 

 a) 

(-, b, t2, t3)

 

 b) 

(*, e, f, t3)

 

 c) 

(-, t2, b, t3)

 

 d) 

(+, t2, t1, t3)

 

 

 

 

 

5.  

Here is a postfix arithmetic expression:

ab+c-d+*e+

The operator - appearing between c and d can represent either unary or binary minus. Normally, the other operators, + and *, are only binary operators. Consider translating the postfix expression into infix, both with - as unary and - as binary. Then, identify the true statement below.

 

 

 

 a) 

- can be unary, and (b+(-c)) is a subexpression of the infix expression.

 

 b) 

- can be binary, and (a+b) is a subexpression of the infix expression.

 

 c) 

- in this postfix expression can be unary but cannot be binary.

 

 d) 

- can be binary, and (c-d) is a subexpression of the infix expression.