Expression

How an expression be transformed into sequence of instructions

The instruction in machine language composed of operator and operands. The number of operands vary from zero (stack instruction), one, two, three. Our hypothetical S2 processor is a 3-operand machine. Each instruction has the form "op r1 r2 r3", all operands are registers. Having three operands mean each operation can take two inputs from two operands and stores the result in the third operand. It is suitable for binary operation such as; add, sub etc. To tranform an expression into S2 instruction, each result of a binary operation needs to store in a temporary register.

a * b + c - d
t1 = a * b
t2 = t1 + c
t3 = t2 - d

The input variables (a,b,c,d) and the temporary variables will be assigned registers.

let r1 = a, r2 = b, r3 = c, r4 = d, r5 = t1, r6 = t2, r7 = t3

the above expression can be written in S2 instructions as follows:

mul r5 r1 r2
add r6 r5 r3
sub r7 r6 r4

In fact, at most two temporary variables are needed for any arbitrary long sequence of binary operations as the temporary value can be accumulated using just one register and another register is used to hold one operand of the binary operator.

let use only t1

t1 = a * b
t1 = t1 + c
t1 = t1 - d

for any expression which has parentheses to control the order of evaluation, the expression can be transformed into postfix ordering:

(a * b) + (c * d)

this expression is transformed into:

t1 = a * b
t2 = c * d
t1 = t1 + t2
((a * b) + (c * d)) / f)
t1 = a * b
t2 = c * d
t1 = t1 + t2
t1 = t1 / f

29 August 2003