course notes

Question 5. Consider the assignment x = y*x + x*2 + y. Give a register-machine instruction stream to compute this assignment. Use the load, store, add, mul instructions and format described in this course note. Consider the assignment statement x = y + (z*y)*z. A pure interpreter (VH, HH) would interpret some internal, direct representation y z z y Powered By Visual Paradigan Community Buition The interpreter would somehow implement three "variable boxes" for x, y, z (e.g., by a hash table or an array), traverse the expression lookup value of z box lookup value of y box multiply them and store the result in temp1 box lookup value of templ box lookup value of z box multiply them and store the result in temp2 box lookup value of y box lookup value of temp2 box add them and store the result in x box As an example of intermediate language, we use stack machine instructions (VI, HI). (The Java Virtual Machine is a stack machine us into the following instruction stream; "x", "Y", "Z" abbreviate the memory cells allocated to the three variables. (We will study stack-n push y // read value of memory cell of y and push it onto the stack push z // read value of memory cell of z and push it onto the stack push y // read value of memory cell of y and push it onto the stack mul // pop top two values of the stack, multiply them, push the result onto the stack push z // read value of memory cell of z and push it onto the stack mul // pop top two values of the stack, multiply them, push the result onto the stack add // pop top two values of the stack, add them, push the result onto the stack pop to x // pop top value of the stack and store it in the memory cell of x Trace these operations step-by-step by writing diagrams of the contents of the stack and verify that "x" gets the value of y + (z*y)*z. expression tree and the runtime overhead of tree traversal and lookups of variable boxes have been compiled away into a linear seque As an example of machine language (VM, HM), we use a register machine typical of today's conventional computers. The above stac into the following instructions using three registers R1, R2, Rz: load y, Ri // load value of memory cell of y into Ri load 2, R2 // load value of memory cell of z into R2 mul Rz, Ru, R3 // R3 - R2 * Ri - zky mul Rz, R2, R2 // R2 + R3 * R2 (z*y) *2 add Ri, R2, R1 // R1 + R + R2 = y + (z*y)*2 store Ri! // store value of Ri in the memory cell of x