Intermediate-Code Operational Semantics (for call-by-value parameter passing)

AR = the activation record for the call currently being executed AR' = the new activation record for the called function to be pushed onto the stack Function Call a = f(E1, ..., En); save the values of the registers being used by the caller, if any, to the caller's activation record AR code to evaluate E1 e1 = result of above evaluation ... code to evaluate En en = result of above evaluation create new AR' fill AR' with necessary data AR'.returnAdd = "returnAddress" AR'.x1 = e1 // pass 1st parameter value ... AR'.xn = en // pass n-th parameter value ... push AR' onto stack goto start_f returnAddress: a = AR'.returnValue // AR' is currently the top activation record of stack pop AR' from stack restore the saved register values from the caller's activation record AR, now at the top of stack 

Convert the insert , search, and delete method of following code into runtime stack mechanism using activation records as used above

Create an abstract class called AR whose objects will be activation records. Actual activation records for function calls will be objects of subclasses of AR. Emulation of activation records of the factorial function and the runtime stack can be achieved by the following subclass of AR called ARfact: class NonEmptyBST extends BST // The class of nonempty binary search trees containing C objects. { C data; // the C object at the root BST left; // left subtree BST right; // right subtree NonEmptyBST(C c, BST l, BST r) { data = c; left = l; right = r; } public String toString() { return objId+":"+visited; } C search(String ID) // Returns the C object in the target tree whose IDcode is equal to ID; returns null if no such object found. // The type of this function is NonEmptyBST x String--> C. { int i = ID.compareTo(data.IDcode); if ( i == 0 ) return data; else if ( i < 0 ) return left.search(ID); else // i > 0 return right.search(ID); } NonEmptyBST insert(C c) // Returns the nonempty tree obtained by inserting parameter C object into the target tree. // If the tree already has the object with the same IDcode, issues a message and returns the target tree unchanged. // The type of this function is NonEmptyBST x C --> NonEmptyBST. { int i = (c.IDcode).compareTo(data.IDcode); if ( i < 0 ) left = left.insert(c); else if ( i > 0 ) right = right.insert(c); else // i == 0, c.IDcode == data.IDcode System.out.println("Data object with the same IDcode "+data.IDcode+" already exists in the tree."); return this; } BST delete(String ID) // Returns the tree obtained by deleting from the target tree the C object whose IDcode is equal to ID. // If the tree has no such object, issues a message and returns the target tree unchanged. // The type of this function is NonEmptyBST x String --> BST. { int i = ID.compareTo(data.IDcode); if ( i < 0 ) { left = left.delete(ID); return this; } else if ( i > 0 ) { right = right.delete(ID); return this; } else // i == 0, ID == data.IDcode, the object with ID found at the root { if ( left instanceof EmptyBST ) return right; else if ( right instanceof EmptyBST ) return left; else // left is nonempty & right is nonempty { // search for the object whose IDcode is the predecessor of ID, which is the maximum (rightmost) key in the left subtree; // replace data by that object; // delete the node containing that object; NonEmptyBST t = (NonEmptyBST)left; if ( t.right instanceof EmptyBST ) { data = t.data; left = t.left; return this; } else // t.right is nonempty { while ( !( ((NonEmptyBST)t.right).right instanceof EmptyBST ) ) t = (NonEmptyBST)t.right; data = ((NonEmptyBST)t.right).data; t.right = ((NonEmptyBST)t.right).left; return this; } } } } }