Worth 18% of your project grade
For this project, you need to generate Intermediate Representation (IR) data structures for some of the ASTs. You should not generate any MIPS code for this project. You should generate IR data for all types of ASTs, except the following AST nodes:
ProcDec, RecordExp, RecordInit, RecordDeref, ArrayDeref, CallExp, CallSt, RetSt
That is, in this project, you should not generate IR code for record construction, array indexing, record projection, function/procedure call, and function/procedure prologue/epilogue (but you should generate IR code for their bodies and store their parameters in the symbol table). Everything left out will be generated by the next project. I have also given the IR for ArrayExp AST because it's difficult. You will have to use the TypeCheck code for ProcDec to make sure that parameters and local variables are inserted in the Symbol table.
Your ASTs that represent IRs, when printed by toString(), should follow the following syntax:
IRexp -> Const(INTEGER_LITERAL) # integer constant Const(STRING_LITERAL) # string constant Const(REAL_LITERAL) # real constant Mem(IRexp) # retrieve the memory content at given address Reg(ID) # a register Binop(binop,IRexp,IRexp) # binary operation Unop(unop,IRexp) # unary operation Call(ID,IRexp,IRexp,...,IRexp) # set register ra to the return address, # set v0 to the callee's static link (first IRexp), # call function ID with the given arguments # and return back the result ESeq(IRStmt,IRexp) # evaluate the statement and return the exp value Assert(IRexp,IRexp) # if the first exp is true return the second exp value, # otherwise, raise an exception Allocate(IRexp) # allocate a number of words in the heap and return the address IRstmt -> Move(Mem(IRexp),IRexp) # set memory with given address Move(Reg(ID),IRexp) # set register value Label(ID) # define a label to be the current address Jump(ID) # jump to label ID CJump(IRexp,ID) # jump to label ID if condition (IRexp) is true Seq(IRstmt,... IRstmt) # sequence of statements Call(ID,IRexp,IRexp,...,IRexp)# set register ra to the return address, # set v0 to the callee's static link, # and call procedure ID with the given arguments SystemCall(ID,IRexp) # a system call can be: READ_INT, READ_FLOAT, # WRITE_INT, WRITE_FLOAT, WRITE_BOOL, or WRITE_STRING Return() # jump to the address in register ra binop -> GT | LT | EQ | GE | LE | NE | PLUS | MINUS | TIMES | SLASH | DIV | MOD | AND | OR unop -> UMINUS | NOTRead Section 8 in the notes for explanation of some of them. Note that SEQ(s1,s2) in the notes is now Seq(s1,s2,...sn), which makes the code generation easier. The IR Call(f,sl,e1,...,en) takes the function/procedure name, f, the static link of the callee, sl, and zero or more arguments e1 ... en. It pushes the arguments e1 ... en in the stack, sets the register v0 to sl, calls procedure f, and, after f returns, it pops n values from the stack. If it is a function, it returns a value. For this project phase, you can use the following six reserved registers (which should not be used for any other purpose):
fp frame pointer sp stack pointer gp pointer to heap (implicitly used by Allocate only) ra return address v0 used in passing the static link from the caller to the callee a0 used in passing the result of a function from the callee to the callerFor example, the IR Reg(fp) represents the register fp. The IR code Allocate(n) allocates n words in the heap, and returns the address of the first word, that is, it is equivalent to gp:=gp+n*4; return gp. You will never deallocate objects from heap.
The only thing that you have to do for this project is to write more code in the static method code in the file Code.gen, which gets an AST exp (for expressions, statements, declarations, etc) as input and generates its IR. The IR code generated is normalized by the normalize method (ie, Seq and ESeq are removed), and the resulting list of IRs is pretty-printed in the output.
Every data value occupies 4 bytes regardless of its type. More specifically, this is how you map PCAT types to IRs:
All PCAT variables should be allocated in the run-time stack, including all global variables (you store global variables in the activation record of the main program).
You should generate IRs for each type of expression, declaration, etc., so that for each input file, you get only one IR tree (like you get one AST only). Statements are a bit tricky. For example, the while loop:
while c do x:= x+5;where x is an integer with offset -60 and c is a boolean with offset -12, generates the following IR when printed:
Seq(Label(loop_10_), CJump(Binop(EQ,Mem(Binop(PLUS,Reg(fp),Const(-12))),Const(0)),exit_11_), Move(Mem(Binop(PLUS,Reg(fp),Const(-60))), Binop(PLUS,Mem(Binop(PLUS,Reg(fp),Const(-60))),Const(5))), Jump(loop_10_), Label(exit_11_))Here I used the name generator new_name for labels that generates new names, such as loop_10_ and exit_11_, each time.)
PCAT read/write statements need special attention. You need to use various system calls: READ_INT, WRITE_INT, WRITE_STRING, etc. For example, the PCAT statement write("x = ",x) has IR:
Seq(SystemCall(WRITE_STRING,Const("x = ")), # write "x = " SystemCall(WRITE_INT,Mem(...)), # write x SystemCall(WRITE_STRING,Const("\n"))) # write end=of-line
You need to run your parser against all tests/*.pcat files. For example:
run 5 helloYou also need to compare your output with that of the solution:
solution 5 hello
After ensuring that your program compiles and executes correctly, cleanup your pcat directory using clean Then, if you are using Linux/MacOS, archive your pcat directory using tar cfz pcat.tgz pcat. If you are using Windows, zip the pcat directory into the file pcat.zip. Then submit your file (pcat.tgz or pcat.zip) here:
Last modified: 03/29/12 by Leonidas Fegaras