Wright State UniversityDepartment of Computer Science and EngineeringCS 780 Fall 2010 PrasadAssignment 1 (Due: Sept 22) (10 pts)This assignment asks you to write a short Cool program. The purpose is to acquaint you with theCool language and to give you experience with some of the tools used in the course.In this assignment, you are to implement a very simple type inference engine for postfix expressions inCool. The input is a sequence of postfix expressions built using integer variables (i and j), real variables(a and b) and overloaded binary operators (+ and *). The output is the sequence of inferred types. Toaccomplish this task, you can use a stack as follows.A machine with only a single stack for storage is a stack machine. Consider the following very prim-itive language for programming a stack machine and the corresponding action for inferring types:Command Meaningi push int on the stackj push int on the stacka push real on the stackb push real on the stack∗, + infer the type of the associated postfix expression using the toptwo stack entries, and pushing the result type back on stack! print contents of the stack topq quitHere are some additional details. The ‘i’ and ‘j’ commands simply push the string “int” on top of thestack. The ‘a’ and ‘b’ commands simply push the string “real” on top of the stack. The behavior of the‘+’ (resp. ‘*’) command is to pop the top two stack entries corresponding to the two sub-expresssions,and to push the type of the resulting postfix expression on the stack. Specifically, the type of e1op e2isint if both the sub-expressions e1and e2are of type int, otherwise, it is real. The ‘!’ command printsthe contents of the stack top.The following examples show the effect of the various commands; the input is read from left to rightand the top of the stack is on the left (that is, stack values are the mirror image of the correspondinginput expression types):input stackj i ∗ . . . int . . .a i j + . . . int real . . .a b ∗ i + . . . real . . .i b ! . . . real intFurthermore, the ‘!’ command has the side-effect of printing the type of b: real.You are to implement this translator in Cool. Input to the program is a series of commands, onecommand per line. Your interpreter should prompt for commands with >>. To simplify coding, yourprogram need not do any sophisticated error checking. However, it is always a good idea to write robustprograms, to facilitate debugging.You are free to implement this program in any style you choose. However, in preparation for buildinga Cool compiler, we recommend that you try to develop an object-oriented solution. One approach is todefine a class Stack of strings with suitable operations.1We wrote a robust solution using about 120 lines of formatted Cool source code. This informationis provided to you as a rough measure of the amount of work involved in the assignment—your solutionmay be either shorter or substantially longer.Sample session. The following is a sample compile and run of our solution on gandalf.cs.wright.edu.gandalf % coolc type.clgandalf % spim -file type.sSPIM Version 6.3a of January 14, 2001Copyright 1990-2000 by James R. Larus ([email protected]).All Rights Reserved.See the file README for a full copyright notice.spim: (parser) immediate value (-4) out of range (0 .. 65535) on line 806 of file /usr/local/lib/cool/lib/trap.handlerandi $gp $gp 0xfffffffc # word align $gp^spim: (parser) immediate value (-4) out of range (0 .. 65535) on line 870 of file /usr/local/lib/cool/lib/trap.handlerandi $a0 $a0 0xFFFFFFFC^spim: (parser) immediate value (-4) out of range (0 .. 65535) on line 990 of file /usr/local/lib/cool/lib/trap.handlerandi $gp $gp 0xfffffffc^... ^spim: (parser) immediate value (-4) out of range (0 .. 65535) on line 1680 of file /usr/local/lib/cool/lib/trap.handlerandi $t1 $t1 0xFFFFFFFC^Loaded: /usr/local/lib/cool/lib/trap.handlerWarning: local symbol main was not defined>>a>>i>>j>>*>>!int>>+>>!real>>qCOOL program successfully executedThe executables, coolc and spim, are compiled for the SPARC-Solaris and installed on gandalf.cs.wright.eduin the directory /usr/local/lib/cool/bin/. As it stands, due to some incompatibilities between the ex-pectations of standard spim and the changes to spim to run Cool, there are “benign” error messagescomplaining about “...immediate value (-4) out of range (0 .. 65535)...”, and about “mainbeing undefined”. Ignore them for this assignment.Important: You should make sure to place /usr/local/lib/cool/bin at the beginning in your pathvariable setting to use the executables meant for this assignment. To change the path variable, add thelinesetenv PATH /usr/local/lib/cool/bin:${PATH}at the end of your .login file (or .tcshrc file) if you use tcsh; add the line2path=/usr/local/lib/cool/bin:$pathexport pathat the end of your .profile file (or .bashrc file) if you use bash.The assembly code for a working version of type.cl is in the file type eg.s. Login to gandalf and runas shown in the example above. You can compare the results from your program with the results oftype eg.s to test whether your program is operating correctly. You can run on a test input file as follows:spim -file type_eg.s < type.testGetting and turning in the assignment.Create a working directory and cd into it. From there, at the prompt gandalf% , typegandalf% make -f /usr/local/lib/cool/assignments/PA1/MakefileThis command creates several files you will need in the directory. Follow the directions in the READMEfile, which explains how to turn in your assignment when you are finished; it also contains a few questionsyou are to answer as part of the assignment. Upon turning in your program, you will receive an automaticemail acknowledgement providing a long listing of copied